logo search
практикум по мат

Полнота и непротиворечивость исчисления высказываний

Формула φ(x1,…,xn) ИВ называется тождественно истинной (обозначается ⊨φ), если φ(x1,…,xn) – тождественно истинная формула как формула алгебры высказываний.

Теорема 4 (о полноте). Формула φ ИВ доказуема тогда и только тогда, когда φ тождественно истинна:

φ⊨φ.

Таким образом, для того чтобы установить, доказуема ли формула ИВ, достаточно составить ее таблицу истинности. Как известно, существует эффективный алгоритм построения таблицы истинности, и, значит, ИВ разрешимо. Кроме того, из теоремы о дедукции и теоремы о полноте легко следует, что отношение эквивалентности ≡ в АВ и ИВ совпадают.

Теорема 5 (о непротиворечивости). ИВ непротиворечиво.

Доказательство. По теореме о полноте любая формула, не являющаяся тождественно истинной, не доказуема в ИВ. Например, такой формулой является формула х∧¬х. Следовательно, ИВ непротиворечиво.

Схема аксиом называется независимой в исчислении, если хотя бы один ее частный случай не доказуем в исчислении без этой схемы.

Теорема 6. Схемы аксиом ИВ независимы.

    1.