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

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

Національний університет “Львівська політехніка”

Інститут комп’ютерних наук та інформаційних технологій

Кафедра автоматизованих систем управління

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

Звіт до лабораторної роботи № 3-4

з дисципліни

“Дискретна математика”

для студентів першого (бакалаврського) рівня вищої освіти

Львів

Лабораторна робота № 3-4

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

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

1. Аналітичне представлення булевих фукцій

1.1 Основні аксіоми та закони булевої алгебри

Нагадаємо основні аксіоми та закони булевої алгебри (в аксіомах x, y, z можуть бути булевими змінними або функціями).

1.

- комутативність

2.

- асоціативність

3.

- ідемпотентність

4.

- властивості констант

5.

0=1

- аксіоми заперечення

6.

- дистрибутивність

7. - закон виключення третього

8. - закон протиріччя

9.

- закони де Моргана

Якщо у формулі декілька однакових по старшинству операцій йдуть один за одним, то вони виконуються зліва направо.

Розглянемо декілька додаткових законів булевої алгебри, які можуть бути доведені з допомогою перелічених вище аксіом і які часто використовуються для еквівалентних перетворень.

1. - поглинання

2. - склеювання

1.2 Нормальні форми булевих функцій

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

Елементарна диз’юнкція – це диз’юнкція визначеної множини змінних або заперечень, де кожна змінна зустрічається не більше одного разу.

Приклад 1.1. , x1

Елементарна кон’юнкція – це кон’юнкція визначеної множини змінних або заперечень, де кожна змінна зустрічається не більше одного разу.

Приклад 1.2. ,

Диз’юнктивною нормальною формою (ДНФ) називається диз’юнкція визначеної множини попарно відмінних елементарних кон’юнкцій.

Приклад 1.3. ,

Аналогічно визначається кон’юнктивна нормальна форма (КНФ), як кон’юнкція визначеної множини попарно відмінних елементарних диз’юнкцій.

Приклад 1.4. ,

В прикладах видно, що є одночасно ДНФ і КНФ.

Для будь-якої функції можна знайти її представлення в ДНФ і КНФ, використовуючи аксіоми та закони алгебри логіки.

Приклад 1.5. Найти ДНФ і КНФ для функції

а)