Intel_Nils (526801), страница 34
Текст из файла (страница 34)
бета перебор с тем, чтобы найти наилучший ход в позиции БТА)(Т. Эначением ЗЕАЕСН должен быть список вида (ВРОЕ!Т10Х, ЧАШЕ), где ВР081Т!ОХ вЂ” это наилучшая дочернян (по отношению к $ТА)(Т) позиция, а ЧАШŠ— обращенная величина для игрока ПЛЮС. *5.6. Напишите для вычислительной машины программу игры в трехмерную игру тик-так-ту (называемую иногда Кьюбик). В эту игру играют два или более игрока на кубе 4Х 4Х4, разделенном иа 54 ячейки. Каждый из игроков по очереди помещает один нз своих значков в одну из свободных ячеек. Первый иэ игроков, которому удается поместить чет)яре своих значка в одну строку, столбец или диагональ любой из плоскостей куба или вдойь любой из главных диагоналей куба, выигрывает.
В программе можно применить любую разумную стратегию перебора, но следует использовать в Мей также н некоторые эвристические элементы, позволяющие ограничивать число дочерних позиций, строящихся в игровом дереве. Чтобы охватить игры и лиц, и ) 2, потребуется обобщить понятия игрового дерева и перебора на игровом дереве. Глава 6 ДОКАЗАТЕЛЬСТВО ТЕОРЕМ В ИСЧИСЛЕНИИ ПРЕДИКАТОВ йп. ИСЧИСЛЕНИЕ ПРЕДИКАТОВ КАК ЯЗЫК ДЛЯ РЕШЕНИЯ ЗАДАЧ Мы отмечали в гл. 1, что для решения многих задач может потребоваться логический анализ. Для автоматического логического рассуждения необходим некоторый формальный язык, на котором можно формулировать посылки и делать верные логические выводы. Все, что для этого требуется, — это возможность описать интересующую нас задачу и средства поиска соответствующих шагов в процессе логического вывода.
Исчисление предикатов первого порядка — это такая система в логике, в которой можно выразить ббльшую часть того, что относится к математике, а также многое из разговорногоязьпса. Эта система содержит правила логического вывода, позволяющие делать верные логические построения новых утверждений, исходя из некоторого заданного множества утверждений.
Благодаря своей общности и логической силе исчисление предикатов может всерьез претендовать на использование его для машинного построения умозаключений. В этой главе мы на время отойдем от нашей главной цели изучения процессов решения и дадим обзор теории исчисления предикатов и приемов дедукции в этой системе, основанных на принципе резольвенций '). В гл.
7 мы вернемся к предмету решения задач и приведем примеры, иллюстрирующие задачи. Наконец„в гл. 8 мы объясним работу некоторых наиболее эффективных способов поиска требуемых логических заключений. Язык, подобный языку в исчислении предикатов, определяется его синтаксисом. Чтобы задать синтаксис, надо задать алфавит символов, которые будут использоваться в этом языке, и правила соединения этих символов друг с другом ~в выражениях, допустимых на этом языке. Один из важных классов выражений в исчислении предикатов — это класс правильно по строенных формул (и. и.
формул). Мы обычно пользуемся языком для того, чтобы делать утверждения, касающиеся интересующей нас области, Отношения между языком и описываемой им областью определяются семантикой этого языка. П. и. формулы исчисления предикатон как раз являются теми выражениями, которые мы будем ис') Используется также термин «резолюния», который нам представляется менее удачным русским переводом английского геао1пноп. — Прим, перев. 6.2.
Синтаксис )тз пользовать в качестве утверждений, касающихся интересующей вас области. Говорят, что п. и. формулы принимают значение Т или г в зависимости от того, являются эти утверждения в этой области истинными или ложными. Приемы обращения с п.
п. формулами позволяют строить умозаключения, относящиеся к некоторой области, и, следовательно, могут представить интерес при создании процессов принятия решения, требуюших такого умозаключения. В следующем разделе мы зададим синтаксис одного из вариантов исчисления предикатов. Затем покажем, как на этом языке можно делать утверждения, касающиеся описываемой им области. 6.2. СИНТАКСИС Синтаксис нашей системы исчисления предикатов включает в себя задание алфавита символов и определение различных полезных выражений, которые можно построить из этих символов. Для того чтобы объяснить основные идеи, мы начнем с введения сравнительно примитивной системы').
Потом добавим к этому алфавиту другие символы, позволяющие записывать некоторые из выражений короче. Основной алфавит состоит из таких множеств символов: 1, Знаки пунктуации:, (). 2. Логические символы: Ф. (Символ читается как «не», а символ =~ как «влечет за собой».) 3. н-местные функциональные буквы: );". (1~)1, а)~0). Я называются константными буквами.
Для простоты записи вместо ~~ удобно употреблять строчные буквы а, 6, с, а вместо е других ~~ — строчные буквы 1, д, й.без индексов.)з) 4. и-местные предикатные буквы: рз (1)1„н)0). (р,' называются нропозимиональнылш буквами. Мы включили их для полноты, но в последуюших примерах мы ими не пользуемся. Для простоты записи вместо р," удобно употреблять прописные буквы Р, Я, )т без индексов.) Из этих символов можно построить различные выражения. Классы выражений, представляющих для нас интерес, можно рекурсивно определить следующим образом: ') Конкретнее, мы временно исключаем из рассмотрения кнаиторы и переменные. з) у читателя может возникнуть вопрос, почему мы сразу не строили определения, употребляя буквы а, Ь, с, й л, Д Причина состоит в том, что нам нужно, чтобы наши формальные определения годились для произвольно больших множеств функциональных букв, таких, как 1".
В конкретных примерах, однако, обычно берется небольшое число функцьональных букв, и поэтому можно ограничиться более простым конечным множеством (а, Ь, С, (, а «). 174 Гл. и. Доказательство теорем е исчислении нредикатое 1. Термы. а) Каждая константная буква есть терм. б) Если Уь, сн (и ) 1) — термы, то ит,"(го ..., г',) — терм. ' в) Никакие другие выражения не являются термами.
(Заметим, что если выРажение Х(уь (э, ..., 1„) использУетсЯ как терм, то оно используется вместо 7,(1,, 1„..., 1„) для некоторого Е Верхний индекс у а был бы излишним.) 2. Атомные формулы. а) Пропозициональные буквы являются атомными форму- лами. б) Если уь тэ, ..., 1„(а ) !) — теРмы, то Р,"(со ст, ...,т„)— атомная формула. в) Никакие другие выражения не являются атомными фор- мулами.
3. Правильно построенные формулы (и. п. формулы). а) Атомная формула есть п. п. формула. б) Если А — п. п. формула, то ( А) — п. п, формула. в) Если А и  — п. п. формулы, то (А Ф В) — также п, п. формула. г) Никакие другие выражения не являются п. п. форму- лами (пока), Приведем примеры п. п. формул'): Р (а, а (а, 6, а)), Р(а, 6)=)э( Я(с)), ( (Р(а)ФР(Ь)))"-)эР(Ь), Р(а) =)ь Я(7(а)). Приведем примеры выражений, не являющихся и.
и. форму- лами: -((а), ) (Р (а)), Я(7" (а), (Р(Ь))эЯ(с))), Добавим к нашему алфавиту логические символы 'Л («и») и ~т («или»), которые позволят короче записывать более слож- ные п. и. формулы, содержащие и =)ь. Пусть Х, и Хэ — лю- бые две и. п. формулы. Тогда Хг ЛХт и Х~'ч'Хэ — также пра- вильно построенные формулы, определяемые равенствами ХтЛХэ= -(Х~Ф -Хт), ХУХэ=(-Х,) =)»Хю ') Если это не может привести к недораэуменнкк нруглые скобки будем опускать. б.З. Сел«ига«а 175 6.3. СЕМАНТИКА Для того чтобы п. п. формуле придать «содержани~е», ее надо интерпретировать как некоторое утверждение, касающееся рассматриваемой области. Для нас областью может служить некоторое непустое множество (возможно, бесконечное). Им может быть множество целых чисел, или множество всех конфигураций игры в восемь, или множество всех математиков и т. д.
Интересующие нас утверждения будут связаны с отношениями между элементами этой области. Например, мы можем захотеть высказать утверждение: «Джон — отец Билла». Тогда областью будет множество людей, а отношением между людьми — бинарное отношение «отцовства». Полезно также иметь функции на этой области. Если 0— область, то и-местная функция ставит в соответствие каждому набору из и элементов области 0 некоторый элемент из этой области. Так, функция плюс отображает пары целых чисел в целые числа в соответствии с хорошо известной операцией сложения.
Именно об этих аспектах области — ее элементах, ее функциях и ее отношениях — мы и хотим говооить на нашем языке исчисления предикатов. Для того чтобы для п. п. формулы сделать утверждение определенного смысла, мы связываем с этой п. п. формулой некоторую непустую область О, а затем с каждым константным символом в п, п. формуле — некоторый конкретный элемент из 0; с каждой функциональной буквой в п. п. формуле — некоторую конкретную функцию на 0 (и-местные функциональные буквы соответствуют и-местным функциям); с каждой предикатной буквой в этой п.
п. формуле — некоторое конкретное отношение между элементами из 0 (а-местные предикатные буквы соответствуют л-местным отношениям). Конкретизация области и указанных соответствий дает интерпретацию, или модель, нашей п. п. формулы. При заданной п. п. формуле и некоторой интерпретации каждой атомной формуле в этой п.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
