🗊Презентация Логика высказываний

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

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

Пример. Пример. «Волга впадает в Черное море»- ложное высказывание; «Волга впадает в Каспийское море»- истинное высказывание; «Какой сегодня день?»- не высказывание; «Расстояние от Земли до Солнца равно 150 млн. км»- не высказывание.

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

Отрицание A истинно тогда и только тогда, когда A ложно. Отрицание A истинно тогда и только тогда, когда A ложно.

Если A и B – высказывания, то высказывание A  B, называемое дизъюнкцией A и B, ложно тогда и только тогда, когда ложны оба высказывания A и B. Если A и B – высказывания, то высказывание A  B, называемое дизъюнкцией A и B, ложно тогда и только тогда, когда ложны оба высказывания A и B. Употребляется в смысле «неисключающее или».

Если A и B – высказывания, то высказывание AB, называемое конъюнкцией A и B, истинно тогда и только тогда, когда истинны оба высказывания A и B. Если A и B – высказывания, то высказывание AB, называемое конъюнкцией A и B, истинно тогда и только тогда, когда истинны оба высказывания A и B. Соответствует связке «и», соединяющей два предложения.

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

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

Если A и B – высказывания, то высказывание A~B истинно тогда и только тогда, когда A и B либо оба истинны, либо оба ложны. Если A и B – высказывания, то высказывание A~B истинно тогда и только тогда, когда A и B либо оба истинны, либо оба ложны.

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

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

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

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

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

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

Формула В является логическим следствием формулы А, если на всех тех наборах атомов, которые входят в А или В при которых А имеет истинное значение, формула В также истина. Формула В является логическим следствием формулы А, если на всех тех наборах атомов, которые входят в А или В при которых А имеет истинное значение, формула В также истина. Теоремы – это формулы, которые являются логическим следствием множества аксиом данного исчисления. Теоремы исчисления высказываний являются тождественно истинными формулами.

Пример. Пример. Определить, является ли высказывание (AB)C логическим следствием высказывания AC. Решение. (AC)((AB)C)= = (AC)((AB)C)= = AC(AB)C= = A(AB)CC= = A(AB)И = = И

Дедуктивным выводом называется вывод формулы B из формулы A, основанный на том, что B является логическим следствием A. Дедуктивным выводом называется вывод формулы B из формулы A, основанный на том, что B является логическим следствием A.

Доказать правильность рассуждения по дедукции: «Резолюция принимается, если за нее голосует большинство депутатов. За резолюцию не проголосовало большинство депутатов, поэтому резолюция не принимается». Доказать правильность рассуждения по дедукции: «Резолюция принимается, если за нее голосует большинство депутатов. За резолюцию не проголосовало большинство депутатов, поэтому резолюция не принимается».

В математике и «чистой» логике доказывают теоремы, т.е. выводят следствия из определенных допущений. В математике и «чистой» логике доказывают теоремы, т.е. выводят следствия из определенных допущений. Допущения называются аксиомами или гипотезами, при этом предполагается, что они тождественно истинны во всей рассматриваемой теории. Доказательство представляет собой логический вывод списка высказываний.

Правила для дедуктивного вывода строятся на основе общезначимых формул логики высказываний вида AB. Эти правила часто записывают как правила формального вывода в следующем виде: Правила для дедуктивного вывода строятся на основе общезначимых формул логики высказываний вида AB. Эти правила часто записывают как правила формального вывода в следующем виде: A1, ..., An – посылки вывода; B – следствие. Тавтология, соответствующая такому правилу – A1A2 ... AnB=1.

Правило введения дизъюнкции. Правило введения дизъюнкции. Правило дедуктивного вывода: P  P  Q Тавтология: P  ( P  Q)

2.Правило введения конъюнкции. 2.Правило введения конъюнкции. Правило дедуктивного вывода: P, Q  P  Q Тавтология: ((P)(Q))  (PQ)

3. Правило удаления дизъюнкции 3. Правило удаления дизъюнкции (Дизъюнктивный силлогизм). Правило дедуктивного вывода: P  Q P  Q Тавтология: (P  Q)  P  Q

4. Правило удаления конъюнкции. 4. Правило удаления конъюнкции. Правило дедуктивного вывода: P  Q  P Тавтология: (PQ)  P

5. Правило контрапозиции импликации. 5. Правило контрапозиции импликации. Правило дедуктивного вывода: PQ  QP Тавтология: (PQ)  (QP)

6. Правило отделения (Modus Ponens). 6. Правило отделения (Modus Ponens). Правило дедуктивного вывода: PQ P  Q Тавтология: (P(PQ))Q

7. Отрицательная форма правила отделения (Modus Tollens). 7. Отрицательная форма правила отделения (Modus Tollens). Правило дедуктивного вывода: Q PQ  P Тавтология: (Q(PQ)) P

8. Гипотетический силлогизм. 8. Гипотетический силлогизм. Правило дедуктивного вывода: P  Q Q  R  P  R Тавтология: ((PQ) (QR)) (PR)

Правило отделения имеет следующий логический смысл: если посылка верна, то верно и следствие из нее. Правило отделения имеет следующий логический смысл: если посылка верна, то верно и следствие из нее.

Пример. Пример. Получить логический вывод из высказываний F1 и F2, используя правило отделения. F1 = (AB) C, F2 = (AB). Решение. Пусть (AB) = D, C = G. (D(DG))G (AB) C(AB) C