5_Исчисление высказываний (Мацнев А.П. - Математическая логика и теория алгоритмов - 2004)

1. Исчисление высказываний.

1. Исчисление высказываний. Основные понятия и определения.

Классическое определение исчисления высказываний.

1. Алфавит: ¬ и → - связки (логический базис Фреге)

(,) - служебные символы.

a, b, ..., a₁, b₁,... - пропозициональные переменные.

2. Формулы: 1)переменные суть формулы.

2)если А,В - формулы, то (¬А) и (А→В) - формулы.

3. Аксиомы: А₁:(A→B(B→A))

A₂:((A→B→C))→((A→B)→(A→C))

A₃:((¬B→¬A)→((¬B→A)→B).

4. Правило: (A, A→B)/B - Modus ponens

Здесь А и В - любые формулы. Таким образом, множество формул бесконечно, хотя задано трёмя схемами аксиом. Множество правил вывода бесконечно, хотя оно задано только одной схемой.

Другие связки вводятся определениями A&B:= ¬(A→¬B);A٧B:= ¬A→B.

Простейшим разделом математической логики является исчисление высказываний. Элементарные высказывания рассматриваются в ней как нерасчленяемые "атомы", а составные высказывания - как молекулы, образованные из "атомов" применением логических операций.

Пусть X, Y и Z - переменные, вместо которых можно подставлять любые элементарные высказывания (или их значения истинности). Такие переменные могут быть названы высказывательными (или булевыми). С помощью высказывательных переменных и символов логических операций любое высказывание можно формализовать, т.е. заменить формулой, выра­жающей его логическую структуру. Например, "Если число делится на 2 и на 5, то оно делится на 10 (X  У)  2”.

Понятие ПФ вводится индуктивно:

1. Символы логических констант 0, 1 являются ПФ.

2. Каждая логическая переменная является ПФ.

3. Если А и В суть ПФ то , А  В, А  В, А  В, А  В также ПФ.

4. Никаких других ПФ в логике высказываний нет.

Определение закончено. В нем 1 и 2 являются базисными пунктами, где указываются объекты множества, 3 - индуктивный пункт, где даны правила получения из базисных объектов новых объектов, которые будут именоваться этим же термином, 4 - косвенный пункт, где указано, что заданный список исчерпывается.

Процедура формализации высказывания состоит из этапов:

1. Если высказывание простое, то ему ставится в соответствие элемен­тарная формула.

2. Если высказывание составное, то нужно:

а) выделить все элементарные высказывания и логические связки, образующие составное высказывание;

б) заменить их соответствующими символами;

в) расставить скобки в соответствии с символами.

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

высказывания. Обычно рассматривают следующие логические связки:

Название Прочтение Обозначение

Отрицание не 

Конъюнкция и &

Дизъюнкция или 

Импликация если ... то 

Формулы.

Правильно построенные составные высказывания называются (пропозициональными) формулами. Формулы имеют следующий синтаксис:

<формула>::=И | Л |

<пропозициональная переменная>|

(<формула>) |

(<формула> & <формула>) |

(<формула>  <формула>) |

(<формула>  <формула>)

Для упрощения записи вводится старшинство связок (,&, , ) и лишние связки не допускаются.

Интерпретация

Пусть A(x₁, ..., x_n) - пропозициональная формула, где x₁, ..., x_n - входящие в нее пропозициональные переменные. Конкретный набор истинности значений, приписанных переменным x₁, ..., x_n, называется интерпретацией формулы А. Формула может быть истинной (иметь значение И) при одной интерпретации и ложной (иметь значение Л) при другой интерпретации. Значение формулы А в интерпретации I будем обозначать I(A). Формула, истинная при некоторой интерпретации, называется выполнимой. Формула, истинная при всех возможных интерпретациях, называется общезначимой (или тавтологией). Формула, ложная при всех возможных интерпретациях, называется невыполнимой (или противоречием).

Пример.

AA – тавтология. A&A – противоречие, A A – выполнимая формула, она истинна при I(A)=Л.

1. Логическое следование. Принцип дедукции.

Говорят, что формула В логически следует из формулы А, если формула В имеет значение И при всех интерпретациях, при которых формула А имеет значение И. Говорят, что формулы А и В логически эквивалентны (обозначается А↔B или просто А=В), если они являются логическим следствием друг друга. Логически эквивалентные формулы имеют одинаковые значения истинности при любой интерпретации.

Наиболее краткий и простой способ вывода основан на теореме дедукции.

Далее вставка 5А.

5.3 Основные схемы логически правильных рассуждений.

Наряду с алфавитом и правилами построения сложных выс­казываний - логических формул, языки логики высказываний содержат правила преобразования логических формул. В алгебре логики - это эквивалентные соотношения, а также правило подстановки и правило замены; в исчислении высказываний - это общие логические аксиомы и правила подстановки и заключения, называемые правилами вывода. Правила преобразования реализуют общие логические законы и обес­печивают логически правильные рассуждения. Корректность допустимых в логике преобразований является фундаменталь­ным свойством формальной (математической) логики.

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

Далее вставка 5В

Процесс получения новых знаний, выраженных высказы­ваниями, из других знаний, также выраженных высказыва­ниями, называется рассуждением (умозаключением). Исход­ные высказывания называются посылками (гипотезами, ус­ловиями), а получаемые высказывания – заключением (следствием).

Приведем примеры наиболее употребляемых схем логически правильных рассуждений:

1. Правило заключения - утверждающий модус (Modus Ponens):

"Если из высказывания А следует высказывание В и справедливо (истинно) высказывание А, то справедливо В" ( Способ спуска). Обозначается:

.

2. Правило отрицания - отрицательный модус (Modus Tollens):

"Если из А следует В, но высказывание В неверно, то неверно А” (Доказательство от противного). Обозначается:

.

3. Правила утверждения-отрицания (Modus Ponendo-Tollens):

"Если справедливо или высказывание А, или высказыва­ние В (в разделительном смысле) и истинно одно из них, то другое ложно" (разделительный силлогизм). Обозначается:

; .

4. Правила отрицания-утверждения (Modus Tollen-Ponens):

а) "Если истинно или А или В (в разделительном смыс­ле) и неверно одно из них, то истинно другое":

; .

б) "Если истинно А или В (в неразделительном смысле) и неверно одно из них, то истинно другое" (Дизъюнктивный силлогизм). Обозначается:

; .

5. Правило транзитивности (упрощенное правило силло­гизма):

"Если из А следует В, а из В следует С, то из А следует С" (гипотетический силлогизм). Обозначается:

.

6. Закон противоречия:

"Если из А следует В и ¬В, то неверно А":

.

7. Правило контрапозиции:

"Если из А следует В, то из того, что неверно В, следует, что неверно А":

.

8. Правило сложной контрапозиции:

"Если из А и В следует С, то из А и ¬С следует ¬В":

.

9. Правило сечения:

"Если из А следует В, а из В и С следует D, то из А и С следует D":

.

Приведем без пояснений еще несколько правил умозак­лючений.

10. Правило импортации (объединения посылок):

.

11. Правило экспортации (разъединения посылок):

.

12. Правила дилемм:

а) (простая конструктивная дилемма);

б) (сложная конструктивная дилемма);

в) (простая деструктивная дилемма);

г) (сложная деструктивная дилемма).

Примечание. Для построения логических формул, отражающих указан­ные выше логически правильные рассуждения, следует все посылки соеди­нить связкой "И" (&) и полученную таким образом обобщенную посылку - связкой "если ..., то ..." (→).Например, правило заключения (Modus Ponens) должно быть представлено логической формулой:

.