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

Свойство аксиоматической теории выводить любой логический закон (как, например, тавтологии в ИВ) называют её полнотой (в широком смысле). Из доказанных выше теорем следует, что ИВ – это полная аксиоматическая теория.

Формальную аксиоматическую теорию называют непротиворечивой, если не существует формулы A, такой, что одновременно выводимы формулы A и A. Теорема: ИВ непротиворечиво. Доказательство: всякая выводимая в ИВ формула тождественно - истинна. Отрицание этой формулы не является тождественно - истинной формулой. Следовательно, ни для какой формулы A невозможно, чтобы одновременно A и A. Теорема доказана.

Оказывается, что система аксиом A1 – A3 исчисления высказываний независима. Установим независимость аксиомы A3 от остальных. Будем считать, что переменные принимают значения из множества {a, b} (двузначная логика). Операции и зададим таблицами:

X	X
a	a
b	b

X	Y	X Y
a	a	a
a	b	b
b	a	a
b	b	a