Системи булевих функцій (стр. 1 из 5)

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

Зміст

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

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

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

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

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

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

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

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

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

Нагадаємо, що булевої функцією називають функцію

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

Таблиця 1

№	X1= 0X2= 0	01	10	11	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₁,X₂,., X_n) =

.

Функція f (X₁,X₂,.,X_n) називається монотонної, якщо для будь-яких двох наборів X = (X₁,X₂,…,X_n) і Y = (Y_l, Y₂,.,Y_n), таких, що X

Y (для будь-якого i X_i Y_i) має місце нерівність:

f (X₁,X₂,., X_n)

f (Y_l, Y₂,.,Y_n).

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

f (X₁,X₂,., X_n) =

,

де

.

Перші чотири властивості перевіряються за допомогою таблиці істинності, а для перевірки лінійності функції необхідно побудувати багаточлен Жегалкина. Наприклад, з табл.1 треба, що f₂ = X₁ÙX₂ і f₈ = X₁ÚX₂ - функції, що зберігають константу 0; f₁₀ = X₁↔X₂ - функція, що не зберігає константу 0, але яка збірегає константу 1; f₇ = X₁

X_{2 -} функція; f₂, f_{g -} монотонні функції; f₁₄ = X₁→X_{2 -} немонотонна функція, тому що монотонність порушується (0, 0) і (1, 0); f₃ - нелінійна функція, тому що відповідний їй багаточлен Жегалкина X₁ + X₂ + X₁X₂ - нелінійна.

Теорема Поста. Система D = {f₁, f₂,. f_m} булевих функцій є повною тоді й тільки тоді, коли серед функцій цієї системи існують: функція, що не зберігає константу 0, функція, що не зберігає константу 1, а також нелінійна, й немонотонна функції.

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

.

Рішення. Нехай K₀ - клас функцій, що зберігають константу 0; К₁ - клас функцій, що зберігають константу 1; Кл,K_c, К_м - класи лінійних, самодвоїстих і монотонних функцій відповідно.

Складемо таблицю Поста наступного виду.

Таблиця 2

№	φi	K0	К1	Кл	Kc	Км
1	X1 X2	+	-	+	-	-
2	X1 Ú X2	+	+	-	-	+
3	1	-	+	+	-	-

Знак "+", щокоштує на перетинанні i - й рядка й j-гo стовпця цієї таблиці, показує, що функція φ_i - належить відповідному класу, записаному в j-ом стовпці,