МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ. Язык логики высказываний. Договоренности использования алфавита Алфавит состоит из пропозициональных переменных, - презентация

1 МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ

2 Язык логики высказываний. Договоренности использования алфавита Алфавит состоит из пропозициональных переменных, знаков конъюнкции ( &), дизъюнкции ( |), импликации ( ), отрицания ( ) и скобок, то понятие формулы можно определить так: 1. Всякая пропозициональная переменная есть формула; А и В – формулы(А & В), (А | В), (A B) – формулы 2. Если А и В – формулы, то (А & В), (А | В), (A B) – формулы; А есть формула А – тоже формула 3. если А есть формула, то А – тоже формула. Алфавит состоит из пропозициональных переменных, знаков конъюнкции ( &), дизъюнкции ( |), импликации ( ), отрицания ( ) и скобок, то понятие формулы можно определить так: 1. Всякая пропозициональная переменная есть формула; А и В – формулы(А & В), (А | В), (A B) – формулы 2. Если А и В – формулы, то (А & В), (А | В), (A B) – формулы; А есть формула А – тоже формула 3. если А есть формула, то А – тоже формула.

3 Лекция 2 – логические операции p p p Истина 1 Истина 1 Ложь 0 Истина 1 Истина 1 pq p & qp & qp & qp & q Унарные : 1) отрицание НЕ - Унарные : 1) отрицание НЕ - Бинарные : 1) Конъюнкция И AND & * Бинарные : 1) Конъюнкция И AND & *

4 Лекция 2 – логические операции pq p q p OR q p XOR q Бинарные : 2) Дизъюнкция ИЛИ OR | + Бинарные : 2) Дизъюнкция ИЛИ OR | + pq p q Бинарные : 3) Эквивалентность EQV 3) Эквивалентность EQV Бинарные : 3) Эквивалентность EQV 3) Эквивалентность EQV

5 p посылка q следствие p q Бинарные : 4 А ) Импликация 4 А ) Импликация Бинарные : 4 А ) Импликация 4 А ) Импликация Бинарные : 4 Б ) Обратная импликация 4 Б ) Обратная импликация Бинарные : 4 Б ) Обратная импликация 4 Б ) Обратная импликация p следствие q посылка p q

6 Условное высказывание – сложное высказывание, формулируемое обычно с помощью связки « если …, то …» и устанавливающее, что одно событие, состояние является основанием или условием для другого. То, которому предпослано слово « если », называется основанием, или антецедентом ( предыдущим ); высказывание, идущее после слова « то », называется следствием, или консеквентом ( последующим )., о чем говорится в его основании, имело место, о чем говорится в следствии, отсутствовало. Иными словами, не может случиться, чтобы антецедент был истинным, а консеквент – ложным Условное высказывание – сложное высказывание, формулируемое обычно с помощью связки « если …, то …» и устанавливающее, что одно событие, состояние является основанием или условием для другого. Например : « Если есть огонь, то есть дым », « Если число делится на 9, оно делится на 3» и т. п. Условное высказывание слагается из двух простых высказываний. То, которому предпослано слово « если », называется основанием, или антецедентом ( предыдущим ); высказывание, идущее после слова « то », называется следствием, или консеквентом ( последующим ). Утверждая условное высказывание, мы прежде всего имеем в виду, что не может быть так, чтобы то, о чем говорится в его основании, имело место, а то, о чем говорится в следствии, отсутствовало. Иными словами, не может случиться, чтобы антецедент был истинным, а консеквент – ложным

7 Сводная таблица значений логических операций pqANDORIMPEQV

8 Высказывания-тавтологии Высказывания-тавтологии является истинным при всех распределениях истинностных значений переменных, то оно тавтологией ( или тождественно-истинным высказыванием). Если высказывание (формула) является истинным при всех распределениях истинностных значений переменных, то оно называется тавтологией ( или тождественно-истинным высказыванием). В формальной логике тавтологии играют важную роль - они служат для записи ее законов, так как тавтологии являются всегда истинными высказываниями только в силу своей символической формы, независимо от содержания входящих в них исходных высказываний. В обычном языке слово «тавтология» означает повторение того, что уже было сказано: «Жизнь есть жизнь» или «Не повезет так не повезет». Тавтологии бессодержательны и пусты, они не несут никакой информации. От них стремятся избавиться как от ненужного балласта, загромождающего речь и затрудняющего общение. является истинным при всех распределениях истинностных значений переменных, то оно тавтологией ( или тождественно-истинным высказыванием). Если высказывание (формула) является истинным при всех распределениях истинностных значений переменных, то оно называется тавтологией ( или тождественно-истинным высказыванием). В формальной логике тавтологии играют важную роль - они служат для записи ее законов, так как тавтологии являются всегда истинными высказываниями только в силу своей символической формы, независимо от содержания входящих в них исходных высказываний. В обычном языке слово «тавтология» означает повторение того, что уже было сказано: «Жизнь есть жизнь» или «Не повезет так не повезет». Тавтологии бессодержательны и пусты, они не несут никакой информации. От них стремятся избавиться как от ненужного балласта, загромождающего речь и затрудняющего общение.

