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

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

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

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

1) ; 2) ;

3) ; 4) ;

5) ; 6) ;

7) ; 8) ;

9) ; 10) ;

11) ; 12) ;

13) ;

14) ; 15) ;

16) ; 17) ;

18) ; 19) .

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

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

1) ; 2) ;

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

;

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

;

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

1) ; 2) .

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