Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Формальная логика.doc
Скачиваний:
7
Добавлен:
01.07.2025
Размер:
6 Мб
Скачать
☆

II. Привести к скнф следующие формулы:

  1. (р->?) V~(~<7Vr);

  2. ((~ (р 9) V ~ <?) V(P Л г).

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

Пусть А», Аг. ., An и В — формулы, а Еь Е2, .Ет со­вокупность всех пропозициональных переменных, входящих по крайней мере в одну из них. Будем говорить, что формула В логически следует из формул А], А2, ..., А„, если при всех тех логических значениях Ei, Е2, ..., Em, при которых формулы Аь А2, Ап истинны, она тоже истинна.

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

(AVA А2Д ... Л А„) -> В,

хотя бы при одном наборе логических значений переменных Еь Е2. Ет, быть ложной. Если эта формула тождественно-истинна, то не существует такого набора логических значений ее переменных, при котором подформулы At, А2. А„ истин­ны, а подформула В ложна. Таким образом, формула В логиче­ски следует из формул Аь А2, ..., А„, если тождественно-истин­на формула

(Ai Л А2 Л ... Л А„)-> В.

Формула В называется в этом случае логическим след­ствием (заключением) формул Аь А2, Ап, а формулы Аь А2, An называются посылками формулы В.

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

Проверим, например, следует ли формула г из формул р V 9, р-+г и q-*г? С этой целью строим формулу

((р Vq)A(p-*r)A(q-*r))-*r и приводим ее к КНФ:

~ ((р V а) Л (~ Р V г) Л (~ q V г)) V г; ~(pVq) V~(~p У г) V ~(~<7Vr) Vr; (~рЛ ~q) V(pA~r)V(?A ~r) V г; ((p V ~p) Л (P V ~q) Л(~ г V ~P) Л (~г V ~?)> V

V(?A~f)Vr; ((?V]5V~p)A(?VpV~<?)A(?V~rV~p)A

A(<7V~rV~<7)A(~rVpV~p)A(~rVpV~<7>A

Af~fV~rV~p)A(~rV~fV~?))Vf; (г V q V P V ~p) Л (г V q V P V~q) Л (г V q V ~r V ~p) A A(/-V<7V~rV~<7)A(rV~/-VpV~p)A A(rV~rVpV~9)A(rV~rV~rV~p)A

A(fV~rV ~rV~?).

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

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

Переведем условия задачи на язык логики высказываний. Пусть высказыванию Первый цех участвует в утверждении проекта соответствует переменная р, высказыванию Второй цех участвует в утверждении проекта — переменная q, а высказыва­нию Третий цех участвует в утверждении проекта — перемен­ная г. Тогда условиям а) и б) соответствуют формулы ~ q -* ~ р и q -* (р Л г).

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

((~ q ~* ~ Р) Л (q -*■ (р Л г))) -* {р.-»► г)

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

~((<7 V ~р) Л (~<7 V (р А г))) V (~р V г);

(~(<7 V ~Р) V ~(~q V (Р Л г))) V ~р V г;

Л р) V {q Л~(Р Л г))) V ~р V г,

((~Я Ар) V (q Л (~р V - г))) V ~р V г;

((<7 V ~q) A (q V р) Л (~Р V ~r V ~q) А

A{~р V ~г Vр)) V ~р у г,

(~ р V г V q V ~ q) А (~ р V г V <? V р) Л

A(~pVrV~pV~rV~<7)A(~pVrV~pV~rVp).

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

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

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

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

pA(p->q);

Р Л (~Р V q)\

(р Л (9 Л ~ q)) Л (~ Р V <7>".

(PV<7)A(P V~<7)A(~p'V<7).

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

1) pVq; 2) pV~q; 3) ~pV<7;

4) (pV<7)A(pV ~q); 5) (p V <7) Л (~P V

6) (pV ~<7)Л(~Р V<7); 7) (pV?)A(pV ~<7)A(~pV<?).

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

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

Пусть высказыванию Теорема о сложении скоростей верна соответствует переменная р; высказыванию В системе непод­вижных звезд свет распространяется по всем направлениям с-одинаковой скоростью — переменная q, а высказыванию На Земле свет распространяется по всем направлениям с одинако­вой скоростью — переменная г. Тогда условия задачи выра­жаются в посылках: 1) (рЛ<7)-> ~г и 2) q Ал

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

((Р Л q) -* ~ г) A q Л г; (~ (р А Я) V ~ г) A q Л П :- (~ р v ~q V ~ г) A q Л П (~р V ~<7 V ~r) Л (q V (Р Л ~Р)) Л (г V (р Л ~Р)); (~р V ~qV~r)A(qV p)A(qV ~р) Л (г V р) Л (г V ~р); (~р V ~q V -г) Л (<7 V р V (г Л ~/0) Л to V ~р V(r Л -г)) Л Л (г УР V (д А ~<7)) Л (г V ~р V (g Л ~?));