Искусственный интеллект. Современный подход

ПРОПОЗИЦИОНАЛЬНАЯ ЛОГИКА: ОЧЕНЬ ПРОСТАЯ ЛОГИКА

В этом разделе будет представлена очень простая логика, называемая пропозициональной логикой. Здесь рассматривается синтаксис пропозициональной логики и ее семантика — способ определения истинности высказываний. Затем мы рассмотрим понятие следствия (отношения между одним высказыванием и другим высказыванием, которое следует из него) и определим, как с помощью этого понятия можно получить простой алгоритм для логического вывода. Безусловно, все это происходит в мире вампуса.
Синтаксис
Синтаксис пропозициональной логики определяет допустимые высказывания. Атомарные высказывания (неделимые синтаксические элементы) состоят из одного пропозиционального символа. Каждый такой символ обозначает высказывание, которое может быть либо истинным, либо ложным. Для обозначения подобных символов в данном разделе используются прописные буквы: Р, Q, R и т.д. Эти обозначения являются произвольными, но часто выбираются таким образом, чтобы они имели для читателя какое-то мнемоническое значение. Например, символ Wli3 может использоваться для обозначения высказывания, согласно которому вампус находится в квадрате [1,3]. (Напомним, что символы, подобные Wli3, являются атомарными; это означает, что W, 1 и 3 не следует рассматривать как осмысленные части этого символа.) Существуют два пропозициональных символа, имеющих постоянный смысл: True — тождественно истинное высказывание, a False — тождественно ложное высказывание.
Сложные высказывания формируются из более простых высказываний с помощью логических связок. Широко применяются пять описанных ниже логических связок.
• -I (нет). Такое высказывание, как ~Wli3, называется отрицанием высказывания wli3. Литерал представляет собой либо атомарное высказывание (положительный литерал), либо отрицаемое атомарное высказывание (отрицательный литерал).
• л (и). Высказывание, основной связкой которого является л, такое как Wi,3 л Рз,ъ называется конъюнкцией; его части называются конъюнктами. (Символ л напоминает букву "А" в слове "And" — "И".)
• v (или). Высказывание, в котором используется связка v, такое как (Wli3 л Рзл) v w2i2, называется дизъюнкцией дизъюнктов (Wli3 л P3il) и w2i2. (Исторически обозначение v произошло из латинского слова "vel", которое означает "или". Большинство людей находят, что форму этой связки проще всего запомнить как перевернутый символ л.)
• => (влечет за собой). Такое высказывание, как (wli3 л P3il) => -nW2i2, называется импликацией (или условным высказыванием). Его предпосылкой, или антецедентом, является (Wli3 л р3/1), а его заключением, или консек-вентом, является -nW2i2. Импликации называют также правилами, или утверждениями if—then (если—то). В других книгах символ импликации иногда записывается как D или —>.
• <=> (если и только если). Высказывание наподобие W1>3 <=> W2i2 называется двухсторонней импликацией.
Формальная грамматика пропозициональной логики показана в листинге 7.2; те, кто не знаком с системой обозначений BNF, должны обратиться за дополнительными сведениями на с. 1.
Листинг 7.2. Грамматика высказываний пропозициональной логики в форме BNF (Backus-Naur Form — форма Бэкуса-Наура)
Sentence —> AtomicSentence \ ComplexSentence Atomic Sentence —> True | False | Symbol Symbol -> P I Q I R I ... ComplexSentence —> IUSentence
I ( Sentence л Sentence ) I ( Sentence v Sentence ) I ( Sentence => Sentence ) I ( Sentence <=> Sentence )
Обратите внимание на то, что эта грамматика предъявляет строгие требования к использованию круглых скобок: каждое высказывание, сформированное с помощью бинарных связок, должно быть заключено в круглые скобки. Это гарантирует полную непротиворечивость синтаксиса. Такое требование также означает, что следует писать, например, ((Ал В) => С), например, вместо А л В => С. Но для удобства чтения мы будем часто опускать круглые скобки, полагаясь вместо них на использование порядка предшествования связок. Это аналогично правилам предшествования, используемым в арифметике, например, выражение ab+c читается как ( (аЬ) +с), а не как а(Ь+с), поскольку операция умножения имеет более высокий приоритет, чем сложение. Порядок предшествования в пропозициональной логике (от высшему к низшему) состоит в следующем: -i, л, v, => и <=>. Поэтому высказывание
-iP v Q л R => S
эквивалентно высказыванию
( HP) v (Q л R) ) => S
Определение порядка приоритета не позволяет устранить неоднозначность при чтении таких высказываний, как А л в л С, которое может быть прочитано как ( (А л В) А С) или (Ал (В л С) ). Но поскольку эти два прочтения, согласно семантике, описанной в следующем разделе, означают одно и то же, допускаются высказывания, подобные А л В л С. Разрешаются также высказывания наподобие A v в v СиА<=> В<=> С. А такие высказывания, как А => В => С, не допускаются, поскольку для них соответствующие два прочтения имеют разный смысл; мы настаиваем на том, что в этом случае должны использоваться круглые скобки. Наконец, в данной книге иногда вместо круглых скобок используются квадратные, если это позволяет немного упростить понимание данного высказывания.
Семантика
Определив синтаксис пропозициональной логики, мы можем приступить к определению ее семантики. Семантика диктует правила выявления истинности высказывания по отношению к конкретной модели. В пропозициональной логике любая модель просто фиксирует истинностное значение (true или false) для каждого пропозиционального символа. Например, если в высказываниях некоторой базы знаний используются пропозициональные символы р1/2, Р2,2 и Р3,ъ то одна из возможных моделей состоит в следующем:
Л71 = {Pi,2 = false, Р2,2 = false, Ръ,\ = true}
При наличии трех пропозициональных символов существует 23=8 возможных моделей; именно столько моделей показано на рис. 7.4. Однако следует отметить, что с тех пор, как мы определили синтаксис, модели стали чисто математическими объектами, которые не обязательно должны быть связаны с миром вампуса. Например, Pi,2 — это просто символ; он может означать, что "в квадрате [1,2] есть яма" или "я буду в Париже сегодня и завтра".
Семантика пропозициональной логики должна определять, как следует вычислять истинностное значение любого высказывания при наличии модели. Эта процедура выполняется рекурсивно. Все высказывания формируются из атомарных высказываний и пяти связок, поэтому необходимо указать, как следует вычислять истинность атомарных высказываний, а затем — как вычислять истинность высказываний, сформированных с помощью каждой из этих пяти связок. Задача вычисления истинности атомарных высказываний, как показано ниже, является простой.
• Высказывание True истинно в любой модели, а высказывание False ложно в любой модели.
• Истинностное значение любого другого пропозиционального символа должно быть указано непосредственно в модели. Например, в модели mi приведенное выше высказывание Plt2 является ложным.
Для определения истинности сложных высказываний применяются правила, подобные приведенному ниже.
• Для любого высказывания s и любой модели т высказывание -is является истинным в модели т тогда и только тогда, когда s является ложным в модели т.
Эти правила позволяют свести задачу определения истинности сложных высказываний к задаче определения истинности более простых высказываний. Правила определения истинности для каждой связки могут быть подытожены в виде истинностной таблицы, которая определяет истинностное значение сложного высказывания для каждого возможного присваивания значений истинности его компонентам. Истинностные таблицы для рассматриваемых пяти логических связок приведены в табл. 7.1. С использованием этих таблиц истинностное значение любого высказывания s применительно к любой модели т может быть вычислено с помощью простого процесса рекурсивной оценки. Например, высказывание -iPi/2 л (Р2/2 v P3/i), оцениваемое в модели ml9 приводит к получению true л (false v true) = true л true = true. В упр. 7.3 предложено написать алгоритм PL-True? (stт), который вычисляет истинностное значение любого высказывания s пропозициональной логики в модели т.
Выше было сказано, что любая база знаний состоит из множества высказываний. Теперь можно показать, что логическая база знаний представляет собой конъюнкцию этих высказываний. Это означает, что, начиная с пустой базы знаний кв и применяя операции Tell (KB, Sl7 ,..., Tell (KB, SN), мы получим: KB=S1A...ASTI.
Таким образом, базы знаний и высказывания могут рассматриваться как взаимозаменяемые понятия.
Истинностные таблицы для связок л ("и"), v ("или") и -. ("нет") почти полностью соответствуют интуитивным представлениям о смысле таких же слов естественного языка. Основным источником возможной путаницы является то, что высказывание Р v Q истинно, если истинными являются Р, или Q, или оба эти высказывания. Есть также другая связка, называемая "исключительное ИЛИ" (сокращенно "XOR" — exclusive OR), которая принимает ложное значение, если оба дизъюнкта являются истинными9. В отношении того, какое обозначение следует применять для связки "исключительное ИЛИ", нет общего согласия; двумя возможными вариантами являются v и ©.
Истинностная таблица для связки => на первый взгляд может показаться озадачивающей, поскольку не совсем соответствует интуитивному пониманию выражений "Р влечет за собой ?)", или "если Р, то ?)". Но прежде всего необходимо отметить, что пропозициональная логика не требует, чтобы между высказываниями Р и Q устанавливались какие-либо причинно-следственные отношения или отношения, определяющие их релевантность применительно к друг другу. Высказывание "то, что 5 — нечетное число, влечет за собой то, что Токио — столица Японии", — это истинное высказывание пропозициональной логики (при нормальной интерпретации), даже несмотря на то, что в естественном языке определенно кажется странным. Еще один источник путаницы состоит в том, что любая импликация является истинной, если ее антецедент ложен. Например, высказывание "то, что 5 — четное число, влечет за собой что, что Сэм умен", является истинным, независимо от того, умен ли Сэм. Это может показаться странным, но приобретает смысл, если рассматривать высказывание в форме "Р => Q" как утверждение: "Если Р истинно, то я утверждаю, что Q истинно. В противном случае я не высказываю никаких утверждений". Единственный вариант, при котором это высказывание может принять значение false, состоит в том, чтобы высказывание Рбыло истинным, а 0 — ложным.
Истинностная таблица для двухсторонней импликации, Р <=> Q, показывает, что это высказывание является истинным, если истинны иР=> Q, и Q => Р. В словесной форме соответствующее высказывание часто записывают следующим образом: "Р тогда и только тогда, когда (?", или сокращенно "Рттогда Q" (ттогда — не опечатка). Правила для мира вампуса лучше всего записывать с помощью связки <=>. Например, в некотором квадрате чувствуется ветерок, если в соседнем квадрате имеется яма, а ветерок в некотором квадрате может чувствоваться, только если в одном из соседних квадратов имеется яма. Поэтому нам потребуются двухсторонние импликации, такие как
Bl.l <=> (Pi,2 V Р2Л)
где Bi,i означает, что в квадрате [1,1] чувствуется ветерок. Обратите внимание на то, что следующая односторонняя импликация:
В1Л (Pi,2 V Р2Л)
в мире вампуса является истинной, но неполной. Она не позволяет исключить из рассмотрения модели, в которых высказывание В1Л ложно и р1<2 истинно и которые нарушают правила мира вампуса. Эту мысль можно иначе выразить таким образом, что импликация требует наличия ям, если чувствуется ветерок, а двухсторонняя импликация требует также отсутствия ям, если ветерок не чувствуется.