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

формулы А и в логики предикатов называют равносильными (логически эквивалентными), если каждая из них логически влечет д р у г у ю . Если формулы А и В равносильны, то, как и в логике высказы­ ваний, записываем: А ^В. Имеют место следующие теоремы. Теорема 2.1. Формула А логически влечет формулу В тогда и только тогда, когда формулаЛ логически общезначима. (В сокращенном виде эту теорему можно записать: А^ В тогда и только тогда, когда [=Л=> £ .) Доказательство. Пусть А ^ В логически общезначима, т.е. истинна в каждой интерпретации. Если В не является логическим следствием А, то при некоторой интерпретации формула В принимает значение Л для некоторой совокупности значений свободных пере­ менных, при которой Л принимает значение И. Но тогда при этой со­ вокупности значений свободных переменных А ^ В будет ложным, что противоречит условию логической общезначимости А ^ В . Итак, если логически общезначима, то>1 логически влечет JB. Обратное тоже доказывается легко. Действительно, если А ло­ гически влечет В, то по определению импликации, очевидно, Л^В истинно в каждой интерпретации, следовательно, логически общезна­ чима. Теорема доказана. Теорема 2.2. Формулы А и В равносильны (логически эквивалентны) тогда и только тогда, когда формула AsB логически общезначима. Доказательство. Согласно определению А и В равносильны тогда и только тогда, когда каждая из них влечет другую, т.е. по пре­ дыдущей теореме тогда и только тогда, когда иВ ^ А логически 62