Ш.И._Галиев_МЛ_и_ТА_2004
.pdfjO(VxAha,b.c)l |
•)Va4(e); |
?(«)); |
■»)/!(*)=» f 1(e). |
D v ,v x ( 4 W ^ W f c v ) ) ;
2)V.TVJ. ^ ( X) = VM2(^ ));
3) « Э ^ Л ,1(*»)) ^ P W '* ! » ) ;
А) (адУдДс(^Су))))),
5) 4 « = . b ;
6 )v x = > v ^ ;w , l)-3 X^ 4 ( y ) ;
8 yA}(y)&Al(xty,a)-
9)(^?tyilC«Xa)=>4J(*,a,&));
10)( ^ р й . Й ^ М 'О ’)»-
а) Vx^)=>5fty,i)vttC(x); б)atV>3^(i)v3>lvr'U(i,>);
£I)1VX1(J:)=>3VS0')=>^(I J )V^0');
r)V*V*VjU(*)=>fl(j)*l<(x); я) izVxA(x,y)z*lyA(i,j:y,
с) V^(ij)=Vb4(r^), |
|
14, |
Указатьъэобъчиы*и саманные торвмемад. |
»)ЭЫ(*)&вМ; |
6)f(*)=>3xC(j)i |
8) 3x4yPtf)SiQ(y)=iVxR(xy |
г)3x3yP(_i.y)&Q(2y, |
д) ViPh)№xQ(,z,iy^dyR(2,yy;Q(2,y.)\ е) 3yP(x.y)&\lx(x!)^Pfy,yy
17. Каждый из следующих предикатов, определенных на мно жестве в«х действительныхчисел, превретте в высказывание:
1)подьтавли вместо свободной переменной какое-либо ее
значение;
2)связывая свободную переменную иаким-лнбо квантором. Определитеистинностныезначение полученныхвысказываний:
t)4xfr+y=y+x)<, |
|
б)х>у, |
в)х-у=5; |
|
г) 3*(xj=5); |
д) г1+>120; |
<й)\ |
е) №гЭу(х+>” г); |
ж>^x(s«a>l |
з)За(х>У). |
18. Пусть приводимые далее предикаты определены на мно жестве все* действительных чисел. Изобразил» графически области изменения свободных переменных, при которых следующие предика ты приникают значениеИ:
а)}**1; |
б) |
»)Вх(ЛУй); |
г) V>3y(siEi)r=!); |
fljVxOr'+^’si); |
е) Vj<jrrsinys2). |
19.1) истинна, ложна илн выполнима формула Alf\(fi[x в каждой изследующих интерпретаций:
а)А^(-ю,<ю), |
Л(х,у):**и fiix.y): х+у, ftzy. 1m, |
5) ИНОМ, |
Мх,у): *=->, МхуУху, f,(x): х\ |
В)M=(0,l], |
Aify): х>-у, ffaj): l/x+j", /{*)'■ х1, |
г) М=№.24 |
Я?,у): i+y. Я*): sins; |
2)истинна, ложна или выполнимаформула чхА$(ху)/^А(*У
в интерпретации: М-(-“ ,»),/j(z): ^,Мху): х+у,А(х,у) х=У
20.Предикативу) заданнамножестве №{1,2,3) таблицей
Определите истинностное значение приводимых прикаждомзначении свободной переменной:
a)VM(^); |
- |
5 ) Э г ^ ; |
e)Vj^(xj-); |
|
г)2уА(Хуу). |
21.Пусть №{1,1,3} и на этом миажестие Ы зяда |
||
и Э(з) таблицами'. |
|
|
л м - |
|
ад . |
Опрсдмите истинностноезначениеформул; |
||
а)3хЛ(хл); |
|
б) Vb4(i^:)s3j:Vj^(j;j;); |
в) ЭхЭ^адАЛ;*,/); |
|
г) |
^3xV>(Sfy)^(rj-)).
22.Пусть формула 8 не содержит свободных переменных
аР(х) - одноместный предикат. Для области М, состоящей из дву; элементов, построить таблицы истинностных значенийформул:
a)Vj-Я, |
6) 1 ,8; |
в) VxPlx): |
г) Э*/>{*); |
д) V.(PW^ff), |
с)Зд(Р(х)^В>; |
ж) W{x)=>B)slxP{x)=>B-, |
з) 3х(Р(я)^В)*УхР{х)=>а. |
83
23.Предикат P(xj>) задан ка множестве целых положительны
чисел бесконечной таблицей, в которой значения И стает впервой строке, первомстолбце ипо диагонали.
Выяснить, при какихзначениях х, у, s следующие формулы при
нимаютзначения#: |
|
a] f(i,4); |
6) Р(*,2)ЛР(г,5); |
»)Пх№Ы5); |
г)Р<ВД*Д*Л |
24. Пусть предикат Р[г,у) тот же, что и а предыдущей задаче. |
|
Выяснить, принимаютля знечекие Иследующие формулы: |
|
a)Зх¥уР(г^}; |
5j ItflJ.r); |
б)V.tayPOv); |
r> VI VJIP(IJI); |
д) 4xVyP(xj>)=sЧуР(5у); |
e) Ъ(УуР{уу)=>Р(хл)); |
*)VxP{i,2); |
.3)^(3j-). |
25. Истиннали формула Зь4,'(х)л Уу^(у):
в) для произвольной одноэлементной области; б) дтл произ вольнойдеухэлеметдай области?
26. Перед следующими предикатами, определенными на множе стве всех действительных чис^1, иост&вые соответствующие кванто рытак, чтобы получоть истинное высказывание;
81^=27; |
б)*+1>1; |
b)>у4-, |
т)х-у*й\ |
д) х+у=г; |
е) |
84
27.Выяснить, выполнима ли форчула '~jx~iy!‘(y..,y.?) в интерпре
тации: МЧ>оз,м), fYjyvi - iry c , является ли эта формула истинной дняданной интерпретации?
28 Для формулы 'ixP(>^y)^>P(y,y) найти интерпретацию, в кото ройэта формула выполнима.
29. Истинна ян формула У на произвольной двух элементной области?
30.Показать, что формула Ух1уЛ(х.у)^/У)дхА(ху) не является логическиобщезначимой. Выполнима ди это формула?
31.Является ли выполнимой формула
^ х (Р (х ,у ^ Р (у ^ г)У '
32.Доказэть, что, если формула логики предикатов А, содержа щая свободно только переменную х, является логически общезначи
мой, то формула V*4 также являете* логически общезначимой, иобратно.
Обобщить сформулированное утверждение ка формулы, содержащие любое конечное числи свободных переменных.
33.Если формула логики предикатовД содержащая только сво бодную переменную х, является логически общезначимой, то ic4 также является логически обш.етныимой. Верно ли обратное?
34.Доказать;
а) если формула логики предикатов А=>В является логически общезначимой, то формулы УхА=эУхВ и ВхД=>Нл5 также являются
б) если формула логики предикатов /1“В являете.» логически общезначимой, то формулы VxA^VxB и ЗхА~.ЗхВ также являются ло гически общезначимыми.
35. Показать, что формула VlVy(f(t)vl Р(у)) является иеткнкой
.'[Ля одаэламенгной области и только дла нее, здесь Р является одно местной предикатной буквой.
85
36.Докажите, что формула ЗхУуА^УуЗхЛ является логически общезначимой.
37.Яшистм ливыполнимой формула 3x'VyP(x.y)^4y3xPtf(x),y)'} Будетли эта формулалогическиобщезначимо!!?
произвольной двущлементной области следующие формулы (А я В не содержат свободных переменных, а Р являет.я одноместнойпреди катнойбуквой):
а) Э«Х=» P{x))a(A^Vx Р(*)); |
6) 3x(P(i)=:B)M.4x P<i)=>8); |
в)Vx(P(j)=5B)s(3i P(x)=fi); |
r) VxM= Дх))в(Л=.Л Pi»); |
2) являются ли формулы a) - |
г) логически общезначимый» |
ИЛИ ИЯ?
39. Являютсяли выполнимымиследующие формулы: &) Чх^г(4(х,хЩА{х>г)=>А{ху)\;А(у^))) =>3x4yA(xj);
б) V»3yy2^(x^)&"U(y^>A(^(^-M=3X(it>')))
40. Пусть А не содержит свободных переменных (Р, Q- однпместные првдикаиые буквы). Выяскту, дклвютс» ли логически общезначимым» следующие формулы:
1)Л& ^еСфУ з^& г));
2)ЛШхОЩвЩЛЩх))’,
3)VxP{x)&VxQ(x)*!xt]\x)liQ{x)%
4)VxPixyrtxQ^Vx^vQix))-,
5)V*i>(j:VV*g(i)^V*(P(x)v6(x));
6)3xP{x)&lxQ(.xfgx(P(.x)&Q(.x));
7)3xP(*)^*a*)=b№)vS(*));
8)ЗДх)&Й*))^Э1едйЭ*2(*).
41.ПустьА не содержит свободных переменных (Р, Q - одно местные предикатные буквы). Какие из следующих формул являйте»
логически общезначимыми
I) Чх{Р(х)=>АЫ1*Щ=>АУ, 2)Зх(Р(х)^А)Ц2хР1&*Л);
3) ЗД*)=эЛН%Р(*)=Л); 4) аС(^=.Р(г))а(^='Э*Р(1))?
42. KOKHS из приводимых лалее форм'1.! являются ышолнимыvn, а какие из них логически общезначимыми (P. Q - одноместные ирсдикатаыс буквы):
1) ЩР1к)^2(х)р:<Щх)^ЗхО(х)-
2)м т ^ О ( : Ф ^ ( Ф '\ 3z&s)r.
3)0/хР(хУ^Чх^г))^\/4Р^У-> 6(1»,
4)v*(P(*)ve(3;))=KV*PW)vV*g(*)).
43.Выяситъ, являются ли равносильными следующие пяры формул {P. Q - однвмосгаыс предикатные букиы, А - произиольни формула, имеющая указанные аргументы)
a) -ix!‘(x)^xQ (x) я txPt*,=>VyQ(y),
5)V*i(io>)HVb4(«v);
в) М е д ^ * ))в Т * < 1 п о = > е о № г) VrtrtflttvSOO) и VxVXP(y)vQ(x)y, д) VxP(x)&0x) и VxP(x))&y(x); г)А{х,а) иЛ(у,а)
И. Дм следующих формул найти равносильные формулы,
в которых1oTHOcirrciiтолько кэлементарнымформулам:
a)V»]fBj<AU)=>fi(y)));
6)l3i(W>H(i,y,?)=>3K5(i,i/))&.VrVv(0:()vD(v)); в) ^ гМА(х)^>\И(!)У,
T)3y}Vx(AmB(y))=.lBzC{x.y,i).
45. Пусть/1(х,у) - двухместный предикат на множества всех ве щественных чисел. Через Мл оАочиачич область истинноегч предика те Л(х,у), г.о. мнолесотио тех точек (х,у) плоскости JP, для которых
,1/х,у)=!{. Рассмотреть предикаты. VxA(xj) и V* /*(х,у) и пыягнить, как емзаны областиистияноста этих предикатов с.мно*естаом Мл
Формула QiXiQiX/... б,*,8, где Qx - квантор вссобщгости или существования, .Vr н (j различны, если frj и В не содержит кванторов, называется формулой в пргдиарвнной нормальной форме {иногда -
8?
пренексной нормальной формой). Сюда относится и случай п=0, когда вообще нет кввнторпи.
46. ]) привести к предваренным нормальным формам формулы
из задачи 44; 2) привайти к предваренным нормальным формам следую
формулы:
a) Чк№(х^В(х,у)}=>((ЗуА(у))=/ЗгВ{у,з)),
B) гЩ х,уЫ А(х)ъЬгВ{Х,1)).
в) '*xrjy32C(x,y,;)-'A(x))^,V/A{x),
г) 11Ы(л)=.УгВу5’гС\%|^ ) .
47. Привести к предваренным нормальным формам следующие
формулы: |
|
а) ЗхА(х)^ЧхВ(х), |
|
б)Уа4М »3:г.В00; |
|
в) |
VXVJ<3Z(^(JJJ)&BO,2)) =s3vQ;^,v)); |
r)V*W*)=s>3,<B(*ofl; д) Зх(А(х) ^уВ(х,у))\
е) 3«T(3^fe.») =(3,5(,) =.С(х)));
ж) Vx3;<Vzd{.w)&(3aS(:r,«) =>3vC(y,v))).
Глава 3. ЛОГИЧЕСКОЕ СЛЕДСТВИЕ И МЕТОД РЕЗОЛЮЦИЙ
Этоконечна. Сою. ИтямВюш-иу».
А. М-Мияя
1 1. Логическое слсдсткве и проблема дедукции в логике высказываний
Пусгь А и В - пропозициональные фирмы (формулы логики выскаэыяаний). Считаем, чтоЯлогически следует ичА, если для каждой совокупности значений пропозициональных букв, при которых А=И форма В тоже принимает значение И. В атом случае записываем
Легко доказать следующуютеорему
Теорема 3.1. НелиА \В л В \С ,т А \С .
89
Запись УА в логике высказываний означает, trro А валяетсятав тологией (общезначимой) Докажем следующуютеорему.
Теорема 3.2. А ^Втогда итолькотогда, когдв ^А=>В.
Докамтепъстпо. Построим таблицу истинности для А&В. Пусть имеем, что А ^ В, тогда в каждой строке таблице, где А~И, будет В=Я, следовательно, А ^В тавтология, то есть ^ Ат$В. Если же имеем (= то втаблице истинностидля А=>В всюду, где А=И, должнобыть В~И, следовательно, получимA |sВ.
Пропозициональнаяформа 8 называетсялогическим следствии* пропозициональных форм Ai^ib—iAn, «21, если для каждой сово купности значении пропозициональных букв, при которых формьМи Aj,...г4* одновременно равны И, форма В тоже принимает значение
И. Вэтом случае записываем: |
|
Au Aw..A jfB . |
(3.1) |
Выяснение, будет ли В логический следствием из <4|, Ai,.„Am |
|
т>1, тазыааютпроблемойдедукции. |
|
Теорема 3,3. Дла проиэьольных формул логики высказыва |
|
ний Ai,Ai,..., Am m>1, имеют место соотношение |
I |
A ,A i,:;A „ lA l6bi>&...&iA„, |
(3.2)1 |
At,Ai.... АЯ1 дпялюбого i. 1< fS in. |
0.3]! |
Теорема 3.4. £слн формула |
|
|
(3.4) |
является противоречием, то В яаляется логически |
слелишем из |
A x,A u -,-4,,, т.е.: |
|
АьАь-Ат^В. |
(3.5) |