0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1

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

1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1

1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1

g0 – функція тотожньо нуль. g1 – кон’юнкція. g2 – заперечення імплікації.

g3 – функція, що приймає значення першого аргументу.

g4 – заперечення антиімплікації.

g5 – функція, яка приймає значення другої змінної.

g6 – сумування за модулем 2. g7 – диз’юнкція. g8 – стрілка Персона.

g9 – еквівалентність. g10 – заперечення другого аргументу. g11 – антиімплікація.

g12 – заперечення першого аргументу. g13 – імплікація. g14 – штрих Шеффера.

g15 – тотожньо одиниця.

Для булевих функцій характерні наступні закони: закон ідемпотентності, комутативності, асоціативності, дистрибутивності, закон поглинання і закон де Моргана.

Деякі додаткові тотожності:

Булеві функції від n аргументів.

Булевою функцією від n аргументів називається функція, яка задана на множині і приймає значення на множині .

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

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

Отримана функція залежить від аргументів.

Теорема: Кількість різних булевих функцій від n аргументів дорівнює .

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

Вираження булевих функцій через кон’юнкцію, диз’юнкцію і заперечення.

Теорема: Будь-яку булеву функцію від n аргументів можна подати у вигляді суперпозиції кон’юнкції, диз’юнкції і заперечення, при чому заперечення стоїть біля змінної, а не біля внутрішніх дужок.

Системи булевих функцій. Повнота системи. Спеціальні класи булевих функцій

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

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

1) 2) 3) 4) 5) 6) 7)

Доведення.

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

2) Виразимо дію через кон’юнкцію і + (сумування за модулем два): Попередня система була повною , але ми замість операції можемо поставити . Це і доводить, що система є повною.

3) Оскільки система є повною: ,

4) Виразимо через : , тобто система є повною.

5) Оскільки система є повною, виразимо через : . 6) У повній системі виразимо кожну цю операцію через | : , . Отже, система є повною.

7) У повній системі виразимо кожну через : , . Що і доводить повноту системи .Доведено.

Спеціальні класи булевих функцій.

Говорять, що функція зберігає нуль, якщо . Клас функцій, що зберігають нуль позначається P0.

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

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

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

Введемо відношення порядку у множині вважаючи, що 00, 01, 11.

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

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

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

Теорема. Класи P0, P1, S, M є власними, замкнутими.

Теорема. Система булевих функцій є повною тоді і тільки тоді, якщо система має функцію, яка не належить P0, і система не належить P1 і S, M.

Типові пристрої ЕОМ. Двійковий суматор. Однорозрядний двійковий суматор. Шифратор і дешифратор.

Нехай - елементи в схемі, тоді всій релейно-контактній схемі ставиться у відповідність булева функція , яку ще називають функцією провідності. Якщо при деякому наборі через схему проходить електричний струм, то булевій функції ставлять у відповідність 1, якщо струм не проходить – 0. В послідовному з’єднанні елементів в схемі відповідає , а паралельному - .

Двійковий суматор

Всі числа в ЕОМ зберігаються у двійковій системі числення у пам’яті порозрядно. Додавання у двійковій системі числення здійснюється за правилами: 0+0=0, 0+1=1, 1+0=1, 1+1=10.

Згідно даних правил додавання здійснюється методом додавання відповідних розрядів. Коли відбувається переповнення розряду (1+1) елемент переноситься у наступний розряд, тобто процес додавання характеризується двома функціями: S(x,y), P(x,y).

S(x,y) – являє собою додавання елементів в одному розряді і запис результату в тому ж розряді.

P(x,y) – це перенос елементу з одного розряду в інший.

Для даних функцій побудуємо таблицю істинності:

x | y | S(x,y) | P(x,y)

0 | 0 | 0 | 0

0 | 1 | 1 | 0

1 | 0 | 1 | 0

1 | 1 | 0 | 1

За даними з таблиці істинності побудуємо досконалу диз’юнктивну нормальну форму:

Однорозрядний двійковий суматор

При додаванні двох елементів у першому розряді ми додаємо елементи порозрядно, і тільки в деяких