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

букв, входящих в Л в , эти формы принимают одинаковые истинно­ стные значения. Например, форма равносильна форме А=>В, в чем легко убедиться с помощью таблиц истинности; 7 А V в и л и л и л и и л и л л л и и и А => в л и л л и и и л л и и и В этих таблицах' результирующие столбцы совпадают, т.е. при одинаковых значениях букв А иВ значения форм 1 AvB и А^В равны, следовательно, эти формы равносильны. Далее, форма AvA&B равно­ сильна^. Действительно, имеем следующие таблицы: А V А & в л л л л л л л . л л и и и и л л и и и и и Л 'л И Таюке, очевидно, A ' vIA равносильно5 v l Л. При определении равносильности двух форм не обязательно предполагать, что они содержат одни и те же пропозициональные бу­ квы. Так, в последних примерах имеем случаи, когда в равносильные формы входят разные буквы. При этом, если какая-нибудь пропози­ циональная буква входит только в одну из двух равносильных форм, то эта форма при всех значениях этой буквы принимает одно и то же значение, если значения других фиксированы. Следовательно, хотя эта буква и входит в форму, но истинностная функция, определенная формой, от значений этой буквы не зависит. Высказывание "А равносильно В" будем обозначать следующим образом: А'~ В. 25