Лекция 12. Формальные теории Содержание лекции: 1.Определение формальной теорииОпределение формальной теории 2.Интерпретация формальной теорииИнтерпретация. - презентация

1 Лекция 12. Формальные теории Содержание лекции: 1.Определение формальной теорииОпределение формальной теории 2.Интерпретация формальной теорииИнтерпретация формальной теории 3.Теоремы ограниченияТеоремы ограничения 4.Понятие изоморфизма в терминах теории формальных системПонятие изоморфизма в терминах теории формальных систем Формальные теории © Н.М. Светлов, /10

2 Литература 1.Лорьер Ж.-Л. Системы искусственного интеллекта. М.: Мир, Формальные теории © Н.М. Светлов, /10

3 1. Формальные теории Формальные теории © Н.М. Светлов, /10

4 Граф доказательства теоремы 3 Аксиома 1 Аксиома 2 Аксиома 3 Аксиома 4 Правило 1 Теорема 1 Правило 2 Теорема 2 Правило 3 Теорема 3 Формальные теории © Н.М. Светлов, /10

5 2. Интерпретация формальной теории(теорема,истина) (теорема, ложь) (нетеорема, истина) (нетеорема, ложь) Формальные теории © Н.М. Светлов, /10

6 Интерпретация одной ф.с. в другую ф.с.: требует задания третьей ф.с., содержащей: алфавиты и синтаксис обеих ф.с. синтаксис описания соответствий между формулами двух ф.с. представляет собой: правила построения формул, рекурсивно перечисляющие все пары формул двух ф.с., между которыми устанавливается соответствие может быть осуществлена с помощью: исчисления предикатов I порядкапри условии, что некоторые константы исчисления предикатов кодируют формулы двух формальных системлюбого другого универсального метаязыка 2. Интерпретация формальной теории Формальные теории © Н.М. Светлов, /10

7 2. Интерпретация формальной теории Формальные теории © Н.М. Светлов, /10

8 2. Интерпретация формальной теории Формальные теории © Н.М. Светлов, /10

9 Формальные теории © Н.М. Светлов, /10 3. Теоремы ограничения Вторая теорема Гёделя – В формальной арифметике существуют такие формулы p, что ни p, ни ¬p не являются теоремами (1931 г.) Теорема Тарского – Не все истинные формулы формальной арифметики являются её теоремами (1935 г.) В арифметике понятие истинности неформализуемо Теорема Чёрча – Исчисление предикатов первого порядка неразрешимо (1936 г.)

10 4. Понятие изоморфизма в терминах теории формальных систем Формальные теории © Н.М. Светлов, /10