Лекция 11. Понятие о формальных системах Содержание лекции: 1.Определение формальной системыОпределение формальной системы 2.Понятия языка и метаязыкаПонятия языка и метаязыка 3.Примеры формальных системПримеры формальных систем Понятие о формальных системах © Н.М. Светлов, /19

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

1. Определение формальной системы Понятие о формальных системах © Н.М. Светлов, /19

1. Определение формальной системы Понятие о формальных системах © Н.М. Светлов, /19

1. Определение формальной системы Примеры алфавита 1.{а,б,в,г,д,е,ё,ж,з,и,й,к,л,м,н,о,п,р,с,т,у,ф,х,ц,ч, ш,щ,ъ,ы,ь,э,ю,я} 2.{,,,, } 3.{1,2,3,4,5,6,7,8,9,0,(,),+,-,*,/} 4.Код ANSI Понятие о формальных системах © Н.М. Светлов, /19

1. Определение формальной системы Пример синтаксиса Используется алфавит {1,2,3,4,5,6,7,8,9,0,(,),+,-,*,/} Цифра ::= 1|2|3|4|5|6|7|8|9|0 ПоложительноеЧисло ::= Цифра|ЦифраПоложительноеЧисло ОтрицательноеЧисло ::= -ПоложительноеЧисло Число ::= ПоложительноеЧисло| ОтрицательноеЧисло Оператор ::= +|-|*|/ Выражение ::= Число|(Выражение)| ВыражениеОператорВыражение Понятие о формальных системах © Н.М. Светлов, /19

1. Определение формальной системы Понятие о формальных системах (с) Н.М. Светлов, 2006 Понятие о формальных системах © Н.М. Светлов, /19

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

2. Понятия языка и метаязыка Использованные выше символы {, } (при задании алфавита) ::= | (при задании синтаксиса) (при задании продукционных правил) – это символы метаязыка, то есть языка, используемого для задания (описания) другого языка или формальной системы Понятие о формальных системах © Н.М. Светлов, /19

