Основні положення алгебри логіки

Аналіз і синтез логічних ланцюгів виконується за допомогою математичного апарата алгебри логіки або булевої алгебри, в якій змінні можуть приймати тільки одне з двох значень: 0 або 1. Над змінними можуть виконуватись три основні дії: логічні додавання, множення і заперечення, що відповідає логічним функціям:

 

X1	Х2	АБО	І	НІ
Y = Х1+Х2	Y = Х1*Х2	Y = Х1

 

В якості прикладу ланцюга, що реалізує функцію АБО, можна навести паралельне з'єднання замикаючих контактів реле (рис. 1, а). Ланцюг, в яке входять ці контакти, буде замкнутий, якщо спрацює хоча б одне реле.

Функцію І реалізують, наприклад, з'єднані послідовно замикаючі контакти декількох реле (рис. 1, б). Ланцюг в цьому випадку буде замкнутий тільки тоді, коли спрацюють всі реле.

Моделлю, що реалізує функцію НІ, може бути схема на рис. 1, в, або розмикаючий контакт реле. При спрацюванні реле, ланцюг, в який входить такий контакт, розмикається. Таким чином, інверсія одиниці дорівнює нулю, а подвійна інверсія не змінює змінної.

Кон'юнкцією, диз’юнкцією і інверсією можна виразити більш складні функції:

X1	Х2	Функція Шефера	Функція Пірса	Суми по модулю 2
Y = Х1*Х2	Y=Х1+Х2	Y = X Х2

Основні закони алгебри логіки

Переміщувальний закон: a+b=b+a

Сполучний закон: (а + b) + с = a+ (b + с); (а * b) * с = а * (b*c)

Розподільний закон: а * (b + c) = a * b + a * c; a + b * c = (a + b)*(a + c)

 

Закон поглинання: a + a * b = a(1 + b) = a; a(a + b) = a + a * b = a;

 

Закон склеювання: a * b + a * b = a; (a + b)(a + b) = b;

 

 

Закон заперечення:

а +b = а * b; а * b = а + b

а + b = а * b а * b = а + b

Закон заперечення (його часто називають правилом де Моргана), справедливий для будь - якого числа змінних.

 

Стандартні форми

Будь-яку логічну функцію F(Х₁,...., Х_n) можна подати в досконалій диз'юнктивній нормальній формі (ДДНФ) або в досконалій кон'юнктивній нормальній формі (ДКНФ). Подання логічної функції проілюструємо згідно заданої таблиці відповідності:

 

аі	F(Аi)
Х1	Х2	Х3	Х4

Для подання логічної функції в ДДНФ достатньо використовувати тільки ті набори змінних А_i, на яких F(А_i)=1. Для подання в ДКНФ використовують ті набори змінних А_i, на яких F(А_i)=0. Через це ДДНФ називають формою подання по одиницям, а ДКНФ - по нулям.

Y=X1X2X2+X1X2X3+ X1X2X3+ X1X2X3+ X1X2X3.

ДКНФ: Y=(Х₁+Х₂+ Х₃)*(Х₁+ Х₂+Х₃)*(Х₁+Х₂+Х₃);

ДДНФ: