Логика Тема 3. «Классическая логика высказываний»

Язык логики высказываний и семантика логических союзов Пропозициональные переменные – p, q, r, s, t, p 1,q 1,… Логические союзы (пропозициональные связки) Логический союз Аналог в естественном языке Знак Коньюнкция«и» &,, (p q) Слабая дизъюнкция«или» p q Строгая дизъюнкция«либо…, либо…», p q Импликация«если …, то …», (p q) Эквиваленция«… тогда и только тогда, когда …», (p q) Отрицание«не …», «не верно, что …»,, p Технические знаки – (, ). А.И.Мигунов

Определение формулы логики высказываний 1. Пропозициональная переменная есть формула; 2. если А – формула, то А тоже формула; 3. если А – формула и В – формула, то (А В), (А В), (А В), (А В), (А В) – тоже формулы; 4. любая последовательность знаков из алфавита языка логики высказываний есть формула только в силу пунктов 1, 2, 3 данного определения. А.И.Мигунов

A B p q (p r) q ((p q) p) (q r) Метаязык

Построение дерева формулы ((A B) A) B C () САВАВ (A B) ((A B) A) (B C) ((A B) A) (B C) А.И.Мигунов

Семантика логических союзов А.И.Мигунов

p q q t Студент A должен сдать все экзамены вовремя или взять академический отпуск, и, если он берет академический отпуск, то сможет продолжить обучение в следующем году. Студент A должен сдать все экзамены вовремя - p Студент A должен взять академический отпуск - q Студент A сможет продолжить обучение в следующем году – t ()()

Или Сэм пойдет на вечеринку, и Макс не пойдет на нее, или Сэм не пойдет на вечеринку, и Макс отлично проведет время (p q) ( p r) Необходимые и достаточные условия счастья для шейха состоит в том, чтобы иметь вино, женщин и услаждать свой слух пением. p (q r s)

Таблицы истинности формул логики высказываний АВ А А В ИИЛЛ ИЛЛЛ ЛИИИ ЛЛИЛ Некто А говорит: «Я лжец, а В не лжец». Кто А и кто В? «А рыцарь» – А «А лжец» - А А В А.И.Мигунов

Некто A говорит: «Если я рыцарь, то съем свою шляпу» A рыцарь – A А ест шляпу - C A C АС А С ИИИ ИЛЛ ЛИИ ЛЛИ

«Это была первая наша встреча с Планом. В тот день я мог бы оказаться в совершенно другом месте. Если бы в тот день я не встретился на улице с Бельбо, сейчас бы я мог... Продавать на рынке в Самарканде кунжутное семя. Готовить в печать издания произведений классической литературы для слепых по Брайлю. Возглавлять филиал Ферст Нейшнл Бэнк на Земле Франца Иосифа... Условно-противительные предложения с недостоверной посылкой всегда истинны, благодаря тому что ирреальна предпосылка. Но в тот день я был не где-нибудь, а там, так что теперь я действительно здесь» У. Эко Маятник Фуко АС А С ИИИ ИЛЛ ЛИИ ЛЛИ

Если я рыцарь, то 2 х 2 = 4 А И АИ ИИИ ЛИИ Если я рыцарь, то 2 х 2 = 5 А Л АЛ ИЛЛ ЛЛИ

«Сокровища на острове есть в том и только в том случае, если я рыцарь» AS A S ИИИ ИЛЛ ЛИЛ ЛЛИ

Пример 1 Где сидит принцесса? 1 По крайней мере, в одной из этих комнат находится принцесса 2 Тигр сидит в другой комнате Истинны ли утверждения на дверях комнат? - спросил узник Может, оба истинны, а может, оба ложны, - ответил король. Принцесса в комнате 1 - p 1 Принцесса в комнате 2 - p 2 Тигр в комнате 1 - t 1 (p 1 v p 2 ) t 1 А.И.Мигунов

p1p1 p2p2 t1t1 p 1 p 2 (p 1 p 2 ) t 1 ИИИИИ ИИЛИЛ ИЛИИИ ИЛЛИЛ ЛИИИИ ЛИЛИЛ ЛЛИЛЛ ЛЛЛЛИ Где сидит принцесса? (p 1 v p 2 ) t 1

Либо свидетель не был запуган, либо, если Генри покончил жизнь самоубийством, то записка была найдена. Если свидетель был запуган, то Генри не покончил жизнь самоубийством. Если записка была найдена, то Генри покончил жизнь самоубийством. Свидетель был запуган - p Генри покончил жизнь самоубийством - q Записка была найдена - r ~p (q r) (r q) (p ~q)(r q)(~p (q r)) (p ~q)

pqr p qq rp qr q ИИИЛЛИИЛИЛ ИИЛЛЛЛЛЛИЛ ИЛИЛИИ И ИЛЛ ИЛЛЛИИИИЛЛ ЛИИИЛИЛИИЛ ЛИЛИЛЛИИИИ ЛЛИИИИЛИЛЛ ЛЛЛИИИЛИИЛ (p q) (r q) ( p (q r)) p (q r) p - Свидетель был запуган q - Генри покончил жизнь самоубийством r - Записка была найдена Свидетель не был запуган Генри покончил жизнь самоубийством Записка не была найдена

