Вопр. Равносильные преобразования формул

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

x₁Vx₂ и (x₁&x₂)

реализуют одну функцию – штрих Шеффера.

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

Равносильность формул A и B будем обозначать следующтм образом: A  B.

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

29 вопрос.Осн.равносильности Булевых формул. Коммутативность. Ассоциативность. Дистрибутивность.

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

а) A&B B&A (для конъюнкции);

б) AVB  BVA (для дизъюнкции).

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

а) A&(B&C)  (A&C)&C (для конъюнкции);

б) AV(BVC)  (AVB)VC (для дизъюнкции).

3. Дистрибутивность.

а) A&(BVC)  A&BVA&C (для конъюнкции относительно дизъюнкции);

б) AV(B&C)  (AVB)&(AVC) (для дизъюнкции относительно конъюнкции).

30 вопр.Осн.равносильности булевых формул.Закон де-моргана, Идемпотентность

4. Закон де Моргана.

а) (A&B)AVB (отрицание конъюнкции есть дизъюнкция отрицаний);

б) (AVB) A&B (отрицание дизъюнкции есть конъюнкция отрицаний).

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

а) A&A  A (для конъюнкции);

б) AVA  A (для дизъюнкции).