9 Если высказывание (формула) на каждой строке таблицы истинности принимает значение ЛОЖЬ, то оно называется противоречием (тождественно ложным высказыванием). Определение. Формула А называется выполнимой, если она принимает значения и 0 и 1. Все формулы алгебры логики можно подразделить на три класса: тавтологии, тождественно ложные и выполнимые. Определение. Две формулы алгебры логики А и В называются равносильными, если они принимают одинаковые логические значения на любом наборе значений входящих в формулы переменных - элементарных высказываний. Равносильность формул будем обозначать знаком, а запись А В означает, что формулы А и В равносильны. Между понятиями равносильности и эквивалентности существует следующая связь: если формулы А и В равносильны, то формула А В - тавтология, и обратно, если формула А В тавтология, то формулы А и В равносильны. Высказывания-противоречия и выполнимые высказывания Равносильность формул

10 Законы логики высказываний. Закон противоречия « Луна спутник Земли » и « Луна не является спутником Земли », « Трава зеленая » и « Неверно, что трава зеленая » Самым популярным является закон противоречия. Закон противоречия говорит о противоречащих друг другу высказываниях. К ним относятся, например, высказывания « Луна спутник Земли » и « Луна не является спутником Земли », « Трава зеленая » и « Неверно, что трава зеленая » и т. п. В одном из противоречащих высказываний что - то утверждается, в другом это же самое отрицается. высказывание и его отрицание не могут быть вместе истинными. Если обозначить буквой А произвольное высказывание, то выражение не - А, будет отрицанием этого высказывания. Идея, выражаемая законом противоречия : высказывание и его отрицание не могут быть вместе истинными. неверно, что А и не - А. Неверно, например, что трава зеленая и не зеленая, что Луна спутник Земли и не спутник Земли. Используя вместо высказываний буквы, эту идею можно передать так : неверно, что А и не - А. Неверно, например, что трава зеленая и не зеленая, что Луна спутник Земли и не спутник Земли. требует непротиворечивости отсюда другое распространенное имя закон непротиворечия. Закон противоречия говорит о противоречащих высказываниях отсюда его название. Но он отрицает противоречие, объявляет его ошибкой и тем самым требует непротиворечивости отсюда другое распространенное имя закон непротиворечия. « Луна спутник Земли » и « Луна не является спутником Земли », « Трава зеленая » и « Неверно, что трава зеленая » Самым популярным является закон противоречия. Закон противоречия говорит о противоречащих друг другу высказываниях. К ним относятся, например, высказывания « Луна спутник Земли » и « Луна не является спутником Земли », « Трава зеленая » и « Неверно, что трава зеленая » и т. п. В одном из противоречащих высказываний что - то утверждается, в другом это же самое отрицается. высказывание и его отрицание не могут быть вместе истинными. Если обозначить буквой А произвольное высказывание, то выражение не - А, будет отрицанием этого высказывания. Идея, выражаемая законом противоречия : высказывание и его отрицание не могут быть вместе истинными. неверно, что А и не - А. Неверно, например, что трава зеленая и не зеленая, что Луна спутник Земли и не спутник Земли. Используя вместо высказываний буквы, эту идею можно передать так : неверно, что А и не - А. Неверно, например, что трава зеленая и не зеленая, что Луна спутник Земли и не спутник Земли. требует непротиворечивости отсюда другое распространенное имя закон непротиворечия. Закон противоречия говорит о противоречащих высказываниях отсюда его название. Но он отрицает противоречие, объявляет его ошибкой и тем самым требует непротиворечивости отсюда другое распространенное имя закон непротиворечия.

