Основні закони алгебри логіки та їх використання для подання одних функцій логіки через інші

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

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

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

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

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

Кон’юнкція являє собою логічний зв’язок “І” (див. табл. 1.5).

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

Таблиця 1.5

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

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

Таблиця 1.6

		= ” або ”

Логічний зв’язок “НЕ” (заперечення). Логічний зв’язок “НЕ” означає заперечення висловлення і читається “НЕ ”, позначається або (табл. 1.7)

Таблиця 1.7

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

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

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

– закон комутативності:

; (1.1)

– закон асоціативності:

; (1.2)

– закон дистрибутивності:

; (1.3)

для спрощення формул крім аксіом використовують такі співвідношення або закони алгебри логіки:

– логічне додавання до нуля:

; (1.4)

– логічне додавання до одиниці:

; (1.5)

– логічне множення на 0:

; (1.6)

– логічне множення на 1:

; (1.7)

– закон протиріччя:

; (1.8)

– закон виключеного третього:

. (1.9)

Всі інші закони є наслідком зазначених вище:

– закон ідемпотентності:

; (1.10)

– закон подвійного заперечення:

; (1.11)

– закон поглинання (х поглинає у):

; (1.12)

– закон де Моргана:

(1.13)

(1.14)

– наслідки законів де Моргана:

; (1.15)

. (1.16)

За допомогою розглянутих співвідношень можна виконувати різні тотожні перетворення булевих виразів.

При цьому порядок виконання дій такий:

При відсутності дужок виконуються операції заперечення, потім кон’юнкції, останніми – диз’юнкції.

Подання одних функцій алгебри логіки через інші

1. Операція заборони:

. (1.17)

Для доведення цього і наступних співвідношень будемо підставляти в ліву і праву частини виразу окремі значення аргументів і перевіряти правильність рівності.

Таблиця 1.8

Таблиця 1.9

2. Сума за модулем 2:

. (1.18)

3. Операція Пірса:

(операція АБО-НЕ). (1.19)

4. Логічна рівнозначність:

. (1.20)

Справедливість першої рівності може бути встановлена безпосередньо по таблицях істинності функції логічної рівнозначності і суми по модулю 2; наступних рівностей - шляхом інвертування лівої і правої частин виразу і перетворення за формулами де Моргана.

5. Імплікація:

. (1.21)

6. Функція Шеффера:

(операція І-НЕ). (1.22)

Логічні елементи - пристрої, призначені для обробки інформації в цифровій формі (послідовності сигналів високого - "1" і низького - "0" рівнів в двійковій логіці, послідовність "0", "1" і "2" в троичной логіці, послідовності "0", "1", "2", "3", "4", "5", "6", "7", "8" і "9" в десятковій логіці). Фізично логічні елементи можуть бути виконані механічними, електромеханічними (на електромагнітних реле), електронними (на діодах і транзисторах), пневматичними, гідравлічними, оптичними та ін

З розвитком електротехніки від механічних логічних елементів перейшли до електромеханічних логічним елементам (на електромагнітних реле), а потім до електронних логічним елементам на електронних лампах, пізніше - на транзисторах. Після докази в 1946 р. теореми Джона фон Неймана про економічність показових позиційних систем числення стало відомо про переваги двійкової та троичной систем числення в порівнянні з десятковою системою числення. Від десяткових логічних елементів перейшли до двійковим логічним елементам. Двоічность і троїчність дозволяє значно скоротити кількість операцій і елементів, що виконують цю обробку, в порівнянні з десятковими логічними елементами.

Логічні елементи виконують логічну функцію (операцію) над вхідними сигналами (операндами, даними).

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

Усього можливі двійкових двухвходових логічних елементів і двійкових трехвходових логічних елементів ( Булева функція).

Крім 16 двійкових двухвходових логічних елементів і 256 трехвходових двійкових логічних елементів можливі 19683 двухвходових трійчастий логічнихелемента і 7 625 597 484 987 трехвходових трійчастий логічних елементів ( трійчастий функції).

Двійкові логічні операції з цифровими сигналами ( бітові операції)

Логічні операції ( булева функція) своє теоретичне обгрунтування отримали в алгебрі логіки.

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

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