В качестве примера преобразования формулы логики высказываний с использованием некоторых перечисленных законов приведем преобразование формулы pq r в формулу p¬r ¬q. Расположим это преобразование в виде так называемой цепочки действий, причем после каждого звена в скобках будет указываться номер закона, согласно которому данное звено справедливо.
pq r ≡ ¬(pq) r (18) ≡ (¬p ¬q) r (16) ≡ (¬p r) ¬q
(3; 5) ≡ ¬ (p¬r) ¬q (1; 16) ≡ p¬r ¬q, что и требовалось доказать.
§ 6. Тождественно истинные формулы
Формулы логики высказываний разбиваются на три класса в зависимости от принимаемых этими формулами значений.
1.Формулы, принимающие значение И при всех наборах значений входящих в них переменных, называются тождественно истинными.
2.Формулы, принимающие значения Л при всех наборах значений входящих в них переменных, называются тождественно ложными (их отрицания — тождественно истинные).
3.Формулы, принимающие при некоторых наборах значений переменных значение И, при других — значение Л, называются выполнимыми.
Тождественно истинные формулы выражают законы логики, на которых основаны наши рассуждения.
Предложение «ϕ — тождественно истинная формула» обозна-
чим◊(ϕ).
Докажем, что если формулы ϕ1 и ϕ2 равносильны, то формула ϕ1 ϕ2 тождественно истинна, и обратно, если ◊(ϕ1 ϕ2 ), то
ϕ1 ≡ϕ2 .
В самом деле, если ϕ1 ≡ϕ2 , то формулы ϕ1 и ϕ2 при любом наборе значений входящих в них переменных принимают обе или значение И, или значение Л, а в этом случае формула ϕ1 ϕ2 , со-
— 27 —
гласно определению эквиваленции, принимает только значение И, т. е. ◊(ϕ1 ϕ2 ). Обратно, пусть ◊(ϕ1 ϕ2 ). Это значит, что ϕ1 и ϕ2 принимают при любом наборе значений входящих в них переменных обе значение И, или обе значение Л, т. е. ϕ1 ≡ϕ2 .
Теперь можно утверждать, что каждая из равносильностей 1-19 (§ 5) порождает тождественно истинную формулу, достаточно только заменить знак равносильности ≡ на знак эквиваленции .
Еще несколько важных тождественно истинных формул:
1)(p q)(r q) (p r q);
2)pq p;
3)(p q)(p r) (p qr);
4)(p q)p q;
5)(p q)¬q ¬p;
6)p q ¬q ¬p (закон контрапозиции);
7)pq r p¬r ¬q (закон расширенной контрапозиции);
8)p (q r) pq r;
9)(p q) ¬p q;
10)(p q¬q) ¬p;
11)(p q)(q r) (p r) (закон силлогизма).
Конечно, это не полный перечень тождественно истинных формул (такого перечня вообще не существует!). Каждая из тождественно истинных формул порождает новые тождественно истинные формулы в результате подстановки вместо какой-нибудь входящей в нее переменной произвольной формулы. Происходит так потому, что любая формула ψ принимает только два значения И и Л, так же как и любая переменная p. Поэтому, например, если вместо переменной p в формулу (9) подставить nm, то получится тождественно истинная формула
(nm q)¬(nm) q.
Пусть имеется произвольная формула логики высказываний. Укажем несколько методов, позволяющих выяснить, является ли данная формула тождественно истинной.
— 28 —
1. Составление таблицы истинности.
Эта процедура уже нами рассматривалась. Если последний столбец таблицы состоит из одних И, значит, данная формула тождественно истинна, в противном случае формула таковой не является. Процедура составления таблицы истинности на практике не
всегда удобна, т. к. содержит 2n строк, но она всегда состоит из конечного числа шагов и всегда дает ответ на поставленный вопрос.
2. Преобразование формулы.
Все операции, содержащиеся в формуле, выражают через конъюнкцию, дизъюнкцию и отрицание, причем, используя законы де Моргана, отрицания сводят к отдельным элементам. В результате таких преобразований формула приводится к виду дизъюнкции из переменных или их отрицаний, либо к виду конъюнкции таких дизъюнкций (конъюнктивной нормальной форме). Если в каждой дизъюнкции содержится какая-нибудь переменная вместе с ее отрицанием, то данная формула тождественно истинна.
Применим этот метод в качестве примера к формуле (11).
(p q)(q r) (p r) ≡ ¬((¬p q)( ¬q r)) (¬p r) ≡
¬ (¬p q) ¬ (¬q r) ¬p r ≡ p¬q q¬r ¬p r ≡ (p ¬p)( ¬q ¬p) (q r)( ¬r r) ≡ И(¬q ¬p) (q r)И ≡ ¬q ¬p q r ≡ (¬q q) (¬p r) ≡ И (¬p r) ≡ И.
3. Метод косвенного доказательства (способ «от противного»). Пусть данная формула не является тождественно истинной. Тогда существует хотя бы один набор значений переменных, при котором она принимает значение Л. Если такой набор переменных удается найти, то данная формула не тождественно истинна. Если же допущение о существовании такого набора ведет к противоре-
чию, то данная формула тождественно истинна. Применим этот метод к формуле (11). Допустим, что формула
(p q)(q r) (p r)
не является тождественно истинной. Тогда существует хотя бы один набор значений переменных (p, q, r), при котором она ложна,
— 29 —
а, следовательно, основание (p q)(q r) истинно, а следствие p r ложно.
Значит, p = И, r = Л. Из условия истинности основания следует p q = И, q r = И. Последнее с учетом r = Л означает, что q = Л, но тогда и p = Л! Получено противоречие, следовательно, наше допущение неверно и формула (11) тождественно истинна.
§ 7. Анализ рассуждений. Правило вывода
Законы логики, выражаемые тождественно-истинными формулами логики высказываний, могут служить основой для рассуждений, в которых учитывается структура сложных высказываний, но не учитывается структура высказываний, рассматриваемых как элементарные. Чтобы учесть и этот фактор, введем сначала поня-
тие рассуждения.
Мы будем понимать рассуждение как вывод из некоторых предложений (посылок) нового предложения (заключения). Рассуждение будет считаться правильным, если с его помощью из ис-
тинных посылок нельзя получить ложное заключение.
Правильность рассуждения является свойством его формы, структуры и не зависит от его содержания. Под анализом рассуждения будем понимать выделение его формы (схемы) и выяснением правильности этой формы (схемы), т. е. невозможности получения по этой схеме из истинных посылок ложного заключения.
Заменив входящие в рассуждение элементарные высказывания переменными, получим следующую общую схему рассуждений
«Из ϕ1, ϕ2 , ... ϕn следует ϕ ».
Это означает, что ϕ истинно, по крайней мере, при всех наборах переменных, при которых истинны все посылки ϕ1, ϕ2 , ... ϕn .
Логическое следование ϕ из посылок ϕ1, ϕ2 , ... ϕn обозначим
(ϕ1, ϕ2 , ... ϕn ) 6 ϕ .
— 30 —
Теперь докажем теорему, устанавливающую связь между логическим следованием заключения из посылок и тождественноистинными формулами.
Теорема: (ϕ1, ϕ2 , ... ϕn ) 6 ϕ тогда и только тогда, когда
◊( ϕi ϕ).
Доказательство.
1. Пусть верно логическое следование. Тогда при всех наборах значений переменных, при которых истинны все посылки, истинно также и заключение и поэтому
◊( ϕi ϕ).
2. Обратно, пусть ◊( ϕi ϕ). Это значит, что не может суще-
ствовать такой набор значений переменных, при которых посылки ϕ1, ϕ2 , ... ϕn (а, следовательно, и их конъюнкция) истинны, а за-
ключение ϕ ложно, т. к. в этом случае формула ( ϕi ϕ) не бу-
дет тождественно-истинной, что противоречит условию. Теорема доказана.
Утверждение типа «Из высказываний со структурой, выражаемой формулами ϕ1, ϕ2 , ... ϕn , — посылок, следует высказывание со структурой, выражаемой формулой ϕ , — заключение» называется правилом вывода. Условимся правило вывода с посылками ϕ1, ϕ2 , ... ϕn и заключением ϕ записывать так:
ϕ1, ϕ2 ,...ϕn .
ϕ
В следующих разделах проведем анализ некоторых рассуждений с целью выделения простейших правил вывода, основанных на тождественно-истинных формулах логики высказываний.
— 31 —