Вт. Мар 5th, 2024

Логическая модель основана на системе исчисления предика­тов первого порядка. Знакомство с логикой предикатов начнем с исчисления высказываний.

Высказыванием называется предложение, смысл которого можно выразить значениями: истина (Т) или ложь (F).

Например, предложения «лебедь белый» и «лебедь черный» будут вы­сказываниями. Из простых высказываний можно составить бо­лее сложные:

«лебедь белый или лебедь черный»,

«лебедь белый и лебедь черный»,

«если лебедь не белый, то лебедь черный».

В свою очередь, сложные высказывания можно разделить на частичные, которые связаны между собой с помощью слов: и, или, не, если — то. Элементарными называются высказывания, которые нельзя разделить на части. Логика высказываний опери­рует логическими связями между высказываниями, т. е. она ре­шает вопросы типа: «Можно ли на основе высказывания А полу­чить высказывание?»; «Истинно ли В при истинности А?» и т.п. При этом семантика высказываний не имеет значения. Элемен­тарные высказывания рассматриваются как переменные логиче­ского типа, над которыми разрешены следующие логические операции:

отрицание (унарная операция); конъюнкция (логическое умножение); дизъюнкция (логическое сложение); импликация (если — то);  эквивалентность.

Операция импликации должна удовлетворять следующим требованиям.

1. Значение результата импликации зависит от двух опе­рандов.

2. Если первый операнд (А) — истинный, то значение резуль­тата совпадает со значением второго операнда (В).

3. Операция импликации не коммутативна.

4.Результат импликации совпадает с результатом выражения

Значения результатов логических операций над переменны­ми А и В, являющимися элементарными высказываниями.

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

Р: «Все люди смертны» Q: «Сократ — человек» R: «Сократ — смертен»

