Главная arrow Логика arrow Кванторы
Как начинался компьютер
Компьютерная революция
Двоичный код
Разработки военных лет
Интегральные микросхемы
Микрокомпьютер
Персоны
Сеть
Язык компьютера
Развитие ПО
Гибкие системы
Средства разработки
Информатика
Вычислительная наука
Операционные системы
Искусственный интеллект
Предыстория
Поиск
Знания и рассуждения
Логика
Робототехника
 

 
Кванторы Печать

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

 

Применение квантора всеобщности (V)

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

Vx King(x) => Person (х)

Квантор V обычно произносится как "для всех ...". (Следует помнить, что перевернутая буква "А" обозначает "all" — все.) Таким образом, в этом высказывании утверждается следующее: "Для всех х, если х — король, то х — человек". Символ х называется переменной. В соответствии с общепринятым соглашением в качестве переменных применяются строчные буквы. Переменная сама является термом и как таковая может также служить параметром функции, например LeftLeg(x). Терм без переменных называется базовым термом.

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

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

х —> Ричард Львиное Сердце

х —> король Джон

х —> левая нога Ричарда

х —> левая нога Джона

х —> корона

Высказывание с квантором всеобщности Vx King(x) => Person (х) является истинным при первоначальной интерпретации, если высказывание King(x) => Person (х) истинно в каждой из пяти расширенных интерпретаций. Это означает, что данное высказывание с квантором всеобщности эквивалентно утверждению об истинности следующих пяти высказываний:

Ричард Львиное Сердце — король => Ричард Львиное Сердце — человек

король Джон — король => король Джон — человек

левая нога Ричарда — король => левая нога Ричарда — человек

левая нога Джона — король => левая нога Джона — человек

корона — король => корона — человек

Рассмотрим внимательно это множество утверждений. Поскольку в нашей модели единственным королем является король Джон, то во втором высказывании утверждается, что он — человек, как и следовало ожидать. А что же можно сказать об остальных четырех высказываниях, в частности о тех, в которых приведены утверждения о ногах и коронах? Являются ли они частью смысла утверждения "Все короли являются людьми"?

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

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

Распространенная ошибка, которую часто допускают даже внимательные читатели, которые прочли предыдущий абзац несколько раз, состоит в том, что они используют конъюнкцию вместо импликации. Тогда следующее высказывание:

Vx King{x) a Person (х)

становится эквивалентным таким утверждениям:

Ричард Львиное Сердце — король л Ричард Львиное Сердце — человек

король Джон — король л король Джон — человек

левая нога Ричарда — король л левая нога Ричарда — человек

и т.д. Очевидно, что такой ряд утверждений не передает желаемый смысл.

 

Применение квантора существования E

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

Eх Crown(х) ^ OnHead(x, John)

Квантор существования с переменной Eх читается как: "Существует х, такой, что ...", или "Для некоторого х...".

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

Ричард Львиное Сердце — корона л Ричард Львиное Сердце находится на голове Джона

король Джон — корона л король Джон находится на голове Джона

левая нога Ричарда — корона л левая нога Ричарда находится на голове Джона

левая нога Джона — корона л левая нога Джона находится на голове Джона

корона — корона а корона находится на голове Джона

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

Итак, логическая связка ==> может рассматриваться как наиболее подходящая для использования с квантором V, а логическая связка л естественным образом подходит для использования с квантором E. В примере, который рассматривался в предыдущем разделе, применение ^ в качестве основной связки в сочетании с квантором V приводило к формированию слишком сильного утверждения, а использование связки => в сочетании с квантором E обычно приводит к формированию действительно очень слабых утверждений. Рассмотрим следующее высказывание:

Eх Crown(x) => OnHead(x, John)

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

Ричард Львиное Сердце — корона => Ричард Львиное Сердце находится на голове Джона

король Джон — корона => король Джон находится на голове Джона

левая нога Ричарда — корона => левая нога Ричарда находится на голове Джона

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

 

Вложенные кванторы

Часто возникает необходимость сформировать более сложные высказывания с использованием нескольких кванторов. Простейшим является случай, когда кванторы относятся к одному и тому же типу. Например, утверждение: "Братья — это люди, связанные братскими родственными узами", может быть записано следующим образом:

