Истинность связок предикатов (И – истина, Л – ложь)

Математически строго формулы логики предикатов определяются рекурсивно:

1) предикат есть формула;

2) если А и В – формулы, то ~А, АВ, АВ, АВ, АВ – тоже формулы;

3) других формул не бывает.

Многие формулы логики предикатов требуют использования кванторов, определяющих область значений переменных – аргументов предикатов. Используются кванторы общности (перевернутое А от английского «Аll» – все) и квантор существования – (перевернутое Е от английского «Exists» – «существует»). Запись x читается «для любого х», «для каждого х»; х – «существует х», «хотя бы для одного х». Кванторы связывают переменные предикатов, на которые они действуют, и превращают предикаты в высказывания.

Пример

Введем обозначения: А(х) – студент х учится отлично; В(х) – студент х получает повышенную стипендию. Тогда формула А (Иванов)В (Иванов) означает: студент Иванов учится отлично, следовательно, студент Иванов получает повышенную стипендию, а формула с квантором общности (х)(А(х)В(х)) означает: каждый студент, который учится отлично, получает повышенную стипендию.

Из всевозможных формул нам потребуется только один их вид, называемый фразамиХорна. Фразы Хорна содержат в общем случае импликацию и конъюнкцию предикатов А, В1, В2,..., Вn следующим образом: В1 В2... ВnА, или в более удобных обозначениях:

А:-В1,В2,...,Вn

(читается: А, если В1 и В2 и ... и Вn).

Очевидно, фраза Хорна является формой записи некоего правила, и в дальнейшем будет называться правилом. Предикат А называется заголовком или головой правила, а предикаты В1, В2,..., Вn – его подцелями.

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

Другой частный случай фразы Хорна – правило без головы:

:-В1,В2,...,Вn,

или

:-В.

Такая фраза Хорна называется вопросом. Мы будем записывать «:-В» в виде «?-В», а «:-В1, В2,..., Вn» в виде «?-В1, В2,..., Вn».

Поясним логический смысл такой формулы. Напомним, что импликация А:-В (ВА) может быть выражена через отрицание и дизъюнкцию: ~BA (проверьте это с помощью таблицы истинности). Значит, если отбросить А, останется только ~В – отрицание В. Формула В1,...,Вn означает отрицание конъюнкции ~(В1В2...Вn), что по закону де Моргана ~(ХY)=(~X)(~Y) равно (~B1)(~B2)...(~Bn) – дизъюнкции отрицаний.

Множество фраз Хорна применительно к некоторой проблемной области образует теорию (в логическом смысле).

Пример

Рассмотрим предметную область: сдачу экзамена по некоторой дисциплине. Введем обозначения:

А – студент успешно сдает экзамен.

В – студент посещал занятия.

С – студент освоил учебный материал.

D – студент занимался самостоятельно.

Е – студент подготовил шпаргалку.

Введем знания о предметной области:

Студент успешно сдаст экзамен, если студент освоил учебный материал.

Студент освоил учебный материал, если студент посещал занятия и студент занимался самостоятельно. Студент посещал занятия. Студент занимался самостоятельно.

Форма логической записи:

А:-С;

С:-В,D;

В;

В приведенном примере можно выполнить логический вывод. Так, из истинности фактов В и D и правила С:-В,D следует истинность С, и из правила А:-С – истинность предиката А, т.е. студент успешно сдаст экзамен. Кроме того, правила А:-С и С:-В, D можно было бы переписать в виде А:-В, D.

В этих случаях используют правила вывода, называемые методомрезолюций. Рассмотрим простейшую форму резолюции. Допустим, имеются «родительские» предложения:

отрицание: ~А импликация: А:-В.

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

допуская, что не А

и А, если В

выводим не В.

Еще более простой случай:

отрицание: ~А

факт: А.

Резольвента – противоречие.

В общем случае имеются родительские предложения:

~(А₁ Ù...ÙАn)

Ak:-B₁,...,Bm 1£k£n.

В качестве резольвенты за один шаг вывода получается ~(А₁Ù…ÙA _k _-1ÙВ₁Ù…В_mÙA_k₊₁Ù...ÙА_n).

Таким образом, резолюция является подстановкой предикатов – подцелей В₁,...В _n, вместо соответствующего предиката A _k из отрицания. Отрицание инициирует логический вывод и поэтому называется запросом (или вопросом) и обозначается А₁, А₂, ... ,A _n. Смысл метода резолюций состоит в том, что строится отрицание конъюнкции и проверяется, истинно его значение или ложно. Если значение результирующей конъюнкции ложь, значит получилось противоречие и, поскольку на старте было отрицание предикатов, выполнено доказательство “от обратного”. Если получено значение “истина”, то доказательство не выполнено.

Пример:

Пусть предикат дает (X,Y,Z) означает, что «X дает Y некоторому объекту Z», а предикат получают (X,Y) означает, что «Y получает X». Пусть знания об этих отношениях выражаются предложениями:

1) получает (вы, сила):- дает (логика, сила, вы);

2) дает (логика, сила, вы).

Задача, которую нужно решить, состоит в том, чтобы ответить на вопрос: получаете ли вы силу?

Представим этот вопрос в виде отрицания ~получает (вы, сила). Резолюция предложения 1 и отрицания приводит к ~дает(логика, сила, вы), что вместе с фактом 2 приводит к противоречию. Следовательно, ответом исходной задачи является “да”.

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

Рассмотрим это на примере.

Пример:

Рассмотрим следующие родительские предложения:

1) ~получает (вы, Y);

2) получает (X, сила) :- дает(Z, сила, X).

Они содержат три переменные X,Y и Z, которые неявно находятся под действием квантора общности. Так, предложение 1 утверждает, что «для всех Y вы не получаете Y», а 2 – «для всех Z любой Х получает силу, если Z дает силу X». Правило резолюции требует совпадения предиката из отрицания 1 и головы правила 2. Это означает, что переменные получают значения (конкретизируются) соответственно их месту в предложениях 1 и 2 следующим образом: Х=вы, Y=сила. Предикат получает(вы, сила) называется общим примером для предикатов получает(вы, Y) и получает(X, сила).

Изложенные положения логики предикатов находят реализацию и дальнейшее развитие в языке программирования Пролог.

Лекция 3,4

Дата добавления: 2019-07-15; просмотров: 211; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 1 2 345 6 7 8 9 10 Следующая ⇒

Мы поможем в написании ваших работ!