77

Знание действия зависит от знания причины и заключает в себе последнее.

Б. Спиноза

Глава 3. ЛОГИЧЕСКОЕ СЛЕДСТВИЕ И МЕТОД РЕЗОЛЮЦИЙ

Врубайся в суть, не боясь затупить клинок, Ибо острота не вечна.

Лао Цзы (Дао Дэ Цзин)

Это конечно, Сова. Или я не Винни-Пух. А я – он…

А. М. Мили

§ 1. Логическое следствие и проблема дедукции в логике высказываний

Пусть А и В пропозициональные формы (формулы логики высказываний). Считаем, что В логически следует из А, если для каждой совокупности значений пропозициональных букв, при которых А=И форма В тоже принимает значение И. В этом случае записываем

А╞ В

и читаем: «из А логически следует В» или «В является логическим следствием из А».

Легко доказать следующую теорему.

Теорема 3.1. Если А╞ В и В╞ С, то А╞ С.

Запись ╞ А в логике высказываний означает, что А является тавтологией (общезначимой). Докажем следующую теорему.

Теорема 3.2. А╞ В тогда и только тогда, когда ╞ А В.

Доказательство. Построим таблицу истинности для А В. Пусть имеем, что А╞ В, тогда в каждой строке таблице, где А=И будет В=И, следовательно, А В тавтология, то есть ╞ А В. Если же имеем ╞ А В, то в

78

таблице истинности для А В всюду, где А=И должно быть В=И, следовательно получим А╞ В.

Пропозициональная форма В называется логическим следствием пропозициональных форм А1,А2,…,Аm, m≥1, если для каждой совокупности значений пропозициональных букв при которых формы А1, А2,…,Аm одновременно равны И форма В тоже принимает значение И. В этом случае

записываем:
А1, А2,…,Аm╞ В	(3.1)

Выяснение будет ли В логическим следствием из А1, А2,…,Аm, m≥1,

называют проблемой дедукции.

Очевидно, что имеет место следующая теорема.

Теорема 3.3. Для произвольных формул логики высказываний А1,А2,…,Аm, m≥1, имеют место соотношения:

	А1,А2,…,Аm╞ А1&А2&…&Аm ,			(3.2)
	А1,А2,…,Аm╞ Аi для любого i, 1≤ i≤ m.
				(3.3)

Теорема 3.4. Если формула
А1&А2&…&Аm& В	(3.4)
является противоречием, тогда В является логическим	следствием из
А1,А2,…,Аm, т.е.:
А1,А2,…,Аm╞ В.	(3.5)
Доказательство. Пусть формула (3.4) является противоречием, тогда
ее отрицание является тавтологией, т.е. имеем:
╞ (А1&А2&…&Аm& В).	(3.6)
Очевидно, что имеем
(А1&А2&…&Аm& В) (А1&А2&…&Аm) В
(А1&А2&…&Аm) В.
Следовательно, утверждение (3.6) можно записать в виде:	(3.7)
╞ (А1&А2&…&Аm) В.
Из (3.7) по теореме 3.2 получаем, что
(А1&А2&…&Аm) ╞ В.	(3.8)

79

Теперь используя утверждение (3.2) теоремы 3.3 и утверждение (3.8) получим требуемое утверждение (3.5). Теорема доказана.

Используя утверждения (3.2) и (3.3) теоремы 3.3, можно получать следствия из заданного множества формул следующим образом. Для заданного множества формул А1, А2,…,Аm, m≥1, строим их конъюнкцию: С=А1&А2&…&Аm. Для С находим с.к.н.ф.: С= D1&D2&…&Dk, здесь Di, 1≤i≤k, элементарные суммы (дизъюнкты). Теперь по указанной теореме 3.3 получаем, что каждый дизъюнкт Di, 1≤ i≤ k, а также их конъюнкции являются следствиями из А1, А2,…,Аm, m≥1, т. е. имеем:

