Лекция 4 Логическое следствие. Анализ рассуждений
Теорема: Бутерброд с колбасой лучше вечной любви Доказательство: Что может быть лучше вечной любви? Да ничего. А бутерброд с
Понятие логического следствия
Понятие логического следствия
Понятие логического следствия
Алгоритм проверки формул на логическое следствие
Задача 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)-ТИ
Задача 1 Выяснить, выполняется ли логическое следствие: A→B, B→C╞ A→C
Свойства логического следования
Свойства логического следования
Свойства логического следования
Свойства логического следования
Свойства логического следования
Свойства логического следования
Правила логических умозаключений
Правила логических умозаключений
Задача 2 Выяснить, выполняется ли логическое следствие: A→B, C→D, A˅C╞B˅D
Метод от противного
Задача 2 Выяснить, выполняется ли логическое следование: A→B, C→D, A˅C╞B˅D
Анализ рассуждений
Задача 2 Выяснить, являются ли следующие рассуждения логически верными: Если Джонс не встречал ночью Смита, то Смит был убийцей
493.50K
Категория: ИнформатикаИнформатика

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

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

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

колбасой – это лучше,
чем ничего.
Следовательно, бутерброд с колбасой
лучше вечной любви

3.

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

4.

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

5. Понятие логического следствия

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

6. Понятие логического следствия

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

7. Понятие логического следствия

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

8. Алгоритм проверки формул на логическое следствие

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

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

t(A) t(B) t(C) t(A→B) t(B→C) t(A→C)
1
1
1
1
1
1
1
1
0
1
0
0
1
0
1
0
1
1
0
1
1
1
1
1
1
0
0
0
1
0
0
1
0
1
0
1
0
0
1
1
1
1
0
0
0
1
1
1

10. Признак логического следствия

Теорема 1
F1, F2, …, Fk ╞ G ((F1˄F2˄…˄Fk)→G)-ТИ

11. Теорема 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)-ТИ

12. Теорема 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

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

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

14. Свойства логического следования

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

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

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

16. Свойства логического следования

3. Если {H1, H2, …, Hs} {F1, F2, …, Fk }
и H1, H2, …, Hs╞G, то F1, F2, …, Fk╞G

17. Свойства логического следования

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

18. Свойства логического следования

5. Если F1,F2, …,Fk╞G и G≡H,
то F1, F2, …,Fk╞H

19. Свойства логического следования

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

20.

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

21. Правила логических умозаключений

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

22. Правила логических умозаключений

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

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

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

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

Требуется выяснить: 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)
–истинны
– Если возникает противоречие, то предположение
неверно
– Если противоречие не возникает, то предположение
подтверждается

25. Задача 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
Ответ: логическое следствие выполняется

26. Анализ рассуждений

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

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

или Джонс лжет. Если
Смит не был убийцей, то Джонс не встречал
Смита этой ночью, и убийство имело место
после полуночи. Если убийство имело место
после полуночи, то Смит был убийцей или
Джонс не лжет. Следовательно, Смит был
убийцей.

28.

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

29.

Доказательство справедливости рассуждений проведем
методом от противного
• Предположим, что
t(A→(B˅C))=1, t( B →(A˄D))=1, t(D→(B˅ С ))=1, а t(В)=0
• t( B →(A˄D))=1 и t( B )=1 => t(A˄D)=1, t(A)=1, t(D)=1
• t(A→(B˅C))=1 и t(A)=1 => t(B˅C)=1, т.к. t(В)=0, то t(C)=1
• t(D→(B˅С))=1 и t(D)=1=>t(B˅С )=1,т.к. t(С )=0, то t(В)=1
• Пришли к противоречию: t(В)=0, t(В)=1
• Следовательно, предположение t(В)=0 неверно, а верно
t(В)=1 и рассуждения логически правильны
English     Русский Правила