Теорема Поста.

Для того, щоб система булевих функцій Q була функціонально повною, необхідно і достатньо, щоб вона містила 1) функцію, яка не зберігає 0; 2) функцію, яка не зберігає 1; 3) несамодвоїсту функцію; 4) немонотонну функцію; 5) нелінійну функцію. Інакше кажучи, для повноти системи Q необхідно і достатньо, щоб для кожного з п`яти замкнених класів T­₀, T₁, S, M, L вона містила функцію, яка цьому класу не належить.

Д. Необхідність випливає з того, що класи T₀, T₁, S, M, L замкнені.

Достатність. Уведемо для функцій із системи Q такі позначення:

f_i – функція, що не зберігає 0

f_j – функція, що не зберігає 1

f_k – несамодвоїста функція

f_m – немонотонна функція

f_l – нелінійна функція.

Перший етап: Одержимо константи 0 і 1. Розглянемо функцію f_i (не зберігає 0): f_i (0..0) = 1. Можливі два випадки:

1. f_i(1…1)= 1, тоді функція ϕ (x)=f(x, …, x) тотожно дорівнює 1, бо ϕ (0)=f_i(0…0)=1, ϕ (1)=f_i(1….1)=1. Із функції f у цьому разі можна отримати константу 0, оскільки f_i(ϕ (x)…..ϕ (x))=f_i(1….1)=0.

2. f_i(1…1)=0, тоді функція ϕ (x)=f_i(x, …., x) – заперечення: ϕ (x)= ˥ x, бо ϕ (0)=f_i(0…0)=1, ϕ (1)=f_i(1..1)=0. Із несамодвоїстої функції f_k та побудованої функції ˥ х за лемою про несамодвоїсту функцію одержимо константу. Другу константу отримаємо, використавши ˥ х, оскільки ˥ 0=1, ˥ 1=0.

Отже в обох випадках ми одержали константи 0 і 1.

Другий етап: Використовуючи константи 0 і 1 та немонотонну функцію f_m, за лемою про немонотонну функцію одержимо˥ х. Потім за допомогою констант 0, 1 функцій ˥ х і f_i не належить L за лемою про нелінійну функцію отримаємо кон. двох змінних ху. Отже, через функції системи Q ми виразили ˥ х та ху. Позаяк система {˥ x, xy} повна, то система Q також повна.

Щоб перевірити, чи виконуються для скінченної системи функцій {f₁….f_q} умови теореми Поста, складають таблицю Поста. ЇЇ рядки позначають функціями системи, а стовпці – назвами 5 основних замкнених класів. У клітках таблиці Поста ставлять знак «+» або «-» залежно від того, чи належить функція відповідному замкненому класу. Для повноти системи функцій необхідно і достатньо, щоб у кожному стовпці таблиці Поста стояв хоча б один знак «-».

37. Постановка задачі мінімізації булевих функцій.

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

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

Елементарну кон. k називають простою імплікантою булевої функції f, якщо k – імпліканта функції f, а елементарна кон. одержана з k вилученням довільної букви, - не імпліканта. ДНФ, що складається з усіх простих імплікант булевої функції, називають СДНФ цієї функції.

Т. СДНФ D_скор булевої функції f задає цю функцію, тобто f=D_скор­.

Т. Мінімальну ДНФ булевої функції f можна одержати з її СДНФ вилученням деяких елмент. кон`юнкцій.

Д. Потрібно довести, що мінімальна ДНФ D_мін довільної булевої функції f являє собою диз. Її простих імплікант. Припустимо, що імпліканта k₁ із D_мін не проста. Тоді із k₁ можна вилучити хоча б одну букву так, щоб отримана елементарна кон. k₂ також була імплікантою функції f. Окрім того, імпліканта k_2­ набуває значення 1 на всіх тих наборах, на яких набуває значення1 імпліканта k₁. Отже у ДНФ D_мін імпліканту k₁ можна замінити на k₂ й отримати ДНФ D_*, яка також подає функцію f. За побудовою D_* має менше букв ніж D_мін. Одержали суперечність.

ДНФ D_туп, яка подає функцію f називають тупиковою ДНФ цієї функції якщо:

1) кожна елементарна кон з D_туп – проста імпліканта функції f.

2) вилучення з формули D_туп, довільного диз. члена призводить до ДНФ D_1* яка не подає f, тобто f≠ D

