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

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

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

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

1) ; 2);

3) ; 4);

5) ; 6);

7) ; 8);

9) ; 10);

11) ; 12);

13) ;

14) ; 15);

16) ; 17);

18) ; 19).

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

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