Логика высказываний (лекция 6)

1. Логика высказываний

Лекция 6

2. Основные понятия

Высказывание
–
это
повествовательное
предложение, о котором можно сказать истинно оно
или ложно в данном контексте в данный момент, но ни
то и другое одновременно.
Истина или ложь, приписанная некоторому
высказыванию, называется истинностным значением
этого высказывания.
Обозначается:
«Истина» – И, T (True) или 1,
«Ложь» – Л , F (False) или 0.
2

3. Основные понятия

Пример.
«Волга впадает в Черное море»ложное высказывание;
«Волга впадает в Каспийское море»истинное высказывание;
«Какой сегодня день?»не высказывание;
«Ученик пятого класса»не высказывание.
3

4. Основные понятия

Атомами (элементарными высказываниями)
называются высказывания, которые соответствуют
простым повествовательным предложениям, т.е. не
имеют составных частей.
Атомы обозначаются заглавными буквами
латинского алфавита A, B, C… или заглавными
буквами с индексами.
Из элементарных высказываний можно
строить
сложные высказывания,
называемые
формулами или молекулами.
4

5. Основные понятия

Формализацией
высказываний
называют
операцию
замены
высказывания естественного языка
формулой математического языка,
включающего
высказывательные
переменные
и
символы
тех
логических
операций,
которые
соответствуют
структуре
самого
высказывания.
5

6. Логические связки в логике высказываний

Название
Обозначение
Эквивалентность
, ,
эквивалентно, равносильно,
«тогда и только тогда»
импликация
,
влечет, «если, то», «только если»
конъюнкция
, &
и
дизъюнкция
или, «или…или оба»
отрицание
, ¯
не, «неверно, что»
Аналоги естественного языка
6

7. Логические связки. Отрицание

Отрицание A истинно тогда и только тогда,
когда A ложно.
Пример.
Записать
в
виде
формулы
логики
высказываний и определить истинностное значение
выражений «Неверно, что 2 2 = 7» и «Неверно, что
3 3 = 9».
A : «2 2 = 7»
А = Л = И
B : «3 3 = 9»
B = И =Л
7

8. Логические связки. Дизъюнкция

Если A и B – высказывания, то высказывание
A B, называемое дизъюнкцией A и B, ложно тогда и
только тогда, когда ложны оба высказывания A и B.
Употребляется в смысле «неисключающее или».
Пример.
Записать в виде формулы логики высказываний и
определить истинностное значение следующих высказываний:
«5 + 2 = 10 или 5 2 = 10», «6 – 3 = 2 или 3 2 = 5»
A : «5 + 2 = 10»
B : «5 2 = 10»
А В=Л И=И
C : «6 – 3 = 2»
D : «3 2 = 5»
C D=Л Л=Л
8

9. Логические связки. Конъюнкция

Если A и B – высказывания, то высказывание A B,
называемое конъюнкцией A и B, истинно тогда и только
тогда, когда истинны оба высказывания A и B.
Соответствует связке «и», соединяющей два предложения.
Пример.
Записать в виде формулы логики высказываний и определить
истинностное значение следующих высказываний:
«6 делится на 3, и 10 больше 5»,
«6 делится на 3, и 7 больше 10».
A: «6 делится на 3»,
B: «10 больше 5»,
C: «7 больше 10».
А В=И И=И
А С=И Л=Л
9

10. Логические связки. Импликация

Если A и B – высказывания, то высказывание
A B,
называемое
импликацией
(условным
предложением), ложно тогда и только тогда, когда A
истинно, а B ложно.
A называется посылкой (условием, антецедентом),
B – следствием (заключением, консеквентом).
10

11. Логические связки

Пример.
Записать в виде формулы логики высказываний и
построить таблицу истинности высказывания «Если
идет дождь, то над моей головой открыт зонтик».
Решение.
A – «идет дождь»
B – «над моей головой открыт зонтик»
А
Л
И
Л
И
В
Л
Л
И
И
А В
И
Л
И
И
Результат
останусь сухим
промокну
останусь сухим
останусь сухим
11

12. Логические связки. Эквивалентность

Если A и B – высказывания, то высказывание
A~B истинно тогда и только тогда, когда A и B либо
оба истинны, либо оба ложны.
Пример.
Записать в виде формулы логики высказываний и
определить истинностное значение высказываний:
«Для того чтобы 2 2 = 4 необходимо и
достаточно, чтобы 2 + 2 = 4»,
«2 2 = 5 равносильно тому, что 3 3 = 8».
A:2 2=4
B:3 3=8
A~C = И~И = И
C:2+2=4
D:2 2=5
D~B = Л~Л = И
12

13. Логика высказываний

– это алгебраическая
структура ({Л, И}, , , ¯, , ~, Л, И), образованная
двоичным множеством {Л: «Ложь», И: «Истина»},
вместе с логическими связками:
– конъюнкции,
– дизъюнкции,
¯ – отрицания,
– импликации,
~ – эквивалентности
и константами:
Л – ложь
И – истина.
13

