Кон'юнктивною нормальною формою логічної функції. Нормальні форми логічних функций. Досконала диз'юнктивна та досконала кон'юнктивна нормальні форми

Введемо поняття елементарної диз'юнкції.

Елементарною диз'юнкцією називається вираз виду

Кон'юнктивною нормальною формою (КНФ) логічної функції називається кон'юнкція будь-якої кінцевої множини попарно різних елементарних диз'юнкцій. Наприклад, логічні функції

є кон'юнкцією елементарних диз'юнкцій. Отже, вони записані у кон'юнктивній нормальній формі.

Довільна логічна функція, задана аналітичним виразом, може бути наведена до КНФ шляхом виконання наступних операцій:

використання правила інверсії, якщо операція заперечення застосована до логічного виразу;

Використання аксіоми дистрибутивності щодо множення:

Використання операції поглинання:

Винятки в диз'юнкціях змінних, що повторюються, або їх заперечень;

Вилучення всіх однакових елементарних диз'юнкцій, крім однієї;

Видалення всіх диз'юнкцій, до яких одночасно входять змінна та її заперечення.

Справедливість перерахованих операцій випливає з основних аксіом та тотожних співвідношень алгебри логіки.

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

Перетворення КНФ до досконалої КНФ здійснюється шляхом виконання наступних операцій:

Додавання до кожної елементарної диз'юнкції кон'юнкцій змінних та їх заперечень, якщо вони не входять до цієї елементарної диз'юнкції;

використання аксіоми дистрибутивності;

Вилучення всіх однакових елементарних диз'юнкцій, крім однієї.

У досконалій КНФ може бути представлена ​​будь-яка логічна функція, крім

тотожно рівної одиниці (). Відмінною властивістю досконалої КНФ є те, що уявлення в ній логічної функції єдине.

Елементарні диз'юнкції, що входять до досконалої КНФ функції, звуться конституентом нуля. Кожна конституента нуля, що входить до досконалої КНФ, звертається в нуль на єдиному наборі значень змінних, що є нульовим набором функції. Отже, число нульових наборів логічної функції збігається з числом конституентів нуля, що входять до її досконалої КНФ.

Логічна функція константа нуля у досконалій КНФ є кон'юнкцією 2nконституент нуля. Сформулюємо правило складання СКНФ логічної функції таблиці відповідності.

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

Приклад 3.4.Для логічної функції z(x), заданою таблицею відповідності 2.2, визначимо досконалу кон'юнктивну форму.

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

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

Простий диз'юнкцією(англ. inclusive disjunction) або диз'юнктом(англ. disjunct) називається диз'юнкція однієї або декількох змінних або їх заперечень, причому кожна змінна зустрічається не більше одного разу.

Проста диз'юнкція

• повнаякщо в неї кожна змінна (або її заперечення) входить рівно один раз;
• монотоннаякщо вона не містить заперечень змінних.

Кон'юнктивна нормальна форма, КНФ(англ. conjunctive normal form, CNF) нормальна форма, в якій булева функція має вигляд кон'юнкції кількох простих диз'юнктів.

Приклад КНФ:$f(x,y) = (x \lor y) \land (y \lor \neg ( z ))$

СКНФ

Досконала кон'юнктивна нормальна форма, СКНФ(англ. perfect conjunctive normal form, PCNF) - це така КНФ, яка задовольняє умовам:

• в ній немає однакових простих диз'юнкцій
• кожна проста диз'юнкція повна

Приклад СКНФ:$f(x,y,z) = (x \lor \neg ( y ) \lor z) \land (x\lor y \lor \neg ( z ))$

Теорема:Для будь-якої булевої функції $f(\vec ( x ))$, не рівної тотожній одиниці, існує СКНФ, що її задає.

Доведення:Оскільки інверсія функції $\neg ( f ) (\vec x)$ дорівнює одиниці тих наборах, у яких $f(\vec x)$ дорівнює нулю, то СДНФ для $\neg ( f ) (\vec x)$ можна записати так:

