Исчисление предикатов. 1. 7. 5. 1. Логика высказываний

1.7.5. Исчисление предикатов. 1.7.5.1. Логика высказываний

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

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

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

Распространенным типом логических моделей является логика предикатов первого порядка. Основным объектом здесь является переменное высказывание (предикат), истинность и ложность которого зависят от значений его перемен­ных.

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

 

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

 Таким образом, под высказыванием будем понимать утвердительное предложение, которое либо истинно (И), либо ложно (Л). Логическим значением высказывания называется И или Л, приписываемые этому высказыванию.

Примеры высказываний:

1) Новгород стоит на реке Волхов.

2) Берлин – столица Дании.

3) Число 12 делится на 3 и на 4.

4) Если молодой человек успешно окончил среднюю школу, то он получает аттестат зрелости.

5) Существует человек, который старше своего отца.

Легко видно, что высказывания 1), 3), 4) истинны, а высказывания 2) и 5) – ложны.

В логике высказываний символы и т. д., используются для обозначения высказываний. Например, пусть  - высказывание «Студент Иванов изучает язык программирования СИ⁺⁺»,  - высказывание «Студент Иванов хорошо знает математику».

Простые высказывания называют элементарными или атомарными.

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

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

Таблица 1. Логические связки Название Обозначение Тип Отрицание ,  , not, НЕ унарный Конъюнкция , &,and, И бинарный Дизъюнкция ˅, +,or, ИЛИ бинарный   Импликация бинарный       Эквивалентность бинарный

 

 

Из высказываний с помощью логических операторов  (не), Ù (и), Ú (или), ® (если..., то...), ↔ (тогда и только тогда, равнозначность) строятся составные высказывания. Выражение, которое представляет высказывание или составное высказывание, называется правильно построенной формулой (ППФ), короче — формулой. Если Р и Q — ППФ, то ( P), (P Ù Q). (P Ú Q), (P ® Q)и (P ↔ Q) тоже есть ППФ. Например,  есть ППФ.

Пусть G — данная пропозициональная формула (пропозиция — высказы­вание) и A₁, А_2,..., A_n — ее атомарные формулы.

Интерпретацией формулы G является такое приписывание истинностных значений атомарным формулам A₁,..., A_n,, при котором каждому A_i приписано либо И, либо Л (но не оба вместе).

Формула G истинна при некоторой интерпретации, тогда и только тогда, когда G получает значение И в этой интерпретации; в противном случае го­ворят, что G ложна при этой интерпретации. Если формула истинна при всех возможных интерпретациях, то говорят, что она является общезначимой фор­мулой (тавтологией). Обозначим ее ■.

 Если формула ложна при всех своих интерпретациях, то говорят, что она является невыполнимой или противоречивой (противоречи­ем). Противоречивая формула невыполнима. Обозначим ее □.

Если формула принимает значение истины хотя бы при одной интерпретации, она называется выполнимой.

Говорят, что две формулы Р и G эквивалентны или что Р эквивалентна Q (P = Q), когда истинные значения Р и Q совпадают при каждой интерпре­тации Р и Q. Существует множество эквивалентных формул, называемых за­конами, которые используются при преобразованиях формул из одной формы в другую, — особенно — в «нормальную форму».

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

Литера — это атомарная формула или ее отрицание. Формула Р нахо­дится в конъюнктивной нормальной форме (КНФ), тогда и только тогда, ког­да Р имеет вид

где каждая из Р₁, Р₂,..., Р_n есть дизъюнкция литер. Здесь знак  означает «равно по определению».

КНФ имеет важное значение для оценки значений формул. Часто возникает вопрос: нельзя ли установить какую-либо связь между структурой формулы и ее семантикой, т.е. связь между ее логической формой и логическим содержанием? Оказывается, можно указать простой метод, позволяющий по виду формулы, приведенной к определенному виду, сделать вывод о том, тождественна она или нет. Этот метод как раз и заключается в приведении исходной формулы к нормальной конъюнктивной форме и последующем ее анализе. Рассмотрим следующий пример.

 

Пусть имеется некоторое выражение F, представленное КНФ:

a