close

Вход

Забыли?

вход по аккаунту

?

19

код для вставкиСкачать
Билет №19
Понятие выводимости формулы из совокупности формул. Определение.
Понятие вывода. Правила выводимости.
Пусть H = {A, ..., Z}
Формула В выводима(˫) из совокупности Н, если В содержится в Н; В - доказуемая формула исчисления высказываний;
В получается по правилу заключения из формул С и С -> В, которые выводимы из совокупности Н.
То, что формула выводима из совокупности Н пишется как Н˫В.
Класс форму, выводимых из совокупности Н совпадает с классом доказуемых формул, когда совокупность Н содержит только доказуемые формулы, либо когда Н пуста. Если совокупность Н содержит хотя бы одну не доказанную формулу, то этот класс шире класса доказуемых формул.
Доказать - Н = { A, B} H˫A&B
AϵH, BϵH
H˫A (1)
H ˫B (2)
Возьмем аксиому (2.3) и подставим вместо x, y, z - A, B, A
∫_(x,y,z)^(A,B,A)▒〖(2.3)〗
H˫(A->A) -> ((A ->B) -> (A ->A&B)) (3)
∫_(x,y)^(B,A)▒〖(2.3)〗
H˫B -> (A -> B) (4)
Тогда получим доказуемые формулы ˫A ->A => H˫A ->A (5); тогда из (5) и (3) =>
H-> (A -> B) -> (A -> A&B) (6)
Из (2) и (4) => H˫ A ->B (7) Из (7) и (6) => H˫ A -> A&B (8)
Из (8) и (1) => H˫ A&B (9)
Понятие вывода.
Выводом из конечной совокупности формул Н называется всякая конечная последовательность функции В1, В2...Вк , каждый член которой удовлетворяет одному из следующих трех условий:
Он является одной из формул совокупности Н;
Он является доказуемой формулой;
Он получается по правилу заключения из любых двух предшествующих членов последовательности В1, В2...Вк.
Из определения выводимой формулы и понятия вывода из совокупности формул следуют следующие свойства вывода:
Всякий начальный отрезок вывода из совокупности Н есть вывод из Н;
Если между двумя соседними членами вывода из Н или в начале или в конце вставить некоторый вывод из Н, то полученная последовательность формул будет выводом из Н;
Всякий член вывода из совокупности Н является формулой выводимой из Н; Если Н содержится в W, то всякий вывод из Н является выводом из W.
Для того, чтобы формула В была выводима из Н необходимо и достаточно, чтобы существовал вывод этой формулы из Н.
Правила выводимости.
Пусть H, W- две совокупности формул исчисления высказываний. H,W=HUW
Если W состоит из первой формулы Н1С = HU{C}
Если Н˫А, то H, W ˫ А, это правило следует непосредственно из определения вывода из совокупности формул.
Если Н, С ˫ А и Н˫С, то Н˫А
Доказательство: Так как по условию из Н,С˫А то существует вывод из Н,С, последней формулой которого является формула А - В1, В2, ..., Вк-1, А (1). Так как из совокупности Н˫С , то существует вывод из Н, последней функцией которой является С - С1, С2, ... ,Сm-1 , С (2). Если в выводе 1 формула С отсутствует, то он является выводом только из Н следовательно А выводима из Н. Если среди формул вывода 1 имеется формула С, ( пусть Вi) тогда между формулами Bi-1 и Bi+1 стоит вывод 2, в результате получим вывод из совокупности Н. B1, B2,...,Bi-1, C1, C2,..., Cm-1, C, Bi+1, Вк-1, A (3)
Если из совокупности Н, С˫А, W˫С, то Н, W ˫ А.
Доказательство: так как из Н, С˫ А, тогда по первому правилу формула А выводима из совокупности Н,W, С˫А, то Н,W˫С. Применим правило 2 и получим Н,W˫А.
Если Н˫С -> А, то Н,С˫А
Доказательство: так как Н˫С ->А, то существует вывод из Н В1, В2, ..., Вк-1, С->A (1). Присоединим к совокупности Н формулу С и добавляя в конец вывода формулу С мы получим В1, В2, ..., Вк-1, С->A, С (2), но можно также получить В1, В2, ..., Вк-1, С->A, С, А (3) из (1) и (2) по правилу заключения следовательно ˫А,С˫А
Если Н,С˫А, то Н˫С ->А - обобщенная теорема дедукции. Если {C1, C2,...,Ck} ˫ A, то ˫С1 -> (C2-> -> (C3 ->...(Ck->A)...))
(H˫A, H˫B)/(H˫A&B)
(H,A˫C; H, B˫C)/(H,A ̬, B˫C)
Автор
lovematanfo
Документ
Категория
Без категории
Просмотров
150
Размер файла
19 Кб
Теги
билет
1/--страниц
Пожаловаться на содержимое документа