Основні закони алгебри логіки та їх використання для подання одних функцій логіки через інші
Вперше логічні функції були використані в алгебрі логіки, початок якій покладено працями англійського математика Дж. Буля, її також називають булевою алгеброю або алгеброю висловлень.
Під висловленням розуміється будь-яке твердження, яке може бути істинним або хибним.
Істинному висловленню приписується 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 трехвходових трійчастий логічних елементів ( трійчастий функції).
Двійкові логічні операції з цифровими сигналами ( бітові операції)
Логічні операції ( булева функція) своє теоретичне обгрунтування отримали в алгебрі логіки.
Логічні операції з одним операндом називаються унарний, з двома - бінарними, з трьома - тернарних (тріарнимі, трінарнимі) і т. д.
З 
можливих унарних операцій з унарні виходом інтерес для реалізації представляють операції заперечення і повторення, причому, операція заперечення має велику значимість, ніж операція повторення, так як повторювач може бути зібраний з двох інверторів, а інвертор з повторювачів не зібрати.