§3 Логическое следствие

Формула G(X₁, X₂…, X_n) называется логическим следствием формул F₁(X₁,X₂…, X_n),…,F_m(X₁,X₂,…X_n), если она принимает значение 1 на всяком наборе значений логических переменных, при котором формулы F_1, F_2,…F_m одновременно принимают значение 1.

(обозначение: F_1, F_2,…F_m ╞ G).

Формулы F_1, F_2,…F_m называются посылками, а формула G – заключением.

Основные методы установления верности логического следствия:

1. С помощью таблиц истинности формул F_1, F_2,…F_m, G;

2. Составить формулу F₁ F₂ … F_mG и показать, что она тождественно истинна;

3. Составить формулу F₁(F₂…(F_mG)…) и показать, что она тождественно истинна;

4. Метод от противного.

Упражнения

1. Верны ли следующие выводимости (доказательство провести с помощью таблиц истинности и методом от противного):

а) AB, AC, BC╞A;

б) AB, CB, AC╞B;

в) AB, A╞B;

г) AB, A╞B;

д) A(BC), AC╞B;

e) XYZ, X╞YZ;

ж) (PQ)(QR)╞PR;

з) A(BC)╞B(AC);

и) P╞PQ;

к) PQ╞PQ;

л) PQ╞(PR)(QR);

м) PQ╞(PR)(QR)?

Решение: б) Используем метод от противного. Предположим, что следствие неверно, тогда:

A B=1 A=C=1

CB=1 B=0

AC=1 AB=1

B=0 откуда CB=1

Полученная система противоречивая, значит нет такого набора значений логических переменных, при котором посылки AB, CB, AC одновременно имеют значение 1, а заключение – значение 0. Поэтому следствие AB, CB, AC╞B верно.

Приведем доказательство этого же следствия с помощью таблиц истинности:

A	B	C	AB	CB	AC	B
0	0	0	1	1	0	0
0	0	1	1	0	0	0
0	1	0	1	1	0	1
0	1	1	1	1	0	1
1	0	0	0	1	0	0
1	0	1	0	0	1	0
1	1	0	1	1	0	1
1	1	1	1	1	1	1

Построив таблицы истинности для всех посылок и заключения, выбираем все строки в которых посылки одновременно принимают значение 1 (это восьмая строка) и смотрим какое значение принимает заключение. Так как B=1, то данное логическое следствие верно.

2. Докажите, что если F╞G и F╞H, то F╞GH и F╞GH.

3. Докажите или опровергните, что F╞GH тогда и только тогда, когда F,G╞H.

4. Методом от противного выясните, верны ли следующие выводимости:

а) FG, KH, HG ╞ FK;

б) FG, ((FL)H)M, LH╞((FL)G)M;

в) (FG)R, (FH)K, FK, (FG)H╞FR;

г) FG, KL, SH, FK, HL ╞ SG;

д) (FG)H, (HK)L M(KL)╞(FG)M;

е) F(GH), (HK)L, M(KL)╞F(GM);

ж) (FG)(HK), (KL)M╞FM;

з) F(GH), GK, (LM)K, G(FL)╞GL;

и) (FG)(HK), (GL)(KM), (LM), FH╞F.

5. Проанализировать рассуждения:

а) Я пойду или в кино на новую комедию, или на занятие по математической логике. Если я пойду в кино на новую комедию, то я от всей души посмеюсь. Если я пойду на занятие по математической логике, то испытаю большое удовольствие от следования по путям логических рассуждений. Следовательно, или я от всей души посмеюсь, или испытаю большое удовольствие от следования по путям логических рассуждений.

б) Если цех II не будет участвовать в выпуске нового образца продукции, то не будет участвовать и цех I. Если же цех II будет участвовать в выпуске нового образца, то в этой работе непременно должны быть задействованы цеха I и III. Необходимо ли участие цеха III, если в выпуске нового образца будет участвовать цех I?

в) Джон или переутомился или болен. Если он переутомился, то он раздражается. Он не раздражается. Следовательно, он болен.

г) Eсли 6-составное число, то 12-составное число. Если 12-составное число, то существует простое число больше чем 12. Если существует простое число больше 12, то существует составное число больше 12. Если 6 делится на 2, то 6 составное число. Число 12 составное, следовательно 6-составное число.

д)Если 2-простое число, то это наименьшее простое число. Если 2-наименьшее простое число, то 1 не есть простое число. Число 1 не есть простое число. Следовательно, 2-простое число.

е) Или Анна и Антон одного возраста, или Анна старше Антона. Если Анна и Антон одного возраста, то Наташа и Антон не одного возраста. Если Анна старше Антона, то Антон старше Николая. Следовательно, либо Наташа и Антон не одного возраста, либо Антон старше Николая.

ж) Если число дробное, то оно рациональное. Если число рациональное, то оно действительное. Следовательно, если число дробное, то оно действительное.

з) Если все посылки истинны и рассуждение проведено по законам логики, то и заключение истинно. В данном рассуждении заключение ложно. Следовательно, не все посылки истинны или рассуждение проведено не по правилам логики.

и) Если он принадлежит к нашей компании, то он храбр и на него можно положиться. Он не принадлежит к нашей компании. Значит, он не храбр или же на него нельзя положиться.

к) Для того, чтобы функция F была интегрируема на [a;c], необходимо, чтобы F была ограничена на на [a;c]. Функция F – интегрируемая на [a;c]. Значит, F-ограничена на [a;c].

Решение: ж) Введем обозначения:

А – число дробное

В – число рациональное

С – число действительное.

Структура рассуждения: АВ, ВС╞АС. Следовательно, необходимо выяснить является ли формула АС логическим следствием формул АВ и ВС. Воспользуемся методом от противного, допустим, что это не логическое следствие. Тогда

А В=1

ВС=1

АС=0

Так как АС=0, то А=1, С=0. Из первого уравнения В=1. Подставляя В и С во второе уравнение, получаем противоречие: 10=1.

Следовательно, наше предположение оказалось неверным. Значит рассуждение логично.