Мета даного параграфа дати відповідь на одне з основних питань алгебри логіки - питання про необхідний і достатній умовах повноти системи булевих функцій. Відповідь на це питання дає наступна теорема, доказ якої буде вестися за методом А. В. Кузнєцова та
С. К. Яблонського.
Теорема 3 (про повноту) Для того, щоб система булевих функцій Д була повною, необхідно і достатньо, щоб вона цілком не містилася ні в одному з п'яти замкнутих класів T0. T1. S, M, L.
Доказ .Необхідно. Нехай Д - повна система, цілком міститься в одному з класів T0. T1. S, M, L. Без обмеження спільності, будемо вважати, що. Тоді. Отже,. що неможливо.
Достатність. Нехай система булевих функцій Д цілком не міститься ні в одному з класів T0. T1. S, M, L. Тоді в системі Д обов'язково знайдуться такі функції:. Ніколи не зберігати 0; . Ніколи не зберігати 1; НЕ самодвоїстих функція; нелінійна функція; НЕ монотонна функція. З огляду на поняття фіктивної змінної, ми можемо вважати, що ці функції залежать від одних і тих же змінних.
Спочатку побудуємо з системи функцій Д константи 0 і 1.
Розглянемо функцію. Ця функція є суперпозиція функцій і. Так як не належить класу T0. . Якщо тепер g (1) = 1, то - константа 1. Підставляючи константу 1 в функцію. ми отримуємо константу 0, бо.
Нехай тепер. З рівності g (0) = 1 і g (1) = 0 робимо висновок, що. Візьмемо несамодвойственную функцію. Очевидно, що в цьому випадку знайдеться такий набір змінних. що =.
Розглянемо функцію і побудуємо за допомогою операції суперпозиції функцію. Тоді отримуємо:
Отже, h (0) = h (1). А це означає, що h (x) є константа 0 або 1. Так як ми побудували функцію. то суперпозиція цієї функції з однією з констант дає іншу константу. Отже, константи 0 і 1 нами побудовані.
Тепер, використовуючи попередню теорему, ми можемо за допомогою суперпозиції функції і констант 0,1 побудувати функцію. а отже і всі функції. Раніше ми показали, що будь-яка булева функція може бути представлена у вигляді суперпозиції вже побудованих функцій і функцій. Отже, для завершення доведення теореми нам залишилося побудувати функцію. Для цього візьмемо функцію і побудуємо для цієї функції поліном Жегалкина. Так як ця функція нелінійна, то в цьому поліномі знайдеться доданок, що містить не менше двох множників. Без обмеження спільності можна вважати, що цими множителями є і. Тоді ми можемо записати поліном Жегалкина для функції в наступному вигляді:
В силу єдиності полінома, функція не дорівнює тотожно нулю. Виберемо такі значення змінних. що. Зважаючи на це, ми приходимо до функції
де константи 0 або 1. Побудуємо функцію наступним чином:
Отже, теорема про повноту повністю доведена.
У тих завданнях, де потрібно з'ясувати, чи є дана система булевих функцій повною, ми будемо складати таблиці, які називаються таблицями Посту. Дані таблиці мають такий вигляд.
Легко перевірити, що ця функція не належить ні Т0. ні Т1. Так як . а значення функції при наборі (0,0,0) більше, ніж при наборі (1,1,1), то функція не є монотонною. Очевидно, що всі змінні даної функції є суттєвими. А так як дана функція не може збігатися ні с. ні с. то вона нелінійна. Як і в прикладі 6, можна показати, що функція є самодвоїстих. Отже, система Д4 не є повною.
Назвемо систему булевих функцій нескоротного. якщо з неї не можна виключити жодної функції так, щоб залишилася після виключення система знову була повною.
Очевидно, що будь-яку повну систему булевих функцій можна звести до нескоротного. Як випливає з теореми про повноту, в будь-нескоротного повній системі міститься не більше 5 функцій. Наступна теорема показує, що насправді їх число завжди може бути скорочено до 4.
Теорема 4Максімальное можливе число функцій в нескоротного повній системі булевих функцій дорівнює 4.
Дійсно, при доведенні теореми про повноту ми бачили, що з будь-якої повної системи булевих функцій можна виділити повну підсистему, що містить не більше п'яти функцій. Причому, функція. Ніколи не зберігати 0, або не зберігає 1, або якщо є самодвоїстих. Отже, крім цієї функції досить залишити в системі лише три функції: нелінійну, немонотонну або функцію, не зберігає 1, або несамодвойственную функцію.
Наступний приклад показує, що константа 4 не може бути знижена.
Приклад 7 Розглянемо систему функцій.
Складемо таблицю Посту для даної системи:
З таблиці видно, що дана система є повною і нескоротного, бо
Питання для самоконтролю
1 Яка система булевих функцій називається повною?
2 Що називається замиканням безлічі булевих функцій?
3 Який клас булевих функцій називається замкнутим?
4 Дайте визначення п'яти найважливіших замкнутих класів.
5 Сформулюйте теорему про повноту.
6 Сформулюйте алгоритм Посту.
7 Яка система булевих функцій називається нескоротного?
8 Яке максимальне можливе число функцій в нескоротного повній системі булевих функцій?