Исчисление высказываний
Напомним, что тавтологией мы называли пропозициональную формулу, истинную при всех значениях переменных. Оказывается, что все тавтологии можно получить из некоторого набора "аксиом" с помощью "правил вывода", которые имеют чисто синтаксический характер и никак не апеллируют к смыслу формулы, ее истинности и т. д. Эту задачу решает так называемое исчисление высказываний. В этой лекции мы перечислим аксиомы и правила вывода этого исчисления, и приведем несколько доказательств теоремы о полноте (которая утверждает, что всякая тавтология выводима в исчислении высказываний).