14. Формулы логики высказываний

В
логике
высказываний
правильно
построенная формула определяется рекурсивно
следующим образом:
1. Атом – есть формула.
2. Если A и B – формулы, то (A B), (A B), (A B),
(A~B) , A и B также формулы.
3. Никаких формул, кроме порожденных указанными
выше правилами, не существует.
14

15. Формулы логики высказываний

Формулы логики высказываний, соответствующие сложным высказываниям, принимают
значение И или Л в зависимости от значений
элементарных высказываний, из которых они
построены, и логических связок.
Приписывание истинностных значений атомам называется интерпретацией высказывания.
Для высказывания, содержащего n атомов,
можно составить 2n интерпретаций.
15

16. Общезначимые и противоречивые формулы

Формула называется тождественно истинной
(тавтологией или общезначимой), если она принимает
значение «Истина» на всех наборах значений входящих в
нее переменных.
Формула называется тождественно ложной
(противоречивой или невыполнимой), если она
принимает значение «Ложь» на всех наборах значений
входящих в нее переменных.
Формула называется необщезначимой или
непротиворечивой, если она при одних наборах
значений входящих в нее переменных принимает
значение «Истина», а при других – «Ложь».
16

17.

x
F1
F2
F3
F4
1. F(x)=0
0
0
1
0
1
2. F(x)=1
3. F(x)=x
1
0
1
1
0
X1
X2
F5
F6
F7
F8
0
0
0
0
1
1
0
1
0
1
1
0
1
0
0
1
0
0
1
1
1
1
1
1
4. F(x)= x
5. F(x1,x2)=x1 x2
6. F(x1,x2)=x1 x2
7. F(x1,x2)=x1 x2
8. F(x1,x2)=x1 ~ x2

18.

9. F(x1,x2)=x1 x2
- сложение по модулю 2
X1
X2
F9
0
0
0
0
1
1
1
0
1
1
1
0
10. F(x1,x2)=x1 | x2 - штрих Шеффера (отрицание конъюнкции)
11. F(x1,x2)=x1 ↓ x2 - стрелка Пирса (отрицание дизъюнкции)
X1
X2
F10
X1
X2
F11
0
0
1
0
0
1
0
1
1
0
1
0
1
0
1
1
0
0
1
1
0
1
1
0

19. Область действия логических связок

Область
действия
логической
связки
определяется частью формулы, ограниченной
скобками, между которыми находится данная
связка.
Приоритет операций:
, , , , ~
19

20. Область действия логических связок

Пример.
Записать в виде формулы логики высказываний
следующее предложение:
«Так как я лег поздно спать, я проспал и из-за
этого не пошел на пару».
Решение.
«(Таккак
«Так
как(я
я(ялег
лег
легпоздно
поздно
поздноспать,
спать),
спать),
я (я
япроспал
(япроспал
проспал)
проспал))
и иизиизиизизза этого не пошел
(пошелна
напару».
пару)».
P – «Я лег поздно спать»,
Q – «Я проспал»,
S – «Я пошел на пару».
(P Q) S
20

21.

Если
доказательство
истинности-ложности
высказывания основано на применении таблиц
истинности, то говорят, что
использован
семантический способ доказательств.
Если в процессе доказательства использовались
равносильности алгебры логики, то способ
называют синтактическим.
Познакомимся с основными равносильностями
алгебры логики, т.е. с её законами.

22. Основные законы алгебры логики

a b b a
a b b a - переместительный закон
a b c a b c
- сочетательный закон
a b c a b c
a b a b a b a b
a a b a b
a a b a b
a 1 1
a 1 a
a a 1
a a 0
a b a b
- закон де Моргана
- закон Порецкого
- правила операций с 1
- закон инверсии
- снятие импликации

23.

Задача. Поможем синоптикам определить
прогноз погоды. Известно, что если атмосферное
давление понижается, то возможен дождь. В
настоящее
время
атмосферное
давление
понижается. Возможен ли дождь?
Решение. Пусть Х – атмосферное давление
понижается; Y – возможен дождь.
Высказывание: «Если давление понижается, то
возможен дождь» имеет вид: X Y .
Тогда «Если давление понижается, то возможен
дождь. Давление понижается» можно записать в
виде конъюнкции X Y X .
Сформулируем теорему:
X Y X Y 1

24.

Докажем истинность вывода,
способа.
Синтактический способ.
используя
оба
X Y X Y X Y X Y
Y X Y X Y Y X Y Y
X Y Y X 1 1.

25.

Семантический способ представлен в таблице:
X
Y
X Y
X Y X
X Y X Y
0
0
1
1
0
1
0
1
1
1
0
1
0
0
0
1
1
1
1
1
Из таблицы видно, что теорема истинна при любом
наборе значений Х и Y. Таким образом, доказана
справедливость утверждения «Возможен дождь».
Получение тождественной единицы с помощью
законов
подтверждает
справедливость
доказываемой теоремы.