11 Законы логики высказываний. Закон Законы логики высказываний. Закон исключенного третьего из двух противоречащих высказываний одно является истинным. Закон исключенного третьего, как и закон противоречия, устанавливает связь между противоречащими друг другу высказываниями. Идея, выражаемая им, представляется поначалу простой и очевидной : из двух противоречащих высказываний одно является истинным. А или не - Аистинно высказывание А или истинно его отрицание, высказывание не - А В полусимволической форме : А или не - А, т. е. истинно высказывание А или истинно его отрицание, высказывание не - А. каждое высказывание является истинным или ложным. Истинность отрицания равнозначна ложности утверждения. В силу этого закон исключенного третьего можно передать и так : каждое высказывание является истинным или ложным. и никакой третьей возможности нет ! Само название закона выражает его смысл : дело обстоит так, как описывается в рассматриваемом высказывании, или так, как говорит его отрицание, и никакой третьей возможности нет ! В сказке А. Н. Толстого « Золотой ключик, или Приключения Буратино » народный лекарь Богомол заключает после осмотра Буратино : Одно из двух : или пациент жив или он умер. Если он жив он останется жив или не останется жив. Если он мертв его можно оживить или нельзя оживить. Одно из двух : или пациент жив или он умер. Если он жив он останется жив или не останется жив. Если он мертв его можно оживить или нельзя оживить. из двух противоречащих высказываний одно является истинным. Закон исключенного третьего, как и закон противоречия, устанавливает связь между противоречащими друг другу высказываниями. Идея, выражаемая им, представляется поначалу простой и очевидной : из двух противоречащих высказываний одно является истинным. А или не - Аистинно высказывание А или истинно его отрицание, высказывание не - А В полусимволической форме : А или не - А, т. е. истинно высказывание А или истинно его отрицание, высказывание не - А. каждое высказывание является истинным или ложным. Истинность отрицания равнозначна ложности утверждения. В силу этого закон исключенного третьего можно передать и так : каждое высказывание является истинным или ложным. и никакой третьей возможности нет ! Само название закона выражает его смысл : дело обстоит так, как описывается в рассматриваемом высказывании, или так, как говорит его отрицание, и никакой третьей возможности нет ! В сказке А. Н. Толстого « Золотой ключик, или Приключения Буратино » народный лекарь Богомол заключает после осмотра Буратино : Одно из двух : или пациент жив или он умер. Если он жив он останется жив или не останется жив. Если он мертв его можно оживить или нельзя оживить. Одно из двух : или пациент жив или он умер. Если он жив он останется жив или не останется жив. Если он мертв его можно оживить или нельзя оживить.

12 Законы логики высказываний. Закон двойного отрицания Законы двойного отрицания позволяют снимать и вводить такое отрицание. Законы двойного отрицания позволяют снимать и вводить такое отрицание. Их можно выразить так : 1) если неверно, что не - А, то А ; 2) если А, то неверно, что не - А. Например : « Если неверно, что Аристотель не знал закона двойного отрицания, то Аристотель знал этот закон », и наоборот. закон тождества. если утверждение истинно, то оно истинно, « если А, то А ». Самый простой из всех логических законов это, пожалуй, закон тождества. Он говорит : если утверждение истинно, то оно истинно, « если А, то А ». Например, если Земля вращается, то она вращается и т. п. Чистое утверждение тождества кажется настолько бессодержательным, что редко кем употребляется. Законы двойного отрицания позволяют снимать и вводить такое отрицание. Законы двойного отрицания позволяют снимать и вводить такое отрицание. Их можно выразить так : 1) если неверно, что не - А, то А ; 2) если А, то неверно, что не - А. Например : « Если неверно, что Аристотель не знал закона двойного отрицания, то Аристотель знал этот закон », и наоборот. закон тождества. если утверждение истинно, то оно истинно, « если А, то А ». Самый простой из всех логических законов это, пожалуй, закон тождества. Он говорит : если утверждение истинно, то оно истинно, « если А, то А ». Например, если Земля вращается, то она вращается и т. п. Чистое утверждение тождества кажется настолько бессодержательным, что редко кем употребляется. Законы логики высказываний. Закон тождества

