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

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

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

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

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

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

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

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

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

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