А1, А2,…,Аm╞ Di для любого i, 1≤ i≤ k;

А1, А2,…,Аm╞ Ds1 & Ds2 & ...& Dsr , для любого r, 1≤ r≤ k и любых s1,

s2,…,sr, 1≤ s1, s2,…,sr ≤ k.

Заметим, что для формул логики предикатов понятие логического следствия из данной формулы (данных формул) введено в 6 – ом параграфе второй главы. Нетрудно убедиться, что теоремы 3.1 - 3.4 остаются в силе и для формул логики предикатов, в частности, теорема 3.2 для формул логики предикатов уже доказана, см. теорему 2.1.

Хочешь взятьУмей отдать.

Вот в чем глубокая истина. Лао Цзы

§ 2. Резольвента дизъюнктов логики высказываний

Пропозициональные буквы с отрицанием либо без отрицания, входящую в элементарную сумму (дизъюнкт), называют литералами (литерами) логики высказываний.

Литеры L и L называются контрарными. Так, например, в дизъюнктах D1=P Q и D2= P Q S литеры P и P контрарные. Также контрарные литеры Q и Q.

Пусть для двух дизъюнктов D1 и D2 существует литера L1 в D1, которая контрарна литере L2 в D2. Вычеркнув L1 и L2 из D1 и D2 соответственно, построим дизъюнкцию оставшихся частей D1 и D2. Полученный таким образом дизъюнкт называется (бинарной) резольвентой D1 и D2, который часто обозначают через R.

Примеры. 1. Пусть D1=P Q, D2= P T, тогда R=Q T.

2.Пусть D1=P, D2= P Q (D2~P Q), тогда R=Q, иначе из P и P Q получаем Q.

3.Пусть D1= P Q (D1=P Q), D2= Q T (D2=Q T), тогда R= P T (R=P T). Иначе из P Q и Q T получаем P T.

80

Теорема 3.5. Пусть для дизъюнктов D1 и D2 существует резольвента R. Тогда R есть логическое следствие из D1 и D2.

Доказательство. Пусть D1=P D1*, D2= P D2*, где Di* оставшаяся часть дизъюнкта Di, i=1,2. Докажем, что D1,D2╞ D1* D2*. Выпишем всевозможные наборы истинностных значений букв входящих в D1 и D2. Выберем набор, положим k-ый, на котором D1=И и D2=И. Допустим, что на этом k-ом наборе буква P принимает значение И, тогда P=Л, поэтому должно быть D2*=И, следовательно D1* D2*=И. Таким образом из истинности D1 и D2 получили истинность D1* D2*. В случае если на k-ом наборе P=Л, то D1*=И и вновь получаем, что из истинности D1 и D2 следует истинность D1* D2*. В силу произвольности выбранного набора получаем, что из истинности D1 и D2 следует истинность для D1* D2*, что и требовалось.

Следует поставить перед собой цель изыскать способ решения всех задач … одним и притом простым способом.

Даламбер

§ 3. Метод резолюций в логике высказываний

Рассмотрим задачу выяснения будет ли В логическим следствием из А1,А2,…,Аm, то есть истинна ли следующая запись:

А1,А2,…,Аm╞ В.

В § 1 данной главы показано, что эта задача сводится к выяснению невыполнимости формы

С=А1&А2&…&Аm& В.

Найдем для формулы С ее к.н.ф., то есть получим конъюнкцию

дизъюнктов: С=D1&D2&…&Dk.

Каждое слагаемое дизъюнкта является литералом.

Множество дизъюнктов {D1,D2,…,Dk} считается невыполнимым тогда и только тогда, когда формула С невыполнима.

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

D1=P T, D2= P T, D3= Т.

Используя D1 и D2 затем D1 и D3 , получим резольвенты

D4=Т, D5=P.

Затем из D3 и D4 получим пустой дизъюнкт. Пустой дизъюнкт будем обозначать через .

Можно доказать следующую теорему.