Литература:
В.Игошин «Математическая логика и теория алгоритмов».
П.С.Новиков «Элементы математической логики».
Э.Мендельсон «Введение в математическую логику».
И.А.Лавров, Л.Л.Максимовы «Сборник задач по теории множеств, математической логике и теории алгоритмов».
Алгебра высказываний.
Логические операции.
Изучение математической логики начнем с алгебры высказываний. Знакомство с законами алгебры высказываний очень облегчает изучение тех логических исчислений, с которыми мы встретимся в дальнейшем.
Определение:
Алгебра – это не пустое множество, замкнутое относительно каких-то операций.
Примеры:
<N, +, * > - арифметика натуральных чисел;
<U,∩,U,\ > - алгебра множеств;
<V2,
,λ>векторная
алгебра.
V – множество высказываний (A,B,C…).
Высказывание величина, которых может принимать два значения: «истина» и «ложь» (И, Л).
Примеры:
«собака – животное» - И;
«Париж – столица Италии» - Л.
Определим над множеством высказываний операции, которые позволяют из данных высказываний получать новые. Эти операции есть связки, употребительные в обычной речи: «и», «или», «если…, то..» и другие. Пусть даны два произвольных высказывания A и B.
Операция отрицания – «не». Обозначим ¬А – «не А». если А - истинно, то ¬А – ложно, и наоборот, если А – ложно, то ¬А – истинно:
А
¬А
И
Л
Л
И
Операция конъюнкции – «и». Обозначается – АΛВ. Действие операции определяется так: сложное высказывание АΛВ истинно в том и только в том случае, если оба высказывания А и В имеют значение И.
Операция конъюнкции называется также логическим умножением и обозначается «∙» или не обозначается.
-
А
В
АΛВ
И
И
И
И
Л
Л
Л
И
Л
Л
Л
Л
Операция дизъюнкции – «или». Обозначается АVВ. Действие операции определяется так: сложное высказывание АVВ ложно в том только в том случае, если ложны оба высказывания.
Операция дизъюнкции называются логическим сложением, и употребляется знак «+».
-
А
В
АVВ
И
И
И
И
Л
И
Л
И
И
Л
Л
Л
Операция импликации – «если…,то…». Обозначается А→В, читается «А имплицирует В», «если А. то В». А называется посылкой, В – следствием. Сложное высказывание "А→В ложно тогда и только тогда, когда А истинно, а В ложно.
А
В
А→В
И
И
И
И
Л
Л
Л
И
И
Л
Л
И
Операция эквивалентности. Обозначается «А~В», читается «А эквивалентно В». Сложное высказывание «А~В» истинно тогда и только тогда, когда оба высказывания А и В истинны или ложны.
-
А
В
А~В
И
И
И
И
Л
Л
Л
И
Л
Л
Л
И
Пусть A, B, C, X, Y, Z произвольные высказывания, принимающие одно из значений истина или ложь. При помощи операций ¬, Λ, V, →, ~ - мы можем образовать различные сложные высказывания, например:
X→(YVZ),
¬(X~A),
¬(X→Y) →(XV¬(AΛB)).
Определение:
Всякое сложное высказывание, составленное из некоторых исходных высказываний посредством применения логических операций 1-5, будем называть формулой алгебры высказываний.
Каждая формула определяет некоторую функцию, аргументами которой являются переменные элементарные высказывания. Так как аргументы и функции способны принимать только два различных значения, то такая функция может быть полностью описана конечной таблицей.