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

Вперше логічні функції були використані в алгебрі логіки, початок якій покладено працями англійського математика Дж. Буля, її також називають булевою алгеброю або алгеброю висловлень.

Під висловленням розуміється будь-яке твердження, яке може бути істинним або хибним.

Істинному висловленню приписується 1, хибному – 0. Висловлення можуть бути простими і складними. Складні висловлення складаються з простих.

Для об’єднання простих висловлень в складні використовуються логічні зв’язки, що відповідають логічним функціям, аргументами яких є прості висловлення.

Логічний зв’язок «І» (кон’юнкція). Кон’юнкцією називають складне висловлення, що містить 2 або більше простих висловлень і яке є істинним тоді і лише тоді, коли істинними є прості висловлення, і хибним, якщо хоч одне з простих висловлень хибне.

Кон’юнкція являє собою логічний зв’язок «І» (див. рис. 1).

З’єднання двох висловлень читається як « і ». Позначається або .

 

Рис. 1. Логічний зв’язок «І».

 

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

Диз’юнкція являє собою логічний зв’язок «АБО» (рис. 2) і позначається . Читається « або ».

 

Рис. 2. Логічний зв’язок «АБО».

 

Логічний зв’язок «НІ» (заперечення). Логічний зв’язок «НІ» означає заперечення висловлення і читається «НІ », позначається або  (рис. 3)

Рис. 3. Логічний зв’язок «НІ».

 

Запереченням висловлення називають складне висловлення «НІ », яке є істинним, коли хибне, і хибним, коли істинне.

Для зручності подальших викладок використаємо позначення:  «∙» – кон’юнкція, «» – диз’юнкція і «» – заперечення.

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