Эквивалентные преобразования

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

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

Основные свойства булевых операций:

1) ;                                   2) ;

3) ;                   4) ;

5) ;                          6) ;

7) ;                                     8) ;

9) ;                                        10) ;

11) ;                                        12) ;

                                 13) ;

14) ;                                       15) ;

16) ;                                         17) ;

18) ;                                         19) .

Эти свойства проверяются путем подстановки в обе части равенства поочередно всех наборов значений аргументов. С помощью основных свойств булевых операций доказываются следующие законы:

– закон поглощения

1) ;                   2) ;

– закон простого склеивания

;

– закон расщепления

;

– закон обобщенного склеивания

1) ;                   2) .

Основные свойства булевых операций и законы применяются для эквивалентных преобразований одной равносильной формулы в другую.

    Правило получения СДНФ из вектор-столбца

1. Выбрать все единичные наборы значений аргументов.

2. Каждому единичному набору поставить в соответствие элементарную конъюнкцию всех переменных так, чтобы в конъюнкции переменная была с отрицанием, если в наборе она равна 0.

3. Соединить полученные элементарные конъюнкции знаком дизъюнкции.

УПРАЖНЕНИЯ

Повторение

1. Упростить формулу с помощью эквивалентных преобразований. Получить дизъюнктивную нормальную форму (ДНФ). Привести формулу к СДНФ путем расщепления.

1) ;

2) ;

3) .

2. Разложить функцию по переменной х; у; z.

1) ;

2) ;

3) .

3. Упростить формулу с помощью эквивалентных преобразований. Получить дизъюнктивную нормальную форму (ДНФ). Построить СДНФ из вектор-столбца.

1) ;

2) ;

3) ;

4) ;

5) ;

6) ;

7) ;

8) .

4. Привести ДНФ к СДНФ путем расщепления.

1) ;

2) ;

3) ;

4) .

Дизъюнктивные и конъюнктивные нормальные формы

    Правило перехода от ДНФ к КНФ

1. Пусть дана ДНФ F функции f.

.

Здесь  – элементарные конъюнкции.

2. Применим закон двойного отрицания: .

3. Приведем к ДНФ .

Здесь  – элементарные дизъюнкции.

4. Возьмем второе отрицание над F. Во время преобразования не будем раскрывать скобки – остановимся на формуле, имеющей вид конъюнкции элементарных дизъюнкций – КНФ.

Замечание.

    Если при приведении к ДНФ (п. 3) получить СДНФ, то в пункте 4 получится СКНФ функции F.

    Правило получения СКНФ из вектор-столбца

1. Выбрать все нулевые наборы значений аргументов.

2. Каждому нулевому набору поставить в соответствие элементарную дизъюнкцию всех переменных так, чтобы в дизъюнкции переменная была с отрицанием, если в наборе она равна 1.

3. Соединить полученные элементарные дизъюнкции знаком конъюнкции.

УПРАЖНЕНИЯ

Повторение

1. Упростить формулу с помощью эквивалентных преобразований. Получить дизъюнктивную нормальную форму (ДНФ). Привести формулу к СДНФ путем расщепления.

1) ;

2) ;

3) .

2. Разложить функцию по переменной х; у; z.

1) ;

2) ;

3) .

3. Перейти от ДНФ  к конъюнктивной нормальной форме (КНФ). Построить СКНФ (совершенную конъюнктивную нормальную форму) путем расщепления.

1) ;

2) ;

3) ;

4) ;

5) ;

6) .

4. Построить СКНФ с помощью вектор-столбца.

1) ;

2) ;

3) ;

4) .

Дизъюнктивные нормальные формы и импликанты

Функция f имплицирует функцию g, если .

Замечание: Если , то .

Если f имплицирует g, и f представлена единственной элементарной конъюнкцией, то f называется импликантом g.

Если из импликанта нельзя удалить ни одной переменной, то оно называется простым импликантом.