Вопрос №9. Связь между алгеброй высказываний и исчислением высказываний

Вопрос №8. Правило выводимости.

Вопрос №7. Понятие вывода.

Выводом из конечной совокупности формул Н называется всякая конечная последовательность формул В1,В2,..Вn, всякий член которой удовлетворяет одному из условий:

1. Он является одной из формул совокупности Н

2. ОН является доказуемой формулой

3. Он получается по правилу заключения из двух любых предыдущих членов последовательности B1.B2...Bn

Пусть H и W – это 2 совокупности формул ИВ. Будем понимать, что идет объединение этих множеств.

I.

II.

III.

IV.

V. Теорема дедукции

Обобщение теоремы дедукции:

VI. Правило выделения конъюнкции:

VII. Правило выделения дизъюнкции:

VIII. Правило соединения посылок:

IX. Правило разъединения посылок:

Связь между алгеброй высказываний и исчислением высказываний (формулировка теорем).

Теорема1. Каждая формула, доказуемая в ИВ, тождественно истина в АВ.

Теорема2.О выводимости.

Пусть А-некоторая формула ИВ; х1,х2..хn - набор переменных, содержащий все переменные входящие в А; i1,i2...in - произвольный фиксированный набор значений этих переменных. Обозначим через H конечную совокупность формул:

Если Ri1,i2,in (значение А на одном наборе значений переменных)=1, то выводима из H, если =0, то не(наверху палочка)A выводима из H.

Теорема3.Каждая тождественно истинная формула алгебры высказываний, доказуема в исчислении высказываний.

Дата добавления: 2015-04-24