3. Примеры формальных систем Пример 1 Алфавит {а, b, #} Синтаксис формул Формула ::= а|b|# Формула ::= ФормулаФормула Аксиома а#а Продукционные правила x#y bx#yb Некоторые теоремы: а#а ba#аb bba#аbb bbba#аbbb … Понятие о формальных системах © Н.М. Светлов, /19

3. Примеры формальных систем Пример 2 Алфавит {M, I, U} Синтаксис формул Формула ::= M|I|U Формула ::= ФормулаФормула Аксиома MI Продукционные правила 1.xI xIU 2.Mx Mxx 3.xIIIy xUy 4.xUUy xy Теоремы: MI (2) MII (2) MIIII (1) MIIIIU (3) MIUU (2) MIUUIUU … Задача: определить, является ли теоремой формула MU. Понятие о формальных системах © Н.М. Светлов, /19

3. Примеры формальных систем Пример 3: исчисление высказываний Алфавит – A 1 = {p, q, …, z, pp, рq, … zz, ppp, …} – A 2 ={,, (, )} Синтаксис формул Формула ::= a | a A 1 Формула ::= (Формула) Формула ::= Формула Формула ::= Формула Формула Аксиомы 1.(a (b a)) 2.(a (b c)) ((a b) (b c)) 3.( a b) (a b) Продукционное правило a b a b Данная формальная система позволяет рекурсивно перечислить все возможные модели тождественно- истинных высказываний, то есть отражает законы дедуктивного рассуждения Понятие о формальных системах © Н.М. Светлов, /19

3. Примеры формальных систем Исчисление высказываний (продолжение) Пусть a b (a b), a b ( a b) Тогда законы Аристотеля – закон тождества p p – закон исключения третьего p p – закон противоречия (p p) являются теоремами исчисления высказываний Исчисление высказываний: непротиворечиво (в том смысле, что если p – теорема, то p – заведомо нетеорема) полно (высказывание тождественно-истинно тогда и только тогда, когда оно является теоремой исчисления высказываний) разрешимо (существует конечный алгоритм доказательства того, что формула является нетеоремой, именно: чтобы доказать, что p – нетеорема, достаточно доказать теорему p) Понятие о формальных системах © Н.М. Светлов, /19

3. Примеры формальных систем Пример 4: исчисление предикатов первого порядка Получается из исчисления высказываний: – введением в алфавит новых символов для обозначения констант предикатов квантора всеобщности в дополнение к символам пропозициональных переменных и логических операций – дополнением синтаксиса: предикатами, характеризуемыми арностью конструкциями для квантификации пропозициональных переменных Понятие о формальных системах © Н.М. Светлов, /19

3. Примеры формальных систем Пример 4: исчисление предикатов первого порядка (продолжение) – введением двух (+) новых аксиом (( t)B(t)) В(u) – «аксиома спецификации» ( t)(a b) (a ( t)b) [при условии, что t не входит в a в качестве свободной (неквантифицированной) переменной] – введением нового продукционного правила a ( t)a – «обобщение» Понятие о формальных системах © Н.М. Светлов, /19

3. Примеры формальных систем Понятие о формальных системах © Н.М. Светлов, /19 Свойства исчисления предикатов I порядка: – – непротиворечивость из пары p и p только одна может быть теоремой – – полнота одна из формул p и p является теоремой – – полуразрешимость существует алгоритм, доказывающий любую наперёд заданную теорему за конечное число шагов – – если заданная алгоритму формула не является теоремой, то такой алгоритм может никогда не достичь команды завершения вычислений не существует алгоритма, способного, доказывая теоремы одну за другой, на каком-либо конечном шаге доказать любую из них Исчисление предикатов I порядка является универсальным метаязыком – – его формулы могут интерпретироваться как определения алфавита, синтаксиса, аксиоматики и продукционных правил – – с помощью его формул может быть описана любая формальная система, включая само исчисление предикатов и системы более высоких порядков Существуют и другие универсальные метаязыки

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

3. Примеры формальных систем Пример 5 – теория чисел Основана на исчислении предикатов первого порядка Алфавит пополняется символами 0, next, +, *, = Аксиоматика пополняется девятью (+) аксиомами: ( a)a+0=a ( a)( b)a+ (next(b))=next(a+b) ( a)( b)(a=b) (next(a)= next(b)) ( a)a*0=0 ( a)( b)a* (next(b))=a*b+a ( a)( b)( c)(a=b) ((a=c) (b=c)) ( a) ̚ (next(a))=0 ( a)( b)(next(a)= next(b)) (a=b) (A(0),( a)(A(a) A(next(a)))) ( a)A(a) Мат. индукция 1.первое свойство нуля (сумма числа и нуля равна числу); 2.второе свойство нуля (произведение числа и нуля равно нулю); 3.третье свойство нуля (нуль не является следующим по отношению к какому-либо числу); 4.первое свойство единицы (увеличение слагаемого на единицу влечёт увеличение суммы на единицу); 5.второе свойство единицы (увеличение множителя на единицу влечёт увеличение произведения на величину другого множителя); 6.если числа, следующие за некоторыми числами a и b, равны друг другу, то сами числа a и b также равны; 7.если два числа равны друг другу, то равны между собой и следующие за ними числа; 8.транзитивность равенства; 9.правило математической индукции: если некоторое утверждение A имеет место по отношению к числу 0, а из его истинности для некоторого числа следует его же истинность для следующего числа, то данное утверждение истинно для любого числа. Понятие о формальных системах © Н.М. Светлов, /19

3. Примеры формальных систем Понятие о формальных системах © Н.М. Светлов, /19 Теория чисел обладает следующими свойствами: – непротиворечивостью – неполнотой (пусть p – формула теории чисел; тогда существуют такие p, что ни p, ни p не являются теоремами) – неразрешимостью (теоремы перечислить невозможно) Теория чисел является универсальным метаязыком – т.к. она является обобщением исчисления предикатов I порядка – содержит все формулы и.п.Iп. – множество теорем теории чисел содержит все теоремы и.п.Iп. Теория чисел содержится в более мощных ф.с.: – алгебра – линейная алгебра – дифференциальное исчисление – теория групп – топология –…–…