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

приклад.Знайти КНФ формули

~ ~

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

1. = 1. алгоритм ДНФ

2. = 2. алгоритм ДНФ

3. = 3. алгоритм ДНФ

4. = 4. алгоритм ДНФ

5. Опустити тотожно неправдиві доданки, тобто доданки виду

6. Поповнити складові, що залишилися, відсутні змінними

7. Повторити пункт 4.

приклад.Знайти СДНФ формули.

~

Для побудови СКНФ можна скористатися наступною схемою:

приклад.Знайти СДНФ формули.

~

Відомо (теореми 2.11, 2.12), що СДНФ та СКНФ визначені формулою однозначно і, отже, їх можна будувати за таблицею істинності формули.

Схема побудови СДНФ та СКНФ за таблицею істинності наведена нижче, для формули ~ :

			~
			1 0 1 0 1 1 0 1	СДНФ; СКНФ.

2.2. Завдання.

2.2.1 Нижче наведено логічні вирази. Максимально спростіть висловлювання свого варіанту, скориставшись законами логіки Буля. Потім за допомогою таблиць істинності порівняйте ваш спрощений вираз з вихідним.

2.2.2. З'ясувати питання про рівносильність f 1 та f 2 шляхом зведення їх до СДНФ (табл. 1).

2.2.3. Знайти подвійну функцію для f 3 за узагальненим і булевим принципом (табл.1). Порівняти отримані результати.

№	f 1	f 2	f 3

2.3. Контрольні питання.

2.3.1. Дайте визначення висловлювання.

2.3.2. Наведіть основні операції над висловлюванням.

2.3.3. Що таке таблиця істинності?

2.3.4. Скласти таблиці істинності для таких формул:

~ ~ ~ ;

2.3.5. Враховуючи угоди про порядок виконання операцій, опустити «зайві» дужки та знак « » у формулах:

;

2.3.6. Застосовуючи рівносильні перетворення, довести тотожну істинність формул:

2.3.7. Знайти подвійні формули:

)

2.3.8. Привести до досконалої ДНФ (СДНФ) форми такі формули:

~

2.3.9. Привести до досконалої КНФ (СКНФ) форми такі формули:

~

Лабораторна робота №3

Тема:«Мінімізація булевих функцій. Логічні схеми»

Ціль:Набуття практичних навичок роботи з методами мінімізації булевих функцій.

3.1. Теоретичні відомості.

Мінімальні форми

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

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

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

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

Нехай, наприклад, функція задана у досконалій нормальній диз'юнктивній формі:

Групуючи члени та застосовуючи операцію склеювання, маємо .

При іншому способі угруповання отримаємо:

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

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

Багатовимірний куб

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

Рис.3.1 Відображення на тривимірному кубі функції, поданої в СДНФ

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

Мінітерм (-1)-го рангу можна як результат склеювання двох мінітермів -го рангу (конституент одиниці), тобто. , На -мірному кубі це відповідає заміні двох вершин, які відрізняються лише значеннями координати , що з'єднує ці вершини, рубом (кажуть, що ребро покриває інцидентні йому вершини). Таким чином, мінітерм (-1)-го порядку відповідають ребра -мірного куба. Аналогічно встановлюється відповідність мінітермів (-2)-го порядку - граням -мірного куба, кожна з яких покриває чотири вершини (і чотири ребра).

Елементи -мірного куба, що характеризуються вимірами, називають кубами. Так, вершини є 0-кубами, ребра – 1-кубами, грані – 2-кубами тощо. Узагальнюючи наведені міркування, вважатимуться, що мінітерм ()-го рангу в диз'юнктивної нормальної формі функції змінних відображається -кубом, причому кожен -куб покриває всі ті -куби нижчої розмірності, пов'язані з його вершинами. Як приклад на рис. 3.2 дано відображення функції трьох змінних. Тут мінітерми відповідають 1-кубам (), а мінітерм відображається 2-кубом ().

Рис.3.2 Покриття функції

Отже, будь-яка нормальна диз'юнктивна форма відображається на -мірному кубі сукупністю -кубів, які покривають всі вершини, відповідні конституентам одиниці (0-куби). Справедливе і протилежне твердження: якщо деяка сукупність -кубів покриває безліч всіх вершин, відповідних одиничним значенням функції, то диз'юнкція відповідних цим -кубам мінітермів є вираз цієї функції в нормальної диз'юнктивної формі. Говорять, що така сукупність -кубів (або відповідних їм мінітермів) утворює покриття функції.

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

