«Автоматизированные системы обработки информации и управления»

Практическое занятие № 1 «Формулы алгебры высказываний» 3

Практическое занятие № 2 «Равносильные преобразования формул алгебры высказываний» 10

Практическое занятие № 3 «Нормальные формы формул» 12

Практическое занятие № 5 «Формулы логики предикатов» 18

Практическое занятие № 7 «Частично рекурсивные функции» 28

Учение о высказываниях – алгебра высказываний, или алгебра логики, – является простейшей логической теорией. Атомарным понятием алгебры высказываний является высказывание– повествовательное предложение, в отношении которого имеет смысл утверждение об его истинности или ложности.

Пример истинного высказывания: "Земля вращается вокруг Солнца". Пример ложного высказывания: "3 > 5". Не всякое предложение является высказыванием, к высказываниям не относятся вопросительные и восклицательные предложения. Не является высказыванием предложение: «Каша – вкусное блюдо», так как не может быть единого мнения о том, истинно оно или ложно. Предложение «Есть жизнь на Марсе» следует считать высказыванием, так как объективно оно либо истинно, либо ложно, хотя никто пока не знает, какое именно.

Поскольку предметом изучения логики являются только значения истинности высказываний, для них вводят буквенные обозначения A, B, … или X,Y.

Считается, что каждое высказывание либо истинно, либо ложно. Для краткости, будем вместо значения истинно писать 1, а вместо значения ложно – 0. Например, X= "Земля вращается вокруг Солнца" иY= "3 > 5", причемX=1 иY= 0. Высказывание не может быть одновременно истинным и ложным.

Высказывания могут быть простыми и составными. Высказывания "Земля вращается вокруг Солнца" и "3 > 5" являются простыми. Составные высказывания образуются из простых с помощью связок естественного (русского) языка НЕ, И, ИЛИ, ЕСЛИ-ТО, ТОГДА-И-ТОЛЬКО-ТОГДА. При использовании буквенных обозначений для высказываний эти связки заменяются специальными математическими символами, которые можно рассматривать как символы логических операций.

Ниже, в таблице 1 приведены варианты символов для обозначения связок и названия соответствующих логических операций.

Отрицанием(инверсией) высказыванияXназывается высказывание, истинное тогда и только тогда, когдаXложно (обозначаетсяили, читается “неX” или “неверно, чтоX”).

Конъюнкциейдвух высказываний называется высказывание, истинное тогда и только тогда, когда истинны оба высказыванияXиY. Эта логическая операция соответствует соединению высказываний союзом ”и”.

Дизъюнкциейдвух высказыванийXиYназывается высказывание ложное в том и только в том случае, когда оба высказыванияXиYложны. В разговорной речи этой логической операции соответствует союз “или” (не исключающее “или”).

Импликациейдвух высказыванийX и Yназывается высказывание, ложное тогда и только тогда, когдаXистинно, аY– ложно (обозначается; читается “XвлечетY”, “еслиX, тоY”). Операнды этой операции имеют специальные названия:X– посылка,Y– заключение.

Эквиваленцией двух высказыванийXиYназывается высказывание, истинное тогда и только тогда, когда истинностные значенияXиYодинаковы (обозначение:).