Т. Мінімальна ДНФ булевої функції являє собою її тупикову ДНФ.

38. Методи Квайна та Мак-Класкі.

У методі Квайна до ДДНФ мулевої функції послідовно застосовують такі рівносильності:

Неповне склеювання: ku v ku = k v ku v ku

Поглинання: ku v k = k

k – елементарна кон’юнкція, u – змінна. Склеювання називається неповним, оскільки ku та ku залишаються у правій частині.

Алгоритм Куайна.

Крок 1. Булеву функцію f(x₁, …, x_n), яку потрібно мінімізувати, записати у ДДНФ, позначити її f₀. Виконати і: =0.

Крок 2. Якщо до ДНФ f_i не можна застосувати жодного неповного склеювання, то зупинитись: f_i – СДНФ. Інакше на однові ДНФ f_i побудувати ДНФ f_i+1 за таким правилом: у формі f_i виконати всі неповні склеювання, які можна застосувати до елементарних кон’юнкції рангу n-i, після цього вилучити всі елементарні кон’юнкції рангу n-i, до яких можна застосувати поглинання.

Крок 3. Виконати і: =і+1 і перейти до кроку 2.

Отже в алгоритмі Куайна, починаючи з ДДНФ f₀, будують послідовність ДНФ f0, f1, f₂, …, доти, доки не отримають СДНФ.

Алгоритм Куайна обґрунтує така теорема – для будь-якої мулевої функції f результатом застосування алгоритму Куайна до ДДНФ цієї функції є СДНФ функції f.

Алгоритм Мак-Класкі.

Крок 1. Булеву функцію, яку потрібно мінімізувати, записати у досконалій ДНФ.

Крок 2. Упорядкувати змінні та записати їх у кожній елементарній кон’юнкції у вибраному порядку. Після цього зобразити кожну кожну елементарну кон’юнкцію послідовністю з 0, 1, -. На і-тій позиції записати 1, якщо і-та змінна входить до елементарної кон’юнкції без заперечення, 0, якщо входить з запереченням, і риску якщо зовсім не входить.

Крок 3. Розбити двійкові вирази, які відповідають елементарним кон’юнкціям, на класи за кількістю одиниць, і розташувати списки цих класів у порядку зростання к-сті одиниць.

Крок 4. Виконати всі можливі склеювання. Склеювання можна застосовувати лише до елементів списку, які містяться у сусідніх класах. Елементи, які склеюють, знаходять у сусідніх класах за простим порівнянням: ці елементи повинні відрізнятись точно в 1 позиції і в цій позиції не повинна бути риска (-).

39. Імплікантна таблиці Квайна. Метод Петрика відбору тупікових ДНФ.

На другому етапі мінімізації знаходять всі тупікові ДНФ, із яких і вибирають мінімальні ДНФ. Основним апаратом для виконання другого етапу є імплікантна таблиця булевої функції. Імплікантною таблицею булевої функції є прямокутна таблиця, рядки якої позначено різними простими імплікантами функції f, а стовпці – наборами значень змінних (або відповідними їм конституантами 1), на яких функція приймає значення 1. Якщо деяка просто імпліканта k_p перетворюється на 1 в наборі aⁿ, який позначає деякий стовпчик імплікантної таблиці, то на перетині рядка позначеного k_p, і стовпчика, позначеного набором aⁿ, ставлять зірочку. У такому випадку кажуть, що проста імпліканта накриває одиницю булевої функції.

Метод Петрика:

Крок 1. Прості імпліканти позначають великими латинськими буквами.

Крок 2. До кожного стовпця імплікантної таблиці будують диз’юнкцію букв, які відповідають рядкам із зірочками у цьому стовпці.

Крок 3. Записують кон’юнкцію отриманих диз’юнкцій. Його називають кон’юктивним зображенням імплікантної таблиці.

Крок 4. В одержаному на кроці 3 кон’юктивному зображенні імплікантної таблиці відкривають дужки за дистрибутивним законом. Знайдений вираз називають диз’юктивним зображенням імплікантної таблиці.

Крок 5. До отриманого на кроці 4 диз’юктивного зображення імплікантної таблиці застосовують всі можливі поглинання A v AB = A та усувають всі повтореня АА = А, A v A = A. Одержаний вираз називають зведеним диз’юктивним зображенням імплікантної таблиці. Можна застосовувати всі закони булевої алгебри, які не містять заперечень для отримання звичайного диз’юктивного зображення.

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