Логические основы компьютерной техники. Булева алгебра презентация

Что такое Булева алгебра !?
АЛГЕБРА – … ???
БУЛЕВА АЛГЕБРА – … ???
раздел математики, посвященный изучению операций над элементами множеств, которые могут так или иначе обобщать множества чисел, а операции — обобщать сложение и умножение.
мат. аппарат, в котором операции выполняются не над числами, а над высказываниями, представленными двоичными переменными.

В обычной алгебре (арифметической) над переменными (чаще это числа) выполняются операции сложения / вычитания, умножения / деления и т. д.
В булевой алгебре основными являются только три операции:
дизъюнкция, конъюнкция, инверсия.

Операция дизъюнкции
Аксиомы:
0+0 = 0;
0+1 = 1;
1+0 = 1;
1+1 = 1.

Операция конъюнкции
Аксиомы:
0•0 = 0;
0•1 = 0;
1•0 = 0;
1•1 = 1.

Инверсия
Аксиомы:

Полный список аксиом :

Формы представления булевых функций
Булевы формулы могут быть записаны либо в виде дизъюнкции, либо в виде конъюнкции каких-либо выражений.
В первом случае говорят о ДИЗЪЮНКТИВНОЙ ФОРМЕ,
во втором— о КОНЪЮНКТИВНОЙ ФОРМЕ.

Формы представления булевых функций
ЭЛЕМЕНТАРНАЯ КОНЪЮНКЦИЯ (ЭК) –
логическое произведение любого конечного числа различных между собой булевых переменных, взятых со знаком инверсии или без него.
ЭЛЕМЕНТАРНАЯ ДИЗЪЮНКЦИЯ (ЭД) –
логическая сумма любого конечного числа различных между собой булевых переменных, взятых со знаком инверсии или без него.

Нормальные формы
ДИЗЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА (ДНФ)
– булева формула, которая записана в виде дизъюнкции выражений, каждое из которых представляет собой либо отдельный аргумент (с инверсией или без инверсии), либо конъюнкцию некоторых аргументов.
– дизъюнкция конечного числа ЭК.

Нормальные формы
КОНЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА (КНФ)
– булева формула, которая записана в виде конъюнкции выражений, каждое из которых представляет собой либо отдельный аргумент (с инверсией или без инверсии), либо дизъюнкцию некоторых аргументов.
– конъюнкция конечного числа ЭД.

Инвертирование сложных выражений
Правило:
Чтобы найти инверсию, необходимо знаки умножения заменить знаками сложения, а знаки сложения — знаками умножения и поставить инверсии над каждой переменной.
(независимо от того, есть над переменными знаки отрицания или нет)

МИНТЕРМЫ
Функции, которые принимают единичное значение только на одном наборе называются
минимальными термами,
или — МИНТЕРМАМИ
(иногда конституентами единицы).

МИНТЕРМЫ
Минтермом n переменных называется такая их конъюнкция, в которую каждая переменная входит только один раз в прямой или инверсной форме.
Обозначаются минтермы буквой m с десятичным индексом, являющимся номером минтерма.
mi
m0 = 000…0

Свойство:
конъюнкция любых двух различных минтермов, зависящих от одних и тех же аргументов, тождественно равна нулю.

МАКСТЕРМЫ
Макстермом n переменных называется такая их дизъюнкция, в которую каждая переменная входит только один раз в прямой или инверсной форме.
Макстерм (конституента нуля) — это булева функция, которая принимает единичное значение на всех наборах, за исключением одного.

МАКСТЕРМЫ
Макстермы обозначают большой буквой M с десятичными индексами (по аналогии с обозначением минтермов).
СВОЙСТВО:
дизъюнкция любых двух различных макстермов, зависящих от одних и тех же аргументов, равна единице.
Mi

Связь между индексами
минтермов и макстермов :

Совершенные нормальные формы
СОВЕРШЕННАЯ КОНЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА (СКНФ)
СОВЕРШЕННАЯ ДИЗЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА (СДНФ)

СОВЕРШЕННАЯ ДИЗЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА – это
ДНФ, в которой все конъюнкции имеют ранг n
дизъюнкция минтермов n аргументов
дизъюнкцию простых конъюнкций
простые конъюнкции содержат все переменные в своей прямой или инверсной форме

y = ∨ х1δ1 х2δ2 х3δ3... х(n–1)δ(n–1) хnδn ,

Всякая булева функция для заданного числа аргументов представима в виде суммы минтермов единственным образом.
Поэтому СДНФ называют
стандартной формой, или канонической.

СОВЕРШЕННАЯ КОНЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА – это
КНФ, в которой все дизъюнкции имеют ранг n
конъюнкция макстермов n аргументов
конъюнкция простых дизъюнкций.
простая дизъюнкция – дизъюнкция переменных или их отрицаний

y = ∧ ( х1δ1 + х2δ2 +х3δ3 + ... + х(n–1)δ(n–1) + хnδn),

Карта Вейча
её модификацию называют диаграммой Карно
На рис.1 приведены минтермы функции от двух переменных А и В.
На рис.2 указаны десятичные номера минтермов.

Карта Вейча для 3-х аргументов

Карта Вейча для 4-х аргументов

Карта Вейча для 5-х аргументов

Нанесение функций на карту Вейча
Пусть есть функция:
f (A,B,C) = A + BC
Ей соответствует представление на карте Вейча:

Минимальная ДНФ (МДНФ)
МДНФ булевой функции называется ДНФ, которая содержит наименьшее число букв в записи (по отношению ко всем другим ДНФ этой функции).

Импликанта булевой функции
Функция g(x1, …, xn) называется импликантой функции f(x1, …, xn), если для любого набора аргументов, на котором g=1, справедливо что f=1.

Импликанта булевой функции, которая представлена элементарной конъюнкцией, называется простой, если никакая ее часть больше не является импликантой этой функции.
Т.Е. простая импликанта – это такая, к которой нельзя применить операцию склеивания.

Пример импликант:
Пусть дана функция:
f = AB + BC.
Представим её в СДНФ:
f = (3,6,7) .
Эта функция содержит три минтерма.
Из них можно образовать семь различных функций, каждая из которых является импликантой функции f.

Импликанты ф-ции f = AB + BC

Методы минимизации
функций алгебры логики
минимизация методом Квайна;
минимизация с использованием карт Карно;
минимизация не полностью определенных (частичных) функций;
минимизация КНФ;
минимизация методом кубического задания функций алгебры логики;
минимизация методом Квайна–Мак–Класски;
минимизация с использованием алгоритма извлечения (Рота);
минимизация ФАЛ методом преобразования логических выражений.

минимизация методом Квайна
Основу метода составляет теорема склеивания, которая применяется к каждой паре минтермов заданной функции.
Например:
f (A,B,C,D) = (0, 1, 3, 6, 7, 8, 12, 13, 14, 15)

Выражение, полученное методом Квайна, называется сокращённой дизъюнктивной нормальной формой заданной функции,
а каждая его конъюнкция называется простой импликантой.

Для всякой булевой функции существует единственная сокращённая ДНФ

Найти методом Квайна
минимальное выражение для функции y

1–й этап

2–й этап - Импликантная таблица

Получение минимальной ДНФ
Функция «покрыта» полностью

Минимальная ДНФ из 3-х импликант

Граф-схема булевой функции

Формы булевых функций