Закон де Моргана

Логічні функції можна розглядати як елементарні операції над однією або двома двійковими змінними. Функціонально повна система таких операцій утворюється на множині двозначних змінних алгебри логіки. Таких алгебр може бути стільки скільки існує придатних функціонально повних систем. Найбільш розповсюдженою є Булева алгебра в якій в якості основних операцій використовують кон’юнкцію (І), диз’юнкцію (АБО), заперечення (НЕ). Для наочності на рис.1(а, б, в) показано визначення операцій І, АБО, НЕ на діаграмах Венна

clip_image002[4]

Рис.1

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

Таблиця 1

Властивість

Перша форма (|) (диз’юнктивна)

Друга форма (||) (кон’юнктивна)

1. Комутативність

x+y=y+x

x·y=y·x

2. Асоціативність

x+(y+z)=(x+y)+z

x·(y·z)=(x·y)·z

3. Дистрибутивність

x(y+z)=xy+xz

x +y·z=(x+y)(x+z)

4. Доповнення

clip_image004

clip_image006

5. Повтор змінної

x+0=x

x·1=x

6. Повтор константи

x+1=1

x·0=0

7. Подвійне заперечення

clip_image008

clip_image010

8. Ідемпотентність

x+x=x

x·x=x

9. Закони де Моргана

clip_image012

clip_image014

10. Склеювання

xy+xy¯=x

(x+y)(x+y¯)=x

11. Поглинання

x+xy=x

x(x+y)=x

12. Заміщення

clip_image016

clip_image018

13. Виявлення

clip_image020

clip_image022

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

Друга форма (для кон’юнкції) у звичайній алгебрі аналогів немає що є основною відмінністю її від алгебри логіки.

Подвійне запереченння не змінює змінну що можна розглядати як порожню операцію.

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

Подані у табл. Пари властивостей мають специфічну симетрію яка відображає принцип дуальності алгебри логіки. У кожній парі одну форму можна отримати з другої заміною операції І, АБО а також констант 0, 1. у звязку з цим операції І, АБО і константи 0, 1 називають дуальними. З принципом дуальності повязане узагальності законів де Моргана на будь-яку кількість змінних.

Закон де Моргана

Якщо функція clip_image024 дуальна функції clip_image026 то

clip_image028, (1)

тобто заперечення деякої функції можна визначити заміною у дуальній функції кожної змінної її заперечення (інверсія).

З формули (1) випливає

clip_image030

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

Оставьте комментарий к статье