Системи булевих функцій

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

Зміст

1. Повні системи булевих функцій

2. Скорочені й тупикові диз'юнктивні нормальні форми

3. Алгоритм Квайна й Мак-Класки мінімізації булевої функції

4. Геометричне подання логічних функцій

5. Геометричний метод мінімізації булевої функції

6. Мінімізація булевої функції за допомогою карти Карно

7. Побудова оптимальних контактно-релейних схем

Бібліографічний список

1. Повні системи булевих функцій

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

Таблиця 1

№	X1 = 0 X2 = 0	0 1	1 0	1 1	fk (X1 , X2 )
0	0	0	0	f1 = 0
0	0	0	1
0	0	1	0
0	0	1	1
0	1	0	0
0	1	0	1
0	1	1	0
0	1	1	1
1	0	0	0
1	0	0	1
1	0	1	0
1	0	1	1
1	1	0	0
1	1	0	1
1	1	1	0
1	1	1	1

Функція f₁ називається нульовою; f_{16 -} одиничною; f₂ - кон'юнкцією; f₈ - диз'юнкцією; f₁₁ і f₁₃ - запереченнями Х₁ і Х₂ відповідно; f₁₂ і f₁₄ - імплікаціями; f₃ і f₅ - коімплікаціями; f₁₀ - еквівалентцією; f₇ - додаванням по модулі дві або розділова диз'юнкції; f₉ - стрілки Пірса (функцією Вебба); f₁₅ - штрихом (функцією) Шеффера.

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

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

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

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

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

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

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

Для перевірки повноти заданої системи булевих функцій може бути використане наступне очевидне твердження:

Якщо система - повна й кожна з функцій f₁ , f₂ ,.,f_m може бути виражена за допомогою суперпозицій через функції g₁ , g₂ ,…,g_k , те система також повна.

Приклад 1 . Довести повноту системи .

Для доказу скористаємося системою , повнота якої вже доведена, ці функції можна виразити через g₁ і g₂ по формулах:

f₁ =g₁ , ,

отже система функцій є повною.

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

Функція f = (Х₁ , Х₂ ,., Х_n ) називається функцією, що зберігає константу 0 (1), якщо

f (0,0,.0) = 0, (f (l, 1.1) = 1).

Функція f (X₁ ,X₂ ,.,X_n ) називається самодвоїстої, якщо

f (X₁