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

Крометого, формулы CV*fl{;r))vVjC«=.y.rt.B(*)va!)).

Теорема 2.6. Пусть А обозначает формулу	не имеющую
свободных вхождений переменной дг, £(х) и Ш ) -	произвольные
формулы, возможно, и содержащие свободные	вхождений х.
Тогда.
- 1х{А&В(х)),	(2-23)
AvVzB(,) - Vr^vD(i)>	(2-24)
А&ЗЩ>) - 3.иИ<5;В(х)Х	(2.25)
А.;ЪВ(г)-ЫА<Щх)),	(2.26)
NxB(x))&4xC(x) ~ ЩЩл)& С(х»,	(2.27)
XB(x)vC(j)).	Ц П )

(2.28)

(2.30) логически общезначимы, а импликации, обратные к (2.29) и (2.30), уже ис /тел»юте» логически общезначимыми (при любых формулв*Жх)иОД).

Доказательство. Докажем соотношение (2.23). Для этого возь­ мем произвольную, НО фиксированную интерпретацию формулы

A&VxB(x).

Если свободных переменных в формулеA&4xBti) нет, то в ин­ терпретации получим высказывание. Пусть это высказывание истин­ но, тогда истинны А и Щх) при любом значении х из области интер­ претации М. Поэтому будет истинно высказывание Vi(^&B(»)). Аналогичным образом из истинности v.*(,4&£(*)) следует истииноегь

А&.ЧхВ(х).

Пуо-гь формула ASUxBU) имеет свободные переменные, для определенности пусть это будут _У(,_уз, ...JV Придадим им произволь­ ные значении иэ X Faпример, £,, bt...,k„ соответственно. Положим,

что при указанных значениях)¾уг, ...у, формула Л&Ях8(*) принимаei значение истины. Последнее означает, что для у;-6;, yt=bi....,y„~ 6, истинны А и В{х) при любок х из М, следояательно, для выбранных значений свободны)! переменных истинно высказывание Ч>(А&.В(>)). Очевидно, верно н обратное. Соотношение (2,23) доказано.

Доказательство равносильностей (2.24)-(2.28) и логической общезначимости формул (2.29) и (2.30) можно провести аналогично доказательству равносильности (2.23), т е. фиксированием интерпрс-

Дия завершения доказательств теоремы осталось доказать, что

импликации, обратные к(129) и (2.30), точнее, формулы
Vj-rfi(x;v'O;>■))=<Vj-B(x))vVj:0(i),	(2.31)
QxB(x))&3xO/y=>3r.(B(x)&Cfr.))	(2.32)

не являются логически общезначимыми при любых формулах В(х) и С(х). Чтобы доказагь это, достаточно для киждой из импликаций (2.31) и (2.32) указать формулы В(*) иС(») в для них привести тетя бы одну интерпретацию, где формулы(2.31) и (2.32) не истинны,

Пусть для (формулы (2.31) область интерпретации сеть

множество целых чисел, формуле	В(х) соотяетствует предикат
"* - четное число", а формуле ОД -	предикат - нечетное число".

Топи, считая, что нульчетно, получим исгнниов выскшывание У ф -

четное чкело или * - нечетное число), в то время, как высказывание [Уф - нечетное число ) или Щ х - четное число)] ложно. Позтоыу формула (2.3!) в приведенной интерпретации ло»на, следовательно, нелогически общезначима

Для формулы (2,32) можно взять ту я« интерпретацию, что идли формулы(2.31), Приэгам легковидеть, что формула (2.32) ложна, следо­ вательно, нелогически обшезначиыа. Теоремадоказана.

72

Правила вынесения кванторов за скобки, когда заляня имплика­ ция некоторых формул, следуют из теоремы.

Теорема 2.7. Пусть А —произвольна? формула, на содержа­ щая свободных вхождений переменой х, а Щх) - произвольная фор­ мула, возможно, и содержащая свободные вхождения х. Тогда

	3*В(х)=>А ~ Ух(В(х)=?Л);	(2,33)
	Л=>УхЖх) -	(2.W)
,	VxB(x)=>A ~ 3i(B(x)=>^),	(2.35)
	А=>ЪЩх) ~ Эх(А-,Щх)}.	(2.36)
Докшательсгво. Докажем соотношение (2.33). Рассмотрим
формулу:
Vx(B{x)=A).		(2.37)
Вместо	формулы (2.37) введем равносильную	формулу

V*(l B(x)vA)t которая по (2.24) равносильна формуле (Vil fl(x))v,4, которая равносильна формул® 1Ух1в(я)=>.4, Используя соотношение (2.15) между кванторами, получим формулу (ЗлН(х))=>А. Таким обра­ зом, формула '4i(S('c)^A) равносильна формуле (ЗхЛ(*)) =>Л, что итребовалось доказать.

Доказательство равносильностей (2.34)-(2.36) можно провести примерно также, как доказывалось соотношение (2.33).

Из изложенного видно, что при вьисесепии квангороэ jn скобки для указапяых формул кванторы могут выноситься без изменения, либо меняться на двойгтаенпые. В общем случае, оказывается, нужно проводить еще и переименование переменных, прежде чем вынести Квангорза скобки.

73

Теорема 2.S. ПустьВД и ОД - произвольные формулыло­ тки предикатов, мгорыг, мсжегбътп., спадржатсвободные вхожде­ ния переменнойи.тсгда имеют место следующие равносильности:

V^S(I (=>W^CJJ:| ' 3>vs(J()>)==0»);	(2J5)
-а«(Я(ЛаС(*));	(2.391
ixB(x^3xC(x} -Уу32(В(»=>СИ);	(2.40)
3*В(х^хС(х) - ^уЩВ(у)^С(г)),	(2.41)

формул В<х) и ОД, а ДО) к ОД - формулы, полученные из Я(г)

яойгнзуиз.
Цоквзатедьсию. Рассмотрим форчулу
VxB(x)=>VxC(x).	(2.42)

Пустьу к г - переметни®, отличные от всех свободны* перемгнных формулы (2.42). Провадеи гге^еимеиопаиие связанной переменкой х в посылке этой формулы на пер’мгинуюу, в в заключе­ ние- 'гй г .Пояуч«м^а5Ийсипь^*фсрри>.ту.

VyB{y)=>'7!Qs)

(2.43)

По построению а формуле(2.43) выражение УгС[г) не содержат свободных вхождений переменной у, тогда по равносильности (2.35) межно вывестиза скобет квантор Vjr, причем он сменится на двойст­ венный, T.s. получим 1у(В(у)тэ^гО/)).

Так кап.формула В/у) не содержит свободных вхождений г, тс, используя равносильной!. (2.34), поручим требуемое соотношение (2.38).

Для доказательства соотношения (2.35) пиратом импликацию елевой части соотношения(2.39) через 1 и v:

ч tB(x>=.axc:(x) - 1ty*Bw vsxc$ - Ы

74

Далее по	доказанной равносильности (2.28) получаем:
1е(1ЛОО'^СТх)), откуда иследует равносильность (2.39).
Равносильное™ (2,40) и (2.4L)доказываются, как для соотноше­
ния (2.38).
Замечание	1. При доказэтелькгве равносильности (2.38)

мы аьгнссли за скобки квантор из посыпки, а затем, из заключения, хотя, как легко видел,, можно сделал, это и в обратной последова­

тельности: сначала вынести квантор			кз заключения,	а затем
из посылки. В этом случае вместо (2.38) получим
VjrB(y)=>Vj:C(jr) -		Vz3XB(jJ)=t.r?)j.		(2.44)
Так как левые части равносильностей (2,38) н (2.44) совпадмот,
lyV-(B(y)=.C(.’))	-			(2.45)
Известно, что	в	общем случае	разноименные	кванторы

не перестановочны, a s частном случае (2.45) разноименные кванторы сказались перестановочными. Таким образом, в равносильности (2.45) в правой части порядок кванторов несущественен. Можно покапать, чго и в правых частях равносильностей (240) и (2.41) порядок кванторов tie существенен.

Замечание 2 Равносильности (2.3В), (2.40) и (2.41) показывают, птп при вынесении кванторов за скобками получили не оаин квантор, как этобыло ранее, в уже два квантора.

Проведя переименования переменных, а чатгы иегюлиуя равно-

CtxB(xi)vVxC(x) - ViVy(B(y)vC(i)).	(2.46)
Также нетрудно получить:
(3xR{x))&JxC(x) ~ ЗгЭДЯДО&ОД).	(2.47)

Твким обозом, из формул (^^В{х))-МтС,г) и (3;сВ(г))&а<ОД мы асе же вынесли кватсры за скобки, ноза скобками оказались уже два icuainepa с различными переменными. Сравнивая равносильности (2.46) н (2.47) с равносильностям!' (2.27) И (2.28), видим, что в послслких кванторы вынесеныбез всякого изменения и улвиения их.

75

Из равносильностей (2.33Н2-36) и (2-38}—¢2.41) очевидным образом следует, что длилюбой формулу мокко добиться, чтобыснача­ ла были запиикы кванторы, п затем формула, не имеющая кван-горов, i.e. "вынести" квангоры за скобки, Здесь применены кавычки, так как для получения равносильных формул кванторы выносятся за скобки, возможно, оставаясь неизмененными, лнби меняясь на двойственные, либо выносятся за скобки только после переименования связанны* переменных (в самом кванторе и области его действия). При этом пе­ реименование переменных осуществляется по правилам, описанным в предыдущем параграфе.

