Ш.И._Галиев_МЛ_и_ТА_2004

данные вначале § 4 ДЭДНОЙ главы, их задавали, мы всегда будем полу­ чатьистинные огнощешх или высказывания.

Примером логически общезначимых формул, очевидно, яшяшгея следующие формулы; A=?A,VxA=>3iA,A=A.

Если формула А является логически общезначимой, то будем записывать иногда в сокращенном виде: «|=Л» и эта запись читается: iA являетсялогическиобщезначимойформулой(логикипредикатов)».

Формула логики предикатов А называется выполнимой, если существует интернреицня, в которой выполнимаЛ.

Примером выполнимой формулы явласюя формула Vr/lle^V) Действительно, если вить 9^[0,®), Л(х.у,Ь,) поставить в соответствие предикат (отношение) х н у 2 г, Ai поставить в соответствие число 2, то наша формула я этой интерпретации означает, что Vx(r + у S 2). Послгднее будет истинно, например, прилюбы* значениях у £ 2. Сле­ довательно, заданная формула выполнима в этой интерпретации. Таким образом, для нашей формулы существует интерпретация, в которой она выполнима, поэтому этаформулавыполнима.

Имеют место следующие очевидные утверждения. Формула А логически общезначим* тогда и только тогда, когда формула Vl не являете» выполнимой. Формула А выполниматогда и только то!ДЯ, шгдл формула 1А не является логическиобщезначимой.

Кулем najLiourt. формулу .юшки продикатов А противоречием, если формула "U является логически общезначимой или, что то же, если формулам ложна во всякойинтерпретации,

Говорят, что формула логики предикатов А логически влечет формулу логики предикатен В, если в любой интерпретации формула В Принимает значение И при каждой совокупное™ значений свобод­ ныхпеременных (вкодящи» иА иВ), при когорш формулаЛ приняла значение И. Иначе говорят, >гго В iiBimei-ся jtoaweaaat следствием формула А. В этом случае записываемА |= В и читаем: «из А логиче­ ски следует В» или «В является логическим следствием из А». Отме­ тим, 'гго «А |« Я» не является формулой, а является метаутиерждепием относительно формулИ иВ(логики предикатов).

61

Формулы Л и в логики предикатов называют равносильными (логически эквивалентными), если каждая из них логически влечет

другую.

Если формулы Ап В равносильны, то, как и в логике высказы­ ваний, записываем: А -Я.

Имеют местоследующиетеоремы.

Теорема 2.2. Формула А логически мечет формулу if тогда ч только тогда, когдаформулаА^>Влогически общезначима.

(В сокращенном виде эту теорему можно записать: А\‘ В

тогда и толькотогда, кош [MSB.)

Доказательство. Пусть А=>В логически общезначима, т.е. истинна в каждой интерпретации. Если В не является логическим

Обратное тоже доказывается легко. Действительно, если А ло­ гически йлечет В, та по определению импликации, очевидно, ATSB истинно а каждой интерпретации, следоеателыю, логически общезна­ чима. Teopeuiдоказана

Теорема 2.2. Формулы А я В равносильны {логически эквивалентны) тогда и только тогда, когда формула АзВ логически общечкячима.

Доказательство. Согласно определению А и В равносильна тогда и толькотогда, когда каждая из них влечет другую, т.е. по пре­ дыдущей теореме тогда итолькотогда, когдаЛ=>В к В л 4 логически

Теорема 2.3. Если формулаЛ логически влечет формулу Б, аА истинно в данной интерпретации, гп в этой *е штерпрегацни ис­ тиннои В

Эту теоремулегко локазт от противного.

Если формула А является замкнуто» формулой, тп, очевидно, при приписывании к А любых каанторое получим формулу, разно­ сильную,4, т.е.:

A -Q lQ1,..,Ql,Al

здесь QiCh....Si - любая совокупность ккакгороь по любым переменным.

Также введем понятие логического слецсгаия из заданного множества форму;] логики предикатов.

Формула В вшивается логическим следствием формул Л], А%, ... Ав гели в любой интерпретации формула В принимает зна­ чение И при каждой сово1супности значений свободных пгременных (входящих 8 В иЛ ь А-,, Л,), при которая; одновременно вое форму­ лы /)[, Ai, .... /1„ приняли значение Я. Иными словами говорят, что

В является логическим следствием формул	т'ц[. В этом
случаезаписываетсяЛ„ А2,...Ат (=В.

§ 7. Правила перенесения отрицания через кванторы ГТрежае чем рассматривал, общинслучай произвольной форму­

лы, исследуем формулы частного вида "frtPM и Тэ*?(;г), где Р ■■ одноместная прзливатная буква; более того, будем рассматривать

(области* интерпрвтадии).

Пусть зашшч формулы ^Vjp(x) иТЗхЯл) и произвольная интер­ претация этих формул на л-элементиоч множестве

63

В J 2 устанокпсно, что квактор обшности является обобщением конъ­ юнкции, а квантор существования - дизъюнкции и для я-элементаых областей интерпретации имеютместосоотношения(2.7) и (2.8):

У.тД*) раиикилыю

3tP{x) равносильноi>(a|)vP(o!)'/„1v?(a „).

Очевидно, высгазыяання равносильны чотда и только тогда, когда равносильны отрицания этих высказываний, поэтому первое из этих соотношенийэквивалентноследующему:

W (x ) ~l(P{aij&P(a!)S,..&/’(a„))-lf(nl)vl)'(fl,)v,..v 1 Р(а,).

Правая часть полученного соотношения есть не что иное, как мпяа выыазыгання 3*1 Pixy Таким о5р«ом, для л-эяементиых областей интерпретации имеем:

'У хО Д -зЛ /’М.	(2.9)
Анаиотчно получим:
. 1ЪР(х)~ I	-1 Р(о,)Л1Р(а!Д .

следааггсльно, д а и-алемвш-их* областей интерпрстаи.ии имеет

Vdi^j:>-VilP(x).

(2.10)

Соотношения (2,9) и (2.Ю) показывают, что при перенесении отрицания через кванторы последние меняются ка двойственные. По­ кажем, что эти правила имеют место для указанных формул, но ужебез ограничения конечностиобластей интерпретации.

Рассмотрим формулу lVx/Yx). Возьмем произвольную (во фик­ сированную) интерпретацию. 13 каждой интерпретации эта формула означает некоторой высказывание (так как не имеет свободных переменны»)

64

Пуси высказывание 1УхДх) истинно. Тогда высказывание vxP(x) - ложно, следовательно, существует значение переменной х, Д1* которого Р(х) ложно. Обозначим одно из таких значений через 4. Иган, be И и l‘( h j- ложно. В таком случае ] Р(Ь) истинно. тв. сущест­

вуеттакоех (равное й), что1Я(У) истинно, поэтому истина. Обратно, пусчг теперь высказыванпв ”д-1 Р(х) истинно. Титла по

определению квантора сущеовования найдена такое значение пере­ менной х что .Я(лг> истинно. СКозначим одно ю писих значений через

Ь. Итак, i s Ж и 1 f'(b) истинно. Следовательно ГЩ ложно. Во тогда, по определению Квантора общности, VxJ'(x)=Jl, a lVx/’fr) истинно. В результате мы доказали, что в каждой интерпретации \lxPix)

истинно тогда и только тогда, когда истинно 1?] ?(х), поэтому: fyx/W -&]?(*).

Аналогичным образом можно установить.'

Далее рассмотрим формулу ~tyxA\x,y) с одной двуместной лредИХатнзй буквой А1. Возьмем для зтой формулы произвольную (но фиксированную) интерпретацию. !Я выбранной интерпретации используем произвольное значение свободной переменнойу, скажем, у=с (ее М) Выражение ~\tfxA‘(x,c) представляет собой отрицание результата иавешилания квантора общности нв одноместный предикат

А1х,с) и по	доказанному йстнндастые	значения ]vx45(t,c)
и ат1л!(*,с) совпадают, следовательно:
УхА\х,у)	- ^ ^ { х .у ) .	(2.11)

дующие равносильности

~кхА"<х^ь.. л ) - 3*,] A,'(xuXi,....*„),

1 ЗХ:А,Ъ,Л ...Л1- W,1 A>Xx,j:b..X).

Можнодоказать, тга иди» прзтподамойформулыА кмекгтместо:

1VxA~3xlA.

(2.12)

1а ы -У х1л.

(2.13)

Если отрицание споит перед несколькими квакгирами, го, ис­ пользуя (2,12) и (2.13), отрицание мо*но перекосить последовачгльно через каждый ш saamopuE, изменяя егонадвойственный.

В результате доказанаследующая теорема.

Теорема 2.4. Огрицанне формулы, начинающем с кваторов, равносильно формуле, полученной заменой каждого квантора на двойственный нперенесением знака отрицания за квзнторы.

Иысказывання (2.12) и (2.13) явпяктта аналогами законов д; Морганя. Испппьлуя их, легко яыразотъ один из кванторов через другой. Для этого применим операцию отриищия к левым и празым частимсоотношений (2.12) и (2.13). Получим соответственно:

У х4~]1х]д	(2.14)
ilw l- 'W U	(2.15)

Равносильности <2.14) и (2.15) показипмот, тго при определе­ нии формул логики предикатов можно было ввести только один из кванторов. Например, можно считать по определению, что для произ­ вольной формулыЛ выражение(V*<4) естьформуле, а выражениеЭхЛ уже является обозначениемдля формулы(faafU)».

Конфуаай

§ 8. Правила перестановки кванторов

Пусть А ■произвольная формула логики предикатов. )’ассмотрим для А произвольную, но фиксированную интерпретацию. Сразу

66

же на опредеЛЗКИЯ кванторов получаем, что там, где истинно Vx'ryA,

истинно и VyVxA, и.наоборот. В силу произвольности интерпретации сделуот, ’па

VxYyA -ЧуУхА.	(2.16)
Точно также поучаем что
ЗхЧуА - ?хЧуА.	(2.17)

Таким образом, при гвременв мает стоящих радом одноимен­ ных UBni'TopoR получаем равносильные формулы. Итак, одноименные кванторы, стоящие рядом, можно перс:тавлять местами.

Известно, чти формулы. А и В равносильны тогда и только тогда, когда А^В язляется логически общезначимой формулой (тео­ рема 2.2). Тогда из (2.16) и(2.17) получаем, что формулы

MxVyAtiVyVxA и rix3yA"3y3zA
являются логически общезначимыми.
Разноименные квангори, оказывается,	можно переставлять
не в каждой формула. Докажем теорему.
Теорема 2.5. Для каждой формулы А и любых предметных
переменных х иу формула
ЭхУуА-^ЪуЗхА	(2.15)
Vy'dxA^ixVyA	(2.19)

не является логически общезчмимоП (при любой формуле А)

Доказательство. Для доказательства логической общезначимо­ сти формулы (2.15) фиксируем произвольную интерпретацию форму­ лы^, и ия определений коанто]>ов сразу получаем, тго формула (2.18) истинна. Таким образом, а любой интерпретации формула (2.18) истинно, следовательно, ока логически общезначима.

Чтобы доказать, 'гго формула (2.19) не является логически об­ щезначимой (при любой формуле ,4), достаточна привести пример формулы А к интерпретации для нее, где формула (2.19) неистинна.

67

Пусть область интерпретации М - множество действительных чисел

и формула.4 означает предикатх>у, тогда высказывание
Vy3x(x>y)	(2.20)

означает, «то дл* любого *жм у ьуиксгвуе? чиило х большее, 'ie« у. Эта высказывание истинно Высказывание, полученное и? (2.20) nepsстановкой кванторов 3xiy{x>y), означает, что существует числи л больше шобосо другого числа и, очевидно, чаляися ложным. Тогда ложна импликация: ЧуЗх(Х>у)=эЗхЧу(Х>у). Следовательно, формула (2.19) не истинна в приведенной интерпретации, те. не ивляетси логи­ чески общезначимой. Теоремадоказана.

Заметим, что в частаом случае формула(2,19) может оказаться н логически общезначимой, налример, когда А являете» замкнутой формулой. В этом случае, как известно (см. § 6), формула А равно­ сильна формуле Q\Qi~Qti, где Q,,Q^...,Q„ - любая сово­ купность кванторов. Поэтому формула (2.19) будет логически общезначимой.

Однако подчеркнем еще раз, wo для произвольной формулы перестановка разноименных кванторов не Всегда приводит к равно­ сильнымформулам.

§ 9. Правила переименования евтнны х переменных

Рассмотрим формулы V*4(x) и Vjvlly). Очевидно, что в каждой интерпретации из истинности первой следует истинность второй, и наоборот, поэтому этиформулы равносильны: УгЛ(д:) ~ ЧуА(у).

Таким образам, переименование переменнойх нау в кванторе и в области действия этого квантора привело к формуле, равносильной исходной.

В математическом анализе имеется аналогичное правило. Налример, замена переменной а подынтегральном выражении опреде­ ленного интеграла не меняетего величины:

Точнотакжеосумм*чгслекссуммированияuoana переименовать;

1 "■■*£ м.

Впоследнем примере гтереименппиплется и на к, но нельм пе­ реименовывать и, ибозга свободная переменны.

Вформуле УхА(х) можнозаменитьпеременнуюх нну. Ясно, что исли х заменить другой переченкой, то полученная формула будет равносильна исходной. Можно доказан., “то и в произвольной формуле переименование (замена) связанных переменных на другие приводит к формуле равносильной исходной. Имея в вида цель­ нейшие приложения, будем придерживаться следующего правила переименования связанных переменных,

Пусть А - произвольная форму» логики предикатов. Формулу Ляполучим 112А заменой связанных переменныхдругими перемекными, отличными от псех переменных формулы Л, прнчем заменяемая переменная в формулеА должка меняться одинаковым образом всюду

воблаете действия квантора, отзывающего ланму(о переменную

ив самом кванторе Тогда/it равносильна/!

При переименовании связанных переменных мы не обязаныгкреиксновывать их всюду, где они входят в формулу А, а лишь только переменную выбранного ними квантор» и о области .действия этого квантора. Это значит, что одинаковые переменные, длs которых связывающие их. кванторы имеитг разлитые обпагпи jrгйствия, MDryr переименовываться разным образом или одна из них может псрсимен'.-выватьсл, адругая нет.

Рассмотрим дейетше приведенного пршила на и.ричерах. Пусть имеем формулу

4xA(?.)=izxll(x)~C{x). (2.21) Переименовав связаннуюпеременную х на у, в г]ервой посылке

получимформулу, равносильную исходной:

69

Vj-J<y)=>Bifi(*)=»C(4

Изформулы(2.21)переименованием можнополучигьформулу УхЛ(*)=>ЭгВ(г)=>ОД

ЧхА(х&-уР4у)-ах)

(при этом каждая полуденная форму.ла будет равкпсильяа исходной формуле (2.21)).

Отметимзщ8 раз, что переименовываются толькосвязанные пе­ ременные, а свободные нетрогаются. Так, в формуле (2.21) помогшее ахоздьние х сзобощю, поэтому при любых переименованиях иере-

Рясемотрим ещеодин пример, Пустьзадана формула

(2.22)

Переименовывая в этойформуле переменную», нужно заменить ее одинаковым образом всюду, где она входит, ибо х в формуле (2.22)

является	либо	переменной	квантора,	либо	находите*
в области	действие	квяетора. Например, переименовпв х на г,
получим следующую формулу, равносильную исходной:

Ъ(ЗуР (2,у)^уф ,у)^т ).

В формуле (2.22) переменнуюу мотто переименовать в первой стосьшкс, например, на переменную м » отарой оставить без изме­ нения, либо заменить, например, переменной и. В последнем случае получим формулу: Vj(Jv/’tr1v)^Vjig(i:,a)=iif(j)). Еслиучесть т е пе­ реименование переменной х, то имеем: Vs(3v/’(r,v)i-Vag(s,a)aS(j)). Полученные формутатоже равносильны исходной формуле(2.22).

§ 10. Прапила пыпшепим кваторон за скобки.

Предпарсняан вормальвая форма

Выясним, каким образом выносятся кванторы за скобки, при этом получим и правилавнесениякванторов под скобки.

70