Смекни!
smekni.com

Системи булевих функцій (стр. 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

Функція f1 називається нульовою; f16 - одиничною; f2 - кон'юнкцією; f8 - диз'юнкцією; f11 і f13 - запереченнями Х1 і Х2 відповідно; f12 і f14 - імплікаціями; f3 і f5 - коімплікаціями; f10 - еквівалентцією; f7 - додаванням по модулі дві або розділова диз'юнкції; f9 - стрілки Пірса (функцією Вебба); f15 - штрихом (функцією) Шеффера.

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

є суперпозицією елементарних функцій: заперечення, диз'юнкції, імплікації.

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

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

. Тому справедливо наступну теорему

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

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

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

Відповідно до цього визначення система булевих функцій

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

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

Якщо система

- повна й кожна з функцій f1, f2,.,fm може бути виражена за допомогою суперпозицій через функції g1, g2,…,gk, те система
також повна.

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

.

Для доказу скористаємося системою

, повнота якої вже доведена, ці функції можна виразити через g1 і g2 по формулах:

f1=g1,

,

отже система функцій

є повною.

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

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

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

Функція f (X1,X2,.,Xn) називається самодвоїстої, якщо

f (X1,X2,., Xn) =

.

Функція f (X1,X2,.,Xn) називається монотонної, якщо для будь-яких двох наборів X = (X1,X2,…,Xn) і Y = (Yl, Y2,.,Yn), таких, що X

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

f (X1,X2,., Xn)

f (Yl, Y2,.,Yn).

Функція f (X1,X2,., Xn) називається лінійної, якщо

f (X1,X2,., Xn) =

,

де

.

Перші чотири властивості перевіряються за допомогою таблиці істинності, а для перевірки лінійності функції необхідно побудувати багаточлен Жегалкина. Наприклад, з табл.1 треба, що f2 = X1ÙX2 і f8 = X1ÚX2 - функції, що зберігають константу 0; f10 = X1↔X2 - функція, що не зберігає константу 0, але яка збірегає константу 1; f7 = X1

X2 - функція; f2, fg - монотонні функції; f14 = X1→X2 - немонотонна функція, тому що монотонність порушується (0, 0) і (1, 0); f3 - нелінійна функція, тому що відповідний їй багаточлен Жегалкина X1 + X2 + X1X2 - нелінійна.

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

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

.

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

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


Таблиця 2

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

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