Расширенный сборник задач для самостоятельного решения, страница 4

, xn }.Óïðàæíåíèå 1.62.Óïðàæíåíèå 1.63.1.2.Âû÷èñëèòå êîìïîçèöèþ ïîäñòàíîâîê θ1 θ2 , ãäå;θ1 = {x/f (x), y/g(x, z), u/v, v/f (c)}, θ2 = {x/f (y), y/c, z/g(y, v), v/u}.θ1 = {x/y}, θ2 = {y/z} {z/x}{x/y}Óïðàæíåíèå 1.64.1. Äîêàæèòå, ÷òî îïåðàöèÿ êîìïîçèöèè ïîäñòàíîâîê îáëàäàåò ñâîéñòâîì àññîöèàòèâíîñòè,ò. å. θ1 (θ2 θ3 ) = (θ1 θ2 )θ3 .2. Äîêàæèòå, ÷òî äëÿ ëþáîé ïîäñòàíîâêè θ âåðíû ðàâåíñòâà θ = θε = εθ.3. Ïîäñòàíîâêà θ íàçûâàåòñÿ îáðàòèìîé, åñëè ñóùåñòâóåò òàêàÿ ïîäñòàíîâêà η, äëÿ êîòîðîé ñïðàâåäëèâî ðàâåíñòâî θη = ε. Äîêàæèòå, ÷òî ïîäñòàíîâêà θ îáðàòèìà òîãäà èòîëüêî òîãäà, êîãäà θ ïåðåèìåíîâàíèå.1.7.17Çàäà÷à óíèôèêàöèèÏîäñòàíîâêà θ íàçûâàåòñÿ èäåìïîòåíòíîé, åñëè îíà óäîâëåòâîðÿåò ðàâåíñòâó θθ = θ.

Äîêàæèòå, ÷òî ïîäñòàíîâêà{x1 , x2 , . . . , xn } ÿâëÿåòñÿ èäåìïîòåíòíîé òîãäà ènSòîëüêî òîãäà, êîãäà {x1 , x2 , . . . , xn } ∩ V art = ∅. ßâëÿåòñÿ ëè êîìïîçèöèÿ äâóõ èäåìïîi=1òåíòíûõ ïîäñòàíîâîê èäåìïîòåíòíîé ïîäñòàíîâêîé?Óïðàæíåíèå 1.65.iÎïðåäåëèì íà ìíîæåñòâå êîíå÷íûõ ïîäñòàíîâîê Subst îòíîøåíèå ñðàâíåíèÿ ñëåäóþùèì îáðàçîì: ïîäñòàíîâêà η ÿâëÿåòñÿ ïðèìåðîì ïîäñòàíîâêè θ (îáîçíà÷àåòñÿη θ), åñëè ñóùåñòâóåò òàêàÿ ïîäñòàíîâêà ρ, äëÿ êîòîðîé âûïîëíÿåòñÿ ðàâåíñòâî η = θρ.Êàêèìè èç ïåðå÷èñëåííûõ íèæå ñâîéñòâ îáëàäàåò îòíîøåíèå :1. òðàíçèòèâíîñòü: åñëè θ1 θ2 è θ2 θ3 , òî θ1 θ3 ;2. ðåôëåêñèâíîñòü: θ θ;3.

