Алгебра логіки

Алгебра логіки є одною з багатьох алгебраїчних структур. Її називають алгеброю Буля (за авторством) або булевою алгеброю, хоча алгебра Буля не єдина у класі булевих алгебр. Алгебру логіки називають також алгеброю висловлень, оскільки операндами (логічними змінними, над якими здійснюються алгебраїчні операції) в цій алгебрі є висловлення.

З опису логічних операцій неважко помітити, що алгебра логіки подається структурою <M, Ù, Ú, >, де M={0, 1} – носій алгебри (двохелементна множина), елементи 0 та 1 якого використовуються відповідно як значення (числові еквіваленти) хибності та істинності висловлень (логічних змінних), а базовий набір операцій (Ù, Ú, ) алгебри достатній для подання формулами будь-яких логічних операцій над логічними змінними.

Правила логічного виведення в алгебрі логіки базуються на її законах (табл. 2.1).

Таблиця 2.1 – Закони алгебри логіки

Назви законів	Тотожності
Закони ідемпотентності	А+А=А; А×А=А
Закони комутативності	А+В=В+А; А×В=В×А
Закони асоціативності	А+(В+С)=(А+В)+С=А+В+С; А×(В×С)=(А×В)×С=А×В×С
Закони дистрибутивності	А×(В+С)=(А×В)+(А×С); А+(В×С)=(А+В)×(А+С)
Закони поглинання	А+(А×В)=А; А×(А+В)=А
Закони повного склеювання	(А×В)+( ×В)=В; (А+В)×( +В)=В
Закони неповного склеювання	АВ+А =А+АВ+А ; (А+В)(А+ )=А(А+В)(А+ )
Закони де Моргана	= × ; = +
Закон подвійного заперечення	=А
Закони суперечності	=1; =0
Властивості одиниці	А+1 =1; А+ =1; A×1 =A
Властивості нуля	A×0=0; А× =0; A+0=A

Закони алгебри логіки являють собою тотожні рівності між аналітичними формулами, якими відображаються логічні зв’язки між логічними змінними (операндами), з використанням символів логічних операцій та дужок. Тотожність цих рівностей означає, що вони справедливі при будь-яких комбінаціях значень 0 і 1 істинності логічних змінних.

В алгебрі логіки (табл. 2.1), так само як в алгебрі множин (табл.1.1), існує принцип двоїстості. Сутність його полягає в тому, що для будь-якого твердження з використанням символів 1 і 0 та операцій диз’юнкції і кон’юнкції можна скласти двоїсте до нього твердження шляхом заміни 0 на 1, 1 на 0, + на × , × на +, яке також буде вірним. Наприклад, двоїстими є твердження алгебри логіки А×(В+С)=(А×В)+(А×С) і А+(В×С)=(А+В)×(А+С). Читач може знайти серед наведених у таблиці 2.1 інші пари тотожностей, що пов’язані відношенням двоїстості.

У вірності формул будь-якого з законів алгебри логіки можна переконатись за допомогою таблиці істинності. Колонки таблиці істинності поділяються на дві групи, перша з яких містить всі можливі набори (комбінації) значень істинності логічних змінних, а друга – значення істинності результатів логічних операцій та формул. В якості прикладу побудуємо таблицю істинності одного з законів де Моргана (табл. 2.2).