Синтаксис языка логики высказываний

Обновлено: 24.11.2024

В предыдущем параграфе показано, что рассуждения агента (поиск решений задачи) сводится к определению правил перехода в соответствии с выбранной стратегией. Каждый шаг состоит в проверке агентом истинности левой части правила (факта нахождения среды в состоянии и допустимости действия с) и, в случае ее истинности, признании факта перехода из состояния в состояние в результате действия с. Естественно, нам хотелось бы иметь математический аппарат, на основе которого можно осуществлять постановку и поиск решения задачи формально, используя наилучшую стратегию поиска. Логика высказываний — это первый шаг к созданию такого аппарата.

Осуществить постановку задачи формально — значит, имея некий формальный язык, выразить на нем все знания о среде, необходимые для решения задачи. Формальный язык в соответствии с современными представлениями требует рассмотрения двух его неотъемлемых частей: синтаксиса и семантики. Синтаксис языка описывает допустимые в языке предложения, состоящие из цепочек (последовательностей) символов, принадлежащих определенному множеству, называемому алфавитом. Синтаксис языка позволяет отличать предложения, принадлежащие языку, от предложений, ему не принадлежащих. Семантика языка определяет смысл этих предложений, сопоставляя символы языка с объектами реального мира, а предложения — отношения между объектами. Без семантики предложения языка являются ничего не значащими для агента

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

2.2.1. Синтаксис логики высиживаний

Синтаксис логики высказываний прост и имеет прямые синтаксические и семантические аналоги в естественных языках, что чрезвычайно облегчает нам понимание логики высказываний. Символами языка логики высказываний, составляющими ее алфавит, являются логчческие константы и сокращенно обозначаемые буквами И и Л, логические переменные обозначаемые строчными буквами латинского алфавита, логические связки и круглые скобки. Значениями логических переменных являются логические константы. Предложения языка логики высказываний, называемые также формулами или высказываниями, составляют в соответствии со следующими правилами: логические константы являются простыми предложениями; логические переменные также простые предложения; сложные предложения формируются из простых с помощью связок

простые и сложные предложения, заключенные или не заключенные в скобки, является предложениями языка логики высказываний;

из предложений с помощью связок и скобок можно образовать новые предложения языка логики высказываний;

связки имеют следующий порядок старшинства т. е. связка самая старшая, а связка — самая младшая.

Формулы логики высказываний, составленные по этим правилам, называют правильно построеннымнм формулами или сокращенно формулам».

2.2.2. Семантика логики высказываний

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

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

Так, например, если формула включает только одну связку, то ее семантика очень близка к соответствующим высказываниям в русском языке. Так семантика формул в которых встречаются соответственно связки практически совпадает с отношениями, определяемыми соответственно смыслом слов «или», «не», употребляемых в русском языке для выражения отношений между свойствами объектов, обозначаемых переменными хотя некоторые различия имеются. Например, формула имеет истинное значение, если хотя бы одна переменная истинна, но она истинна и при истинности обеих переменных. Говоря на русском языке или обычно предполагаем, что это предложение истинно, если истинна только одна переменная, т.е. это предложение русского языка по смыслу ближе к формуле логики высказываний

Еще больше различий между семантикой формулы в логике высказываний и похожему на нее высказыванию на русском языке влечет у. Первое различие состоит в том, что в русском языке мы полагаем, что предложение х влечет у истинно, если истинны т.е. предложение русского языка по смыслу совпадает с формулой в то время как формула может быть истинной не только тогда, когда истинны обе переменные х и у, но и когда обе ложны или когда х ложна, а у истинна. Кроме того, семантика формулы вообще не предполагает какой либо связи между переменными х и у. Чтобы не обсуждать в дальнейшем подобные несоответствия, впредь будем полагать, что, употребляя формулу х мы вкладываем в нее смысл, вытекающий из следующего предложения: «Мы заявляем, что истинность высказывания влечет у означает, что истинность х влечет истинность у, а больше мы ничего не заявляем».

Истинностные значения любой формулы, т.е. ее семантику, всегда можно задать таблицей, состоящей из двух частей: в левой части таблицы перечислены все наборы значений аргументов, а в правой соответствующие наборам значения формулы. Задание таких таблиц для связок облегчается тем, что значениями аргументов и формул являются только две величины — И или Л. Такие таблицы в логике высказываний называют таблицами истинности (табл. 2.2). Таблицы истинности можно построить для любой формулы, поскольку любая формула является композицией формул для связок. Если

Таблица 2.2 (см. скан)

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

2.2.3. Общезначимые формулы и их роль

Формулы, истинные на всех наборах значений своих аргументов, называют общезначимыми формулами. Если какая-либо формула а является общезначимой, то этот факт обычно записывается с использованием знака общезначимости который ставится перед формулой: Проверку формулы на общезначимость можно осуществить с помощью таблицы истинности: если формула истинна во всех строках таблицы истинности, которая содержит все возможные наборы аргументов формулы, то эта формула общезначима. Рассмотрим, например, формулу Таблицей истинности для нее является табл. 2.3.

Таблица 2.3 (см. скан)

Из табл: 2.3 ясно, что формула является общезначимой (во всех строках последнего столбца стоит значение И). Ранее было заявлено, что истинность высказывания всегда означает, что истинность а; влечет истинность (эдесь являются формулами логики высказываний). Потому, установив факт общезначимости формулы истинности всегда можно сделать заключение об истинности Так, например, предположим, что истинное значение логической переменной х в формуле соответствует местонахождению кота слева (Слева), а ложное значение логической переменной хсоответствует местонахождению кота справа (Справа), истинное значение переменной у соответствует наличию сыра около левой комнаты (Да), а ложное его отсутствию там (Нет). В этом случае при истинности формулы можно сделать заключение об истинности формулы х, что соответствует нахождению кота у правой комнаты (Справа).

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

законы Де Моргана

закон двойного отрицания

В этих законах а обозначает любую правильно построенную формулу логики высказываний.

Кроме общезначимых, существуют формулы выполнимые и невыполнимые. Формула называется выполнимой, если существуют наборы значений ее аргументов, на которых она принимает истинное значение, и наборы значений, на которых она принимает ложное значение. Если формула на всех наборах значений ее аргументов принимает ложное значение, то она называется невыполнимой.

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

2.2.4. Модель формулы

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

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

Читайте также: