Ш.И._Галиев_МЛ_и_ТА_2004
.pdfданные вначале § 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