Тавтологии

1. (p«q)«[(p®q)Ù(q®p)]

2. (p«q)«(q®p)

3. (p«q)®(p®q)

4. p®p

5. Ø(pÙØp) (закон противоречия)

6. (pÙØp)®q (из противоречия следует все, что угодно)

7. ØØp«p (закон двойного отрицания)

8. pÚØp (закон исключенного третьего: p или не p – третьей возможности нет)

Замечание. 1. Закон противоречия. В соответствии с законом противоречия ни высказывание и его отрицание не могут быть одновременно ми. другими словами, каким бы ни было высказывание А, составное высказывание всегда ложно. В этом легко убедиться, построив таблицу истинности для высказывания .

A
И	Л	Л
Л	И	Л

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

2. Закон исключения третьего Этот закон говорит, что высказывание и его отрицание не могут быть ложными одновременно: либо истинно A, либо истинно . Используя таблицу истинности для определения , постоим частную таблицу истинности для определения :

A
И	Л	И
Л	И	И

Высказывание и его отрицание, соединенные союзом ИЛИ, всегда образуют истинное высказывание. Абсолютно (тождественно) истинное высказывание информативно. (в истории про Буратино народный лекарь Богомол констатировал: «Или пациент жив, или он умер». Очевидно, что независимо от пациента и его действительного состояния, данное высказывание истинно). Аналогично, высказывание «На Марсе есть жизнь или ее там нет» воспринимается как истинное. Тождественно истинные высказывания можно конструировать сколько угодно. При формулировке данного закона предполагалось, что значения истинности высказываний А и противоположны: если A истинно, то ложно, и наоборот. Если высказывание истинно, то возможны только два варианта:

1) если истинно высказывание А, то высказывание ложно;

2) если истинно высказывание , то высказывание А ложно.

Третьего и других вариантов нет. Поэтому закон исключения третьего можно формулировать так: «Либо А, либо , третьего не дано». Если же быть точным, то этому утверждению следует придать такой вид: «Истинно А либо , но не оба вместе»

Задача. Что можно сказать о значении истинности высказывания «Слова Абракадабра нет в этой книге»? Искомое слово находится в самом вопросе, а он напечатан в данной книге. Следовательно, рассматриваемое высказывание ложно. Тогда должно быть истинным его отрицание, т. е. высказывание «Слово Абракадабра есть в этой книге» О каком бы слове x ни шла речь в высказывнии вида «Слово x не содержится в этой книге», самое это высказывание всегда будет ложным. И наоборот, противоположное высказывание «Слово x содержится в этой книге» всегда будет истинным, т. е. тавтологичным. Действительно, достаточно сформулировать высказывание как «Слова Абракадабра нет в этой книге, за исключением данного предложения», чтобы оно стало истинным, если, конечно, это слово и в самом деле далее нигде в тексте не встречается.

9. (pÙp)«p

10. (pÚp)«p

11. p®(q®p) (если p истинно, то p истинно при любом предположении)

12. [p®(q®r)]«[(pÙq)®r]

13 Øp®(p®r) (может быть получено из 12) подстановкой высказывания Øp вместо p, высказывания p вместо q, высказывания q вместо r и с использованием 6))

14 (p®q)Ú(q®p) (следует из истинностной таблицы для импликации. Если p истинно, то второй член дизъюнкции истинен; если p ложно, то первый член дизъюнкции истинен. Следовательно, по крайней мере, один член дизъюнкции истинен)

15. (p®q)«(ØpÚq)

16 (p®q)«(Øq®Øp) (закон контрапозиции. На нем основано косвенное доказательство. Докажем, что q истинно в предположении p. Согласно принципу дедукции это приведет к доказательству истинности высказывания p®q. Вместо этого можно, согласно 16) доказать Øq®Øp. В таком случае предположим Øq, то есть, что q – ложно, и из этого предположения выведем Øp. Таким образом, получим p®q с помощью Øq®Øp).

17 [(p®q)Ù(q®r)]®(p®r) (транзитивность импликации)

18. (p®q)®[(q®r)®(p®r)]

19. (pÚq)«(qÚp) (коммутативность связки Ú)

20. (pÙq)«(qÙp) (коммутативность связки Ù)

21 [(pÚq)Úr]«[pÚ(qÚr)] ö

22 [(pÙq)Ùr]«[pÙ(qÙr)] ý (ассоциативность связок Ú и Ù соответственно. В силу этих законов можно писать:

pÚqÚr вместо (pÚq)Úr и pÚ(qÚr) и pÙqÙr вместо (pÙq)Ùr и (pÙ(qÙr), так как расстановка скобок не влияет на истинностные значения)

23. [(pÚq)Ùr]«[(pÙr)Ú(qÙr)] ö

24 [(pÙq)Úr]«[(pÚr)Ù(qÚr)] ý (законы дистрибутивности)

Замечание. Законы 19)-24) похожи на аналогичные законы для операций над множествами.

25. [Ø(pÚq)]«(ØpÙØq) ö

26. [Ø(pÙq)]«(ØpÚØq)ý (законы обратимости)

27. [(p®r)Ù(q®r)]«[(pÚq)®r] ö

28. [(p®q)Ù(p®r)]«[p®(qÙr)] ý (Эти два закона могут быть доказаны непосредственно или могут быть выведены из законов дистрибутивности посредством закона 15))

29. Ø(p®q)]«(pÙØq) (Следует из 15) и 25))

30. [(p®q)Ù(r®s)]®[(pÙr)®(qÙs)]

31. [(p®q)Ú(r®s)]®[(pÙr)®(qÚs)]