Основные положения дискретной математики

3. БУЛЕВА АЛГЕБРА

Множество В, на котором определены две бинарные операции (конъюнкция и дизъюнкция) и одна унарная операция (отрицание ) и выделены два элемента 0 и 1rc="images/referats/7492/image095.png"> называется булевой алгеброй.

Причем для этих операций необходимо выполнение следующих свойств:

1. Ассоциативность

·

·

2. Коммутативность

·

·

3. Дистрибутивность конъюнкции относительно дизъюнкции

·

4. Дистрибутивность дизъюнкции относительно конъюнкции

·

5. Идемпотентность

·

·

6. Двойное отрицание

·

7. Свойства констант

·

·

·

·

·

·

8. Правила де Моргана

·

·

9. Закон противоречия

·

10. Закон исключенного третьего

·

В алгебре логики эти законы называются равносильностями.

3.1 Совершенные нормальные формы

3.1.1 Совершенная дизъюнктивная нормальная форма

Введем обозначения:

; АА=1; ХА=1, если Х=А, ХА=0, если ХА.

Формула ХА1……ХАn, где А=- какой-либо двоичный набор, а среди переменных Хi могут быть совпадающие называется элементарной конъюнкцией.

Всякая дизъюнкция элементарных конъюнкций называется дизъюнктивной нормальной формой (ДНФ).

Элементарная конъюнкция называется правильной, если в нее каждая переменная входит не более одного раза (включая ее вхождение под знаком отрицания).

Например: 1) (значок конъюнкции в данном случае опущен).

1),4) – правильные элементарные конъюнкции;

2)– переменная х входит один раз сама и второй раз под знаком отрицания;

3) – переменная y входит трижды: один раз сама и два раза под знаком отрицания.

Правильная элементарная конъюнкция называется полной относительно переменных х1… хn, если в нее входит каждая их этих переменных причем только один раз (может быть и пол знаком отрицания).

Например: из перечисленных в предыдущем примере конъюнкций полной является только 4) относительно переменных x,y,z,t; а относительно переменных x,y,z полной является только 1).

Совершенной дизъюнктивной нормальной формой (СДНФ) относительно переменных х1… хn называется дизъюнктивная нормальная форма, в которой нет одинаковых элементарных конъюнкций и все элементарные конъюнкции правильны и полны относительно переменных х1… хn

3.1.2 Разложение по переменным

Теорема 1. Всякая логическая функция может быть представлена в СДНФ:

, (1)

где m, а дизъюнкция берется по всем 2m наборам значений переменных х1,…хm . Функция f разложена по первым n-переменным. Данное равенство называется разложением по переменным. х1,…хm. Например при n=4, m=2 разложение имеет вид:

теорема доказывается подстановкой в обе части равенства (1) произвольного набора (b1,…,bm, bm+1,…,bn) всех n-переменных.

При m = 1 из (1) получаем разложение функции по одной переменной:

(2)

Очевидно, что аналогичное разложение справедливо для любой из n- переменных.

Другой важный случай когда n=m. При этом все переменные в правой части (1) получают фиксированные значения и функции в конъюнкции правой части становятся равными 0 или 1, что дает:

, (3)

где дизъюнкция берется по всем наборам (b1…bn), на которых f=1. При f=0 множество конъюнкций в правой части пусто. Такое разложение называется совершенной дизъюнктивной нормальной формой. СДНФ функции f содержит ровно столько конъюнкций, сколько единиц получается в таблице истинности f. Каждому единичному набору (b1,…, bn) соответствует конъюнкция всех переменных, в которой xi взято с отрицанием, если bi =0 b ,и без отрицания, если, bi=1. Таким образом существует взаимно однозначное соответствие между таблицей истинности функции f и ее СДНФ, и ,следовательно, СДНФ для всякой логической функции единственна. Единственная функция не имеющая СДНФ – это константа 0.

Формулы, содержащие кроме переменных и скобок, только знаки дизъюнкции, конъюнкции и отрицания, называются булевыми формулами.

Теорема 2. Всякая логическая функция может быть представлена в виде булевой формулы.

Действительно, для всякой функции, кроме константы 0, таким представлением может служит ее СДНФ. Константу 0 можно представить булевой формулой:

3.1.3 Алгоритм преобразования формулы в СДНФ

Равенство (3) дает возможность находить СДНФ для функции по ее таблице истинности

Например таблицей задана функция от трех переменных равная 1, если большинство аргументов равно 1.

Таб. 4.

 Скачать реферат