Кон'юнктівной нормальною формою логічної функції. Диз'юнктивна і Кон'юнктивна вчинені нормальні форми
простий кон'юнкція називається кон'юнкція однією або декількох змінних, при цьому кожна змінна зустрічається нЕ більше одного рази (або сама, або її заперечення).
Наприклад, є простий кон'юнкція,
диз'юнктивній нормальної формою (ДНФ) називається диз'юнкція простих кон'юнкція.
Наприклад, вираз є ДНФ.
досконалої диз'юнктивній нормальної формою (СДНФ) називається така діз'юнктівная нормальна форма, у якої в кожну кон'юнкцію входять усе змінні даного списку (або самі, або їх заперечення), причому в одному і тому жпорядку.
Наприклад, вираз є ДНФ, але не СДНФ. вираз 
є СДНФ.
Аналогічні визначення (з заміною кон'юнкції на диз'юнкцію і навпаки) вірні для КНФ і СКНФ. Наведемо точні формулювання.
простий диз'юнкція називається диз'юнкція однією або декількох змінних, при цьому кожна змінна входить нЕ більше одного рази (або сама, або її заперечення) .Наприклад, вираз - проста диз'юнкція,
кон'юнктівной нормальної формою (КНФ) називається кон'юнкція простих диз'юнкцій (Наприклад вираз - КНФ).
Досконалої кон'юнктівной нормальною формою (СКНФ) називається така КНФ, у якій в кожну просту диз'юнкцію входять всі змінні даного списку (або самі, або їх заперечення), причому в однаковому порядку.
Наприклад, вираз 
є СКНФ.
Наведемо алгоритми переходів від однієї форми до іншої. Природно, що в конкретних випадках (при певному творчому підході) застосування алгоритмів буває більш трудомістким, ніж прості перетворення, що використовують конкретний вид даної форми:
а) перехід від ДНФ до КНФ
Алгоритм цього переходу наступний: ставимо над ДНФ два заперечення і за допомогою правил де Моргана (не чіпаючи верхнє заперечення) наводимо заперечення ДНФ знову до ДНФ. При цьому доводиться розкривати дужки з використанням правила поглинання (або правила Блейка). Заперечення (верхнє) отриманої ДНФ (знову за правилом де Моргана) відразу дає нам КНФ:
Зауважимо, що КНФ можна отримати і з початкового виразу, якщо винести у за дужки;
б) перехід від КНФ до ДНФ
Цей перехід здійснюється простим розкриттям дужок (при цьому знову-таки використовується правило поглинання)
Таким чином, отримали ДНФ.
Зворотний перехід (від СДНФ до ДНФ) пов'язаний з проблемою мінімізації ДНФ. Детальніше про це буде розказано в розд. 5, тут же ми покажемо, як спростити ДНФ (або СДНФ) за правилом Блейка. Така ДНФ називається скороченою ДНФ;
в) скорочення ДНФ (або СДНФ) по правилом Блейка
Застосування цього правила складається з двох частин:
Якщо серед діз'юнктних доданків в ДНФ є складові 
, То до всієї диз'юнкції додаємо доданок До 1 До 2. Проробляємо цю операцію кілька разів (можна послідовно, можна одночасно) для всіх можливих пар доданків, а потім, застосовуємо звичайне поглинання;
Якщо додається доданок вже містилося в ДНФ, то його можна відкинути зовсім, наприклад,
або
Зрозуміло, скорочена ДНФ не визначається єдиним чином, але всі вони містять однакову кількість літер (наприклад, є ДНФ 
, Після застосування до неї правила Блейка можна прийти до ДНФ, равносильной даної):
в) перехід від ДНФ до СДНФ
Якщо в якийсь простий кон'юнкції бракує змінної, наприклад, z, Вставляємо в неї вираз, після чого розкриваємо дужки (при цьому повторюються діз'юнктние складові не пишемо). наприклад:
г) перехід від КНФ до СКНФ
Цей перехід здійснюється способом, аналогічним до попереднього: якщо в простій диз'юнкції не вистачає якоїсь змінної (наприклад, z, То додаємо в неї вираз (це не змінює самої диз'юнкції), після чого розкриваємо дужки з використанням розподільного закону):
Таким чином, з КНФ отримана СКНФ.
Зауважимо, що мінімальну або скорочену КНФ зазвичай отримують з відповідною ДНФ.
Кон'юнктивна нормальна форма зручна для автоматичного доведення теорем. Будь-яка булева формула може бути приведена до КНФ. Для цього можна використовувати: закон подвійного заперечення, закон де Моргана, дистрибутивность.
енциклопедичний YouTube
-
1 / 5
формули в КНФ:
¬ A ∧ (B ∨ C), (\\ displaystyle \\ neg A \\ wedge (B \\ vee C),) (A ∨ B) ∧ (¬ B ∨ C ∨ ¬ D) ∧ (D ∨ ¬ E), (\\ displaystyle (A \\ vee B) \\ wedge (\\ neg B \\ vee C \\ vee \\ neg D) \\ wedge ( D \\ vee \\ neg E),) A ∧ B. (\\ Displaystyle A \\ wedge B.)формули не в КНФ:
¬ (B ∨ C), (\\ displaystyle \\ neg (B \\ vee C),) (A ∧ B) ∨ C, (\\ displaystyle (A \\ wedge B) \\ vee C,) A ∧ (B ∨ (D ∧ E)). (\\ Displaystyle A \\ wedge (B \\ vee (D \\ wedge E)).)Але ці 3 формули не в КНФ еквівалентні такими формулами в КНФ:
¬ B ∧ ¬ C, (\\ displaystyle \\ neg B \\ wedge \\ neg C,) (A ∨ C) ∧ (B ∨ C), (\\ displaystyle (A \\ vee C) \\ wedge (B \\ vee C),) A ∧ (B ∨ D) ∧ (B ∨ E). (\\ Displaystyle A \\ wedge (B \\ vee D) \\ wedge (B \\ vee E).)побудова КНФ
Алгоритм побудови КНФ
1) Позбутися від всіх логічних операцій, що містяться у формулі, замінивши їх основними: кон'юнкція, диз'юнкція, запереченням. Це можна зробити, використовуючи рівносильні формули:
A → B \u003d ¬ A ∨ B, (\\ displaystyle A \\ rightarrow B \u003d \\ neg A \\ vee B,) A ↔ B \u003d (¬ A ∨ B) ∧ (A ∨ ¬ B). (\\ Displaystyle A \\ leftrightarrow B \u003d (\\ neg A \\ vee B) \\ wedge (A \\ vee \\ neg B).)2) Замінити знак заперечення, що відноситься до всього висловом, знаками заперечення, що відносяться до окремих змінним висловлювань на підставі формул:
¬ (A ∨ B) \u003d ¬ A ∧ ¬ B, (\\ displaystyle \\ neg (A \\ vee B) \u003d \\ neg A \\ wedge \\ neg B,) ¬ (A ∧ B) \u003d ¬ A ∨ ¬ B. (\\ Displaystyle \\ neg (A \\ wedge B) \u003d \\ neg A \\ vee \\ neg B.)3) Позбутися від знаків подвійного заперечення.
4) Застосувати, якщо потрібно, до операцій кон'юнкції і диз'юнкції властивості дистрибутивности і формули поглинання.
Приклад побудови КНФ
Наведемо до КНФ формулу
F \u003d (X → Y) ∧ ((¬ Y → Z) → ¬ X). (\\ Displaystyle F \u003d (X \\ rightarrow Y) \\ wedge ((\\ neg Y \\ rightarrow Z) \\ rightarrow \\ neg X).)перетворимо формулу F (\\ displaystyle F) до формули, яка не містить → (\\ displaystyle \\ rightarrow):
F \u003d (¬ X ∨ Y) ∧ (¬ (¬ Y → Z) ∨ ¬ X) \u003d (¬ X ∨ Y) ∧ (¬ (¬ ¬ Y ∨ Z) \u200b\u200b∨ ¬ X). (\\ Displaystyle F \u003d (\\ neg X \\ vee Y) \\ wedge (\\ neg (\\ neg Y \\ rightarrow Z) \\ vee \\ neg X) \u003d (\\ neg X \\ vee Y) \\ wedge (\\ neg (\\ neg \\ В отриманій формулі перенесемо заперечення до змінних і скоротимо подвійні заперечення:F \u003d (¬ X ∨ Y) ∧ ((¬ Y ∧ ¬ Z) ∨ ¬ X). (\\ Displaystyle F \u003d (\\ neg X \\ vee Y) \\ wedge ((\\ neg Y \\ wedge \\ neg Z) \\ vee \\ neg X).)
Наприклад, наступна формула записана в 2-КНФ:(A ∨ B) ∧ (¬ B ∨ C) ∧ (B ∨ ¬ C). (\\ Displaystyle (A \\ lor B) \\ land (\\ neg B \\ lor C) \\ land (B \\ lor \\ neg C).)
Диз'юнктивні і кон'юнктівние нормальні форми алгебри висловлювань.Для кожної функції логіки висловлювань можна скласти таблицю істинності. Зворотній завдання теж завжди можна вирішити. Введемо кілька визначень.елементарних кон'юнкція
(Кон'юнктив) називаються кон'юнкції змінних або їх заперечень, в яких кожна змінна зустрічається не більше одного разу.
диз'юнктивній нормальною формою
(ДНФ) називається формула, що має вигляд диз'юнкції елементарних кон'юнкція. елементарними диз'юнкції
(Диз'юнкт) називаються диз'юнкції змінних з запереченнями або без них. Кон'юнктівной нормальною формою
(КНФ) називається формула, що має вигляд кон'юнкції елементарних диз'юнкцій. Для кожної функції алгебри висловлювань можна знайти безліч діз'юнктівних і кон'юнктивні нормальних форм.
Алгоритм побудови ДНФ:
1. Перейти до булевих операцій, використовуючи формули еквівалентних перетворень.
{!LANG-00a8f0d6f9f2e188291654be3e33481e!}
2. Перейти до формул з тісними запереченнями, тобто до формули, в якій заперечення розташовуються не вище, ніж над змінними - застосувати закони де Моргана.
3. Розкрити дужки - застосувати закони дистрибутивности.
4. Що повторюються складові взяти по одному разу - закон ідемпотентності.
5. Застосувати закони поглинання і полупоглощенія.
Приклад 6.Знайти ДНФ формули:.
В алгебрі Буля справедливий принцип подвійності. Він полягає в наступному.
функція називається двоїстої до функції, якщо. Тобто для знаходження функції, двоїстої до заданої, необхідно побудувати заперечення функції від заперечень аргументів.
Приклад 7.Знайти функцію, двоїсту до.
Серед елементарних функцій алгебри логіки 1 двоїста 0 і навпаки, х двоїста х, двоїста, двоїста і навпаки.
Якщо у формулі F 1 представляє функцію все кон'юнкції замінити
на диз'юнкції, диз'юнкції на кон'юнкції, 1 на 0, 0 на 1, то отримаємо формулу F *, що представляє функцію *, двоїсту.
Кон'юнктивна нормальна форма (КНФ) - подвійне для ДНФ поняття, тому її легко побудувати за схемою:
Приклад 8.Знайти КНФ формули:.
Скориставшись результатом прикладу 6, маємо
Досконала діз'юнктівная і досконала Кон'юнктивна нормальні форми.У кожному з типів нормальних форм (диз'юнктивних і кон'юнктивні) можна виділити клас скоєних форм СДНФ і СКНФ.
Досконалої елементарної кон'юнкція називається логічне твір всіх змінних з запереченням або без них, причому, кожна змінна входить в твір тільки один раз.
Будь-яку ДНФ можна привести до СДНФ розщепленням кон'юнкція, які містять не всі змінні, тобто додаванням для відсутньої змінної x i множиться із застосуванням закону дистрибутивности
Приклад 9.Знайти СДНФ для ДНФ прикладу 6
Досконалої елементарної диз'юнкція називається логічна сума всіх змінних з запереченнями або без них, причому, кожна змінна входить в суму тільки один раз.
Будь-яку КНФ можна привести до СКНФ, додаючи член кон'юнкції, що не містить будь - якої змінної X i кон'юнкція і застосовуючи дистрибутивний закон
Приклад 10.Привести КНФ до СКНФ:
Для побудови СКНФ можна скористатися схемою
Приклад 11.Знайти СКНФ для формули прикладу 6.
Будь-яка функція має СДНФ і, до того ж, єдину. Кожна функція має СКНФ і, до того ж, єдину.
Оскільки СДНФ і СКНФ визначені формулами однозначно, їх можна будувати по таблиці істинності формули.
Для побудови СДНФ необхідно виділити рядки, в яких F приймає значення 1 і записати для них вчинені елементарні кон'юнкції. Якщо значення змінної в потрібному рядку таблиці істинності дорівнює одиниці, то в скоєному Кон'юнктів вона береться без заперечення, якщо нулю - то з запереченням. Потім вчинені Кон'юнктів (їх число дорівнює числу одиниць в таблиці) з'єднуються знаками диз'юнкції.
Для побудови СКНФ по таблиці істинності необхідно виділити в ній рядки, де F \u003d 0, і записати вчинені елементарні диз'юнкції, після чого з'єднати їх знаками кон'юнкції. Якщо в необхідної рядку таблиці істинності (F \u003d 0) значення змінної відповідає нулю, то в скоєному диз'юнкт вона береться без заперечення, якщо одиниці - то з запереченням.
Приклад 12.Знайти СДНФ і СКНФ по таблиці істинності для формули прикладу 6.
У таблиці 14 наведено лише кінцеве значення F \u003d 10101101. У справедливості цього твердження слід переконатися самостійно, побудувавши розгорнуту таблицю істинності.
Таблиця 14
x y z Визначення 1.Кон'юнктивний одночленной (елементарної кон'юнкція) від змінних називається кон'юнкція цих змінних або їх заперечень.
наприклад, - елементарна кон'юнкція.
Визначення 2.Диз'юнктивним одночленной (елементарної диз'юнкція)від змінних називається диз'юнкція цих змінних або їх заперечень.
наприклад, - елементарнаядіз'юнкція.
Визначення 3.Формула, рівносильна даній формулі алгебри висловлювань і є диз'юнкція елементарних кон'юнктивні одночленним, називається диз'юнктивній нормальною формою (ДНФ) цієї формули.
наприклад, - ДНФ.
Визначення 4.Формула, рівносильна даній формулі алгебри висловлювань і є кон'юнкція елементарних діз'юнктівних одночленним, називається кон'юнктівной нормальною формою (КНФ) цієї формули.
наприклад, - КНФ.
Для кожної формули алгебри висловлювань можна знайти безліч діз'юнктівних і кон'юнктивні нормальних форм.
Алгоритм побудови нормальних форм
За допомогою рівносильних алгебри логіки замінити всі наявні в формулі операції основними: кон'юнкція, диз'юнкція, запереченням:
Позбутися від знаків подвійного заперечення.
Застосувати, якщо потрібно, до операцій кон'юнкції і диз'юнкції властивості дистрибутивности і формули поглинання.
2.6. Досконала діз'юнктівная і досконала Кон'юнктивна нормальні форми
Будь-яка булева функція може мати багато уявлень у вигляді ДНФ і КНФ. Особливе місце серед цих уявлень займають вчинені ДНФ (СДНФ) і вчинені КНФ (СКНФ).
Визначення 1. Досконала діз'юнктівная нормальна форма (СДНФ) - це ДНФ, в якій в кожен кон'юнктивний одночлен кожна змінна з наборавходіт рівно один раз, причому входить або сама, або її заперечення.
Конструктивно СДНФ для кожної формули алгебри висловлювань, наведеної до ДНФ, можна визначити наступним чином:
Визначення 2. Досконалої диз'юнктивній нормальною формою(СДНФ) формули алгебри висловлювань називається її ДНФ, що володіє наступними властивостями:
Визначення 3. Досконала кон'юнктивна нормальна форма (СКНФ) - це КНФ, в якій в кожен диз'юнктивний одночлен кожна змінна з наборавходіт рівно один раз, причому входить або сама, або її заперечення.
Конструктивно СКНФ для кожної формули алгебри висловлювань, наведеної до КНФ, можна визначити наступним чином.
Визначення 4. Досконалої кон'юнктівной нормальною формою(СКНФ) даної формули алгебри висловлювань називається така її КНФ, яка задовольняє наступним властивостям.
Теорема 1.Кожна булева функція від змінних, що не є тотожним помилковою, може бути представлена \u200b\u200bв СДНФ, і до того ж єдиним чином.
Способи знаходження СДНФ
1-й спосіб
2-й спосіб
виділяємо рядка, де формула приймає значення 1;
складаємо диз'юнкцію кон'юнкція за умови, що якщо змінна входить в кон'юнкцію зі значенням 1, то записуємо цю змінну, якщо зі значенням 0, то її заперечення. Отримуємо СДНФ.
Теорема 2.Кожна булева функція від змінних, що не є тотожно істинною, може бути представлена \u200b\u200bв СКНФ, і до того ж єдиним чином.
Способи знаходження СКНФ
1-й спосіб - за допомогою рівносильних перетворень:
2-й спосіб - за допомогою таблиць істинності:
виділяємо рядка, де формула приймає значення 0;
складаємо кон'юнкцію диз'юнкцій за умови, що якщо змінна входить в диз'юнкцію зі значенням 0, то записуємо цю змінну, якщо зі значенням 1, то її заперечення. Отримуємо СКНФ.
Приклад 1. Побудуйте КНФ функції.
Рішення
Виключимо зв'язку «» за допомогою законів перетворення змінних:
\u003d / Закони де Моргана і подвійного заперечення / \u003d
/ Дистрибутивні закони / \u003d
Приклад 2. Наведіть до ДНФ формулу.
Рішення
Висловимо логічні операції ічерез, і:
\u003d / Віднесемо заперечення до змінних і скоротимо подвійні заперечення / \u003d
\u003d / Закон дистрибутивности /.
Приклад 3. Запишіть формулу в ДНФ і СДНФ.
Рішення
Використовуючи закони логіки, наведемо цю формулу до вигляду, який містить тільки диз'юнкції елементарних кон'юнкція. Отримана формула і буде шуканої ДНФ:
Для побудови СДНФ складемо таблицю істинності для даної формули:
Помічаємо ті рядки таблиці, в яких формула (останній стовпець) приймає значення 1. Для кожної такого рядка випишемо формулу, справжню на наборі змінних ,, цього рядка:
рядок 1:;
рядок 3:;
рядок 5:.
Диз'юнкція цих трьох формул буде приймати значення 1 тільки на наборах змінних в рядках 1, 3, 5, а отже, і буде шуканої досконалої диз'юнктивній нормальною формою (СДНФ):
Приклад 4. Наведіть формулу до СКНФ двома способами:
а) за допомогою рівносильних перетворень;
б) за допомогою таблиці істинності.
Рішення:
Перетворимо другу елементарну диз'юнкцію:
Формула має вигляд:
б) складемо таблицю істинності для даної формули:
Помічаємо ті рядки таблиці, в яких формула (останній стовпець) приймає значення 0. Для кожної такого рядка випишемо формулу, справжню на наборі змінних ,, цього рядка:
рядок 2:;
рядок 6:.
Кон'юнкція цих двох формул буде приймати значення 0 тільки на наборах змінних в рядках 2 і 6, а отже, і буде шуканої досконалої кон'юнктівной нормальною формою (СКНФ):
Питання і завдання для самостійного рішення
1. За допомогою рівносильних перетворень приведіть до ДНФ формули:
2. За допомогою рівносильних перетворень приведіть до КНФ формули:
3. За допомогою другого дистрибутивного закону перетворіть ДНФ в КНФ:
а)
;4. Перетворіть задані ДНФ в СДНФ:
5. Перетворіть задані КНФ в СКНФ:
6. Для заданих логічних формул побудуйте СДНФ і СКНФ двома способами: за допомогою рівносильних перетворень і за допомогою таблиці істинності.
б)
;простий диз'юнкція (Англ. Inclusive disjunction) або диз'юнкт (Англ. Disjunct) називається диз'юнкція однієї або декількох змінних або їх заперечень, причому кожна змінна зустрічається не більше одного разу.
проста диз'юнкція
- повна, Якщо в неї кожна змінна (або її заперечення) входить рівно один раз;
- монотонна, Якщо вона не містить заперечень змінних.
Кон'юнктивна нормальна форма, КНФ (Англ. Conjunctive normal form, CNF) нормальна форма, в якій булева функція має вигляд кон'юнкції декількох простих диз'юнктів.
Приклад КНФ: $ F (x, y) \u003d (x \\ lor y) \\ land (y \\ lor \\ neg (z)) $
СКНФ
Досконала кон'юнктивна нормальна форма, СКНФ (Англ. Perfect conjunctive normal form, PCNF) - це така КНФ, яка задовольняє умовам:
- в ній немає однакових простих диз'юнкцій
- кожна проста диз'юнкція повна
Приклад СКНФ: $ F (x, y, z) \u003d (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) \u003d \\ bigvee \\ limits_ (f (x ^ (\\ sigma_ (1)), x ^ (\\ sigma_ (2)), ..., x ^ (\\ sigma_ (n ))) \u003d 0) (x_ (1) ^ (\\ sigma_ (1)) \\ wedge x_ (2) ^ (\\ sigma_ (2)) \\ wedge ... \\ wedge x_ (n) ^ (\\ sigma_ (n ))) $, де $ \\ sigma_ (i) $ позначає наявність або відсутність заперечення при $ x_ (i) $
Знайдемо інверсію лівої і правої частини виразу:
$ F (\\ vec x) \u003d \\ neg ((\\ bigvee \\ limits_ (f (x ^ (\\ sigma_ (1)), x ^ (\\ sigma_ (2)), ..., x ^ (\\ sigma_ (n ))) \u003d 0) (x_ (1) ^ (\\ sigma_ (1)) \\ wedge x_ (2) ^ (\\ sigma_ (2)) \\ wedge ... \\ wedge x_ (n) ^ (\\ sigma_ (n ))))) $
Застосовуючи двічі до отриманого в правій частині виразу правило де Моргана, отримуємо: $ f (\\ vec x) \u003d \\ bigwedge \\ limits_ (f (x ^ (\\ sigma_1), x ^ (\\ sigma_2), \\ dots, x ^ (\\ Останній вираз і є СКНФ. Так як СКНФ отримана з СДНФ, яка може бути побудована для будь-якої функції, не рівної тотожному нулю, то теорема доведена.
Алгоритм побудови СКНФ по таблиці істинності
У таблиці істинності відзначаємо ті набори змінних, на яких значення функції дорівнює $ 0 $.
- Для кожного зазначеного набору записуємо диз'юнкцію всіх змінних за таким правилом: якщо значення деякої змінної є $ 0 $, то в диз'юнкцію включаємо саму змінну, інакше її заперечення.
- Всі отримані диз'юнкції пов'язуємо операціями кон'юнкції.
- Приклад побудови СКНФ для медіани
1). У таблиці істинності відзначаємо ті набори змінних, на яких значення функції дорівнює $ 0 $.
x
y $ \\ Langle x, y, z \\ rangle $ z 2). Для кожного зазначеного набору записуємо кон'юнкцію всіх змінних за таким правилом: якщо значення деякої змінної є $ 0 $, то в диз'юнкцію включаємо саму змінну, інакше її заперечення. 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 $ (X \\ lor y \\ lor z) $
y $ \\ Langle x, y, z \\ rangle $ z 2). Для кожного зазначеного набору записуємо кон'юнкцію всіх змінних за таким правилом: якщо значення деякої змінної є $ 0 $, то в диз'юнкцію включаємо саму змінну, інакше її заперечення. 0 0 0 0 $ (X \\ lor y \\ lor \\ neg (z)) $ 0 0 1 0 $ (X \\ lor \\ neg (y) \\ lor z) $ 0 1 0 0 $ (\\ Neg (x) \\ lor y \\ lor z) $ 0 1 1 1 1 0 0 0 3). Всі отримані диз'юнкції пов'язуємо операціями кон'юнкції. 1 0 1 1 1 1 0 1 1 1 1 1 $ \\ Langle x, y, z \\ rangle \u003d (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)) $
Приклади СКНФ для деяких функцій
{!LANG-3a7557f24522228bd8a642f999b91bd8!}
Стрілка Пірса: $ x \\ downarrow y \u003d (\\ neg (x) \\ lor (y)) \\ land ((x) \\ lor \\ neg (y)) \\ land (\\ neg (x) \\ lor \\ neg (y) ) $
Що виключає або: $ x \\ oplus y \\ oplus z \u003d (\\ 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) $
