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

Пусть 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.

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

Пусть высказыванию Теорема о сложении скоростей верна соответствует переменная р; высказыванию В системе неподвижных звезд свет распространяется по всем направлениям с одинаковой скоростью — переменная 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. Проверить справедливость следующего рассуждения полицейского детектива: «Если Джонс не встречал этой ночью Смита, то либо Смит был убийцей, либо Джонс лжет. Если Смит не был убийцей, то Джонс не встречал Смита этой ночью, и убийство имело место после полуночи. Если убийство имело место после полуночи, то либо Смит был убийцей, либо Джонс лжет. Следовательно, Смит был убийцей».

Не нашли, что искали? Воспользуйтесь поиском: