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

Теорема 2.1. Формула А логически влечет формулу В тогда и только то- гда, когда формула Л логически общезначима. (В сокращенном виде эту теорему можно записать: В тогда и только тогда, когда \=А^В). Доказательство. Пусть А^ В. Если А логически влечёт В, то по опреде­ лению импликацииА ^ В истинно в каждой интерпретации, следовательно, ло­ гически общезначима. ПустьА ^ В логически общезначима, т.е. истинна в каждой интерпретации. Если В не является логическим следствием А, то при некоторой интерпретации формула В принимает значение Л для некоторой совокупности значений сво­ бодных переменных, при которой А принимает значение И. По тогда при этой совокупности значений свободных переменныхА ^ В будет ложным, что про­ тиворечит условию логической общезначимостиА^В . Итак, еслиА ^ В логи­ чески общезначима, то А логически влечёт В . Теорема доказана. Теорема 2.2. Формулы А иВ равносильны (логически эквивалентны) то- гда и только тогда, когда формулаЛло гич е ски общезначима. Доказательство. Согласно определению А и В равносильны тогда и толь­ ко тогда, когда каждая из них влечёт другую, тогда и только тогда, когда Л иВ^А логически общезначимы (по теореме 2.1), т.е. тогда и только тогда, ко­ гда логически общезначима. Теорема 2.3. Если формула/! логически влечёт формулу В, а формула/! истинна в данной интерпретации, то в этой же интерпретации истинно и В. Эту теорему легко доказать от противного. Формула в называется логмчес/<-мл/ следствием формулЛ 7, А2, . . ., если в любой интерпретации формула В принимает значение И при каждой совокуп­ ности значений свободных переменных (входящих в В Ai, А2, ..., An), при ко­ торых одновременно все формулы Ai, А2, An приняли значение И. Иными словами говорят, что В является логическим следствием формул А1^2')---Лт^ т>1. В этом случае записывается Л;, Л2,.--Иот h^- § 6. Правила перенесения отрицания через кванторы Прежде чем рассматривать общий случай произвольной формулы, иссле­ дуем формулы частного вида —i VxP(x) и -^ВхР(х), где Р - одноместная преди­ катная буква; более того, будем рассматривать интерпретации этих формул на конечных и-элементных множествах (областях интерпретации). Пусть заданы формулы —i \/хР(х)ж —\ВхР(х) и произвольная интерпретация этих формул на и-элементном множестве 5Vf={<2i,<22,...,a „}. В § 2 установлено, что квантор общности является обобщением конъюнкции, а квантор существо­ 40