13 Законы логики высказываний. Законы контрапозиции если первое влечет второе, то отрицание второго влечет отрицание первого. 1) Один из этих законов, называемый иногда законом простой контрапозиции, звучит так : если первое влечет второе, то отрицание второго влечет отрицание первого. Например : « Если верно, что число, делящееся на шесть, делится на три, то верно, что число, не делящееся на три, не делится на шесть ». если верно, что если не - первое, то не - второе, то верно, что если второе, то первое. 2) Другой закон контрапозиции : если верно, что если не - первое, то не - второе, то верно, что если второе, то первое. Если то Если то Например : « Если верно, что рукопись без положительного отзыва не публикуется, то верно, что публикуемая рукопись имеет положительный отзыв ». Или другой пример : « Если нет дыма, когда нет огня, то если есть огонь, есть и дым ». Если то 3) Еще два закона контрапозиции : если дело обстоит так, что если А, то не - В, то если В, то не - А ; например : « Если квадрат не является треугольником, то треугольник не квадрат »; Если то 4) если верно, что если не - А, то В, то если не - В, то А ; например : « Если не являющееся очевидным сомнительно, то не являющееся сомнительным очевидно ». если первое влечет второе, то отрицание второго влечет отрицание первого. 1) Один из этих законов, называемый иногда законом простой контрапозиции, звучит так : если первое влечет второе, то отрицание второго влечет отрицание первого. Например : « Если верно, что число, делящееся на шесть, делится на три, то верно, что число, не делящееся на три, не делится на шесть ». если верно, что если не - первое, то не - второе, то верно, что если второе, то первое. 2) Другой закон контрапозиции : если верно, что если не - первое, то не - второе, то верно, что если второе, то первое. Если то Если то Например : « Если верно, что рукопись без положительного отзыва не публикуется, то верно, что публикуемая рукопись имеет положительный отзыв ». Или другой пример : « Если нет дыма, когда нет огня, то если есть огонь, есть и дым ». Если то 3) Еще два закона контрапозиции : если дело обстоит так, что если А, то не - В, то если В, то не - А ; например : « Если квадрат не является треугольником, то треугольник не квадрат »; Если то 4) если верно, что если не - А, то В, то если не - В, то А ; например : « Если не являющееся очевидным сомнительно, то не являющееся сомнительным очевидно ».

14 Законы логики высказываний. Законы де Моргана Именем английского логика XIX в. А. де Моргана называются логические законы, связывающие с помощью отрицания высказывания, образованные с помощью союзов « и » и « или ». Один из этих законов : отрицание высказывания « А и В » эквивалентно высказыванию « не - А или не - В »., если и только если ( тогда и только тогда ) Например : « Неверно, что завтра будет холодно и завтра будет дождливо, если и только если ( тогда и только тогда ) завтра не будет холодно или завтра не будет дождливо ». неверно, что А и В, если и только если неверно А и неверно В. Другой закон : неверно, что А и В, если и только если неверно А и неверно В., если и только если Например : « Неверно, что ученик знает арифметику и знает геометрию, если и только если он не знает ни арифметики, ни геометрии ». На основе этих законов, используя отрицание, связку « и » можно определить через « или », и наоборот : « А и В » означает « неверно, что не - А или не - В », « А или В » означает « неверно, что не - А и не - В ». Например : « Идет дождь и идет снег » означает « Неверно, что нет дождя или же нет снега »; « Сегодня холодно или сыро » означает « Неверно, что сегодня не холодно и не сыро ». Именем английского логика XIX в. А. де Моргана называются логические законы, связывающие с помощью отрицания высказывания, образованные с помощью союзов « и » и « или ». Один из этих законов : отрицание высказывания « А и В » эквивалентно высказыванию « не - А или не - В »., если и только если ( тогда и только тогда ) Например : « Неверно, что завтра будет холодно и завтра будет дождливо, если и только если ( тогда и только тогда ) завтра не будет холодно или завтра не будет дождливо ». неверно, что А и В, если и только если неверно А и неверно В. Другой закон : неверно, что А и В, если и только если неверно А и неверно В., если и только если Например : « Неверно, что ученик знает арифметику и знает геометрию, если и только если он не знает ни арифметики, ни геометрии ». На основе этих законов, используя отрицание, связку « и » можно определить через « или », и наоборот : « А и В » означает « неверно, что не - А или не - В », « А или В » означает « неверно, что не - А и не - В ». Например : « Идет дождь и идет снег » означает « Неверно, что нет дождя или же нет снега »; « Сегодня холодно или сыро » означает « Неверно, что сегодня не холодно и не сыро ».

