Исчисление высказываний

1. Пропозициональные переменные. Их будем обозначать малыми буквами латинского алфавита с индексами или без них: x, у, х,..., p, q, .. . Различные буквы обозначают разные суждения, внутренняя структура суждений нас интересовать не будет. Суждения, обозначенные пропозициональными переменными, будут называться высказываниями. Будем полагать, что высказывания удовлетворяют закону исключенного третьего и закону непротиворечия, т.е. каждое высказывание либо истинно, либо ложно. Так что каждая переменная у нас будет принимать два значения: значения «истина» будем обозначать «1», а значение «ложь» – «0».

Определение формулы исчисления высказываний.
Алгебра высказываний.
Равносильность формул исчисления высказываний. Конъюнктивная нормальная форма.
Дизъюнктивная нормальная форма. Проблема разрешимости.
Совершенная конъюнктивная нормальная форма. Совершенная