Логическое следствие. Анализ рассуждений. Лекция 4

Теорема:
Бутерброд с колбасой лучше вечной любви
Доказательство:
Что может быть лучше вечной любви? Да ничего.
А бутерброд с колбасой – это лучше, чем ничего.
Следовательно, бутерброд с колбасой лучше вечной любви

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

Теория логического следования
изучает закономерности образования формул F1, F2, …, Fk, G, по которым первые k из них связаны с последней отношением логического следования

Понятие логического следствия
Определение 1
F1, F2, …, Fk ╞ G
Формула G называется логическим следствием формул
F1, F2,…, Fk, если она обращается в истинное высказывание при всяком наборе значений высказывательных переменных, при котором в истинное высказывание обращаются все формулы F1,F2, …,Fk

Понятие логического следствия
F1, F2, …, Fk ╞ G
Формулы F1, F2, …, Fk называются посылками для логического следствия G
Формула G является (заключением) логическим следствием формул
F1, F2, …, Fk

Понятие логического следствия
F1, F2, …, Fk ╞ G,
если для любых высказывательных переменных, при которых:
t(F1)=1, t(F2)=1, …, t(Fk))=1
следует t(G)=1

Алгоритм проверки формул
на логическое следствие
Построить истинностную таблицу для формул F1, F2, …, Fk и G
Выделить в этой таблице все строки, в которых формулы F1, F2, …, Fk принимают одновременно значение «истина»
Выяснить, какое значение в выделенных строках принимает формула G:
если формула G во всех этих строках принимает значение «истина», то F1, F2, …, Fk ╞ G;
если хотя бы в одной из данных строк формула G принимает значение «ложь», то G не является логическим следствием формул F1, F2, …, Fk

Задача 1
Выяснить, выполняется ли логическое следствие:
A→B, B→C╞ A→C

Признак логического следствия
Теорема 1
F1, F2, …, Fk ╞ G ⬄ ((F1˄F2˄…˄Fk)→G)-ТИ

Теорема 1
F1, F2, …, Fk ╞ G ⬄ ((F1˄F2˄…˄Fk)→G)-ТИ
Доказательство (необходимость). Дано: F1, F2, …, Fk ╞ G
Докажем: ((F1˄F2˄…˄Fk)→G)-ТИ
Возьмем какой-нибудь набор значений высказывательных переменных, входящих в формулы F1, F2, …, Fk при котором:
Рассмотрим два случая:
Пусть t(F1)=1,t(F2)=1, …, t(Fk)=1. Тогда, в силу условия:
F1, F2, …, Fk╞ G, имеем t(G)=1. Следовательно,
t((F1˄F2˄…˄Fk)→G)=1
Пусть t(Fi)=0. Тогда t(F1˄…˄Fi˄…˄Fk)=0, и
t((F1˄F2˄…˄Fk)→G)=1
Таким образом, формула ((F1˄F2˄…˄Fk)→G) при любом наборе значений высказывательных переменных принимает значение «истина», отсюда
((F1˄F2˄…˄Fk)→G)-ТИ

Теорема 1
F1, F2, …, Fk ╞ G ⬄ ((F1˄F2˄…˄Fk)→G)-ТИ
Доказательство (достаточность).
Дано: ((F1˄F2˄…˄Fk)→G)-ТИ
Докажем: F1, F2, …, Fk ╞ G
Возьмем какой-нибудь набор значений высказывательных переменных, входящих в формулы F1, F2, …, Fk
Предположим, что при этом наборе значений высказывательных переменных все формулы F1, F2, …, Fk принимают значение «истина».
Т.к. ((F1˄F2˄…˄Fk)→G)-ТИ, t((F1˄F2˄…˄Fk)→G)=1, то t(G)=1
Таким образом, при любом наборе значений высказывательных переменных, при котором t(F1)=1,t(F2)=1, …, t(Fk)=1, формула G также принимает значение «истина», следовательно F1, F2, …, Fk╞ G

Задача 1
Выяснить, выполняется ли логическое следствие:
A→B, B→C╞ A→C
Решение (2 способ)
по признаку логического следствия
A→B, B→C╞A→C⬄(((A→B)˄(B→C))→(A →C ))–ТИ

Свойства логического следования
1. (рефлексивное свойство логического следования)
F1, F2, …,Fk╞ Fi (i=1,2,…,k)

Свойства логического следования
2. (транзитивное свойство логического следования)
Если F1, F2, …, Fk╞ Hi (i=1, 2, …, s)
и если H1, H2, …, Hs╞ G,
то F1, F2, …, Fk╞ G

