Материал: Описание самостоятельной работы студентов по дисциплине Cистемы представления знаний

Построить дерево игры. Предложить оценочную функцию. Сравнить применение метода минимакса и α-β отсечение.

3.2.4. Игра калах

Max

3 3 3

3 3 3

Min

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

16

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

Построить часть дерева этой игры. Предложить оценочную функцию позиции. Что даст применение метода минимакса и α-β отсечения?

17

Тема 4. Представление знаний формулами исчисления предикатов

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

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

4.1.Вопросы для самопроверки

1.Какие специальные символы используются при записи формул языка исчисления предикатов первого порядка?

2.Что такое интерпретация формальной теории?

3.Что такое истинностное значение формулы?

4.Что такое логическое следование и что такое формальная выводимость?

5.В каких случаях говорят, что правила вывода логичны?

6.В каких случаях говорят, что правила вывода полны?

18

7.Что такое метод резолюций? Выпишите правило резолюции для исчисления высказываний.

8.Что такое унификация? Выпишите правило резолюции для исчисления предикатов.

9.Что такое предложение? Опишите алгоритм сведения произвольной формулы исчисления предикатов к предложениям.

10.Перечислите известные вам стратегии метода резолюций.

11.Как определяется полная и неполная стратегия метода резолюций.

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

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

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

15.Опишите подкласс хорновских предложений.

16.Что вы знаете о полноте и неполноте стратегий метода резолюций в хорновском случае?

4.2.Задачи для самостоятельного решения

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

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

19

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

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

4.2.1. Метод резолюций для исчисления высказываний

Доказать методом резолюций:

A (B C) D Æ (A B) (C D)

4.2.2. Метод резолюций для исчисления предикатов

Доказать методом резолюций:

х y (((P(x, y) Æ Q(x, y)) Æ P(x, y)) Æ P(x, y))

4.2.3. Представление утверждений предикатами

Даны следующие утверждения.

а) у каждой группы есть любители

б) The Beatles нравятся каждому, кому нравится какая-нибудь группа

в) у каждого есть любимая группа г) "Тату" не является рок-группой д) The Beatles нравится всем

е) существуют люди, которым не нравится "Тату".

20