Логическое и функциональное программирование (стр. 7 из 16)

Задание 2

Если собака видит кошку, то она за ней гонится. Если за котом Васькой гонится собака и рядом есть дерево, то кот Васька забирается на дерево. В саду много деревьев. Однажды, в саду Ваську увидела собака.

Доказать, пользуясь логическими правилами вывода, что Васька забрался на дерево.

Компьютерное задание

Реализовать программу решающую следующую задачу:

На входе программы – таблица истинности для функции четырех переменных.

На выходе программы – СДНФ, СКНФ, диаграмма Вейча и минимальная нормальная форма.

2.2 Исчисление предикатов

Исчисление предикатов расширяет язык исчисления высказываний так, что мир оказывается, состоящим из объектов, отношений и свойств.

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

1. Слова, задающие сущности изучаемого мира.

2. Слова, задающие атрибуты / свойства этих сущностей, а также их поведение и отношения.

Первый тип слов называется термами, второй – предикатами.

Некие сущности и переменные определяются упорядоченными последовательностями конечной длины из букв и символов, исключая зарезервированные. Константы и переменные определяют отдельные объекты рассматриваемого мира. Последовательность из n констант или переменных (1 £n < ¥), заключенная в круглые скобки, следующие за символом функции, имя которой задано некоторой конечной последовательностью букв, называется функцией.

Например, функция f(x, y) принимает некоторые значения, которые определяются значениями констант и переменных (аргументов функции), содержащимися под знаком функции. Эти значения, так же как и аргументы, являются некоторыми сущностями рассматриваемого мира. Поэтому все они объединяются общим названием терм (константы, переменные, функции).

Атомарным предикатом (атомом) называется последовательность из n (1 £n <¥) термов, заключенных в круглые скобки, следующие за предикатным символом, имя которого выражается конечной последовательностью букв. Предикат принимает одно из двух значений true или false в соответствии со значениями, входящих в него термов.

Предикат @ Нераспространенное простое предложение

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

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

но используются т.к. ® эквивалентен фразе «Если А, то В», а » - «А и В эквивалентны».

В качестве символов второго класса используются " и $. Эти символы называются кванторами общности и существования, соответственно. Переменная, которая квантифицирована, т.е. к ней применен один из кванторов

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

Действительно, пусть

Тогда для любого предиката U выполняется:

Аналогом законов Де Моргана для кванторов являются:

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

Пусть задан некоторый предикат U(x, y). Очевидно, что возможно восемь случаев связывания его кванторами существования и общности:

Необходимо дать интерпретацию этим восьми случаям.

Рассмотрим, например, предикат подсистема(x, y), который задает отношение x подсистема y. Пусть переменная x связана квантором общности, а y – квантором существования. В этом случае существует две интерпретации: 1. «Для всех x, существует y, для которых x подсистема», 2. «Существует y, что все x его подсистемы».

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

- ("x)($y)подсистема(x, y) – все объекты являются подсистемами;

- ($x)("y)подсистема(x,y) – существует объект, который является подсистемой любого объекта;

- ("y)($x)подсистема(x, y) – для всякого объекта существует объект, являющийся его подсистемой;

- ("x)($y)подсистема(x, y) – существует объект, который является чей-то подсистемой.

Сделаем некоторые важные обобщения.

1.Чтобы найти отрицание выражения, начинающегося с кванторов, надо каждый квантор заменить на его двойственный и перенести знак отрицания за кванторы. Отсюда:

2.Одноименные кванторы можно переставлять. Разноименные кванторы можно переставлять только в одну сторону. Отсюда:

Если

то

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

Если

то

Действительно, если существует y, что все x его подсистемы, то для всех x существует y, для которого x подсистемы. Однако, перестановка в обратную сторону неверна. Например:

Если

то необязательно.

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

3.

Докажем эту равносильность.

В этой выкладке мы опирались на следующее утверждение:

Определение ППФ и семантика логики предикатов

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

1. Атомарный предикат является ППФ.

2. Если F и G являются ППФ, то

также ППФ.

3. Если F(x) – ППФ, то ("x)F(x) и ($x)F(x) – ППФ.

4. Все результаты, полученные применением конечного числа раз (1) – (3) являются ППФ. Ничто другое не является ППФ.

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

1. Устанавливаются соответствия между константами логики предикатов и сущностями этой области. Константы º Имена объектов.

2. Устанавливаются соответствия между формулами и функциональными отношениями предметной области.

3. Устанавливаются соответствия между атомарными предикатами и концептуальными отношениями предметной области.

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

1. Задается непустое множество D, определяющее сущности рассматриваемой предметной области, и элементы из D определяются как константы или переменные.

2. Для функций (функциональные отношения), определенных на множестве аргументов от

до D назначаются функциональные символы.

3. Каждому предикату n переменных назначается отношение, определенное на Dⁿ, и его значение – True или False.