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

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

ВЫСКАЗЫВАНИЯ элементарные сложные (составные) Примеры высказываний: * Великий Новгород стоит на Волхве * Париж – столица Англии * Если юноша окончил среднюю школу, то он получает аттестат зрелости.

Логические операции над высказываниями 1. Отрицание 2. Конъюнкция 3. Дизъюнкция 4. Импликация 5. Эквивалентность

1. Отрицание отрицанием двух высказываний X называется такое новое высказывание, которое является истинным, если высказывание X ложно и ложным – если X – истина. Читается: «не икс» «не верно, что X…» … Построим таблицу истинности X¬ X 10 01

2. Конъюнкция (логическое умножение) конъюнкцией двух высказываний X и Y называется новое высказывание, которое считается истинным, если оба высказывания X, Y – истинны и ложным, если хотя бы одно из них ложь. (читается – «X и Y») Построим таблицу истинности XY X ˄ Y

3. Дизъюнкция (логическое сложение) дизъюнкцией двух высказываний X, Y – называется новое высказывание, которое считается истинным, если хотя бы одно из высказываний X, Y – истина, или ложным, если они оба ложны (читается – «X или Y») Построим таблицу истинности XY X ˅ Y

4. Импликация (наложение) из двух высказываний X, Y называется новое высказывание, которое считается ложным, если X – истина, а Y – ложно, и истинным во всех остальных случаях (читается – «из X следует Y», «если X, то Y» и т.д.) Построим таблицу истинности XYX Y

5. Эквиваленция эквиваленцией двух высказываний X, Y называется новое высказывание, которое считается истинным, когда оба высказывания X, Y либо одновременно истинны, либо одновременно ложны, и ложны в остальных случаях (читается – «X тогда и только тогда, когда Y») Построим таблицу истинности XYX Y

Формулы алгебры логики С помощью логических операций над высказываниями можно строить сложные высказывания. Формулы алгебры логики обозначают большими буквами A, B, C и т.д. Для упрощения формул принят ряд соглашений: 1. Конъюнкция выполняется раньше, чем все остальные операции 2. Дизъюнкция выполняется раньше, чем эквиваленция и импликация 3. Если над формулой стоит знак отрицания, то скобки можно опустить Логические значения формулы полностью определяются логическими значениями входящих в нее элементарных высказываний. Если формула содержит n элементарных высказываний, то она принимает 2 n значений, состоящих из 0 и 1

Равносильные формулы алгебры логики Две формулы алгебры логики A и B называются равносильными, если они принимают одинаковые логические значения на любом наборе значений, входящих в формулы элементарных высказываний. Формула А называется тождественно истинной (или тафталогией), если она принимает значение 1 при всех значениях входящих в нее переменных. Формула А называется тождественно ложной, если она принимает значение 0 при всех значениях входящих в нее переменных. Отношение равносильности рефлексивно, симметрично и транзитивно.

Важнейшие равносильности алгебры логики I. Основные равносильности 1) X ˄ X X 2) X ˅ X X 3) X ˄ истина X 4) X ˅ истина истина 5) X ˄ ложь ложь 6) X ˅ ложь X 7) X ˄ ¬X ложь – закон противоречия 8) X ˅ ¬X истина – закон исключенного третьего 9) ¬¬X X – Закон снятия двойного отрицания 10) X ˄ (Y ˅ X) X 11) X ˅ (Y ˄ X) X

Важнейшие равносильности алгебры логики II. Равносильности, выражающие одни логические операции через другие: 1) X Y (X Y) ˄ (Y X) 2) X Y ¬X ˅ Y 3) ¬(X ˄ Y) ¬ X ˅ ¬Y 4) ¬(X ˅ Y) ¬ X ˄ ¬Y 5) X ˄ Y ¬(¬ X ˅ ¬ Y) 6) X ˅ Y ¬(¬ X ˄ ¬ Y)

Важнейшие равносильности алгебры логики III. равносильности, выражающие основные законы алгебры логики 1) X ˄ Y Y ˄ X – коммутативность конъюнкции 2) X ˅ Y Y ˅ X – коммутативность дизъюнкции 3) X ˄ (Y ˄ Z) (X ˄ Y) ˄ Z – ассоциативность конъюнкции 4) X ˅ (Y ˅ Z) (X ˅ Y) ˅ Z – ассоциативность дизъюнкции 5) X ˄ (Y ˅ Z) (X ˄ Y) ˅ (X ˄ Z) – дистрибутивность конъюнкции относительно дизъюнкции 6) X ˅ (Y ˄ Z) (X ˅ Y) ˄ (X ˅ Z) – дистрибутивность дизъюнкции относительно конъюнкции