15 Законы логики высказываний. Модусы « Модусом » в логике называется разновидность некоторой общей формы рассуждения. Далее будут перечислены четыре близких друг другу модуса, известных еще средневековым логикам. Модус поненс Модус поненс, называемый иногда гипотетическим силлогизмом, позволяет от утверждения условного высказывания и утверждения его основания перейти к утверждению следствия этого высказывания : Если А, то В ; А В Другая запись : Если А, то В. А. Следовательно, В. Благодаря этому модусу от посылки « если А, то В », используя посылку « А », мы как бы отделяем заключение « В ». На этом основании данный модус иногда называется « правилом отделения ». Например : Если у человека диабет, он болен. У человека диабет. Человек болен. Если таллий металл, он проводит электрический ток. Таллий металл. Таллий проводит электрический ток. « Модусом » в логике называется разновидность некоторой общей формы рассуждения. Далее будут перечислены четыре близких друг другу модуса, известных еще средневековым логикам. Модус поненс Модус поненс, называемый иногда гипотетическим силлогизмом, позволяет от утверждения условного высказывания и утверждения его основания перейти к утверждению следствия этого высказывания : Если А, то В ; А В Другая запись : Если А, то В. А. Следовательно, В. Благодаря этому модусу от посылки « если А, то В », используя посылку « А », мы как бы отделяем заключение « В ». На этом основании данный модус иногда называется « правилом отделения ». Например : Если у человека диабет, он болен. У человека диабет. Человек болен. Если таллий металл, он проводит электрический ток. Таллий металл. Таллий проводит электрический ток. Здесь высказывания « если А, то В » и « А » посылки, высказывание « В » заключение. Горизонтальная черта стоит вместо слова « следовательно ».

16 Законы логики высказываний. Модусы Модусом толленсом называется следующая схема рассуждения : Если А. то В ; неверно В Неверно А Если А, то В. Не - В. Следовательно, не - А. Другая запись : Если А, то В. Не - В. Следовательно, не - А. Т. о. от утверждения условного высказывания и отрицания его следствия осуществляется переход к отрицанию основания. « Если гелий металл, он электропроводен. Гелий неэлектропроводен. Следовательно, гелий не металл ». Например : « Если гелий металл, он электропроводен. Гелий неэлектропроводен. Следовательно, гелий не металл ». По схеме модус толленс идет процесс фальсификации, установления ложности теории или гипотезы в результате ее эмпирической проверки. Из проверяемой теории Т выводится некоторое эмпирическое утверждение А, то есть устанавливается условное высказывание « если Т, то А ». Посредством эмпирических методов познания ( наблюдения, измерения или эксперимента ) предложение А сопоставляется с реальным положением дел. Выясняется, что А ложно и истинно предложение не - А. Из посылок « если Т, то А » и « не - А » следует « не - Т », то есть ложность теории Т. Модусом толленсом называется следующая схема рассуждения : Если А. то В ; неверно В Неверно А Если А, то В. Не - В. Следовательно, не - А. Другая запись : Если А, то В. Не - В. Следовательно, не - А. Т. о. от утверждения условного высказывания и отрицания его следствия осуществляется переход к отрицанию основания. « Если гелий металл, он электропроводен. Гелий неэлектропроводен. Следовательно, гелий не металл ». Например : « Если гелий металл, он электропроводен. Гелий неэлектропроводен. Следовательно, гелий не металл ». По схеме модус толленс идет процесс фальсификации, установления ложности теории или гипотезы в результате ее эмпирической проверки. Из проверяемой теории Т выводится некоторое эмпирическое утверждение А, то есть устанавливается условное высказывание « если Т, то А ». Посредством эмпирических методов познания ( наблюдения, измерения или эксперимента ) предложение А сопоставляется с реальным положением дел. Выясняется, что А ложно и истинно предложение не - А. Из посылок « если Т, то А » и « не - А » следует « не - Т », то есть ложность теории Т. Здесь высказывания « если А, то В » и « неверно В » являются посылками, а высказывание « неверно А » заключением.

17 Логическое следствие ЛОГИЧЕСКОЕ СЛЕДСТВИЕ - ЛОГИЧЕСКОЕ СЛЕДСТВИЕ - суждение ( предложение, высказывание, формула ), логически вытекающее ( или, иначе, логически следующее ) из посылок умозаключения ( или из посылок вывода, состоящего из ряда умозаключений ), т. е. выводимое из посылок на основе правил и законов логики. ЛОГИЧЕСКОЕ СЛЕДСТВИЕ ЛОГИЧЕСКОЕ СЛЕДСТВИЕ - суждение ( предложение, высказывание, формула ), полученное посредством дедуктивного рассуждения из некоторых исходных суждений.

18 Дедукция Дедукция ( лат. deductio выведение ) метод мышления, при котором частное положение логическим путём выводится из общего, вывод по правилам логики ; цепь умозаключений ( рассуждений ), звенья которой ( высказывания ) связаны отношением логического следования. Началом ( посылками ) дедукции являются аксиомы или просто гипотезы, имеющие характер общих утверждений (« общее »), а концом следствия из посылок, теоремы (« частное »). Если посылки дедукции истинны, то истинны и её следствия. Дедукция основное средство доказательства. Противоположно индукции методу рассуждения от общего к частному.. Пример дедуктивного умозаключения : Все люди смертны. Сократ человек. Следовательно, Сократ смертен.