Формула вида: ¢,(¾...0 Д где QuQb-.Q* - любая совокуп­ ность кванторов, а формула В не содержит кванторов, называется формулой е предваренной нормальной форме или в пртексной норишльиой форме

Дли	формулы А	~ QiQi—QuB совокупность квапгоров
QbQi -Q*	называется	префиксом формулы А. а формула В -

матрицей формулы А. Будем дополнительно считать, что матрица приведена к конъюнизивной нормальной форме.

Из докизанныхтесреилегко следует следующая теорема.

Теорема 2.9. Для каадой формулылогики предикатов сущесюует!!

равносильная ейформугаа предвареннойнормальной форме.

;1

КозьмаПрутаи

§11. Допросы и темы длн самопроверки

1.Понятие предаката.

2.Кванторы. Использование кванторов и лредикэтои для сим­ волизации языка.

3.Термы, элементарныеформуши формулылогккипредикатов.

76

4.Свободные и связанные переменные. Замкнутые формулы. Замыкание формулы.

5.Интерпретация, выполнимые, истинные и ложные в донной

итерпретации формулы.

6.Модель.

7.Свойства формул в данной интерпретации.

8.Логически общезначимые формулы. Выполнимые формулы.

формулы.

10.Правила перенесений отрицания черт* кванторы.

11.Можно пи переставлять радон стоящие одноименные SBSIK-

12.Можно ли переставлять рядом гтоипие разноименные кван-

13.Определение предваренных нормальных фпрм. Для каждой ли формулы ппгики предикатов существует предваренная нормальная форма?

14.Алгоритмы нахождения предваренныхнормальных форм.

§12. Упражнения

I.Какие из следующих выражений являются предикатами:

5)*=у+я	I
в)к=2у+3 Lздесь*,у - действительныечисла;
г)	2х-Уу	\

д) все подобные треугольники рапны; е) >^-/<0 (ь у - действительные числа);

и) 8 - нечетное число;.

к) имеется бесчисленное множество различных простых чисел;

м) npwrasbre число 2й1 - 1 в виде произведений двух чисел, отличных от единицыИ самогочнспа.

Оыделик средипредикатов высказывания.

2. Зипикште символичссит следующие предложения:

а) для всякого числа*сущесгеусттакое число у, что x-hy“5;

б)	для	любого	числа у найдется хотя бы одно	число х,
В)	при	любом	х, не равном нулю, существует	у такое,

ч п х /гЪ

г) для любых чиселх ау имеет место равенство х+у=у-х'. д) все рациональныечисла дейстеителинме; е) ии однорациональное число не является действительным;

з) некоторые рададальные числанеявляете* действительными, 3. Введем следующиеобозначения:

2(x.t): я вижу предметл амомент времени /, Р(х,1): я беру предметх в моментвремени !,

