Теорема о дедукции
F1, …,Fn, A├ B<*>F1, …,Fn ├ A-> B.
Следствие: A├ B<*>├ A-> B.
Проблема разрешения: существует ли алгоритм, выясняющий для любой формулы логики высказываний, является ли она тождественно
истинной или нет. Имеются нормальные формы, с помощью которых можно решить эту проблему.
Теорема: Для того, чтобы формула логики высказываний была тождественно истинной, необходимо и достаточно, чтобы каждая
элементарная дизъюнкция, составляющая КНФ, содержала бы некоторую переменную с её отрицанием.
<*>(необходимость) очевидно, так как если в каждой элементарной дизъюнкции есть Х и, то она И, то есть, конъюнкция истин
тождественно истинна.
<*>(достаточность) формула тождественно истинна. Покажем, что все элементарные дизъюнкции содержат Х и . Предположим
противное, то есть есть элементарные дизъюнкции, в которых нет таких переменных: Х -дизъ- -дизъ- Z. Тогда эта элементарная
дизъюнкция примет ложное значение, если вместо переменных, которые просто входят в эту элементарную дизъюнкцию, взять
значение Л, а вместо тех, которые входят с отрицанием, взять И, тогда и вся формула примет ложное значение. Чего не может
быть. То есть предположение не верно, а значит в каждой элементарной дизъюнкции есть переменная и её отрицание.
Теорема: Для того, чтобы формула логики высказывания была тождественно ложной, необходимо и достаточно, чтобы каждая
элементарная конъюнкция ДНФ содержала некоторую переменную и её отрицание.