Класи булевих функцій. Теорема про повноту

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

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

Будь-яку повну систему функцій називають базисом.

Виходячи з визначення ДДНФ, ДКНФ, ДПНФ, до ФПСБФ слід віднести системи: . Природним є питання про те, які властивості повинні мати функції, які утворюють ФПСБФ. Розв’язання цієї задачі базується на понятті замикання відносно операції суперпозиції класу функцій.

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

Таким чином, з попереднього випливає, якщо через P₂ позначити множину всіх булевих функцій, то [{Ù, Ú, Ø}] = [{Å, Ù, 1}] = P₂.

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

Означення. Множина функцій S називається передповним класомалгебри А, якщо [S]¹F і для будь-якої функції f з множини F\S набір SÈ{f} є повним: [SÈ{f}]=F.

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

Коротко розглянемо кожний із п’яти перед повних класів.

Клас функцій, які зберігають нуль ( ). Якщо функція на нульовому наборі дорівнює нулю, то кажуть, що функція зберігає нуль: .

До функцій, що зберігають нуль відносяться диз’юнкція і кон’юнкція: . До функцій, що не зберігають нуль відносяться заперечення і еквівалентність: .

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

До функцій, що зберігають одиницю відносяться диз’юнкція і кон’юнкція: . До функцій, що не зберігають одиницю відносяться заперечення і еквівалентність: .

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

До само двоїстих функцій з класу елементарних функцій відносяться та .

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

.

Теорема. Для будь-якої булевої функції існує єдиний поліном Жегалкіна.

До лінійних функцій відносяться: , , .

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

Між наборами α і β має місце зростання у тому і лише в тому випадку, якщо має місце не спадання для всіх компонентів цих наборів і, принаймні, для одної компоненти має місце відношення строгого зростання, наприклад:

.

Приклади наборів, які не задовольняють умові зростання:

.

Приклади немонотонних функцій: , . Справді: ; , .

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

Таблиця 14

Функція		Класи
					+	–	–	+	+
					+	+	–	–	+
					+	–	–	–	–
					+	+	+	+	+
					+	–	–	–	–
					+	+	+	+
					+	–	–	+	–
					+	+	–	–	+
					–	–	–	–	–
					–	+	–	+	–
					–	–	+	+	–
					–	+	–	–	–
					–	–	+	+	–
					–	+	–	–	–
					–	–	–	–	–
					–	+	–	+	+
			–	–	–	–	+	+	–

Для елементарних функцій від однієї і двох змінних розбиття на класи наведено в табл. 14, де знак + означає належність до класу.

Наведемо без доведення два формулювання теореми про функціональну повноту (Теореми Поста).

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

Теорема 2. Система булевих функцій є функціонально повною тоді і тільки тоді, коли вона повністю не міститься ні в одному з передповних класів.

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

– базис 1 – функції (“ І ”, “АБО”, “НЕ”);

– базис 2 – функції (“ І ”, “НЕ”);

– базис 3 – функції (“АБО”, “НЕ”);

– базис 4 – функція Шеффера /;

– базис 5 – функція Пірса ¯;

– базис 6 – функції (“І ”, “додавання за модулем 2”, “1”);

– базис 7 – функції (“АБО”, “додавання за модулем 2”, “1”.

Наведені приклади показують, що базиси можуть бути надлишкові (базис 1) і мінімальними (базиси 4 і 5).

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

Базис 1 є надлишковим, оскільки можливе вилучення однієї з функцій Ù або Ú.

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

Що стосується базисів 6 і 7, то вони є мінімальними. Зменшити кількість функцій в цих базисах не можна.

Найпоширенішою є система з трьох функцій – І, АБО, НЕ.

Приклад 10. Визначити за допомогою теореми Поста, чи є система функцій функціонально повною?

Розв’язання. Як відомо, заперечення зображається поліномом Жегалкіна: , отже функція заперечення лінійна.

За таблицею істинності (табл. 15) визначаємо, що функція заперечення самодвоїста, не зберігає 0, не зберігає 1, немонотонна.

Подамо функцію ”→” у вигляді полінома Жегалкіна. За таблицею іс

тинності (табл. 16) запишемо її ДДНФ і виконаємо наступні перетворення:

.

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

Результати проведених досліджень наведено в табл. 17. Як бачимо, в кожному стовпчику присутній знак ”–”. Отже, для кожного класу Поста в даній системі функцій є принаймні одна функція, яка цьому класу Поста не належить. За теоремою Поста така система функцій є функціонально повною.

Таблиця 15 Таблиця 16 Таблиця 17

	x		x y x→y		x – – + + – x→y – + – – –

Вправи для самостійної роботи

1. Знайти двоїсті формули до таких функцій:

а) , б) , в) .

2) Визначити чи є наступні функції само двоїстими:

а) , б) , в) .

3. Спочатку, за допомогою законів булевої алгебри, спростити нижче наведені вирази, а потім за допомогою таблиць істинності порівняти одержані вирази з вихідними:

а) , б) ,

в) , г) .