Лабораторная работа №1 по дисциплине "Системы искусственного интелекта"



Скачать 90.22 Kb.
Дата02.12.2012
Размер90.22 Kb.
ТипЛабораторная работа
ЛАБОРАТОРНАЯ РАБОТА №1

по дисциплине “Системы искусственного интелекта"
ПРИМЕРЫ НА ДОКАЗАТЕЛЬСТВО ТЕОРЕМ В ИСЧИСЛЕНИИ ПРЕДИКАТОВ ПЕРВОГО ПОРЯДКА
Введение
Исчисление предикатов первого порядка является теоретической основной множества формализмов методов искусственного интеллекта. Задачи на доказательство теорем исторически рассматривались в данной дисциплине одними из первых.

 

1. Цель занятия

  • приобретение навыков формализации постановки заданий в терминах языка исчисления предикатов первого порядка;

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

 

  1. Задание на занятие




  1. построить формальное описание выданного (по вариантам) задания;

  2. решить задание (доказать утверждение) в исчислении предикатов первого порядка.




  1. Методические указания

Язык исчисления предикатов первого порядка.


Основные конструкции языка L – языка исчисления предикатов первого порядка достаточно просты и называются формулами. Введем вначале алфавит языка L. Алфавит включает:

  1. Счетное множество букв: ,…; которое будем называть множеством символов для обозначения переменных языка;

  2. Счетное множество букв ; которое будем называть множеством символов для обозначения констант языка;

  3. Счетное множество прописных букв ; для обозначения предикатных символов языка;

  4. Счетное множество строчных букв ; для обозначения функциональных символов.

  5. Символы для логических связок (влечет),(не).

  6. (для всех), (существует)- символы для кванторов;

7. (, )- скобки.

Предикатные буквы P, Q, … и функциональные буквы f, g,…могут быть n – местными или, как еще говорят, n – арными. Иначе говоря, с каждым предикатным или функциональным символом будем связывать некоторое натуральное число, равное числу его аргументов.

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

Формулы языка определяются индуктивным образом.
Начнем с определения
терма языка:

  1. Переменная есть терм.

  2. Константа есть терм.

  3. Если t1 ,t2 , …,tm - термы, а f m – местный функциональный символ, то f (t1 ,t2 , …,tm ) терм.

  4. Если t1 ,t2 , …,tm - термы, а P m – местный предикатный символ, то P(t1 ,t2 , …,tm ) - атомарная формула.

  5. Атомарная формула есть формула.

  6. Если - формулы, то (AB),, - также формулы.

  7. Если A – формула, то xA – формула.

  8. Всякое слово в алфавите языка является формулой тогда и только тогда, когда это можно показать с помощью конечного числа применений п.п. 1-7.


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

Можно, например, определить логические связки (читается и и или), выразив их через связки и :

1.AB = (AB)
2. A B =AB
Квантор существования -  (существует) также выражается через квантор всеобщности и отрицание:

xA(x) = x A(x)
Разумеется, и с тем же успехом можно было бы включить в язык в качестве трех дополнительных символов. Есть, однако, некоторые преимущества в том, чтобы сохранить список символов как можно более коротким. Например, индуктивные определения и доказательства по индукции оказываются в этом случае короче.

В дальнейшем нам придется использовать понятия свободного и связанного вхождения переменной в формулу. Вхождение переменной x в формулу A называется связанным, если эта переменная находится в области действия квантора существования существования или всеобщности. В противном случае, вхождение переменной называется свободным. Если в формуле A отсутствуют свободно входящие в нее переменные (т.е. либо все переменные связаны, либо отсутствуют), то формула называется замкнутой формулой или предложением. Атомарная замкнутая формула называется фактом. В том случае, если язык состоит только лишь из предложений, то он называется пропозициональным языком, а буквы A, B, …, входящие в формулы этого языка – пропозициональными переменными.

Исчисление предикатов первого порядка.

Рассмотрим вкратце основные понятия исчисления предикатов первого порядка.

Введем вначале аксиомы исчисления предикатов:

1.

2.

3.

Правила вывода


  1. Правило отделения: если выводимо и выводимо , то выводимо B;

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

Если в аксиомах 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. Выполнимы ли следующие формулы:

А) ;

Б) .

Похожие:

Лабораторная работа №1 по дисциплине \"Системы искусственного интелекта\" iconЛабораторная работа №2 по дисциплине "Системы искусственного интеллекта"
Дедуктивные и индуктивные рассуждения. Задачи на поиск доказательства методом резолюций
Лабораторная работа №1 по дисциплине \"Системы искусственного интелекта\" iconЛабораторная работа №3 по дисциплине "Системы искусственного интеллекта"
Задачи на исследование свойств систем правил. Написание простых систем, основанных на правилах
Лабораторная работа №1 по дисциплине \"Системы искусственного интелекта\" iconЛабораторная работа №3 по дисциплине «организация ЭВМ и систем» Вариант №2
Изучение архитектуры и основ системы команд арифметического сопроцессора К1810ВМ87 (i8087). Получение навыков программирования сопроцессорной...
Лабораторная работа №1 по дисциплине \"Системы искусственного интелекта\" iconЛабораторная работа №3. Знакомство с прерываниями. Лабораторная работа №4. Программная обработка клавиатуры
Лабораторная работа №1. Знакомство с общим устройством и функционированием ЭВМ. Изучение структуры процессора, организации памяти,...
Лабораторная работа №1 по дисциплине \"Системы искусственного интелекта\" iconЛабораторная работа №1 Работа в Oracle Database Express Edition 1 Лабораторная работа №6
Лабораторная работа Выполнение расчетов с использованием программирования в среде Visual Basic for Applications
Лабораторная работа №1 по дисциплине \"Системы искусственного интелекта\" iconЛабораторная работа №17 по дисциплине " Методы и средства гидрометеорологических измерений". Устройство осциллографов
Устройство осциллографов. Лабораторная работа №17 по курсу “Гидрометеорологические измерения”. С. Петербург: рггму, 2002, 14 с
Лабораторная работа №1 по дисциплине \"Системы искусственного интелекта\" iconЛабораторная работа №7 по дисциплине " Методы и средства гидрометеорологических измерений". Исследование анемометров
Лабораторная работа №. Исследование анемометров. По дисциплине “Методы и средства гидрометеорологических измерении”. – С. Петербург.:...
Лабораторная работа №1 по дисциплине \"Системы искусственного интелекта\" iconЛабораторная работа №16 по дисциплине " Методы и средства гидрометеорологических измерений". Измерение радиоактивности
Лабораторная работа №16. Измерение радиоактивности. По дисциплине “Методы и средства гидрометеорологических измерении”. – С. Петербург.:...
Лабораторная работа №1 по дисциплине \"Системы искусственного интелекта\" iconЛабораторная работа №3 «Исследование измерителей параметров движения летательного аппарата вокруг центра масс» по дисциплине «Системы управления транспортных средств»
Изучение методов численного интегрирования и дифференцирования непрерывных функций
Лабораторная работа №1 по дисциплине \"Системы искусственного интелекта\" iconЛабораторная работа №2 по дисциплине "Операционные системы, среды и оболочки" Создание пакетных файлов
Символ ( ) отменяет специальное использование управляющего символа, и управляющий символ можно использовать в тексте
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org