Логика для всех / Учебные материалы

Некоторые формулы и законы логики высказываний

1. a & b == b & a - коммутативность конъюнкции
2. a v b == b v a - коммутативность дизъюнкции
3. a & (b & c) == (a & b) & c - ассоциативность конъюнкции
4. a v (b v c) == (a v b) v c - ассоциативность дизъюнкции
5. a & (b v c) == (a & b) v (a & c) - дистрибутивность конъюнкции относительно дизъюнкции
6. a v (b & c) == (a v b) & (a v c) - дистрибутивность дизъюнкции относительно конъюнкции

Все формулы, за исключением последней, при замене "&" на знак умножения и "v" на знак сложения превращаются в знакомые арифметические формулы перестановки, сочетания и распределения.

А кроме того действует так называемый принцип двойственности (свойство симметрии): при замене всех "и" на "или", всех "или" на "и" и всех "1" на "0", а всех "0" на "1" формула останется верной.

1. ~~a == a - закон снятия двойного отрицания

здесь, думаю, все ясно.

2. a & a == a - закон идемпотентности

1 & 1 == 1, 0 v 0 == 0

3. a v a == a - закон идемпотентности

1 v 1 == 1, 0 v 0 == 0

4. a & 0 == 0

ложь, помноженная на "все, что угодно" - ложь.

5. a & 1 == a

"все, что угодно" и истина - "все, что угодно".

6. a v 0 == a

ложь или "все, что угодно" - "все, что угодно".

7. a v 1 == 1

истина или "все, что угодно" - истина.

8. a & ~a == 0 - закон противоречия

одно из двух: если одно истинно, то другое ложно.

9. a v ~a == 1 - закон исключенного третьего

а или не а, третьего не дано.

10. ~(a & b) == ~a v ~b - закон Де Моргана
11. ~(a v b) == ~a & ~b - закон Де Моргана
12. a & b == ~(~a v ~b) - закон Де Моргана
13. a v b == ~(~a & ~b) - закон Де Моргана
14. a => b == ~a v b - выражение импликации через отрицание и дизъюнкцию
15. a <=> b == (a => b) & (b => a)

10-15 легко проверить, построив таблицы истинности для левой части выражения и правой.

16. a & (b v a) == a - закон поглощения

a(b + a) = ab + aa = ab + a = a(b + 1) = a 1 = a

17. a v (b & a) == a - закон поглощения

a + ba = a (1 + b) = a

18. a & (~a v b) == a & b

a(~a + b) = a~a + ab = 0 + ab = ab

19. a v (~a & b) == a v b

(!) a + ~ab = (a + ~a)(a + b) = 1(a + b) = a + b

20. (a & b) v (a & ~b) == a - закон склеивания

ab + a ~b = a (b + ~b) = a 1 = a

21. (a v b) & (a v ~b) == a - закон склеивания

(a + b)(a + ~b) = aa + ab + a ~b + b ~b = a + a(b + ~b) + 0 = a

Здесь и далее для облегчения воспроизведения формул знак дизъюнкции "v" заменен на "+", а знак конъюнкции "&" опущен (запись "a b" следует понимать как "a и b").

И несколько примеров использования формул. Если вы внимательно их просмотрите, а еще лучше возьмете бумагу, ручку и прорешаете (заодно и проверите, не ошиблась ли я где-нибудь, выписывая все эти "крестики-нолики"), то многие формулы станут понятнее и ближе.

 (a + c)(a + ~c)(~b + c) = (a + ~cc)(~b + c) =

= (a + 0)(~b + c) = a(~b + c)

 ~a ~b + a ~b + ab + bc = ~a ~b + a ~b + a ~b + ab + bc =

= ~b(~a + a) + a(~b + b) + bc = ~b + a + bc =

= a + ~b + bc

 ab + bc + ~ac = ab + bc(a + ~a) + ~ac =

= ab + bca + bc~a + ~ac = ab + abc + ~acb + ~ac =

= ab(1 + c) + ~ac(b + 1) = ab + ~ac

 ~((~a ~b + c)~ad) = ~(~a ~b + c) + ~~a + ~d =

= ~(~a ~b)~c + a + ~d = (~~a + ~~b)~c + a + ~d =

= a + (a + b)~c + ~d = a + a ~c + b ~c + ~d = a + b ~c + ~d

x + y(x + ~y) = x + yx + y ~y = x(1 + y) + 0 = x

~x ~(~y + x) = ~x(~~y ~x) = ~x y

 ~(x (~x ~y))= ~x + ~(~x ~y)= ~x + ~~x + ~~y =

= ~x + x + y = 1 + y = 1

~(x + ~(~x ~y)) = ~x ~~(~x ~y) = ~x ~x ~y = ~x ~y = ~(x+y)

или

~(x + ~(~x ~y)) = ~(x + ~~x + ~~y) = ~(x + x + y) = ~(x + y) = ~x ~y

~x + ~(x y ~y) = ~x + ~(x 0) = ~x + ~0 = ~x + 1 = 1

~(~x ~y) + ~x = ~~x + ~~y + ~x = x + y + ~x = 1 + y = 1