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

общезначимы, т.е. тогда и только тогда, когда Л=В логически обще­ значима. Теорема 2.3. Если формула Л логически влечет формулу В, а Л истинно в данной интерпретации, то в этой же интерпретации ис­ тинно и В. Эту теорему легко доказать от противного. о Если формула Л является замкнутой формулой, то, очевидно, при приписывании к Л любых кванторов получим формулу, равно­ сильную Л, т.е.: ^ ~ Q\Qi>- ->Qn^, здесь QIQJ,..,, Q „ - любая совокупность кванторов по любым переменным. Также введем понятие логического следствия из заданного множества формул логики предикатов. Формула В называется логическим следствием формул Ли Лг, если в любой интерпретации формула В принимает зна­ чение И при каждой совокупности значений свободных переменных (входящих в В иЛь А2, ..., Л„), при которых одновременно все форму­ лы А\, А2, ..., А„ приняли значение И. Иными словами говорят, что В является логическим следствием формул w>l. В этом случае записываетсяЛь [=5. § 7. Правила перенесения отрицания через кванторы Преисде чем рассматривать общий случай произвольной форму­ лы, исследуем формулы частного вида 1Уд:Р(л:) и 1Эл:Р(х), где Р - одноместная предикатная буква; более того, будем рассматривать интерпретации этих формул на конечных н-элементных множествах (областях интерпретации). Пусть заданы формулы 1У л :Р( д:) и ~\^ХР{Х) и произвольная интер­ претация этих формул на н-элементном множестве M={ai,a2,--,an}- 63