Vx Vy Brother{x,y) => Sibling(x, у)

Последовательно применяемые кванторы могут быть записаны как один квантор с несколькими переменными. Например, чтобы выразить мысль о том, что родственные отношения между людьми, связанными братскими узами, являются симметричным, можно составить следующее высказывание:

Ух, у Sibling{x,y) <=> Siblingiy, х

В других случаях возникает необходимость в использовании сочетания разных кванторов. Например, строка из песни "Everybody loves somebody" (Каждый кого-то любит) означает, что для каждого человека существует кто-то, кого этот человек любит:

Vx Зу Loves (х, у)

С другой стороны, чтобы сформулировать утверждение "Есть некто, кого любят все", можно записать следующее:

Vy Зх Loves (х, у)

Таким образом, порядок расположения кванторов очень важен. Он становится очевиднее после вставки круглых скобок. В высказывании Vx (Зу Loves(х,у) ) утверждается, что каждый имеет конкретное свойство, а именно то свойство, что его кто-то любит. С другой стороны, в высказывании Зх (Vy Loves (х, у) ) утверждается, что некто в мире имеет конкретное свойство, а именно свойство быть любимым всеми.

Если два квантора используются с одним и тем же именем переменной, может возникнуть некоторая путаница. Рассмотрим следующее высказывание:

Vx [Crown(x) v (Зх Brother(Richard,х))]

Здесь к переменной х в атомарном высказывании Brother {Richard, х) применяется квантор существования. Общее правило состоит в том, что переменная принадлежит к самому внутреннему квантору, в котором она упоминается; это означает, что такая переменная не может стать субъектом действия любого другого квантора. Еще один способ анализа приведенного выше высказывания состоит в следующем: Зх Brother {Richard, х) — это высказывание о Ричарде (о том, что у него есть брат), а не о переменной х, поэтому размещение квантора Vx за пределами данного высказывания не оказывает на него никакого действия, и оно могло быть равным образом записано как 3z Brother (Richard, z). Но поскольку такая ситуация может стать источником путаницы, в подобных обстоятельствах мы всегда будем использовать разные переменные.

 

Связь между кванторами V и E

Кванторы V и 3 фактически тесно связаны друг с другом через отрицание. Утверждение о том, что никто не любит пастернак, равносильно утверждению о том, что не существует никого, кто бы его любил, и наоборот:

Vx ^Likes (х, Parsnips) эквивалентно высказыванию-i3x Likes (х, Parsnips)

По такому же принципу может быть сформирована более сложная конструкция; например, выражение "Все любят мороженое" означает, что нет никого, кто не любил бы мороженое:

Vx Likes (х, Icecream) эквивалентно высказыванию-i3xiLikesix, IceCream)

Поскольку квантор V фактически определяет в универсуме объектов конъюнкцию, а квантор 3 определяет дизъюнкцию, нет ничего удивительного в том, что они подчиняются правилам де Моргана.

Таким образом, в действительности нет необходимости иметь одновременно кванторы V и 3, так же как фактически не нужны обе связки л и v. Тем не менее удобство для чтения важнее, чем экономия выразительных средств, поэтому мы будем пользоваться обоими этими кванторами.

 

Равенство

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

Father(John) = Henry

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

Символ равенства может использоваться для констатации фактов, касающихся данной конкретной функции, как было только что сделано применительно к функциональному символу Father. Он может также применяться с отрицанием как указание на то, что два терма не представляют собой один и тот же объект. Чтобы выразить мысль о том, что Ричард имеет по меньшей мере двух братьев, можно записать следующее:

Зх,у Brother (х, Richard) л Brother {у, Richard) л —i{x = у)

С другой стороны, высказывание:

Зх,у Brother(х, Richard) л Brotherly, Richard)

не имеет такого намеченного смысла. В частности, оно истинно в модели, где у Ричарда имеется только один брат. Чтобы убедиться в этом, рассмотрим расширенную интерпретацию, в которой обеим переменным, хну, присваивается объект— король Джон. Но в результате добавления выражения -i(x=y) такие модели становятся недействительными. В качестве сокращения для -I (х=у) иногда используется обозначение х=у.