§ 4. Логическое следование и логические следствия

Пусть A₁, А₂, ..., A_n и В — формулы, a E₁, E₂, ..., Е_m — совокупность всех пропозициональных переменных, входящих по крайней мере в одну из них. Будем говорить, что формула В логически следует из формул A₁, А₂, ..., A_n, если при всех тех логических значениях E₁, E₂, ..., Е_m, при которых формулы A₁, А₂, ..., A_n истинны, она тоже истинна.

Для того чтобы проверить, выполняется ли это условие, нужно выяснить, может ли формула

(A₁  А₂ ... A_n)  В,

хотя бы при одном наборе логических значении переменных E₁, E₂, ..., Е_m, быть ложной. Если эта формула тождественно-истинна, то не существует такого набора логических значений ее переменных, при котором подформулы A₁, А₂, ..., A_n истинны, а подформула В ложна. Таким образом, формула В логически следует из формул A₁, А₂, ..., A_n, если тождественно-истинна формула

(A₁  А₂ ... A_n)  В.

Формула В называется в этом случае логическим следствием (заключением) формул A₁, А₂, ..., A_n, а формулы A₁, А₂, ..., A_n называются посылками формулы В.

Используя в качестве разрешающей процедуры процесс приведения формул к КНФ, можно для любой формулы В и любого списка формул A₁, А₂, ..., A_n решить логическую задачу: является В логическим следствием совокупности посылок A₁, А₂, ..., A_n или нет?

Проверим, например, следует ли формула r из формул р  q, p  r и q  r? С этой целью строим формулу

((р  q)  (p  r)  (q  r))  r

и приводим ее к КНФ:

((р  q)  (р  r)  (q  r))  r;

(р  q)  (р  r)  (q  r)  r;

(р  q)  (р  r)  (q  r)  r;

((р  р)  (p  q)  (r  р)  (r  q))  (q  r)  r;

((q  р  р)  (q  p  q)  (q  r  р)  (q  r  q) 

 (r  р  р)  (r  p  q)  (r  r  р)  (r  r  q))  r;

(r  q  р  р)  (r  q  p  q)  (r  q  r  р)  (r  q  r  q) 

 (r  r  р  р)  (r  r  p  q)  (r  r  r  р)  (r  r  r  q);

Так как в каждом из конъюнктов КНФ данной формулы содержится по крайней мере одна переменная со знаком отрицания и без него, то данная формула тождественно-истинная и r логически следует из (р  q), (p  r) и (q  r).

Рассмотрим другой пример. Три цеха договорились, что при утверждении проектов должны соблюдаться следующие условия: а) если второй цех не участвует в утверждении проекта, то в этом утверждении не участвует и первый цех; б) если второй цех принимает участие в утверждении проекта, то в нем принимают участие первый и третий цеха. Обязан ли при этих условиях третий цех принимать участие в утверждении проекта, когда в нем принимает участие первый цех?

Переведем условия задачи на язык логики высказываний. Пусть высказыванию Первый цех участвует в утверждении проекта соответствует переменная р, высказыванию Второй цех участвует в утверждении проекта — переменная q, а высказыванию Третий цех участвует в утверждении проекта — переменная r. Тогда условиям а) и б) соответствуют формулы q  p и q  (p  r).

Требуется решить, следует ли из этих условий формула р  r? Для этого строим формулу

((q  p)  (q  (p  r)))  (р  r)

и приводим ее к КНФ:

((q  p)  (q  (p  r)))  (р  r);

((q  p)  (q  (p  r)))  р  r;

((q  p)  (q  (p  r)))  р  r;

((q  p)  (q  (p  r)))  р  r;

((q  q)  (q  p)  (p  r  q) (p  r  p))  p  r;

(р  r  q  q)  (р  r  q  p)  (р  r  p  r  q) (р  r  p  r  p).

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

Процедуру приведения формулы к СКНФ используют для решения задачи отыскания логических следствий данных посылок. 'Можно указать следующий метод систематического обзора следствий из любого числа посылок.

