Математическая логика и теория алгоритмов

Пусть Л, В, С ~ произвольные пропозициональные формы. От­ ношение равносильности пропозициональных форм, как легко видеть, обладает следующими свойствами: рефлексивность; 2) если А ~ В, то В ~ А ~ симметричность; 3) если А В и В ~ С ,тоА ~ С- транзитивность. Следовательно, отношение равносильности является отношени­ ем эквивалентности и порождает разбиение множества пропозицио­ нальных форм на непересекающиеся классы. В ка^кдый класс попада­ ют равносильные меиоду собой пропозициональные формы. Докансем теорему. Теорема 1.3. Пропозициональные формы А и В равносильны тогда и только тогда, когда является тавтологией. Доказательство. Необходимость. Пусть А т В равносильны, следовательно, они при каждой совокуп^юсти значений всех пропози­ циональных букв, входящих в них, принимают одинаковые истинно­ стные значения, тогда по определению связки s форма AsB всегда принимает значение И, т.е. является тавтологией. Достаточность. Пусть А=В тавтология, т.е. принимает всегда значение И. Это означает, что А и В имеют всегда одинаковые истин­ ностные значения, т.е. они равносильны. Теорема доказана. В природе существует внутренне присущая ей скрытая гармония, отражающаяся в наших умах в виде простых математических знаков. Г. Вейль § 6. Важнейшиеп а ры равносильных пропозициональных форм Пусть А, В, С- пропозищ-юнальные буквы, Т- тавтологияи i 7 - про­ тиворечие. Используя таблицу истинности, легко показать: 1 ) 1 (1 равносильно А. 26