Семантика исчисления высказываний

Ранее мы познакомились с синтаксисом исчисления высказываний и определили набор правил для создания допустимых предложений. Здесь мы формально определим семантику этих предложений. Важно показать, что правдивость их заключений зависит только от правдивости начального знания, т. е. что процедуры вывода не содержат логических ошибок. Для этого требуется точная интерпретация семантики.

Символ предложения соответствует некоторому утверждению. Напри­мер, Р может обозначать высказывание "идет дождь", а О — высказывание "Я живу в кирпичном доме". Предложение может быть истинным и ложным. Присвоение значения истинности логическим предложениям на­зывается интерпретацией. Следовательно, интерпретация — это утвер­ждение относительно правдивости предложения в некоторой среде.

Формально интерпретация— это отображение логических символов на множество {Т, F} (true — истина, false — ложь). Как упомянуто ранее, символы true и false являются также частями ряда ППФ исчисления высказываний; т. е. значения ППФ отличны от значения истинности, присвоенного предложению. Чтобы подчеркнуть это различие, для присвоения значения истинности используются символы Т и F.

Каждое возможное отображение значения истинности высказывания соответствует возможной интерпретации мира. Например, если Р обозначает высказывание "идет снег", а Q — "я отдыхаю", то набор высказываний {Р, Q } имеет четыре различных функциональных отображения в таблице истинности {T, F}. Эти отображения соответствуют четырем различным интерпретациям.

Семантика исчисления высказываний, подобно его синтаксису, определена индуктивно. Интерпретация набора высказываний — это присвоение значения истинности, Т или F, каждому пропозициональному символу.

Символу true (истина) всегда присваивается Т, а символу false (ложь) — значение F. Интерпретации, или значения истинности, действительных предложений определены следую­щим образом.

Определение истинности отрицания Ø Р, где Р — это любой препозиционный символ, осуществляется так. Высказывание Ø Р есть F, если Р имеет значение Т ; и выска­зывание Ø Р есть Т, если Р имеет значение F.

Определение истинности конъюнкции Ùосуществляется так: высказывание имеет значение Т, если оба конъюнкта имеют значение Т; иначе выражение имеет значение F.

Определение истинности дизъюнкции Ú осуществляется так: высказывание имеет значение F, только если оба дизъюнкта имеют значение F; иначе выражение имеет значение Т.

Определение истинности импликации ® осуществляется так: высказывание имеет значение F только тогда, когда предпосылка (символ перед импликацией) есть Т, и значение истинности следствия (символа после импликации) есть F; иначе выражение имеет значение Т.

Истинность эквивалентности ºопределяется так: высказывание эквивалентности имеет значение Т только тогда, когда оба выражения имеют одинаковое значение ис­тинности для всех возможных интерпретаций; иначе выражение эквивалентности имеет значение F.

Значения истинности сложных выражений часто описываются таблицами истинно­сти. Таблица истинности содержит все возможные варианты значения истинности для элементарных суждений (атомарных формул), составляющих большие выражения, и за­дает значение истинности выражениям для каждой возможной интерпретации. Таким образом, в таблице истинности перечисляются все возможные варианты интерпретации данного выражения.

Например, таблица истинности для Р Ù Q (табл. 2.1) дает значения истинности выражения для каждого возможного значения операнда. Выражение Р Ù Q ис­тинно только тогда, когда Р и Q имеют значение Т. Операции "или" (Ú), "не" (Ø), "импликация" (®) и "эквивалентность" (º) можно определить аналогичным образом с помощью таблиц истинности.

Таблица 2.1. Таблица истинности для операции Ù

Два выражения в исчислении высказываний эквивалентны, если они имеют одни и те же значения при всех возможных значениях элементов, составляющих выражение. Эта эквивалентность может быть продемонстрирована с помощью таблиц истинности. Например, доказательство эквивалентности Р-^Q и —<PvQ определяется таблицей истинности, показанной на рис. 2.2.

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

Ø (ØР) º Р

(PÚQ) º (ØР®Q)

Закон контрапозиции импликации: P-»Qs (-,Q-»-,P). Закон Моргана:-i(PvQ)h(-,Pa-iO) и-i(PaO)s(-₁Pv-.O). Законы коммутативности: (PaO)s(QaP) и (PvQ)s(OvP). Ассоциативный закон: ((PaO)aR)=(Pa(OaR)). Ассоциативный закон: ((PvQ)vR)h(Pv(OvR)). Дистрибутивный закон: Pv( OaR)=( PvO)л(PvR). Дистрибутивный закон: Рл(OvR)s(PaO)v(PaR).

Эти тождества могут быть использованы для приведения выражения исчисления выска­зываний к синтаксически различным, но логически эквивалентным формам. Используя эти тождества вместо таблиц истинности данных выражений, докажите эквивалентность выра­жений, преобразуя одно выражение в другое через последовательность эквивалентных вы­ражений. Первая программа искусственного интеллекта Logic Theorist (Логический теоре­тик) [Newell и Simon, 1956], разработанная Ньюэллом, Саймоном и Шоу, использовала преобразования эквивалентных форм выражений для доказательства многих теорем из [Whitehead и Russell, 1950]. Правила вывода дают возможность заменять логическое выра­жение другими формами с эквивалентными значениями истинности, что очень важно. Для использования правил modus ponens (раздел 2.3) и резолюции (resolution) (глава 12) необ­ходимо, чтобы выражения были заданы в определенной форме.

Р О РлО

Рис. 2.1. Таблица истинности для оператора л

Рис. 2.2. Таблица истинности, демонстр­рующая тождественность выражений и -*PvQ