Q(t*,t)\ момент времени (*предшествует моменту i(f*< г). Напишете, используя эти обозначения, символические выраже­

нияДЛ* слсдуюшах предложений: •

1.Я зеегда что-re вижу.

2.Иногда я ничего не нижу.

3.Существуют предмета, которыея никогда не вижу

4.Я вижу каждую вещь внекоторыймомент времени.

5.Если я вижу предмет, то я т/г же егс беру.

6.Если я вижу предмет, то я беру его спустя некоторое время.

7.Перед тек, какя берупредаст, я вижу его.

R. Если л беру предмет, не видя его до этою, то через некоторое время я вижу его.

9.Не существует предметов, которыея никогда не беру.

10.Я никогда неберу того, что я всегдавижу.

11.Всегда существуют аещп, которые « не BWKV и не5еру,

12, Яберу «сшую вещь, которую никогда не вижу.

13. Я Серу всякий предмет, который еще не вчял до этого.

15. Некиторые вещи. которые я видея ранее, всегда вижу вновь спустиопределенное время

16. Если я когда-либо виден две вещи одновременно, го в буду­ щем тоже увижу их одновременна.

4. Пусть переменные в следующих выражениях пробегают мно­ жество действительных чисел, а алгебраические знаки имеют свои обычные значения Прочтите эти выражения и определите, истинны

1)Чх?у(л-1у=у+х1;

2)Чх4Х*+У-3);

3)Ъ Щ х + у -3 );

4 )3 ^ ^ 4 ,-3 ):

5)VxVj-C^y-Я);

6)(YiV><*+y=3))=>(2=3)j

7)3«3j>((x>y>0)A:(x+y=0)):

8)9j{(?«]=((x>l)v(r<0)i);

9)V*(((*>?.)*V>3M2<«:3));

10)У1<((»2)4(«1))ф^));

5.Рассмотриre предложения, получающиеся в результате при-

ния и всеобщности. Какие из поиученньи предложений BL-TOHHLI?

6. Пусть Р(х) обозначает: х - смертен. Сформулируйте словесно

следующие выражения:
а) УхР(х),	5) 3хР(х);
B)lVxP(jr);	г) У* ]Г(х,1
л) 3x1 Р(х);	е) ’! ЗхР(х);
ж)СЗ*Г(ж»ЛЭу1 Р(у);	a) (Vxl Д*»=>1 Э^С-с).

79

7. Для действительных чисел юлишите символически, т.

используя обозначения tfjf,3r, х=>ит.П,, предложении, чыра*аюл[Ив: а) коммутативностьсложения; б) коммутативностьумножения; в) ассоцнатигностьслокент; г) ассоциативность умножения;

л) дистрибутивностьумножение относительносложения.

8 Выразете обласп иститтости предикатаР{х,у) через область истинности предикатовА(ху) и 5(хД если:

а)P(XJI)~1Л(х#\	б)Р(ху Г А ^ Щ х у );
в)R v r /iM v В(г,у),	г)PfrjpAfxyfrKw);

A)P(x,y-pA(x,y)?B(xj>)

9. Пусть Kf- мновсестео действительны!: чисел, aA(i) обозна­ чает, чтох обладаетнекоторым свойством А. Запишите символически следующие предложения'

]) существуетхотя быоднохеМтакое, ктоЛ(х)-, 2) существуетровно одноisWraKoe, чтоЛ(У), 3} существуетне более одногожеМтакого, что

4)существуетв точностиавьхвМ таких, чтоЛ(г);

5)существуетне менее двух.сеWтаких, чтоА(х)\ б) существуетнеболеедву*хеМ таких, 'ггоЛ(г).

10.Пусть^(<,)>)двухместный предикатна множестве всехве«е-

ственшлх чисел. Через	обозначим область истинности предиката
А(х,у\ т е. множество тек	точек (х,у) плоскости Л2, для которых

А(т.у)=И Рассмотрите предикаты3xAfcy) и3x1А(х,у) и выясните, как «МЗаКЫ областиистинностиутихпредикатовс множествомМ>.

11. Запишитесимволически следующие предложения:

а| Ж*) при произвольномJ ;	6 } (д) каковобыни было<;
в) всегдаимеетместаА(х);	г)найдетсях, для которого/)(г),
д) не при всякомг /(t);	е)А(х) недля всехх;