Альтернативные системы аксиом
Методическое пособие - Философия
Другие методички по предмету Философия
Альтернативные системы аксиом
Система аксиом Гилберта Иакермана
Связки:
, ,
Вводятся следующие аксиомы:
Система аксиом Россера
Вводятся связки:
&,-,A->B=-(A&-B)>(A&A)&B->B
(A->B)->(-(B&C)->-(C&A))
Система аксиом Мередита:
(Связки: ->, -)
[((A->B)->(-C->-D))->C]->((C->A)->(D->B))
Во всех случаях задавались схемы аксиом, т.е. реальное количество аксиом в каждом случае бесконечно. Можно задать систему с конечным числом аксиом, говоря, что задана не схема, а формула, но при этом возникает необходимость введения нового правила вывода, называемого правилом подстановки:
Если дана формула Ф(А1… Аn) и имеются некоторые формулы Ф1…Фn, то мы можем получить формулу Ф(Ф1…Фn), подставив формулы Фi вместо соответствующих пропозиционных переменных.
Система аксиом Клини.
(K1) А->(B-A)
(K2)
(K3) A&B->A
(K4) A&B->B
(K5) A->(B->(A&B))
(K6) A->(AB)
(K7) B->(AB)
(K8) (A->C)->((B->C)->((AvB))->C
(K9) (A->B)->((A->-B)->-A)
(K10) - -A->A
Здесь все логические связки вводятся напрямую, а не рассматриваются, как сокращения друг друга.
В принципе, можно показать, что исчисление высказываний К, и ИВ L равносильны, как формальные теории. Основная задача в процессе подобных доказательств о равносильности аксиом и введенных в них связок, заключается в том, что формулы, необходимые для вывода более короткой или заданной явно логической связкой, выводимы на основе эквивалентной ей формуле в другой аксиоматике. При этом из формулы из первой аксиоматике, выводятся формулы, из которых можно вывести формулы второй аксиоматике.
Например, рассмотрим эквивалентность формул:
(A->-B) в аксиоматике ИВ L и A&B.
На основании схемы К5 и МР доказывается, что из формулы A&B выводится формула в аксиоматике К формула А->В. Далее на основе аксиом К3 и К4 видим что из A&B выводится А, из A&B выводится В.
В теории L имеется тавтология A->(B->-(A->-B)) выводимость которой можно доказать с помощью теоремы о полноте. Исходя из этой формулы и МР, получаем, что .
В аксиоматике L имеет место тавтологии и , следовательно, по МР имеем и .
В итоге можно сделать вывод (A&B).
На основании вышеизложенного, можно сделать вывод
По аналогии можно вывести
Что касается , то уже было доказано и.
Таким образом, мы можем переносить аксиомы между схемами аксиом.
Теорема
Рассмотрим теоремы:
F1…Fn,
т.е. тогда, когда последняя формула является тавтологией.
Рассмотрим доказательство:
Выводимость G и множества F1…Fn означает по теореме дедукции
F1,F2…Fn-1Fn->G…
(тут типа все через импликации через вложенные скобки)
Выводимость данной формулы по теореме означает что она является тавтологией.
Представим импликацию через дизъюнкцию:
Отсюда следует, что выводится т. и т.т., когда последняя формула является тавтологией.
Пример покажем с использованием ModusTollens.
Покажем, что
Для этого нам нужно доказать что
является тавтологией
Просто находим таблицу истинностей для всех значений P и Q.
F1…Fn,
т.е. является противоречием.
Док - во. В соответствие с предыдущей теоремой, эта теорема равносильна является тавтологией, это в свою очередь равносильно , раскроем импликацию
,
далее по законам Де Моргана
В качестве примера рассмотрим доказательство корректности еще одного правила вывода ModusTollendoTollens. Т.е. покажем, что
В соответствии с только что доказанной теоремой надо вывести, что
по таблице истинности видно, что это верно.
Теорема
F1,…,FnG когда выводима формула F1&F2&…&FnG, т.е. когда эта формула - тавтология
Док-во:
F1,…,Fn |- Gпо теореме дедукции F1,…, Fn-1 |- FnGF1 (F2 … (FnG) … ) - тавтология ? =
F1V (F2 … (FnG) … ) = … = F1VF2V … VFnVG = (по з-ну Де Моргана) = (F1&F2& … &Fn) VG = F1&F2& … &Fn G - тавтология.
Теорема:
F1, … ,Fn |- G
является ли формула F1&F2& … &Fn&G - противоречием ?
Док-во:
По предыдущей теореме: F1, … ,Fn |- GF1&F2& … &Fn&G - противоречие ?
Способ доказательства утверждения от противного: (А B) (BA).
Пример:
Докажем, что из формулы PQ и Q выводится P, т. е. PQ, Q |- P/
По 1-й теореме достаточно показать, что формула ((PQ) &Q) P - тавтология.
PQ123ЛЛИИИЛИИЛЛИЛЛЛЛИИИЛЛ
тавтология=>такая выводимость имеет место.
Приведение формулы к КНФ. Выводимость на основе противоречия
Дизъюнктом наз. дизъюнкция пропозициональных переменных или их отрицаний, кот.наз. литералами. Для простоты дизъюнкт принято записывать как перечень литералов, т. е. если C = L1VL2V … VLn, то С = (L1, …, Ln).
КНФ наз. логическое произведение дизъюнктов. Принято считать, что в дизъюнкте переменные и литералы не повторяются, т. к. LVL = L, LVL И (тождественная и