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

Стандартний базис. Елементарні формули - літерали. Елементарна кон'юнкція (диз'юнкція). Диз'юнктивна (Кон'юнктивна) нормальна форма і досконала форма. Теорема: будь-яка булева функція, відмінна від 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,..., Yn) приймає значення 1 на векторі (t 1,..., Tn ) (такий вектор називають констітуенти одиниці ). Тоді елементарна кон'юнкція також приймає значення 1 на цьому наборі, але звертається в нуль на всіх інших n-мірних бульових векторах. Розглянемо формулу

в якій сума (об'єднання) поширюється на всі ті набори (t 1,..., tn) значень аргументів, на яких задана функція приймає значення 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, хоча обидві форми рівнозначні.

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

енциклопедичний 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 = ¬ A ∨ B, (\ displaystyle A \ rightarrow B = \ neg A \ vee B,) A ↔ B = (¬ A ∨ B) ∧ (A ∨ ¬ B). (\ Displaystyle A \ leftrightarrow B = (\ neg A \ vee B) \ wedge (A \ vee \ neg B).)

2) Замінити знак заперечення, що відноситься до всього висловом, знаками заперечення, що відносяться до окремих змінним висловлювань на підставі формул:

¬ (A ∨ B) = ¬ A ∧ ¬ B, (\ displaystyle \ neg (A \ vee B) = \ neg A \ wedge \ neg B,) ¬ (A ∧ B) = ¬ A ∨ ¬ B. (\ Displaystyle \ neg (A \ wedge B) = \ neg A \ vee \ neg B.)

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

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

Приклад побудови КНФ

Наведемо до КНФ формулу

F = (X → Y) ∧ ((¬ Y → Z) → ¬ X). (\ Displaystyle F = (X \ rightarrow Y) \ wedge ((\ neg Y \ rightarrow Z) \ rightarrow \ neg X).)

перетворимо формулу F (\ displaystyle F)до формули, яка не містить → (\ displaystyle \ rightarrow):

F = (¬ X ∨ Y) ∧ (¬ (¬ Y → Z) ∨ ¬ X) = (¬ X ∨ Y) ∧ (¬ (¬ ¬ Y ∨ Z) ∨ ¬ X). (\ Displaystyle F = (\ neg X \ vee Y) \ wedge (\ neg (\ neg Y \ rightarrow Z) \ vee \ neg X) = (\ neg X \ vee Y) \ wedge (\ neg (\ neg \ neg Y \ vee Z) \ vee \ neg X).)

В отриманій формулі перенесемо заперечення до змінних і скоротимо подвійні заперечення:

F = (¬ X ∨ Y) ∧ ((¬ Y ∧ ¬ Z) ∨ ¬ X). (\ Displaystyle F = (\ 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).)

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

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

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

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

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

простий диз'юнкція(Англ. 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) $

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

~ ~

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

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-куб відповідає сукупність 2 сусідніх клітин, розміщених в рядку, стовпці, квадраті або прямокутнику (з урахуванням сусідства протилежних країв карти). Тому всі положення, викладені в вище (див. П. багатовимірний куб), Справедливі для карт Карно. Так, на рис. 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, б) виражаються наступним чином.