Рис. 3.3 Покриття функції.

ліворуч – ; справа –

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

Рис. 3.4 Відображення функції на чотиривимірному кубі

Карти Карно

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

Рис. 3.5 Карти Карно для двох, трьох та чотирьох змінних

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

Рис. 3.6 Відображення на карті Карно функції чотирьох змінних

(а) та її мінімального покриття (б)

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

Зчитування мінітермів з картки Карно здійснюється за простим правилом. Клітини, що утворюють s-Куб, дають мінітер (n-s)-го рангу, до якого входять ті (n-s)змінні, які зберігають однакові значення на цьому s-кубе, причому значенні 1 відповідають самі змінні, а значення 0 - їх заперечення. Змінні, які не зберігають свої значення на s-кубі, в мінітермі відсутні. Різні способи зчитування призводять до різних уявлень функції у диз'юнктивній нормальній формі (крайня права є мінімальною) (рис. 3.7).

Використання карт Карно вимагає більш простих побудов порівняно з відображенням на n-мірному кубі, особливо у випадку чотирьох змінних. Для відображення функцій п'яти змінних використовується дві карти Карно на чотири змінні, а для функції шести змінних – чотири карти. При подальшому збільшенні кількості змінних карти Карно стають практично непридатними.

Відомі у літературі карти Вейчавідрізняються тільки іншим порядком прямування наборів значень змінних і мають ті ж властивості, що і карти Карно.

Комплекс кубів

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

). 0-куби, відповідні конституентам одиниці, представляються наборами значень змінних, у яких функція дорівнює одиниці. Очевидно, у записі

Рис. 3.8 Комплекс кубів функції трьох змінних ( а) та його символічне уявлення ( б)

Комплекс кубів утворює максимальне покриття функції. Виключаючи з нього всі ті s-куби, які покриваються кубами вищої розмірності, отримуємо покриття, що відповідають тупиковим формам Так, для прикладу, що розглядається (рис. 3.8) маємо тупикове покриття

,

яке відповідає функції . В даному випадку це покриття є мінімальним.

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

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

Мінімізація булевих функцій

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

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

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

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

Наведені визначення ілюструються на рис. 3.9 де скорочене покриття (див. рис. 3.9а, ) і мінімальні покриття (рис. 3.9б) та (див. рис. 3.9, б) виражаються наступним чином.

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

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

кон'юнктивна нормальна форма (КНФ)-- кон'юнкція декількох диз'юнкцій, наприклад, $ \ 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.

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

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

Для будь-якої логічної формули за допомогою тотожних перетворень можна побудувати нескінченно багато рівносильних формул. У алгебрі логіки однією з основних завдань є пошук канонічних форм (тобто формул, побудованих за єдиним правилом, каноном).

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

Серед нормальних форм виділяються досконалі нормальні форми (такі форми, у яких функції записуються єдиним чином).

Досконала диз'юнктивна нормальна форма (СДНФ)

Визначення. Формулу називають елементарною кон'юнкцією, якщо вона утворена кон'юнкцією певної кількості змінних або їх заперечень.

Приклади: y, ¬ y, х 1 ∧ ¬ х 2 ∧ х 3 ∧ х 4

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

ДНФ записується в наступній формі: F 1 ∨ F 2 ∨ ... ∨ F n , де F i - елементарна кон'юнкція

Приклади: ¬ х 1 ∧ х 2 ∨ х 1 ∧ ¬ х 2 ∨ х 1 ∧ ¬ х 2 ∧ х 3 , ¬ y 1 ∨ y 1 ∧ y 2 ∨ ¬ y 2

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

Приклад: (¬ х 1 ∧ х 2 ∧ х 3) ∨ (х 1 ∧ ¬ х 2 ∧ х 3) ∨ (х 1 ∧ х 2 ∧ ¬ х 3)

Досконала кон'юнктивна нормальна форма (СКНФ)

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

Приклади: х 3 , х 1 ∨ х 2 , х 1 ∨ х 2 ∨ х 3

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

КНФ записується в наступній формі: F 1 ∧ F 2 ∧ ... ∧ F n , де F i - елементарна диз'юнкція

Приклади: (х 1 ∨ ¬ х 2) ∧ х 3 , (х 1 ∨ х 2) ∧ (¬ х 1 ∨ х 2 ∨ х 3) ∧ (х 1 ∨ ¬ х 2 ∨ ¬ х 3)