Свойства логического следования
3. Если {H1, H2, …, Hs} {F1, F2, …, Fk }
и H1, H2, …, Hs╞G, то F1, F2, …, Fk╞G

Свойства логического следования
4. (теорема дедукции)
Если F1,F2, …,Fk-1,Fk╞G,
то F1, F2, …,Fk-1╞(Fk→G)

Свойства логического следования
5. Если F1,F2, …,Fk╞G и G≡H,
то F1, F2, …,Fk╞H

Свойства логического следования
6. Пусть дано множество формул
F1, F2, …,Fk (1)
и последовательность формул
H1, H2, …, Hs (2)
причем каждая из формул последовательности (2) либо совпадает с одной из формул последовательности (1), либо является логическим следствием предыдущих формул, тогда имеет место
F1, F2, …,Fk ╞ Hi (i=1,2,…,s)

Дедуктивное рассуждение ( или вывод) – логическая операция, в результате которой из одного или нескольких взаимосвязанных по смыслу предложений получается предложение, содержащее новое (по отношению к исходным) знание
Иными словами, вывод есть такая последовательность формул (или шагов), что каждая формула этой последовательности является либо одной из посылок, либо получается из некоторых предыдущих формул по какому-то из правил вывода

Правила логических умозаключений
Правило заключения: F, F→G╞G
2. Правило силлогизма: F→G, G→H ╞ F→H
3. Правило контрапозиции: F→G ╞ →
4. Правило отрицания: F→G, ╞
5. Введение дизъюнкции: F ╞ F˅G
6. Удаление дизъюнкции: F˅G, ╞ F
7. Введение конъюнкции: F, G ╞ F˄G
8. Удаление конъюнкции: F˄G╞F, F˄G╞G

Правила логических умозаключений
1. Правило заключения (modus ponens):
F, F→G╞G
Доказательство (modus ponens) :

Задача 2
Выяснить, выполняется ли логическое следствие:
A→B, C→D, A˅C╞B˅D
Решение (3 способ) – на основе вывода:
B˅D≡ →D – свойство 5 логического следствия
A→B, C→D, A˅C, ╞D – свойство 4 (Т. дедукции)
– посылка;
A→B – посылка;
→ – из 1) и 2) по правилу контрапозиции;
– из 1) и 3) по правилу заключения;
A˅C – посылка;
С – из 4) и 5) по правилу удаления дизъюнкции;
C→D – посылка;
D – из 6) и 7) по правилу заключения
По теореме дедукции получаем: A→B, C→D, A˅C╞B˅D

Метод от противного
Требуется выяснить: F1, F2, …, Fk ╞ G
Суть метода
Предположим, что G не есть логическое следствие формул F1, F2, …, Fk
Значит, существуют такие конкретные высказывания A1, A2, …, An, что G(A1, A2, …, An) - ложно, в то время как все высказывания
F1(A1, A2, …, An), F2(A1, A2, …, An), …, Fk(A1, A2, …, An) –истинны
Если возникает противоречие, то предположение неверно
Если противоречие не возникает, то предположение подтверждается

Задача 2
Выяснить, выполняется ли логическое следование:
A→B, C→D, A˅C╞B˅D
Решение (4 способ) – от противного: Допустим, что существуют такие конкретные высказывания A, B, C и D что t(A→B)=1, t(C→D)=1, t(A˅C)=1, но t(B˅D)=0
Т.к. t(B˅D)=0 t(B)=0, t(D)=0
Т.к. t(A→B)=1, t(B)=0 t(A)=0
Т.к. t(C→D)=1, t(D)=0 t(C)=0
Тогда t(A˅C)=0
Пришли к противоречию: t(A˅C)=1, которое означает, что наше предположение неверно. А значит верно: t(B˅D)=1 и A→B, C→D, A˅C╞B˅D
Ответ: логическое следствие выполняется

Анализ рассуждений
Алгоритм установления справедливости рассуждения
Выделить все простые высказывания, входящие в состав рассуждения, и обозначить каждое из них высказывательной переменной
Записать каждое предложение данного рассуждения в виде логической формулы, используя введенные высказывательные переменные и логические операции
Выделить (по смыслу) из полученных формул посылки и заключение
Выяснить, является ли заключение логическим следствием посылок:
Если заключение является логическим следствием посылок, то рассуждение справедливо
Если заключение не является логическим следствием посылок, то рассуждение несправедливо

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

Решение:
Введем логические переменные:
А: «Джонс не встречал ночью Смита»
В: «Смит убийца»
С: «Джонс лжет»
D: «убийство состоялось после полуночи»
A→(B˅C), →(A˄D), D→(B˅ ) ╞ В