Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Аксиоматическая теория L исчисления высказываний

Формальная (аксиоматическая) теория

Лекция 4

Простой пример формального исчисления (исчисление А)

 

Формальный язык:

1. Алфавит: O I + =

2. Терм: O, OI, OII, OIII, … - суть термы, если t1, t2, t3 – термы, то t1+t2=t3 – формула.

Обозначим OII…I через n, где n – количество палочек.

Исчисление:

3. Аксиомы: 0 + 0 = 0, 1 + 0 = 1, 0 + 1 = 1

4. Правило вывода: из k1 + m1 = n1 и k2 + m2 = n2 непосредственно следует k1+k2 + m1+m2 = n1+n2

Вывести 2 + 3 = 5

Формальная (аксиоматическая) теория считается определенной, если:

(1). Задано счетное множество символов. Конечные цепочки символов - выражения теории .

(2). Выделено подмножество выражений теории , называемых формулами .

(3). Выделено некоторое подмножество формул , называемых аксиомами теории .

(4). Задано конечное отношений между формулами, называемых правилами вывода.

«Непосредственное следствие», вывод, следствие множества формул, теорема.

(1). Символы L: и заглавные буквы латинского алфавита (с цел. полож. индексами).

(2). Все буквы - формулы. Если ,- формулы, то и - тоже формулы.

(3). Каковы бы ни были формулы теории L, следующие формулы суть аксиомы L:

(A1) ;

(A2) ;

(A3) .

(4). Правило вывода - modus ponens (МР): есть непосредственное следствие и .

Пример вывода формулы в теории L:

(1.) -

Теорема дедукции: Если Г - множество формул, и - формулы и , то .

В частности, если , то .

Доказательство: , пусть вывод , где .

Индукцией по i (1<=i<=n) докажем (тогда теорема дедукции доказана).

- либо элемент Г, либо аксиома, либо совпадает с .

В первых двух случаях из схемы аксиом (А1) и по МП .

В третьем случае, когда совпадает с , из (1.) , следовательно, .

Допустим, что для любого k<i.

- либо элемент Г, либо аксиома, либо совпадает с , либо следует по МП из каких-то и (j,m<i).

Первые три случая как и при i=1.

В четвертом случае имеет вид ,

согласно индуктивному предположению, и .

Из схемы аксиом (А2) .

По МП , и снова по МП .

Утверждение доказано по индукции (а, значит, и теорема дедукции доказана).

Замечания:

1. При доказательстве использованы только схемы аксиом (А1) и (А2).

2. Доказательство позволяет по данному выводу из Г и построить вывод из Г.

Следствия:

1. . Действительно, ведь из .

2. . Действительно, ведь из .

3. . Действительно, ведь

Утверждение: Формула теории L является теоремой теории L, тогда и только тогда, когда она является тавтологией.

Утверждение: Всякая теорема теории L является тавтологией.

Теорема о полноте теории L: Если формула теории L является тавтологией, то она является теоремой теории L.

<== предыдущая лекция | следующая лекция ==>
Формальная аксиоматическая теория | Лекция 5. Доказательство нескольких утверждений (a - g)
Поделиться с друзьями:


Дата добавления: 2013-12-13; Просмотров: 3168; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.009 сек.