Описание системы аксиом Гилберта Иакермана, Россера, Мередита, Клини. Доказательств о равносильности аксиом и введенных в них связок. Расчет корректности вывода ModusTollendoTollens. Теорема о полноте метода резолюций. Выводимость на базе противоречия.
Аннотация к работе
Альтернативные системы аксиом Система аксиом Гилберта Иакермана Связки: , , Вводятся следующие аксиомы: Система аксиом Россера Вводятся связки: &,-,A->B=-(A&-B) A->(A&A) A&B->B (A->B)->(-(B&C)->-(C&A)) Система аксиом Мередита: (Связки: ->, -) [((A->B)->(-C->-D))->C]->((C->A)->(D->B)) Во всех случаях задавались схемы аксиом, т.е. реальное количество аксиом в каждом случае бесконечно. (K1) А->(B-A) (K2) (K3) A&B->A (K4) A&B->B (K5) A->(B->(A&B)) (K6) A->(A B) (K7) B->(A B) (K8) (A->C)->((B->C)->((AvB))->C (K9) (A->B)->((A->-B)->-A) (K10) - -A->A Здесь все логические связки вводятся напрямую, а не рассматриваются, как сокращения друг друга. В принципе, можно показать, что исчисление высказываний К, и ИВ L равносильны, как формальные теории. В теории L имеется тавтология A->(B->-(A->-B)) выводимость которой можно доказать с помощью теоремы о полноте. Рассмотрим доказательство: Выводимость G и множества F1…Fn означает по теореме дедукции F1,F2…Fn-1 Fn->G … (тут типа все через импликации через вложенные скобки) Выводимость данной формулы по теореме означает что она является тавтологией. Приведение формулы к КНФ. КНФ тоже можно записывать как множество дизъюнктов. Т. е. есть КНФ С1 С2 … Сn => (C1, C2, …,Cn) - КНФ. Формула, не содержащая свободных переменных, называется предложением.