Набір логічних функцій двох змінних

Аргументи	Функція	Назва функції
Х₁ Х₂
			у₁ = 0	Константа 0
			у₂ = х₁х₂	Кон’юнкція, операція І
				Заборона по х₂
			у₄ = х₁	Тотожність х₁
				Заборона по х₁
			у₆ = х₂	Тотожність х₂
			х₁х₂	АБО, що виключає нерівнозначність (сума по модулю 2)
				Диз'юнкція, операція АБО
				Операція АБО – НЕ (стрілка Пірса)
				Рівнозначність, еквівалентність
				Інверсія х₂, заперечення х₂
				Імплікація від х₂ до х₁
				Інверсія х₁, заперечення х₁
				Імплікація від х₁ до х₂
				Операція І – НЕ (штрих Шеффера)
			у₁₆ = 1	Константа 1

Операція логічного множення для двох змінних характеризується так: 0∙ 0 = 0; 0∙ 1 = 0; 1∙ 0 = 0; 1∙ 1 = 1, тобто функція в = 1, якщо всі аргументи рівні 1.

Операцію логічного додавання позначають . Вона означає, що: 0 0 = 0; 0 1 = 1; 1 0 = 1; 1 1 = 1, тобто в = 1, якщо хоча б один аргумент дорівнює 1.

Кон’юнкція і диз'юнкція можуть виконуватися над будь-якою кількістю змінних.

Логічна функція може бути задана словесно, алгебраїчним вираженням і таблицею істинності. Наприклад, функцію , задану у виді словесного опису: = 1, коли значення змінних , і = 0, коли , можна представити у виді таблиці істинності (таблиця 10.3) чи в алгебраїчній формі (див. таблицю 10.2). Для операцій кон’юнкції та диз'юнкції таблична форма завдання має вид – таблиця 10.4.

Таблиця 10.3	Таблиця 10.4

Таблиця істинності містить усі N = 2ⁿ можливі набори значень змінних і значення функції, що відповідають кожному з наборів.

Щоб здійснити перехід від табличного представлення до алгебраїчного, кожного числового набору змінних ставиться у відповідність мінтерм m_i. Мінтерм (конституанта одиниці) – це кон’юнкція всіх змінних , причому ті змінні , котрі в наборі мають значення 1, представляються в прямому виді, а ті, котрі мають значення 0, − в інверсному. Тоді шукане алгебраїчне вираження представляється у виді наступної логічної суми:

(10.4)

де − значення функції (0 чи 1) і мінтерм, що відповідають i-му числовому набору змінних . Таке представлення функції називається її зробленою диз'юнктивною нормальною формою (СДНФ).

Наприклад, потрібно одержати алгебраїчний запис функції в₁₀,заданої таблиці 10.3. Для цього необхідно відповідно до вище викладеної методики скласти мінтерми (таблиця 10.5) і скористатися вираженням (10.4). Вийде

Таблиця 10.5

Мінтерми, макстерми і значення функції в₁₀

Мінтерми Макстерми Значення функції у₁₀

Інша алгебраїчна форма представлення функції виходить при використанні макстермів. Макстермом (конституентой 0) називається диз'юнкція всіх змінних , причому ті змінні, котрі в наборі мають значення 1, представляються в прямому виді, а ті, котрі мають значення 0, − в інверсному. Алгебраїчне вираження функції виходить у виді логічного множення:

(10.5)

де − значення функції і макстерм, що відповідають i-му числовому набору змінних . Таке представлення функції називається її зробленою кон’юнктивною нормальною формою (СКНФ).

Вираження функції в СДНФ і CKHФ, звичайно, розрізняються по виду, але вони еквівалентні один одному. Наприклад, і . Крім того, вираження в СДНФ і СКНФ часто не є найбільш простими. Використовуючи тотожності і закони булевої алгебри, можна в багатьох випадках одержати більш прості форми представлення функції, що називаються мінімізованими.

При відносно невеликому числі змінних (n ≤ 6) дуже зручним і наочної є графічне представлення функцій у виді так званих карт мінтермів, найбільш розповсюдженою формою яких вважаються карти Карно. Техніка представлення функцій за допомогою карт Карно викладена, наприклад, у [6].

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

Як відзначалося вище, для перетворення алгебраїчних виражень використовують тотожності (аксіоми) і закони булевої алгебри. Основні з них приведені в таблиці 10.6.

У ній алгебраїчні вираження тотожностей і законів задані парами на підставі принципу дуальності (подвійності), відповідно до якого операції кон’юнкції та диз'юнкції допускають взаємну заміну, якщо одночасно поміняти логічну 1 на 0, 0 на 1, знак \/ на ∙ , а ∙ на \/ .

Застосування аксіом і законів булевої алгебри покажемо на прикладі перетворення функції в₁₀ зі СКНФ у СДНФ. Для цього можна використовувати розподільний закон (10.14), потім тотожність (10.10):

Таблиця 10.6