Математическая логика и теория алгоритмов
|
1.1 Логика высказываний |
назад | оглавление | вперёд |
       Под высказыванием принято понимать языковое предложение, о котором имеет смысл говорить, что оно истинно или ложно. Примерами высказываний могут служить следующие предложения:
       Например, повествовательное предложение "Я лгу" не может быть высказыванием (парадокс лжеца). Действительно, если бы это предложение было верным, то по смыслу оно было бы ложным. А если бы предложение было бы ложным, то по смыслу оно должно быть истинным. Но ни то, ни другое для высказывания невозможно, так как оно не может быть одновременно и истинным, и ложным. Этот пример показывает, насколько внимательно следует относиться к принимаемым определениям (в данном случае - к определению высказывания).
        В логике высказываний интересуются не содержанием, а истинностью или ложностью высказываний. Истинностное значение – истина или ложь – будем обозначать И и Л соответственно. Для соединения высказываний в более сложные высказывания используют следующие логические операции (связки).
        Отрицанием высказывания A называется высказывание, истинное тогда и только тогда, когда высказывание A ложно. Обозначается ¬A. В естественном языке отрицание ¬A соответствует следующим конструкциям:
       Конъюнкцией двух высказываний A и
B называется высказывание, истинное тогда и только тогда,
когда истинны оба высказывания. Обозначается .
В естественном языке конъюнкция
соответствует следующим конструкциям:
       Алфавит логики высказываний содержит следующие символы: высказывательные переменные – обычно заглавные латинские буквы; логические символы, символы скобок (, ).
       Последовательность символов в логике высказываний называется формулой, если она удовлетворяет следующему определению:
Пример 1. Выражение является формулой, поскольку
получено при помощи логической связки →
из двух подформул
. Каждая из подформул представляет
собой логическую связку двух переменных.
Пример 2.
Выражение не является формулой, поскольку
логическая связка →
связывает два выражения
. Первое выражение не является
формулой, поскольку не получено по правилам 1–3, т.е. не удовлетворяет определению формулы.
Пример 3.
Перевести следующее высказывание в логическую символику:
Я заплачу за работу по ремонту телевизора, если он будет
работать.
       Выделим отдельные высказывания, встречающиеся в данном
высказывании и обозначим их переменными:
       Если каждой высказывательной переменной, входящей в формулу, придать истинностное значение И или Л, то формула будет определять истинностную функцию, т.е. функцию, определенную на множестве высказывательных переменных со значениями в множестве {И, Л}. Если, кроме того, принять И=1, Л=0, то любую формулу логики высказываний можно интерпретировать как формулу логики переключательных функций. По аналогии с переключательными функциями, для любого высказывания можно построить таблицу истинности.
Пример 4.
Построим таблицу истинности для формулы .
       
       Упорядоченный набор высказывательных
переменных
назовем списком переменных формулы A, если все переменные
формулы A содержатся в этом наборе. В списке переменных
формулы A часть переменных может быть фиктивной, т.е. может не
входить явно в формулу A. Очевидно, что если список переменных
для формулы A содержит k переменных, то таблица
истинности для формулы A будет содержать 2 k строк.
       
Пусть формула A зависит от списка
переменных . Дадим несколько определений:
Теорема. Справедливы следующие логические эквивалентности для алгебры высказываний (1 и 0 – тождественно истинное и тождественно ложное высказывания соответственно):
Теорема (о логическом следствии двух формул). тогда и только тогда, когда
– тавтология.
тогда и только тогда, когда
– противоречие.
Доказательство.
Докажем первое утверждение.