Лекция №10,11

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

План

1. Введение в логику высказываний. Логические связки.

2. Особенности построения доказательств в логике высказываний.

3. Аксиоматический метод доказательства логических клауз.

4. Конструктивный метод доказательства логических клауз.

5. Доказательство логических клауз принципом резолюций.

6. Доказательство логических клауз методом Вонга.

7. Доказательство логических клауз методом натурального исчисления.

1. Введение в логику высказываний. Логические связки

Логика - это наука о способах доказательства. Логика высказываний (ЛВ) составляет основу математической логики. Она представляет собой грамматиче­ски правильное предложение и определяет способы получения верных умозак­лючений из заданных высказываний А, В, С,... В основу ИВ кладется требова­ние, чтобы его собственные построения, формулируемые в общем виде, были истинными независимо от истинности А, В, С,...

Возьмем два простых высказывания:

А = «На улице идет дождь»

В = «Над моей головой раскрыт зонт»

С помощью пяти основных логических связок можно образовать следую­щие сложные высказывания:

1. Отрицание А = «На улице не идет дождь». Высказывание/! по другому можно прочитать так;

«Истинно то, что на улице идет дождь».

Поэтому, если , A = 0, то это означает, что на улице не идет дождь. Дополняющее

высказывание также ориентируется на истинное высказывание, то есть его следует понимать как:

«Истинно то, что на улице не идет дождь».

Тогда будет означать ту же самую ситуацию, что и в предыдущем случае, то есть отсутствие дождя.

2. Дизъюнкция = «На улице не идет дождь или над моей головой раскрыт зонтик ».

В нашем конкретном примере дизъюнкция двух высказываний в принципе, мо­жет подразумевать и коньюнкцию этих же высказываний. Однако часто грамма­тический союз или не включает в себя союз и. Например, пусть даны два других высказывания:

Р = «Петр находится в кинотеатре»

Q = «Петр находится в бассейне».

Если для нас не столь важно, где находится Петр, то можем использовать союз или с включенным в него союзом и, формально записав:

= «Петр находится в кинотеатре или/и в бассейне»,

Но если нам нужно точно установить, где находится Петр, необходимо исклю­чить случай одновременного присутствия Петра в кинотеатре и бассейне, то есть формально записать:

Подобные высказывания называются строгой дизъюнкцией, которая означает «либо Р, либо Q, но не Р и Q одновременно». Хотя с точки зрения логики Буля, эта операция равносильна операции симметрической разности, исторически сложилось так, что символ « + » в логике высказываний не используется.

3. Конъюнкция = «На улице идет дождь н над моей головой не рас­крыт зонт».

Логический союз и не обязательно должен представляться через грамматический союз и. В частности, приведенное выше выражение можно прочитать несколько иначе:

= «На улице идет дождь, а над моей головой не раскрыт зонт».

Союзы а и но по смыслу часто совпадают с союзом и, поэтому они используются в сложных конъюнктивных предложениях.

4. Импликация А → B = «Если на улице идет дождь, то над моей головой раскрыт зонтик».

Высказывания типа «если А, то В» носят объясняющий характер. Оно как бы разъясняет почему имело место событие В - потому что имело место событие А. Это свойство импликации особенно ценно для логики высказываний.

Объясняющий характер импликации тесно связан с причинно-следственным. отношением, при котором А выступает в роли причины, а В - в роли следствия. Причинно-следственная связь между А и В грамматически мо­жет быть оформлена предложениями: «A является достаточным основанием для B», «В при условии выполнения A» и др. Если под A и B понимать прежние вы­сказывания, то результат причинно-следственного отношения можно оформить таблицей истинности (табл. 10. 1.).

Таблица 10.1.

А	В	А → В	Результат
0	0	1	Останусь сухим
1	0	0	Вымокну
0	1	1	Останусь сухим
1	1	1	Останусь сухим

Вторая строка таблицы говорит об отсутствии причинно-следственного отноше­ния между событиями А и В.

5. Эквивалентность: В ~ А = «Над моей головой раскрыт зонт тогда и только тогда, когда на улице идет дождь».

Высказывание «A эквивалентно В» может быть заменено на «A равно В», «A тогда и только тогда, когда B» и т.д. Так как эквивалентность выражается через конъ­юнкцию двух импликаций:

A ~ B = ( A → B ) ( B → A )

то это отношение часто возникает при одновременном выполнении двух усло­вий: «из А следует В» и «из В следует А» . Таким образом, при эквивалентности двух событий невозможно одному из них приписать роль только причины, а дру­гому - только следствия.