Визначення. Логічна формула від k змінних називається досконалою кон'юнктивною нормальною формою (КДНФ), якщо:
1) формула є КНФ, в якій кожна елементарна диз'юнкція є диз'юнкція k змінних х 1, х 2, …, х k, причому на i-му місці цієї диз'юнкції стоїть або змінна х i, або її заперечення;
2) всі елементарні диз'юнкції у такій КНФ попарно різні.

Приклад: (х 1 ∨ х 2 ∨ х 3) ∧ (¬ х 1 ∨ ¬ х 2 ∨ х 3)

Зауважимо, що будь-яку логічну функцію, не рівну тотожно 0 або 1, можна подати у вигляді СДНФ або СКНФ.

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

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

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

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

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

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

x	y	z	F(x, y, z)
0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	1

Т.к. більшості рядків таблиці істинності значення функції дорівнює 1, то побудуємо СКНФ. В результаті отримаємо наступну логічну формулу:
F = (¬ x ∨ y ∨ z) ∧ (¬ x ∨ y ∨ ¬ z)

Перевіримо отриману формулу. Для цього збудуємо таблицю істинності функції.

x	y	z	¬ x	¬ x ∨ y ∨ z	¬z	¬ x ∨ y ∨ ¬ z	F(x, y, z)
0	0	0	1	1	1	1	1
0	0	1	1	1	0	1	1
0	1	0	1	1	1	1	1
0	1	1	1	1	0	1	1
1	0	0	0	0	1	1	0
1	0	1	0	1	0	0	0
1	1	0	0	1	1	1	1
1	1	1	0	1	0	1	1

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

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

Наприклад, є простою кон'юнкцією,

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

Наприклад, вираз є ДНФ.

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

Наприклад, вираз є ДНФ, але не СДНФ. Вираз є СДНФ.

Аналогічні визначення (із заміною кон'юнкції на диз'юнкцію та навпаки) правильні для КНФ та СКНФ. Наведемо точні формулювання.

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

Кон'юнктивний нормальною формою(КНФ) називається кон'юнкція простих диз'юнкцій(Наприклад вираз - КНФ).

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

Наприклад, вираз є СКНФ.

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

а) перехід від ДНФ до КНФ

Алгоритм цього переходу наступний: ставимо над ДНФ два заперечення та за допомогою правил де Моргана (не чіпаючи верхнього заперечення) наводимо заперечення ДНФ знову до ДНФ. У цьому доводиться розкривати дужки з допомогою правила поглинання (чи правила Блейка). Заперечення (верхнє) отриманої ДНФ (знову за правилом де Моргана) відразу дає нам КНФ:

Зауважимо, що КНФ можна отримати і з первісного виразу, якщо винести уза дужки;

б) перехід від КНФ до ДНФ

Цей перехід здійснюється простим розкриттям дужок (при цьому використовується правило поглинання)

Таким чином отримали ДНФ.

Зворотний перехід (від СДНФ до ДНФ) пов'язаний із проблемою мінімізації ДНФ. Докладніше про це буде розказано в розд. 5, тут ми покажемо, як спростити ДНФ (або СДНФ) за правилом Блейка. Така ДНФ називається скороченоюДНФ;

в) скорочення ДНФ (або СДНФ) за правилу Блійка

Застосування цього правила складається із двох частин:

Якщо серед диз'юнктних доданків у ДНФ є доданки , то до всієї диз'юнкції додаємо доданок До 1 До 2 . Проробляємо цю операцію кілька разів (можна послідовно, можна одночасно) для всіх можливих пар доданків, а потім застосовуємо звичайне поглинання;

Якщо додане доданок вже містилося в ДНФ, його можна відкинути зовсім, наприклад,

або

Зрозуміло, скорочена ДНФ не визначається єдиним чином, але всі вони містять однакову кількість букв (наприклад, є ДНФ , після застосування до неї правила Блейка можна прийти до ДНФ, що дорівнює даній):

в) перехід від ДНФ до СДНФ

Якщо в якійсь простій кон'юнкції немає змінної, наприклад, z, вставляємо в неї вираз ,після чого розкриваємо дужки (при цьому повторювані диз'юнктні доданки не пишемо). Наприклад:

г) перехід від КНФ до СКНФ

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

Таким чином, із КНФ отримано СКНФ.

Зауважимо, що мінімальну чи скорочену КНФ зазвичай одержують із відповідної ДНФ.