$ \ neg ( f ) ( \ vec x ) = \ bigvee \ limits_ ( f ( x ^ ( \ sigma_ ( 1 ) ) , x ^ ( \ sigma_ ( 2 ) ) ) , ... , x ^ ( \ sigma_ ( n ) )) = 0 ) ( x_ ( 1 ) ^ ( \ sigma_ ( 1 ) ) \ wedge x_ ( 2 ) ^ ( \ sigma_ ( 2 ) ) \ wedge ... \ wedge x_ ( n ) ^ ( \ sigma_ ( n ) )) $, де $ \sigma_ ( i ) $ позначає наявність або відсутність заперечення при $ x_ ( i ) $

Знайдемо інверсію лівої та правої частини виразу:

$ f(\vec x) = \neg (( \bigvee\limits_ ( f(x^ ( \sigma_ ( 1 ) )) , x^ ( \sigma_ ( 2 ) )) , ... ,x^ ( \sigma_ ( n ) )) = 0 ) ( x_ ( 1 ) ^ ( \ sigma_ ( 1 ) ) \ wedge x_ ( 2 ) ^ ( \ sigma_ ( 2 ) ) \ wedge ... \ wedge x_ ( n ) ^ ( \ sigma_ ( n ) )) )) $

Застосовуючи двічі до отриманого у правій частині виразу правило де Моргана, отримуємо: $ f(\vec x) = \bigwedge \limits_ ( f(x^ ( \sigma_1 ) , x^ ( \sigma_2 ) , \dots ,x^ ( \ sigma_n )) = 0 ) $ $(\neg ( x_1^ ( \sigma_1 ) ) \vee \neg ( x_2^ ( \sigma_2 ) ) \vee \dots \vee \neg ( x_n^ ( \sigma_n ) )) $

Остання вираз і є СКНФ. Так як СКНФ отримана з СДНФ, яка може бути побудована для будь-якої функції, що не дорівнює тотожному нулю, теорема доведена.

Алгоритм побудови СКНФ за таблицею істинності

• У таблиці істинності відзначаємо ті набори змінних, у яких значення функції дорівнює $0$.
• Для кожного зазначеного набору записуємо диз'юнкцію всіх змінних за таким правилом: якщо значення деякої змінної є $0$, то диз'юнкцію включаємо саму змінну, інакше її заперечення.
• Усі отримані диз'юнкції пов'язуємо операціями кон'юнкції.

Приклад побудови СКНФ для медіани

1). У таблиці істинності відзначаємо ті набори змінних, у яких значення функції дорівнює $0$.

x	y	z	$ \langle x,y,z \rangle $
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

2). Для кожного зазначеного набору записуємо кон'юнкцію всіх змінних за таким правилом: якщо значення деякої змінної є $0$, то в диз'юнкцію включаємо саму змінну, інакше її заперечення.

x	y	z	$ \langle x,y,z \rangle $
0	0	0	0	$(x \lor y \lor z)$
0	0	1	0	$(x \lor y \lor \neg ( z ))$
0	1	0	0	$(x \lor \neg (y) \lor z)$
0	1	1	1
1	0	0	0	$(\neg (x) \lor y \lor z)$
1	0	1	1
1	1	0	1
1	1	1	1

3). Усі отримані диз'юнкції пов'язуємо операціями кон'юнкції.

$ \langle x,y,z \rangle = (x \lor y \lor z) \land (\neg (x) \lor y \lor z) \land (x \lor \neg (y) \lor z) \land (x \lor y \lor \neg ( z ))$

Приклади СКНФ для деяких функцій

Стрілка Пірса: $ x \downarrow y = (\neg (x) \lor(y)) \land ((x) \lor \neg(y)) \land (\neg(x) \lor \neg(y) ) $

Виключне або: $ x \oplus y \oplus z = (\neg ( x ) \lor \neg ( y ) \lor z) \land (\neg ( x ) \lor y \lor \neg ( z )) \land (x \lor \neg ( y ) \lor \neg ( z )) \land (x \lor y \lor z)$

Нормальна форма логічної формули не містить знаків імплікації, еквівалентності та заперечення неелементарних формул.

Нормальна форма існує у двох видах:

кон'юнктивна нормальна форма (КНФ)-- кон'юнкція декількох диз'юнкцій, наприклад, $ \ left (A \ vee \ overline (B) \ vee C \ right) \ wedge \ left (A \ vee C \ right) $;

диз'юнктивна нормальна форма (ДНФ)-- диз'юнкція декількох кон'юнкцій, наприклад, $ \ left (A wedge \ overline (B) \ wedge C \ right) \ vee \ left (B \ wedge C \ right) $.

