Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

При определении равносильности двух форм не обязательно предполагать, что они содержат одни и те же пропозициональные буквы. При этом, если какая-нибудь буква, например, В входит только в одну из двух равносильных форм, то эта форма от значений В не зависит. Высказывание "Л равносильно В" будем обозначать следующим образом: Пусть А, В, С - произвольные формы. Отношение равносильности форм, как легко видеть, обладает следующими свойствами: \) А ~ А- рефлексивность; 2) если А ~ В, то В ~ А - симметричность; 3) если А ~ В vi^B ~ С ,тоА~ С - транзитивность. Следовательно, отношение равносильности является отношением эквивалентности и порождает разбиение множества форм на непересекающиеся классы. В каждый класс попадают равносильные между собой формы. Докажем теорему. Теорема 1.7. Пропозициональные формы А и В равносильны тогда и только тогда, когда А=В является тавтологией. Доказательство. Необходимость. Пусть А и В равносильны, следовательно, они при каждой совокупности значений всех пропозициональных букв, входящих в них, принимают одинаковые истинностные значения, тогда по определению связки = форма А=В всегда принимает значение И, т.е. является тавтологией. Достаточность. Пусть А=В тавтология, т.е. принимает всегда значение И. Это означает, что А и В имеют всегда одинаковые истинностные значения, т.е. они равносильны. Теорема доказана. Пусть А, В, С - пропозициональные буквы, Т- тавтология я П - противоречие. Используя таблицу истинности, легко показать: 1) —i(—iAJ равносильной. Если под А понимать обозначение некоторого высказывания, то получаем, что двойное отрицание А означает то же, что и А. Полученное соотношение между —if—iAJ и А называют законом двойного отрицания. Аналогичным образом можно показать, что имеют место следующие законы (правила): А~В. законы коммутативности; законы ассоциативности; 13