Лабораторная работа №1 по дисциплине “Системы искусственного интелекта
Скачать 98.28 Kb.
|
по дисциплине “Системы искусственного интелекта" ПРИМЕРЫ НА ДОКАЗАТЕЛЬСТВО ТЕОРЕМ В ИСЧИСЛЕНИИ ПРЕДИКАТОВ ПЕРВОГО ПОРЯДКА Введение Исчисление предикатов первого порядка является теоретической основной множества формализмов методов искусственного интеллекта. Задачи на доказательство теорем исторически рассматривались в данной дисциплине одними из первых. 1. Цель занятия
Язык исчисления предикатов первого порядка.Основные конструкции языка L – языка исчисления предикатов первого порядка достаточно просты и называются формулами. Введем вначале алфавит языка L. Алфавит включает:
7. (, )- скобки. Предикатные буквы P, Q, … и функциональные буквы f, g,…могут быть n – местными или, как еще говорят, n – арными. Иначе говоря, с каждым предикатным или функциональным символом будем связывать некоторое натуральное число, равное числу его аргументов. Определим теперь понятие формулы или правильно построенного выражения языка исчисления предикатов первого порядка. Формулы языка определяются индуктивным образом. Начнем с определения терма языка:
Таким образом, мы завершили одно из возможных определений языка исчисления предикатов первого порядка. Существуют и другие определения, однако, язык, определенный нами, является полным, т.е. в нем выразимо все то, что выразимо в языках (исчисления предикатов первого порядка), определенных любым иным способом. Можно, например, определить логические связки  (читается и и или), выразив их через связки и :1.AB = (AB) 2. A B =AB Квантор существования - (существует) также выражается через квантор всеобщности и отрицание: xA(x) = x A(x) Разумеется,  и с тем же успехом можно было бы включить в язык в качестве трех дополнительных символов. Есть, однако, некоторые преимущества в том, чтобы сохранить список символов как можно более коротким. Например, индуктивные определения и доказательства по индукции оказываются в этом случае короче.В дальнейшем нам придется использовать понятия свободного и связанного вхождения переменной в формулу. Вхождение переменной x в формулу A называется связанным, если эта переменная находится в области действия квантора существования существования или всеобщности. В противном случае, вхождение переменной называется свободным. Если в формуле A отсутствуют свободно входящие в нее переменные (т.е. либо все переменные связаны, либо отсутствуют), то формула называется замкнутой формулой или предложением. Атомарная замкнутая формула называется фактом. В том случае, если язык состоит только лишь из предложений, то он называется пропозициональным языком, а буквы A, B, …, входящие в формулы этого языка – пропозициональными переменными. Исчисление предикатов первого порядка. Рассмотрим вкратце основные понятия исчисления предикатов первого порядка. Введем вначале аксиомы исчисления предикатов: 1.  2.  3.  Правила вывода
Если в аксиомах 1. – 3. все переменные являются пропозициональными, то такое исчисление называется пропозициональным исчислением или исчислением высказываний. Рассмотрим пример вывода в исчислении высказываний. Возьмем, например, три закона логики, сформулированные Аристотелем и называемые постулатами Аристотеля. В языке исчисления высказываний они записываются следующим образом: Пусть  - пропозициональная переменная исчисления высказываний.Первый из постулатов Аристотеля – это так называемый закон тождества; второй – закон исключённого третьего и третий – закон противоречия. Докажем один из постулатов, например  .Используем аксиому 1. и правило подстановки (вместо B подставим ): получим  Из аксиомы 2:  Вместо  подставим  :  Применим правило отделения: та часть последней формулы, которая обозначена через X является аксиомой, т.е. выводима, тогда в силу правила отделения, выводима формула, обозначенная через Y. Теперь применим правило отделения к Y:  и, рассуждая таким же образом, получим, что Y’ -выводимо. Таким образом, закон тождества Аристотеля является теоремой исчисления высказываний. Действуя таким же образом, можно доказать, что второй и третий постулаты Аристотеля также являются теоремами исчисления высказываний. Однако, исчисление предикатов первого порядка не исчерпывается приведенными выше тремя аксиомами и правилами вывода. Смысл кванторов устанавливается еще двумя аксиомами и одним правилом вывода. 4.Аксиома генерализации:  ,где x не является свободной переменной в A; 5.Аксиома спецификации: t A(t) A(x), где t -терм, а x не содержится в t в качестве свободной переменной. Правило обобщения: A xA, где x – свободная переменная в A. Аксиомы 1.-5. исчисления предикатов первого порядка (или математической логики первого порядка) называются логическими аксиомами, они описывают логические законы, справедливые всегда, независимо от предметной области. Если же к аксиомам 1.5. добавить еще и аксиомы, опсывающие некоторую предметную область, например, арифметику или теорию групп, то получим формальную терию - формальную арифметику или формальную теорию групп, соответственно. При этом, разумеется, в алфавит языка следует ввести спецальные функциональные символы, такие как сложение в арифметике или умножение в теории групп. Словосочетание “первый порядок” отностся исключительно к тому обстоятельству, что кванторы и действуют на некотором множестве U. Логика второго порядка разрешает одному из кванторов действовать на подмножествах множества U и на функциях из степеней U в U. Логика третьего порядка может использовать кванторы по множествам функций и т.д. Уже из этих разъяснений видно, что в логиках более высоких порядков (как говорят, более сильных логиках) используются и некоторые нелогические понятия, такие как множество. Некоторым обобщением понятия исчисления является понятие формальной системы. 1. В алгебраической системе определены следующие трехместные предикаты: S(x, y, z) = и <=> x + y = z, P(x, y, z) = и <=> x · y = z. Записать формулу с одной свободной переменной x, истинную в данной системе тогда и только тогда, когда А) x = 0; Ответ: Q(x)   Б) x = 2; Ответ: Q(x)  B) x – нечетно. Ответ: Q(x)  2. Для условий задачи 1 записать формулу с двумя свободными переменными x и y, истинную тогда и только тогда, когда А) x = y; Ответ: x = y  Б) x ≤ y. Ответ: x ≤ y  3. В системе множеств определен предикат Q(x, y) = и <=> x  y. Записать, чтоА) x есть пересечение y и z; Ответ: x = y∩z  Б) x есть пустое множество. Ответ: x = O/   4. Являются ли тождественно истинными следующие формулы: A)  ; Ответ: Нет. Формула ложна в системе натуральных чисел с P(x) = и x – четное число.Б)  ? Ответ: Нет формула ложна для P(x) = и для всех x.5. Доказать тождественную истинность следующих формул: A)  .Б)  6. Выполнимы ли следующие формулы: А)  ; Ответ: Выполнима для P(x)=и x – четно.Б)  ? Ответ: Выполнима для P(x) ≡ л.4 Структура отчета Отчет по лабораторной работе должен содержать: 1. формальную постановку задачи; 2. ход решения и его обоснование; 3. выводы по лабораторной работе. 5 Варианты заданий 1. В алгебраической системе определены следующие трехместные предикаты: S(x, y, z) = и <=> x + y = z, P(x, y, z) = и <=> x · y = z. Записать формулу с одной свободной переменной x, истинную в данной системе тогда и только тогда, когда А) x = 1; Б) x – нечетно; B) x – простое число. 2. Для условий задачи 1 записать формулу с двумя свободными переменными x и y, истинную тогда и только тогда, когда А) x < y; Б) x делит y. 3. В системе множеств определен предикат Q(x, y) = и <=> x y. Записать, чтоА) x есть объединение y и z; Б) x есть дополнение y. 4. Являются ли тождественно истинными следующие формулы: A)  ;Б)  .5. Доказать тождественную истинность следующих формул: A)  .6. Выполнимы ли следующие формулы: А)  ;Б)  . |
,…; которое будем называть множеством символов для обозначения переменных языка;
; которое будем называть множеством символов для обозначения констант языка;
; для обозначения предикатных символов языка;
; для обозначения функциональных символов.
(влечет),
(не).
- формулы, то (A
,
- также формулы.
и выводимо 
, то выводимо B;
Похожие:
 | Лабораторная работа №4 по дисциплине “Системы искусственного интеллекта Целью лабораторных работ является освоение технологии и методики построения экспертных систем на примере разработанной учебной экспертной... | | Лабораторная работа №2 по дисциплине “Системы искусственного интеллекта Дедуктивные и индуктивные рассуждения. Задачи на поиск доказательства методом резолюций |
| Лабораторная работа №3 по дисциплине “Системы искусственного интеллекта Задачи на исследование свойств систем правил. Написание простых систем, основанных на правилах | | Конспект лекций по дисциплине «Системы искусственного интеллекта» Место среди других наук, первые шаги и современные направления искусственного интеллекта |
| Лабораторная работа №2 по дисциплине «ТСиСА» на тему: «Структурное моделирование системный анализ структуры сложной системы» Целью данной работы является изучение программы структурного моделирования систем сдкмс (Системы Декомпозоции Композиции и Модификации... | | Лабораторная работа №18 по дисциплине “ Методы и средства гидрометеорологических измерений” «Прием телевизионного изображения Земли из космоса». Лабораторная работа 18 по дисциплине "Методы и средства гидрометеорологических... |
| Лабораторная работа №4 по дисциплине «Имитационное моделирование экономических процессов» «Системы с разнородными потоками событий. Статистика очередей. Цикличная обработка» | | Лабораторная работа №2 по дисциплине: «Информационно-поисковые системы» Перешла на сайт поисковой системы Апорт (Яндекс, Рамблер. Нашла в каждой системе ссылки на ее описание в целом, на описание языка... |
| Лабораторная работа №2 по дисциплине: «Информационно-поисковые системы» Перешла на сайт поисковой системы Апорт (затем Яндекс и Рамблер). Нашла в каждой системе ссылки на ее описание в целом, на описание... | | Лабораторная работа По дисциплине «Операционные системы» Содержание упражнения №9 содержит контрольный срез умений, обязательный для выполнения каждым учащимся. Дополнительные задания выдаются... |