Математическая логика и теория алгоритмов

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

назад | оглавление | вперёд

 

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

       Не всякое предложение может быть истинным или ложным, а значит, быть высказыванием. Так, вопросительное или повелительное предложение не является высказыванием.

       Например, повествовательное предложение "Я лгу" не может быть высказыванием (парадокс лжеца). Действительно, если бы это предложение было верным, то по смыслу оно было бы ложным. А если бы предложение было бы ложным, то по смыслу оно должно быть истинным. Но ни то, ни другое для высказывания невозможно, так как оно не может быть одновременно и истинным, и ложным. Этот пример показывает, насколько внимательно следует относиться к принимаемым определениям (в данном случае - к определению высказывания).

        В логике высказываний интересуются не содержанием, а истинностью или ложностью высказываний. Истинностное значение – истина или ложь – будем обозначать И и Л соответственно. Для соединения высказываний в более сложные высказывания используют следующие логические операции (связки).

        Отрицанием высказывания A называется высказывание, истинное тогда и только тогда, когда высказывание A ложно. Обозначается ¬A. В естественном языке отрицание ¬A соответствует следующим конструкциям:

       Конъюнкцией двух высказываний A и B называется высказывание, истинное тогда и только тогда, когда истинны оба высказывания. Обозначается . В естественном языке конъюнкция соответствует следующим конструкциям:

        Дизъюнкцией двух высказываний A и B называется высказывание, ложное тогда и только тогда, когда оба высказывания ложны. Обозначается . В естественном языке дизъюнкция соответствует следующим конструкциям:        Импликацией двух высказываний A и B называется высказывание, ложное тогда и только тогда, когда A истинно, а B ложно. Обозначается . В естественном языке импликация соответствует следующим конструкциям:        Эквиваленцией двух высказываний A и B называется высказывание, истинное тогда и только тогда, когда истинностные значения A и B совпадают. Обозначается . В естественном языке эквиваленция соответствует следующим конструкциям:        Можно попытаться прочесть полученные высказывания, когда A - это высказывание "Солнце взошло", а B - высказывание "Птицы смолкли".

       Алфавит логики высказываний содержит следующие символы: высказывательные переменные – обычно заглавные латинские буквы; логические символы, символы скобок (, ).

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

  1. любая высказывательная переменная – формула;
  2. если A и B – формулы, то – формулы;
  3. других формул нет.
       Для упрощения записи вводится приоритет операций и лишние скобки опускаются.

Пример 1. Выражение является формулой, поскольку получено при помощи логической связки → из двух подформул . Каждая из подформул представляет собой логическую связку двух переменных.

Пример 2. Выражение не является формулой, поскольку логическая связка → связывает два выражения . Первое выражение не является формулой, поскольку не получено по правилам 1–3, т.е. не удовлетворяет определению формулы.

Пример 3. Перевести следующее высказывание в логическую символику: Я заплачу за работу по ремонту телевизора, если он будет работать.
       Выделим отдельные высказывания, встречающиеся в данном высказывании и обозначим их переменными:

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

       Если каждой высказывательной переменной, входящей в формулу, придать истинностное значение И или Л, то формула будет определять истинностную функцию, т.е. функцию, определенную на множестве высказывательных переменных со значениями в множестве {И, Л}. Если, кроме того, принять И=1, Л=0, то любую формулу логики высказываний можно интерпретировать как формулу логики переключательных функций. По аналогии с переключательными функциями, для любого высказывания можно построить таблицу истинности.

Пример 4. Построим таблицу истинности для формулы .
       

       Упорядоченный набор высказывательных переменных назовем списком переменных формулы A, если все переменные формулы A содержатся в этом наборе. В списке переменных формулы A часть переменных может быть фиктивной, т.е. может не входить явно в формулу A. Очевидно, что если список переменных для формулы A содержит k переменных, то таблица истинности для формулы A будет содержать 2 k строк.

        Пусть формула A зависит от списка переменных . Дадим несколько определений:


Теорема. Имеют место следующие логические эквивалентности: .
Доказательство проводится сравнением таблиц истинности двух формул.
       Теорема доказана.

Теорема. Справедливы следующие логические эквивалентности для алгебры высказываний (1 и 0 – тождественно истинное и тождественно ложное высказывания соответственно):

  1. Закон двойного отрицания
  2. Законы коммутативности
  3. Законы ассоциативности
  4. Законы дистрибутивности
  5. Законы идемпотентности
        
  6. Законы де Моргана
        
  7. Законы нуля и единицы
        
  8. Законы поглощения
        
  9. Закон противоречия
        
  10. Закон исключенного третьего
        
       Теорема доказана.

Теорема (о логическом следствии двух формул). тогда и только тогда, когда – тавтология. тогда и только тогда, когда – противоречие.
Доказательство. Докажем первое утверждение.

       Теорема доказана.
назад | оглавление | вперёд