Побудова ДДНФ для логічної функції

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

Терм – це група логічних змінних в прямій або інверсній формі, поєднаних однією функцією: ab̅c, a̅bc̅, a+b̅̅+c, a̅+b+c … В термі кожна змінна або її інверсія можуть бути присутні тільки раз.

Ранг терма визначається кількістю змінних, що входять до нього. Максимальний ранг терма містить всі змінні логічної функції.

Диз’юнктивний терм (макстерм) – це група логічних змінних в прямій або інверсній формі, поєднаних диз’юнкцією: a+b̅̅+c, a̅+b+c …

Макстерм називають конституентою нуля, якщо ця логічна функція дорівнює 0, тільки якщо всі її аргументи дорівнюють 0.

Кон’юнктивний терм (мінтерм) – це група логічних змінних в прямій або інверсній формі, поєднаних кон’юнкцією: ab̅c, a̅bc̅, …

Мінтерм називають конституентою одиниці, якщо ця логічна функція дорівнює 1, тільки якщо всі її аргументи дорівнюють 1.

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

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

Нормальною диз’юнктивною формою (НДФ) називають диз’юнктивне поєднання мінтермів різних рангів, включаючи і ті, ранг яких дорівнює 1.

Наприклад: f(x₁,x₂,x₃) = x₃ +x₁x₂ + x₂x₃ +x₁x₂x₃

Нормальною кон’юнктивною формою (НДФ) називають кон’юнктивне поєднання макстермів різних рангів, включаючи і ті, ранг яких дорівнює 1.

Наприклад: f(x₁,x₂,x₃) = (x₁ +x₂)(x₂ + x₃)(x₁ +x₂ + x₃).

Нормальні кон’юнктивні і диз’юнктивні форми не еквівалентні самій логічній функції. Для однозначної відповідності логічній функції використовують досконалі нормальні форми:

Досконалою диз’юнктивною нормальною формою (ДДНФ) називають диз’юнктивне поєднання всіх конституетн одиниці максимальних рангів.

Розглянемо процедуру на прикладі: f(x, y, z) = (x®y)~(y̅∧z).Для побудови ДДНФ побудуємо конституенти одиниці функції.

x	y	z	x®y	y̅	y̅∧z	f	Конституенти одиниці
							x̅∧y̅∧z
							x∧y̅∧z̅

Конституенти будуємо для тих інтерпретацій, де f = 1. Будуємо їх як кон’юнкцію змінних, виконуючи інверсію тих змінних, значення яких в даній інтерпретації – 0.

Тобто, для f(0, 0, 1) = 1, перша конституента має вигляд: x̅∧y̅∧z. Для f(1, 0, 0) = 1 друга конституента має вигляд: x∧y̅∧z̅.

ДДНФ f =(x̅∧y̅∧z)Ú(x∧y̅∧z̅).

Спростимо формулу, використовуючи закони булевої алгебри. Використаємо закон де Моргана: ДДНФ f =(x̅∧y̅∧z)Ú(x∧y̅∧z̅) = .

Перевіримо, чи еквівалентна побудована функція даній.

x	y	z			∧z	x ∧	f

Побудована ДДНФ еквівалентна даній функції, але містить тільки ті операції, для реалізації яких є відповідні логічні елементи.

Табличне задання логічної функції досить громіздке і більшість таблиці істинності є задання всіх інтерпритацій, а тількі один стовпчик – значення ЛФ на кожній інтерпритації. Для компактності можна таблицю істинності функції описати таким чином: f(x₁, x₂, x₃)=1 для X∈{0, 3, 5, 6}. Х – це двійкове число, що утворене значеннями змінних x₁, x₂, x₃, причому десяткове значення цього двійкового числа може бути 0, 3, 5, 6.

0₁₀=000₂, тобто f(0, 0, 0)=1. 3₁₀=011₂, тобто f(0, 1, 1)=1. 5₁₀=101₂, тобто f(1, 0, 1)=1.

6₁₀=110₂, тобто f(1, 1, 0)=1. На всіх інших інтерпритаціях (x₁, x₂, x₃)=0.

Для самостійної роботи

Критерії оцінювання: Кожне завдання – 4 бали. Максимальна кількість балів – 12.

Завдання Побудувати ДДНФ для логічних функцій, визначених в вигляді:

а) f(x₁, х₂, х₃)=1 для Х; b) f(x₁, х₂, х₃, х₄)=1 для Х; c) f = f(x, y, z).

Варіант	a) X; b) X; c) f = f(x, y, z);	Варіант	a) X; b) X; c) f = f(x, y, z);
	d) X={1, 2, 5, 7}; e) X={0, 3, 5, 9, 13} f) ;		a) X={1, 2, 4, 6}; b) X={0, 2, 3, 10, 14}; c) ;
	a) X={0, 1, 4, 5}; b) X={0, 1, 5, 7, 11}; c) ;		a) X={0, 1, 3, 7}; b) X={1, 3, 8, 10, 12}; c) ;
	a) X={1, 3, 4, 6}; b) X={2, 3, 6, 9, 15}; c) ;		a) X={0, 2, 4, 7}; b) X={1, 4, 7, 12, 15}; c) ;

Самостійна робота № 12

Тема: Побудова нормальної форми для логічної функції

Мета: Закріпити набуті знання та навички, перевірити їх при виконанні практичних завдань.