àíòèñèììåòðè÷íîñòü: åñëè θ1 θ2 è θ1 θ2 , òî θ1 = θ2 ;4. ñóùåñòâîâóåò òàêîé íàèáîëüøèé ýëåìåíò θmax , ÷òî η θmax äëÿ ëþáîé ïîäñòàíîâêè η;5. ñóùåñòâîâóåò òàêîé íàèìåíüøèé ýëåìåíò θmin , ÷òî θmin η äëÿ ëþáîé ïîäñòàíîâêè η.Óïðàæíåíèå 1.66.Íàéòè íàèáîëåå îáùèé óíèôèêàòîð ñëåäóþùèõ ïàð àòîìàðíûõ ôîðìóë(çàãëàâíûìè áóêâàìè îáîçíà÷åíû ïåðåìåííûå, à ïðîïèñíûìè êîíñòàíòû è ôóíêöèîíàëüíûå ñèìâîëû):Óïðàæíåíèå 1.67.P (c, X, f (X)),P (c, Y, Y );P (f (X, Y ), Z, h(Z, Y )), P (f (Y, X), g(Y ), V );P (f (Y ), W, g(Z)),P (U, U, V );P (f (Y ), W, g(Z)),P (V, U, V );R(Z, f (X, b, Z)),R(h(X), f (g(a), Y, Z));P (X, f (Y ), h(Z, X)),P (f (Y ), X, h(f (Y ), f (Z)));P (a, X, h(g(Z)),P (Z, h(Y ), h(Y ));P (X1 , X2 , X3 , X4 ),P (f (c, c), f (X1 , X1 ), f (X2 , X2 ), f (X3 , X3 )).Óïðàæíåíèå 1.68.Ïðè êàêèõ óñëîâèÿõ ÍÎÓ(E1 , E2 ) ÿâëÿåòñÿ êîíå÷íûì ìíîæåñòâîì?Ïðè êàêèõ óñëîâèÿõ êàæäûé óíèôèêàòîð äâóõ âûðàæåíèé E1 è E2ÿâëÿåòñÿ íàèáîëåå îáùèì óíèôèêàòîðîì?Óïðàæíåíèå 1.69.Ïóñòü θ1 è θ2 äâå ïîäñòàíîâêè, è ïðè ýòîì θ1 ∈ ÍÎÓ(E1 , E2 ).

Äîêàæèòå, ÷òî θ2 ∈ ÍÎÓ(E1 , E2 ) òîãäà è òîëüêî òîãäà, êîãäà ñóùåñòâóåò òàêîå ïåðåèìåíîâàíèåη , äëÿ êîòîðîãî ñïðàâåäëèâî ðàâåíñòâî θ2 = θ1 η . Ïðè êàêèõ óñëîâèÿõ ÍÎÓ(E1 , E2 ) ÿâëÿåòñÿêîíå÷íûì ìíîæåñòâîì?Óïðàæíåíèå 1.70.Äîêàæèòå, ÷òî ÍÎÓ(E1 , E2 ) = ∅ òîãäà è òîëüêî òîãäà, êîãäà ÍÎÓ(E1 θ, E2 η) =äëÿ ëþáûõ ïðèìåðîâ E1 θ, E2 η ëîãè÷åñêèõ âûðàæåíèé E1 è E2 . Ïðèâåäèòå ïðèìåð äâóõíåóíèôèöèðóåìûõ âûðàæåíèé E1 è E2 , èìåþùèõ óíèôèöèðóåìûå ïðèìåðû E1 θ, E2 η.Óïðàæíåíèå 1.71.∅18Ãëàâà 1.ÓÏÐÀÆÍÅÍÈßÄîêàæèòå, ÷òî åñëè ëîãè÷åñêèå âûðàæåíèÿ E1 è E2 íåóíèôèöèðóåìûè ïðè ýòîì V arE ∩ V arE = ∅, òî è ëþáûå ïðèìåðû E1 θ, E2 η ëîãè÷åñêèõ âûðàæåíèé E1 èE2 òàêæå íåóíèôèöèðóåìû.Óïðàæíåíèå 1.72.12Äîêàæèòå, ÷òî ëþáàÿ ïîäñòàíîâêà, êîòîðóþ âû÷èñëÿåò àëãîðèòì óíèôèêàöèè Ìàðòåëëè-Ìîíòàíàðè, ÿâëÿåòñÿ èäåìïîòåíòíîé (ñì.

óïðàæíåíèå 1.65). Âåðíî ëè,÷òî ëþáîé íàèáîëåå îáùèé óíèôèêàòîð äâóõ àòîìîâ A1 è A2 ÿâëÿåòñÿ èäåìïîòåíòíîé ïîäñòàíîâêîé?Óïðàæíåíèå 1.73.Ïîäñòàíîâêà θ íàçûâàåòñÿ óíèôèêàòîðîì êîíå÷íîãî ìíîæåñòâà àòîìîâ, åñëè îíà óäîâëåòâîðÿåò ðàâåíñòâó A1 θ = A2 θ = · · · = An θ. Óíèôèêàòîðìíîæåñòâà àòîìîâ íàçûâàåòñÿ íàèáîëåå îáùèì óíèôèêàòîðîì, åñëè ëþáîé óíèôèêàòîðìíîæåñòâà àòîìîâ ÿâëÿåòñÿ ïðèìåðîì θ. Ïðåäëîæèòå àëãîðèòì âû÷èñëåíèÿ íàèáîëåå îáùåãî óíèôèêàòîðà ìíîæåñòâà àòîìîâ M .Óïðàæíåíèå 1.74.M = {A1 , A2 , .

. . , An }θMMÓïðàæíåíèå 1.75.Âû÷èñëèòå íàèáîëåå îáùèé óíèôèêàòîð ñëåäóþùåãî ìíîæåñòâà àòîìîâ:M = { R(h(X), Y, Z), R(Y, h(Z), h(U )), R(h(h(U )), h(c), X) }.Ïóñòü M = {A1 , A2 , . . . , An } ïðîèçâîëüíîå íåïóñòîå ìíîæåñòâî àòîìîâ. Äîêàæèòå, ÷òî â M ñóùåñòâóåò òàêàÿ ïàðà àòîìîâ Ai è Aj îáëàäàþùàÿ ñëåäóþùèìñâîéñòâîì: âñÿêàÿ ïîäñòàíîâêà θ ÿâëÿåòñÿ óíèôèêàòîðîì ìíîæåñòâà àòîìîâ M òîãäà è òîëüêî òîãäà, êîãäà îíà ÿâëÿåòñÿ óíèôèêàòîðîì ïàðû àòîìîâ Ai è Aj .Óïðàæíåíèå 1.76.Ïðåäëîæèòå àëãîðèòì âû÷èñëåíèÿ íàèáîëåå îáùåãî óíèôèêàòîðà äâóõáåñêâàíòîðíûõ ôîðìóë ëîãèêè ïðåäèêàòîâ ϕ(x1 , x2 , . . .

, xn ) è ψ(x1 , x2 , . . . , xn ).Óïðàæíåíèå 1.77.1.8Ìåòîä ðåçîëþöèé â ëîãèêå ïðåäèêàòîâÏîñòðîéòå âñåâîçìîæíûå ðåçîëüâåíòû ñëåäóþùèõ ïàð äèçúþíêòîâ (çàãëàâíûìè áóêâàìè îáîçíà÷åíû ïðåäèêàòíûå ñèìâîëû è ïåðåìåííûå, à ñòðî÷íûìè êîíñòàíòû è ôóíêöèîíàëüíûå ñèìâîëû).1. D1 = ¬P (f (X1 , Y1 ), Z, h(Z1 , Y1 )) ∨ R(Z1 , V1 ),Óïðàæíåíèå 1.78.D2 = Q(X2 ) ∨ P (f (Y2 , X2 ), g(Y2 ), V2 );2.3.4.,D1 = P (X1 , Y1 , h(Y1 , X1 )) ∨ R(Y1 , f (X1 ))D2 = ¬P (X2 , f (X2 ), h(X2 , Y2 )) ∨ ¬P (Y2 , g(X2 ), h(Y2 , Y2 ));,D1 = ¬R(X1 , Y1 , X1 ) ∨ ¬P (X1 , Y1 , Y1 ) ∨ R(X2 , X2 , X2 )D2 = R(g(X2 , Y2 ), X2 , Y2 ) ∨ R(c, Z2 , f (Z2 , Z2 ));,D1 = ¬Q(X, Y ) ∨ ¬Q(Y, X)D2 = Q(U, V ) ∨ Q(V, U ).Óïðàæíåíèå 1.79.Ïîñòðîéòå ñêëåéêè ñëåäóþùèõ äèçúþíêòîâ.1.8.1.2.3.Ìåòîä ðåçîëþöèé â ëîãèêå ïðåäèêàòîâ19¬P (f (X)) ∨ R(Z, V ) ∨ P (X);P (X) ∨ Q(f (X)) ∨ P (a) ∨ Q(f (a));¬Q(X, f (X)) ∨ ¬Q(Z, Z) ∨ ¬Q(a, Z).Ïîñòðîèâ ðåçîëþòèâíûé âûâîä, äîêàçàòü ïðîòèâîðå÷èâîñòü ñëåäóþùèõìíîæåñòâ äèçúþíêòîâ.1. S = {D1 , D2 , D3 , D4 , D5 }Óïðàæíåíèå 1.80.D1D2D3D4D52.P (X, f (X)),R(Y, Z) ∨ ¬P (Y, f (a)),¬R(c, X),R(X, Y ) ∨ R(Z, f (Z)) ∨ ¬P (Z, Y ),P (X, X).=====¬E(b, U ),H(U, g(U )),H(U, U ),E(U, V ) ∨ ¬H(U, g(a)),E(U, V ) ∨ E(Z, g(Z)) ∨ ¬H(Z, V ).S = {D1 , D2 , D3 , D4 , D5 }D1D2D3D4D53.=====S = {D1 , D2 , D3 , D4 , D5 , D6 , D7 }D1D2D3D4D5D6D74.=======E(x) ∨ V (y) ∨ C(f (x)),E(x) ∨ S(x, f (x)),¬E(a),P (a),P (f (x)) ∨ ¬S(y, x),¬P (x) ∨ ¬V (g(x)) ∨ ¬V (y),¬P (x) ∨ ¬C(y);S = {D1 , D2 , D3 , D4 }D1D2D3D4====P (y, f (x)),¬Q(y) ∨ ¬Q(z) ∨ ¬P (y, f (z)) ∨ Q(v),Q(b),¬Q(a);Èñïîëüçóÿ ìåòîä ðåçîëþöèé, îáîñíîâàòü îáùåçíà÷èìîñòü ñëåäóþùèõôîðìóë.1.

∃x P (x) → ¬∀x ¬P (x);2. ∃x ∀y R(x, y) → ∀y ∃x R(x, y);Óïðàæíåíèå 1.81.203.4.5.6.7.8.9.10.11.12.Ãëàâà 1.ÓÏÐÀÆÍÅÍÈß∀x (P (x) → ∃y R(x, f (y))) → (∃x ¬P (x) ∨ ∀x∃zR(x, z));∀x ∃y ∀z (P (x, y) → P (y, z));∃x ∀y ∃z (P (x, y) → P (y, z));∃x∀y(∀z(P (y, z) → P (x, z)) → (P (x, x) → P (y, x)));∃x∃y(P (x, y) → R(x)) → ∀x(¬∃yP (x, y) ∨ R(x));;∀x(P (x, x) → (R(x) → ∀x(∀xP (x, x)&R(x))))∃x((∀yP (x, y) ∨ ∃xR(x)) → (∃xP (x, x) ∨ R(x)));∃x(∃y¬P (x, y) → ∀xR(x)) → ∀x(R(x) ∨ ∃xP (x, f (x)));∀x(∀y∃v∀u((A(u, v) → B(y, u))&(¬∃wA(w, u) → ∀wA(w, v))) → ∃yB(x, y));∀x∃u(∃v∀y((E(u, y) → H(y, v))&∃w∀x(H(w, y) → ¬H(x, v))) → ∃y¬E(x, y)).Äîêàæèòå, ÷òî ðåçîëþòèâíûé âûâîä îáëàäàåò ïåðåêëþ÷àòåëüíûì ñâîé, êîòîðîå ôîðìóëèðóåòñÿ òàê (ñì.

ðèñ. 1.1).Ïðåäïîëîæèì, ÷òî äèçúþíêòû D1 , D2 èìåþò ðåçîëüâåíòó D0 , è äèçúþíêòû D0 è D3èìåþò ðåçîëüâåíòó D. Òîãäà îäèí èç äèçúþíêòîâ Di , i ∈ {1, 2}, è äèçúþíêò D3 èìåþò ðåçîëüâåíòó D00 , à äèçúþíêòû D00 è D3−i èìåþò ðåçîëüâåíòó D0 , êîòîðàÿ ÿâëÿåòñÿ âàðèàíòîìäèçúþíêòà D.Ââåäÿ íåîáõîäèìûå ïðåäèêàòû, çàïèøèòå ôîðìóëû ëîãèêè ïðåäèêàòîâ,âûðàæàþùèå ñëåäóþùèå ñóæäåíèÿ:¾Åñëè â ñòðàíå åñòü õîòü êàêèå-íèáóäü ãðàæäàíå, òî âñå ïîëèòèêè ÿâëÿþòñÿ ãðàæäàíàìè ýòîéñòðàíû¿.¾À åñëè ãäå-òî â ìèðå è åñòü ÷åñòíûå ëþäè, òî âñå ãðàæäàíå ñòðàíû ÷åñòíûå ëþäè¿.Èñïîëüçóÿ ìåòîä ðåçîëþöèé, äîêàæèòå, ÷òî èç ýòèõ óòâåðæäåíèé ñëåäóþò âûâîäû:1. ¾Åñëè ñðåäè ãðàæäàí ñòðàíû åñòü ÷åñòíûå ëþäè, òî âñå ïîëèòèêè ÷åñòíûå¿.2. ¾Åñëè ñðåäè ïîëèòèêîâ íàéäåòñÿ õîòü îäèí áåñ÷åñòíûé ÷åëîâåê, òî âî âñåì ìèðå áîëüøåíå îñòàëîñü ÷åñòíûõ ëþäåé¿.Óïðàæíåíèå 1.82.ñòâîìÓïðàæíåíèå 1.83.Ðàññìîòðèì îðèåíòèðîâàííûé ãðàô Γ ñ ìíîæåñòâîì âåðøèí a, b, c, d, e èìíîæåñòâîì äóã ha, bi, ha, ei, hb, ai, hd, bi, he, ci, he, ci, hc, di.

Ýòîò ãðàô ïîëíîñòüþ îïðåäåëåòñÿñëåäóþùèì ñïèñêîì àòîìàðíûõ ôîðìóë:Óïðàæíåíèå 1.84.ϕ1ϕ2ϕ3ϕ4ϕ5ϕ6======A(b, e),A(a, e),A(b, a),A(d, b),A(e, c),A(c, d).1.8.21Ìåòîä ðåçîëþöèé â ëîãèêå ïðåäèêàòîâD1D2@DiD3@@@@@R@D00@RD0D39?DD0 âàðèàíò D:D3−i9?D0D = D0 θD0 = DηÏåðåêëþ÷àòåëüíîå ñâîéñòâî ðåçîëþòèâíîãî âûâîäàÐèñ. 1.1.Âåðøèíà v îðèåíòèðîâàííîãî ãðàôà ñ÷èòàåòñÿ äîñòèæèìîé èç âåðøèíû u, åñëè â ýòîì ãðàôå ñóùåñòâóåò îðèåíòèðîâàííûé ïóòü (ìàðøðóò) èç âåðøèíû u â âåðøèíó v.

Îòíîøåíèåäîñòèæèìîñòè E (2) îïèñûâàåòñÿ ñëåäóþùèìè ôîðìóëàìè:ψ1ψ2ψ3===∀X E(X, X),∀X∀Y (A(X, Y ) → E(X, Y )),∀X∀Y ∀Z (E(X, Y ) & E(Y, Z) → E(X, Z)).1. Ñôîðìóëèðóéòå â òåðìèíàõ ëîãè÷åñêîãî ñëåäñòâèÿ çàäà÷ó ïðîâåðêè äîñòèæèìîñòè âãðàôå Γ âåðøèíû d èç âåðøèíû a. Ðåøèòå ýòó çàäà÷ó ïðè ïîìîùè ìåòîäà ðåçîëþöèé.2. Îðèåíòèðîâàííûé ãðàô íàçûâàåòñÿ ñèëüíî ñâÿçíûì, åñëè äëÿ ëþáîé ïàðû åãî âåðøèíu, v âåðøèíà v äîñòèæèìà èç âåðøèíû u. Ñôîðìóëèðóéòå â òåðìèíàõ ëîãè÷åñêîãî ñëåäñòâèÿ çàäà÷ó ïðîâåðêè ñèëüíîé ñâÿçíîñòè ãðàôà Γ. Ðåøèòå ýòó çàäà÷ó ïðè ïîìîùèìåòîäà ðåçîëþöèé.Ãðàô íàçûâàåòñÿ äâóäîëüíûì, åñëè ìíîæåñòâî âñåõ åãî âåðøèíû ìîæíî ðàçáèòü íà äâà òàêèõ êëàññà, ÷òî íèêàêèå äâå âåðøèíû èç îäíîãî è òîãî æå êëàññà íåñîåäèíåíû äóãîé.Óïðàæíåíèå 1.85.1.

Ââåäÿ âñïîìîãàòåëüíûå ïðåäèêàòû, çàïèøèòå ôîðìóëó âûðàæàþùóþ ñâîéñòâî äâóäîëüíîñòè ãðàôà.22Ãëàâà 1.ÓÏÐÀÆÍÅÍÈß2. Äîêàæèòå ïðè ïîìîùè ìåòîäà ðåçîëþöèé, ÷òî ãðàô Γ èç óïðàæíåíèÿ 1.84 íå ÿâëÿåòñÿäâóäîëüíûì.Ãðàô íàçûâàåòñÿ 3-ðàñêðàøèâàåìûì, åñëè ìíîæåñòâî âñåõ åãî âåðøèíûìîæíî ðàçáèòü íà òðè òàêèõ êëàññà, ÷òî íèêàêèå äâå âåðøèíû èç îäíîãî è òîãî æå êëàññà íåñîåäèíåíû äóãîé.1. Ââåäÿ âñïîìîãàòåëüíûå ïðåäèêàòû, çàïèøèòå ôîðìóëó âûðàæàþùóþ ñâîéñòâî 3-ðàñêðàøèâàåìîñòè ãðàôà.2. Äîêàæèòå ïðè ïîìîùè ìåòîäà ðåçîëþöèé, ÷òî ãðàô Γ íå ÿâëÿåòñÿ 3-ðàñêðàøèâàåìûì.Óïðàæíåíèå 1.86.1.9Ïîëíîòà ìåòîäà ðåçîëþöèéÏóñòü çàäàíî íåêîòîðîå íåïóñòîå ìíîæåñòâî äèçúþíêòîâ S0 . Ïóñòü S1 ýòî ìíîæåñòâî âñåõ ôîðìóë, ðåçîëþòèâíî âûâîäèìûõ èç ìíîæåñòâà äèçúþíêòîâ S0 .