одання виразів, але для побудови такої нормальної форми використовується розширений набір правил синтаксичних перетворень. Нижче наведена послідовність застосування таких правил. Для приведення будь-якого виразу до нормальної форми слід виконати наступні операції.
(1) Виключити оператори еквівалентності, а потім імплікації.
(2) Використовуючи правила Де Моргана й правила заміщення (EX) U на - (будь-який X)-U (а отже, і (будь X) U на - (E X)-U), виконати приведення заперечення. p> (3) Виконати приведення змінних. При цьому слід враховувати особливості визначення області інтерпретації змінних кванторами. Наприклад, у виразі (E Х) (ФІЛОСОФ (Х)) & (E Х) (АТЛЕТ (Х)) змінні можуть мати різні інтерпретації в одній і тій же області. Тому винесення квантора за дужки - (E Х) (ФІЛОСОФ (Х)) &. (АТЛЕТ (Х)) - дасть вираз, який не слід з вихідної формули.
(4) Виключити квантори існування. Квантори існування, які з'являються поза області інтерпретації будь-якого квантора спільності, можна замінити довільним ім'ям (його називають константою Сколема), в той час як екзистенційні змінні, які можуть існувати всередині області інтерпретації одного або більше кванторів спільності, можуть бути замінені функціями Сколема. Функція Сколема-це функція з довільним ім'ям, яка має наступний зміст: "значення даної змінної є деяка функція від значень, присвоєних універсальним змінним, в області інтерпретації яких вона лежить ".
(5) Перетворення в префіксних форму. На цьому кроці всі залишилися квантори (залишаться тільки квантори спільності) переносяться "в голову" вираження і таким чином виявляються ліворуч у списку квантифікованій змінних. За ними слід матриця, в якій відсутні квантори.
(6) Рознести оператори диз'юнкції і кон'юнкції.
(7) Відкинути квантори спільності. Тепер всі вільні змінні є неявно універсально квантифікувати змінними. Екзистенційні змінні стануть або константами, або функціями універсальних змінних.
(8) Як і раніше, відкинути оператори кон'юнкцій, залишивши безліч фраз.
(9) Знову перейменувати змінні, щоб одні й ті ж імена не зустрічалися в різних фразах. p> Обчислення предикатів у спрощеному вигляді. Там вираз виду
at (робот, комнатаА)
означає, що робот знаходиться в кімнаті А. Терми робот і комнатаА в цьому виразі представляли собою константи, які описували певні реальні об'єкти. Але що буде означати вираз виду
at (X, комнатаА),
в якому х є змінною? Чи означає воно, що щось знаходиться в кімнаті А? Якщо це так, то говорять, що змінна має екзистенціальну підстановку (імпорт). А може бути, вираз означає, що всі об'єкти знаходяться в кімнаті А? У такому випадку змінна має універсальну підстановку. Таким чином, відсутність набору чітких правил не дозволяє однозначно інтерпретувати наведену формулу.
Перераховані в цьому розділі правила обчислення предикатів забезпечують однозначну інтерпретацію виразів, що містять змінні.
Зокрема, фраза
at (X, комнатаА) <-at (X, ящік1) інтерпретується як
"для всіх XX знаходиться в кімнаті А, якщо X знаходиться в ящику 1 ". У цій фразі змінна має універсальну підстановку. Аналогічно, фраза
at (X, комнатаА) <-Інтерпретується як "для всіх XX знаходиться в кімнаті А". А ось фраза
<- at (X, комнатаА) інтерпретується як "для всіх XX чи не знаходиться в кімнаті А".
Іншими словами, це не той випадок, коли деякий об'єкт X знаходиться в кімнаті А і, отже, мінлива має екзистенціальну підстановку.
Тепер можна перетворити фразову форму, в якій позитивні літерали згруповані ліворуч від знаку стрілки, а негативні - справа. Якщо фраза у формі
P1, ..., Рт <- q1, ... qn містить змінні х1, ..., Xk, то правильна інтерпретація має наступний вид:
для всіх x1, ..., хk
p1 або ... або pm є істинним, якщо q1 і ... і qn є істинними.
Якщо п = 0, тобто відсутній хоча б одна умова, то вираз буде інтерпретуватися наступним чином:
для всіх x1, ..., xk
p1 або ... або рт є істинним.
Якщо т = 0, тобто відсутні терми укладення, то вираз буде інтерпретуватися наступним чином:
для всіх x1, ..., xk
не має значення, що q1 і ... і qn є істинними.
Якщо ж т = п = 0, то ми маємо справу з порожньою фразою, яка завжди інтерпретується як помилкова.
В
3.2 Програмування на пролозі.
В
При програмуванні на Пролозі зусилля програміста повинні бути спрямовані на опис логічної моделі фрагменту предметної області розв'язуваної задачі в термінах об'єктів предметної області, їх властивостей і відносин між собою, а не деталей програмної реалізації. Фактично Пролог являє собою не стільки мова для програмування, скільки мова для опису даних і логіки їх обробки. Програма на Пролозі не є такою в класичному розумінні, оскільки не містить явних керуючих конструкцій типу умовн...