СКНФ

Досконала кон'юнктивна нормальна форма (СКНФ) -- це КНФ, яка задовольняє трьома умовами:

не містить однакових елементарних диз'юнкцій;

жодна з диз'юнкцій не містить однакових змінних;

кожна елементарна диз'юнкція містить кожну змінну з тих, що входять до цієї КНФ.

Будь-яка булева формула, яка не є тотожно істинною, може бути подана у СКНФ.

Правила побудови СКНФ за таблицею істинності

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

СДНФ

Досконала диз'юнктивна нормальна форма (СДНФ) -- це ДНФ, яка задовольняє трьома умовами:

не містить однакових елементарних кон'юнкцій;

жодна з кон'юнкцій не містить однакових змінних;

кожна елементарна кон'юнкція містить кожну змінну з тих, що входять до цієї ДНФ, до того ж в однаковому порядку.

Будь-яка булева формула, яка не є тотожно хибною, може бути представлена ​​в СДНФ, до того ж єдиним чином.

Правила побудови СДНФ за таблицею істинності

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

Приклади знаходження СКНФ та СДНФ

Приклад 1

Записати логічну функцію за її таблицею істинності:

Малюнок 1.

Рішення:

Скористаємося правилом побудови СДНФ:

Малюнок 2.

Отримаємо СДНФ:

Скористаємося правилом побудови СКНФ.

Стандартний базис. Елементарні формули – літерали. Елементарна кон'юнкція (диз'юнкція). Диз'юнктивна (кон'юнктивна) нормальна форма та досконала форма. Теорема: будь-яка функція булева, відмінна від 0 (від 1) представима у вигляді СДНФ (СКНФ). Повнота стандартного базису. Приклади повних базисів: базис Жегалкіна, штрих Шеффера, стрілка Пірса.