Используя для обозначения высказываний логические пере­менные Р, Q, R, можно составить формулу: (.которая может быть интерпретирована как «Если все люди смертны и Со­крат является человеком, то Сократ является смертным». Однако эта формула не является общезначимой, поскольку относится только к одному объекту (Сократу). Кроме того, высказывание R не выводится из Р и Q, т.е., если бы мы не сформулировали R за­ранее, мы не смогли бы записать приведенную выше формулу.

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

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

Приведем объяснение понятия предиката, данное Д. А. По­спеловым: «Под предикатом будем понимать некоторую связь, которая задана на наборе из констант или переменных.

Пример предиката: «Р больше Q».

Если семантика Р и Q не задана, то о предикате сказать осо­бенно нечего.

Пожалуй, только то, что он является антирефлек­сивным, антисимметричным и транзитивным. Но при задании семантики (т.е. областей определения переменных Р viQ) о пре­дикате можно будет сказать существенно больше. Например, ес­ли Р и Q — площади городов в России и Японии, то при задании списков городов и подстановке значений из этих списков в пере­менные мы получим отношение между двумя сущностями и смо­жем судить о его истинности, например:

«Площадь Волгограда больше площади Хиросимы» =Т; «Площадь Вологды больше площади Токио»=Е

Иногда для утверждения об истинности или ложности преди­ката можно обойтись без подстановки. Например, если областью определения переменной Xявляются целые положительные чис­ла, то предикат «Хбольше —5» будет тождественно истинен».

Основными синтаксическими единицами логики предикатов являются константы, переменные, функции, предикаты, кванто­ры и логические операторы. Формальный синтаксис исчисления предикатов первого порядка удобно представить в нормальной форме Бэкуса—Наура, которая традиционно применяется для за­писи грамматик языков программирования.

В данной записи любое имя в угловых скобках представляет собой тип синтаксического объекта. Определение каждого типа начинается с появления его имени в левой части каждой записи, т. е. слева от знака —>. В правой части каждой записи приводятся возможные способы организации синтаксически корректных объектов определяемого типа. Альтернативные варианты разде­лены знаком |, который можно интерпретировать как ИЛИ. Но­мера идентификаторов следует трактовать в том смысле, что идентификаторы, используемые для обозначения объектов раз­ных типов, должны быть различимыми. Например, константы обозначаются именами , которые формиру­ются из строчных букв, причем первым символом должен быть один из следующих: а, Ъ, с, d, e, к, l, т, п, х, у, z, v, w, и. Имена пе­ременных должны начинаться, например, с заглавной буквы. Идентификаторы функций состоят из строчных букв, при этом первой является/ g, h, p или q. Имена предикатов должны состоять из про­писных букв. Функции, как и предикаты, задают некоторую связь между переменными или константами. Но эта свять или от­ношение не характеризуются истинностным значением. С помо­щью функции можно представить сложный объект, например, функция fbook (Author, Tytle, Publisher, Year) представляет набор информации, характеризующей книгу. Предикат и функция от­личаются также на синтаксическом уровне, а именно: функции могут являться аргументами предикатов (т.е. термами), а преди­каты — нет. Следует заметить, что в логике предикатов более вы­соких порядков по сравнению с первым аргументами предикатов могут быть другие предикаты. Функции с нулевым числом мест (аргументов) являются аналогами констант. Предикат без аргу­ментов эквивалентен высказыванию.

Кванторы в логике предикатов необходимы для определения области действия переменных. Так, в логическом выводе о Сок­рате высказывание «Все люди смертны» можно уточнить следую­щим образом:

«Для всех X, если X является человеком, то X является смерт­ным».

Введя предикаты ЧЕЛОВЕК (X) и СМЕРТЕН (X), можем со­ставить логическую формулу ЧЕЛОВЕК (X)->СМЕРТЕН (X). Что­бы показать справедливость этой формулы для любого X, исполь­зуется квантор общности:

MX— «для любого X».

Тогда рассматриваемое утверждение запишется в видеОтрицание кванторных выражений выполняется в соответст­вии со следующими правилами: Кроме квантора общности в логике предикатов есть квантор существования: ЗХ — «существует хотя бы один такой X, что …» или «найдется хотя бы один X, такой, что …»

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

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

• для любого X существует хотя бы один человек Y, которого любит X;

• существует по крайней мере один человек Y, которого любят все X;

Для устранения этой неопределенности введем скобки и по­рядок применения кванторов — слева направо, тогда получим следующие формулы, соответствующие интерпретациям:

Рассмотрим остальные варианты расположения кванторов и их интерпретации.

 — «Всеобщее человеколюбие».

 — «Существует хотя бы один человек, который любит всех людей».

 — «Каждого человека кто-нибудь любит».

 — «Существует хотя бы один человек, который не утратил чувства любви».

В одной логической формуле не допускается применение раз­ных кванторов к одной переменной, например выражение  является недопустимым.

64

Справедливость приведенных выражений вытекает из смысла кванторов. Эти соотношения позволяют любую формулу в логи­ке предикатов представить в виде предваренной нормальной формы (ПНФ), в которой сначала выписываются все кванторы, а затем — предикатные выражения.

Пример ПНФ:

В логике предикатов первого порядка не разрешается приме­нение кванторов к предикатам (более высокие порядки это поз­воляют).

Формула, в которой все переменные связаны, называется предложением. Каждому предложению можно поставить в соот­ветствие определенное значение — «истина» или «ложь».

Пример: пусть— функция, задающая отношение «отец»; Р(Х) — предикат, задающий отношение «человек». Тогда логическая формулабудет интерпретироваться как «Все

существа, отцом которых является человек, — люди».

Операции в логике предикатов имеют неодинаковые приори­теты. Самый высокий приоритет имеет квантор общности, са­мый низкий — операция эквивалентности.

убывание приоритета

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

Логическая модель применяется в основном в исследователь­ских системах, так как предъявляет очень высокие требования к качеству и полноте знаний предметной области.