Если магнит нагревать, то он размагнитится. Этот магнит нагревали, следовательно, он размагничен. ((A B) A) B АВ A B((A B) A((A B) A) B ИИИИИ ИЛЛЛИ ЛИИЛИ лЛИЛИ А.И.Мигунов

Только «и»Хотя бы одно значение «и» Хотя бы одно значение «л» Только «л» Т.-и., общезначимые Нейтральные Т.-л., невыполнимые выполнимые необщезначимые

Отношение логического следования Формула В логически следует из формул А 1, А 2,…, А n (А 1, А 2, …, А n В), если и только если в каждой пропозициональной интерпретации, в какой все формулы А 1, А 2, …, А n принимают значение «и», формула В также есть «и». p q q p А 1, А 2 В А.И.Мигунов

Отношение логического следования (Теорема дедукции) Задача установления того, следует ли высказывание В из высказываний А 1, А 2,…, А n (имеет ли место А 1, А 2, …, А n В) сводится к задаче выяснения является ли высказывание (( А 1 А 2 … А n ) В) тождественно-истинным (тавтологией, законом логики). А.И.Мигунов Формула логики высказываний является тождественно-истинной формулой, если при любых интерпретациях вхордящих в ее состав пропозициональных переменных она принимает значение «истина».

p q q p Отношение логического следования Формула В логически следует из формул А 1, А 2,…, А n (А 1, А 2, …, А n В), если и только если в каждой пропозициональной интерпретации, в какой все формулы А 1, А 2, …, А n принимают значение «и», формула В также есть «и». А 1, А 2 В (А 1 А 2 ) В ((p q) q) p А.И.Мигунов

pq p qp q(p q) q((p q) q) p ИИЛЛИЛИ ИЛЛИЛЛИ ЛИИЛИЛИ ЛЛИИИИИ А.И.Мигунов p q q p

Основные модусы логики высказываний MODUS TOLLENS A B B A ((A B) B) A MODUS PONENS A B A B ((A B) A) B АВ A B ИИИ ИЛЛ ЛИИ ЛЛИ А.И.Мигунов АВ A BA B ИИЛЛИ ИЛЛИЛ ЛИИЛИ ЛЛИИИ

Если магнит нагревать, то он размагнитится. Этот магнит нагревали, следовательно, он размагничен. ((A B) A) B АВ A B((A B) A((A B) A) B ИИИИИ ИЛЛЛИ ЛИИЛИ лЛИЛИ А.И.Мигунов

АВ A B ИИИ ИЛЛ ЛИИ ЛЛИ В А ? А.И.Мигунов ((A B) B((A B) B) A ИИ ЛИ ИЛ ЛИ

Я заплатил бы за работу по ремонту телевизора, если бы он стал работать. Он же не работает. Поэтому я платить не буду. Я плачу за работу по ремонту телевизора – p Телевизор работает - r r p, r p ((r p) r) p

rp r pr p(r p) r((r p) r) p ИИЛЛИЛИ ИЛЛИЛЛИ ЛИИЛИИЛ ЛЛИИИИИ

Необходимые и достаточные условия Я плачу за ремонт телевизора, если он работает. P – я плачу за ремонт R – телевизор работает Если R, то P R P Если P, то R P R RP R P иии илл лии ли PR P R иии илл лии ли

Необходимые и достаточные условия P R P R P R R P (?) P R ~R ~P P R ~P ~R (?)

MODUS TOLENDO PONENS A B A B ((A B) A) B MODUS PONENDO TOLLENS A B А В ((A B) А) В А.И.Мигунов Основные модусы логики высказываний АВ А ВA B А В ИИЛЛИЛ ИЛЛИИИ ЛИИЛИИ ЛЛИИЛЛ

ПРОСТАЯ КОНСТРУКТИВНАЯ ДИЛЕММА A B C B A C B ((A B) (C B) (A C)) B СЛОЖНАЯ КОНСТРУКТИВНАЯ ДИЛЕММА A B C D A C B D ((A B) (C D) (A C)) (B D) Основные модусы логики высказываний

ПРОСТАЯ ДЕСТРУКТИВНАЯ ДИЛЕММА A B A D ~B ~D ~A ((A B) (A D) (~B ~D)) ~A СЛОЖНАЯ ДЕСТРУКТИВНАЯ ДИЛЕММА A B C D ~B ~D ~A ~C ((A B) (C D) (~B ~D)) (~A ~C) Основные модусы логики высказываний

СЛОЖНАЯ КОНСТРУКТИВНАЯ ДИЛЕММА A B C D A C B D ((A B) (C D) (A C)) (B D) «Если ваши книги согласуются с Кораном, то они излишни. Если ваши книги не согласуются с Кораном, то они вредны. Но они либо согласуются с Кораном, либо нет. Следовательно, они либо излишни, либо вредны» А.И.Мигунов

Зенон: Если тело находится в движении, то оно должно двигаться или там, где оно есть, или там, где его нет. Но тело не может двигаться ни там, где оно есть, ни там, где его нет. Следовательно, оно вообще не может двигаться, т.е. движение невозможно» ПРОСТАЯ ДЕСТРУКТИВНАЯ ДИЛЕММА p (q r) ~(q r) ~p ((p (q r)) ~(q r)) ~p ? A B B A ((A B) B) A А.И.Мигунов Modus Tollens