III. Равносильности, выражающие основные законы алгебры логики

II. Равносильности, выражающие одни логические операции через другие.

Основные равносильности.

1. x&xºx(x& x&… &xºx) - законы

2. x v xºx(x v x v… v xº x) идемпотентности.

3. x&1º x.

4. x v1º1.

5. x&0º0.

6. x v0ºx.

7. x &`xº0 – закон противоречия.

8. x v `xº1 – закон исключенного третьего.

9. ˥˥x º x – закон снятия двойного отрицания.

10. x &(y v x) º x - законы

11. x v (y&x) º x поглощения

1. x«yº (x® y)&(у®х).

2. x® yº `x v y.

3. ˥(x& y)º `x v `y. – законы

4.

x v yº `x &`y. де Моргана

5. x& yº ˥(`x v `y).

6. x v yº ˥(`x &`y).

1. x& yº y & x.

2. x v yº y v x.

3. x&(y & z) º(x& y) & z.

4. x v(y v z) º(x v y) v z.

5. x&(y v z) º(x& y) v (x & z).

6. x v(y& z) º(x v y) &(x v z).

Используя равносильности групп I, II, III, можно часть формулы алгебры логики или всю формулу заменить равносильной ей формулой. Такие преобразования называются равносильными. Равносильные преобразования формул применяются для доказательства равносильностей, для приведения формул к заданному виду, для упрощения формул.

Пример 5. Доказать равносильность ˥(x®y)º x & ˥y

Решение. Для доказательства равносильности подвергнем ее левую часть равносильным преобразованиям:

˥(x®y) º ˥(˥x v y) º ˥˥x & ˥y º x & ˥y.

Пример 6. Упростить формулу А º(˥(x v y)® ˥x v y)&y.

Решение. Подвергнем формулу А равносильным преобразованиям:

А º (˥(x v y)® ˥x v y) & y º (˥˥(x v y) v ˥x v y) & yº

º (x v y v ˥x v y) & yº ((x v ˥x) v(y v y)) & yº

º(1 v y)& yº1& yº y.

Пример 7. Доказать, что формула А º x®(y® x) тождественно истинная.

Решение. Подвергнем формулу А равносильным преобразованиям:

А º x®(y® x) º ˥x v(˥y v x) º ˥x v(x v ˥y) º(˥x v x) v ˥yº1 v ˥y º1.