Связываем посылки знаком конъюнкции и получившуюся формулу приводим к СКНФ. Каждый конъюнктивный член СКНФ, а также любая конъюнкция конъюнктивных членов являются следствием конъюнкции посылок.

Например, пусть даны посылки р и p  q. Конъюнкцию посылок приводим к СКНФ:

p  (p  q);

p  (p  q);

(p  (q  q))  (p  q);

(p  q)  (p  q)  (p  q).

С помощью этой СКНФ мы можем теперь получить обзор всех таких следствий из конъюнкции данных посылок, каждое из которых само имеет СКНФ:

1) p  q; 2) p  q; 3) p  q;

4) (p  q)  (p  q); 5) (p  q)  (p  q);

6) (p  q)  (p  q); 7) (p  q)  (p  q)  (p  q).

Затем, используя, например, равносильность (18), можно упрощать полученные следствия: из следствия 4 получить следствие р, которое является одной из посылок (вторая посылка есть 3), а из следствия 5 получить следствие q.

Рассмотрим следующий пример². Если теорема о сложении скоростей верна, и в системе неподвижных звезд свет распространяется по всем направлениям с одинаковой скоростью, то на Земле скорость распространения света не по всем направлениям одинакова. Из опыта известно, что свет в системе неподвижных звезд распространяется по всем направлениям с одинаковой скоростью и что на Земле скорость распространения света по всем направлениям одинакова. Что отсюда следует?

Пусть высказыванию Теорема о сложении скоростей верна соответствует переменная р; высказыванию В системе неподвижных звезд свет распространяется по всем направлениям с одинаковой скоростью — переменная q, а высказыванию На Земле свет распространяется по всем направлениям с одинаковой скоростью —переменная r. Тогда условия задачи выражаются в посылках: 1) (p  q)  r и 2) q  r.

Находим СКНФ конъюнкции этих посылок:

((p  q)  r)  q  r;

((p  q)  r)  q  r;

(p  q  r)  q  r;

(p  q  r)  (q  (р  р))  (r  (р  р));

(p  q  r)  (q  р)  (q  р)  (r  р)  (r  р);

(p  q  r)  (q  р  (r  r))  (q  р  (r  r))  (r  р  (q  q))  (r  р  (q  q));

(p  q  r)  (q  р  r)  (q  р  r)  (q  р  r)  (q  р  r)  (r  р  q)  (r  р  q)  (r  р  q)  (r  р  q).

К конъюнкции 1-го и 5-го, 4-го и 7-го конъюнктивных членов получившейся СКНФ несколько раз применяем правило замены по равносильности (18) и находим наиболее интересное по содержанию следствие:

(p  q  r)  (q  р  r)  (q  р  r)  (r  р  q);

(p  r)  (p  r);

p,

т. е. что теорема о сложении скоростей неверна.

Упражнения

I. Выяснить, верно ли, что

1) формула r  q логически следует из формул р и р  (q  r);

2) формула р  r логически следует из формул p  q и (q  r);

3) формула (r  s) логически следует из формул р  q, р  r и q  s?

II. Найти все следствия в СКНФ из посылок:

1) р  q, р  r и р  q;

2) p  q, q  r и r  р.

III. В студенческой группе возникла следующая ситуация: каждый студент, который умеет играть в шахматы, или имеет спортивный разряд, или хорошо учится, но не то и другое вместе; если студент имеет спортивный разряд, то он умеет играть в шахматы. Следует ли отсюда, что в группе нет студентов, которые имеют спортивный разряд и в то же время хорошо учатся?

IV. Проверить справедливость следующего рассуждения полицейского детектива: «Если Джонс не встречал этой ночью Смита, то либо Смит был убийцей, либо Джонс лжет. Если Смит не был убийцей, то Джонс не встречал Смита этой ночью, и убийство имело место после полуночи. Если убийство имело место после полуночи, то либо Смит был убийцей, либо Джонс лжет. Следовательно, Смит был убийцей».