Стандартний базис - це набір із трьох вихідних операцій булевої алгебри: додавання (об'єднання), множення (перетину) та заперечення.

Тут ми називатимемо літералом змінну x або її заперечення x та позначати xˆ. Булево перетин кількох літералів, визначених різними змінними, тобто. вираз виду X = x 1 x 2 . . . xˆ л називається елементарною кон'юнкцією . Вимога, щоб усі змінні були різні, обумовлюється наступним. Якщо в кон'юнкцію входить кілька однакових літералів, то через комутативність, асоціативність та ідемпотентність кон'юнкції можна, переходячи до еквівалентної формули, залишити лише один літерал (наприклад, x 1 x 1 = x 1). Якщо кон'юнкцію входить змінна та її заперечення, то формула еквівалентна константі 0, оскільки x x = 0 і для будь-якої формули Y маємо Y x x = 0.

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

x 1 x 3 + x 2 x 3 x 4 + x 1 x 2 x 3 x 5 .

Якщо склад змінних у кожній елементарній кон'юнкції цієї ДНФ той самий, то ДНФ називається досконалою . Наведений приклад - це ДНФ, яка не є досконалою. Навпаки, формула

x 1 x 2 x 3 x 4 +x 1 x 2 x 3 x 4 +x 1 x 2 x 3 x 4

є досконала форма.

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

Теорема 1.4.Будь-яка булева функція, відмінна від константи 0, представна у вигляді СДНФ.

◀Умовимося під x σ розуміти формулу x, якщо σ = 1, і формулу x , якщо σ = 0. Нехай функція f(y 1 , . . . , y n) набуває значення 1 на векторі (t 1 , . . . , t n ) (такий вектор називають конституентою одиниці ). Тоді елементарна кон'юнкція також приймає значення 1 на цьому наборі, але звертається в нуль на решті всіх n-вимірних булевих векторах. Розглянемо формулу

в якій сума (об'єднання) поширюється на всі ті набори (t 1 , . доданок.

Неважко помітити, що формула Φ звертається в 1 при тих, і тільки при тих значеннях змінних, при яких звертається в 1 функція, що розглядається. Отже, формула Ψ представляє функцію f.

Наслідок 1.1.Стандартний базис є повним.

◀ Дійсно, якщо функція не є константою 0, то вона уявна або у вигляді СДНФ, яка є формулою над стандартним базисом. Константу 0 можна подати, наприклад, формулою f(x 1 , x 2 , . . . , x n) = x 1 x 1 .

приклад 1.2.Розглянемо функцію трьох змінних m(x 1 , x 2 , x 3) (табл. 1.4), звану мажоритарної функції ̆. Ця функція набирає значення 1, якщо більше половини її аргументів мають значення 1. Тому її часто називають функцією голосування. Побудуємо для неї СДНФ.

Повнота стандартного базису дозволяє підбирати інші повні системи функцій. Повнота множини F може бути встановлена ​​з таких міркувань. Припустимо, кожна з трьох функцій стандартного бузи представимо формулою над F . Тоді з теореми 1.3 іноже F буде повним.

приклад 1.3.Безліч операцій складання по модулю 2, множення і константи 1 називають базисом Жегалкіна . Додавання за модулем 2 і множення - базові операції кільця Z2, вирази, складені з їх допомогою - це багаточлени над кільцем Z2. Константа 1 у цьому випадку необхідна для запису вільного члена. Оскільки xx = x, то всі співмножники в многочлен мають ступінь 1. Тому при записі многочлена можна обійтися без поняття ступеня. Приклади формул над базисом Жегалкіна:

xy⊕x⊕y, x⊕1, xyz⊕xz⊕x⊕y⊕1.

Будь-яку таку формулу називають поліномом Жегалкіна. Фактично поліном Жегалкіна – це багаточлен над кільцем Z2.

Неважко сконструювати формули над базисом Жегалкіна, що представляють операції складання та заперечення стандартного базису (множення у двох базисів загальне):

x+y=x⊕y⊕xy, x =x⊕1.

Тому базис Жегалкіна - безліч.
Можна показати, що для будь-якої булевої функції поліном Жегалкіна визначено однозначно

(точніше, з точністю до порядку доданків). Коефіцієнти полінома Жегалкіна при невеликій кількості змінних можна визначити методом невизначених коефіцієнтів.

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

x = x | x, xy = x | y = (x | y) | (x | y), x + y = x | y = (x | x) | (y | y).

приклад 1.5.Базис, що складається з єдиної функції – стрілки Пірса, також є повним. Перевірка цього аналогічна випадку штриха Шеффера. Втім, цей висновок можна зробити і на підставі принципу двоїстості для симетричних напівкілець.

*Штрих Шеффера - бінарна, але з асоціативна операція. Тому при використанні інфіксної форми слід бути уважним: результат залежить від порядку виконання операцій. І тут рекомендується явно вказувати порядок операцій з допомогою дужок, наприклад писати (x | y) | z, а чи не x | y | z, хоча обидві форми рівнозначні.

Визначення 1.Кон'юнктивним одночленом (елементарною кон'юнкцією)від змінних називається кон'юнкція цих змінних чи його заперечень.

Наприклад, - Елементарна кон'юнкція.

Визначення 2.Диз'юнктивним одночленом (елементарною диз'юнкцією)від змінних називається диз'юнкція цих змінних чи його заперечень.

Наприклад, - Елементарна диз'юнкція.

Визначення 3.Формула, що дорівнює даній формулі алгебри висловлювань і є диз'юнкцією елементарних кон'юнктивних одночленів, називається диз'юнктивною нормальною формою(ДНФ) цієї формули.

Наприклад,- ДНФ.

Визначення 4.Формула, що дорівнює даній формулі алгебри висловлювань і є кон'юнкцією елементарних диз'юнктивних одночленів, називається кон'юнктивною нормальною формою(КНФ) цієї формули.

Наприклад, - КНФ.

Для кожної алгебри формули висловлювань можна знайти безліч диз'юнктивних і кон'юнктивних нормальних форм.

Алгоритм побудови нормальних форм

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

Позбутися знаків подвійного заперечення.

Застосувати, якщо потрібно, до операцій кон'юнкції та диз'юнкції властивості дистрибутивності та формули поглинання.

2.6. Досконала диз'юнктивна та досконала кон'юнктивна нормальні форми

Будь-яка функція булева може мати багато уявлень у вигляді ДНФ і КНФ. Особливе місце серед цих уявлень займають досконалі ДНФ (СДНФ) та скоєні КНФ (СКНФ).

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

Конструктивно СДНФ кожної формули алгебри висловлювань, наведеної до ДНФ, можна визначити так:

Визначення 2. Досконала диз'юнктивна нормальна форма(СДНФ) формули алгебри висловлювань називається її ДНФ, яка має наступні властивості:

Визначення 3. Досконала кон'юнктивна нормальна форма(СКНФ) - це КНФ, в якій в кожен диз'юнктивний одночлен кожна змінна з набору входить рівно один раз, причому входить або сама, або її заперечення.

Конструктивно СКНФ кожної формули алгебри висловлювань, наведеної до КНФ, можна визначити так.

Визначення 4. Досконала кон'юнктивна нормальна форма(СКНФ) даної формули алгебри висловлювань називається така її КНФ, яка задовольняє такі властивості.

Теорема 1.Кожна булева функція від змінних, яка не є тотожно хибною, може бути представлена ​​в СДНФ, причому єдиним чином.

Способи знаходження СДНФ

1-й спосіб

2-й спосіб

виділяємо рядки, де формула набуває значення 1;

складаємо диз'юнкцію кон'юнкцій за умови, якщо змінна входить у кон'юнкцію зі значенням 1, то записуємо цю змінну, якщо зі значенням 0, то її заперечення. Отримуємо СДНФ.

Теорема 2.Кожна булева функція від змінних, яка не є тотожно істинною, може бути представлена ​​в СКНФ, і до того ж єдиним чином.

Способи знаходження СКНФ

1-й спосіб- За допомогою рівносильних перетворень:

2-й спосіб- За допомогою таблиць істинності:

виділяємо рядки, де формула набуває значення 0;

складаємо кон'юнкцію диз'юнкцій за умови, що якщо змінна входить у диз'юнкцію зі значенням 0, то записуємо цю змінну, якщо зі значенням 1, то її заперечення. Отримуємо СКНФ.

приклад 1.Побудуйте функції КНФ .

Рішення

Виключимо зв'язку «» за допомогою законів перетворення змінних:

= / Закони де Моргана та подвійного заперечення / =

/дистрибутивні закони/ =

приклад 2.Приведіть до ДНФ формулу.

Рішення

Висловимо логічні операції і через:

= /віднесемо заперечення до змінних і скоротимо подвійні заперечення/ =

= / Закон дистрибутивності / .

приклад 3.Запишіть формулу в ДНФ та СДНФ.

Рішення

Використовуючи закони логіки, наведемо цю формулу до виду, що містить лише диз'юнкції елементарних кон'юнкцій. Отримана формула і буде шуканою ДНФ:

Для побудови СДНФ складемо таблицю істинності для цієї формули:

Позначаємо ті рядки таблиці, в яких формула (останній стовпець) приймає значення 1. Для кожного такого рядка випишемо формулу, дійсну на наборі змінних даного рядка:

рядок 1: ;

рядок 3: ;

Рядок 5: .

Диз'юнкція цих трьох формул прийматиме значення 1 тільки на наборах змінних у рядках 1, 3, 5, а отже, і буде шуканою досконалою диз'юнктивною нормальною формою (СДНФ):

приклад 4.Наведіть формулу до СКНФ двома способами:

а) за допомогою рівносильних перетворень;

б) з допомогою таблиці істинності.

Рішення:

Перетворимо другу елементарну диз'юнкцію:

Формула має вигляд:

б) складемо таблицю істинності для цієї формули:

Позначаємо рядки таблиці, в яких формула (останній стовпець) приймає значення 0. Для кожного такого рядка випишемо формулу, істинну на наборі змінних даного рядка:

рядок 2: ;

Рядок 6: .

Кон'юнкція цих двох формул прийматиме значення 0 тільки на наборах змінних у рядках 2 і 6, а отже, і буде шуканою досконалою кон'юнктивною нормальною формою (СКНФ):

Запитання та завдання для самостійного вирішення

1. За допомогою рівносильних перетворень наведіть до ДНФ формули:

2. За допомогою рівносильних перетворень наведіть до КНФ формули:

3. За допомогою другого дистрибутивного закону перетворіть ДНФ на КНФ:

а) ;

4. Перетворіть задані ДНФ на СДНФ:

5. Перетворіть задані КНФ на СКНФ:

6. Для заданих логічних формул побудуйте СДНФ та СКНФ двома способами: за допомогою рівносильних перетворень та за допомогою таблиці істинності.

б) ;