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

T1 = h ∀x P (c, x, x), ∀x∀y∀z (P (x, y, z) → P (f (x), y, f (z))) | P (f (c), c, f (c)) i;2. T2 = h ∀x P (c, x, x), ∀x∀y∀z (P (x, y, z) → P (f (x), y, f (z))) | ∃z P (f (c), z, f (f (c))) i;3. T3 = h ∀x∀y∀z (P (x, y) & P (y, z) → P (x, z)), ∀x ¬(P (x, x) | ∀x∀y (P (x, y) → ¬P (y, x)) i;4.

T4 = h ∃x (P (x) & R(x)), ∀x (P (y) → Q(y)) | ∃z (Q(z) ∨ R(z)) i.Óïðàæíåíèå 1.29.Êàêèå èç ïðèâåäåííûõ íèæå ìíîæåñòâ ôîðìóë ÿâëÿþòñÿ íåïðîòèâîðå÷èâûìè? Èñïîëüçóéòå äëÿ ïðîâåðêè íåïðîòèâîðå÷èâîñòè èñ÷èñëåíèå ñåìàíòè÷åñêèõ òàáëèö.1. Γ1 = { ∀x ¬R(x, x), ∃x P (x), ∀x∃y R(x, y), ∀x (P (x) → R(y, x)) };2. Γ2 = { ∀x ¬R(x, x), ∀y∃x R(y, x), ∀x∀y∀z (R(x, y)&R(y, z) → R(x, z)) }.Óïðàæíåíèå 1.30.Ïóñòü ϕ(x) ôîðìóëà ëîãèêè ïðåäèêàòîâ, íå ñîäåðæàùàÿ êîíñòàíòû. Äîêàæèòå, ÷òî ôîðìóëà ∀x ϕ(x) ÿâëÿåòñÿ îáùåçíà÷èìîé òîãäà è òîëüêî òîãäà, êîãäà îáùåçíà÷èìà ôîðìóëà ϕ(c). Îñòàåòñÿ ëè ýòî óòâåðæäåíèå ñïðàâåäëèâûì è â òîì ñëó÷àå, êîãäàêîíñòàíòà c ñîäåðæèòñÿ â ôîðìóëå ϕ(x)?Óïðàæíåíèå 1.31.cÈçâåñòíî, ÷òî íåêîòîðàÿ ìîäåëü äëÿ ôîðìóëû ϕ íå ÿâëÿåòñÿ ìîäåëüþ äëÿ ôîðìóëû ψ. Êàêèå èç ïðèâåäåííûõ íèæå óòâåðæäåíèé âñåãäà âåðíû äëÿ ëþáûõçàìêíóòûõ ôîðìóë ϕ è ψ ?1. Íå ñóùåñòâóåò óñïåøíîãî òàáëè÷íîãî âûâîäà èç òàáëèöû T 0 = h ψ | ϕ i;Óïðàæíåíèå 1.32.12Ãëàâà 1.ÓÏÐÀÆÍÅÍÈß2. Íå ñóùåñòâóåò óñïåøíîãî òàáëè÷íîãî âûâîäà èç òàáëèöû T = h ϕ | ψ i;3.

Ôîðìóëà ϕ ÿâëÿåòñÿ ëîãè÷åñêèì ñëåäñòâèåì ôîðìóëû ψ;4. Ôîðìóëà ψ ÿâëÿåòñÿ ëîãè÷åñêèì ñëåäñòâèåì ôîðìóëû ϕ.Èçâåñòíî, ÷òî äëÿ ñåìàíòè÷åñêîé òàáëèöû T = h ϕ | ψ i íåëüçÿ ïîñòðîèòü íè îäíîãî óñïåøíîãî òàáëè÷íîãî âûâîäà. Êàêèå èç ïðèâåäåííûõ íèæå óòâåðæäåíèéâñåãäà âåðíû äëÿ ëþáûõ çàìêíóòûõ ôîðìóë ϕ è ψ?1. Òàáëèöà T = h ϕ | ψ i íå ÿâëÿåòñÿ âûïîëíèìîé;2.

Äëÿ òàáëèöû T 0 = h ψ | ϕ i òàêæå íå ñóùåñòâóåò íè îäíîãî óñïåøíîãî òàáëè÷íîãî âûâîäà;3. Ôîðìóëà ϕ íå ÿâëÿåòñÿ ëîãè÷åñêèì ñëåäñòâèåì ôîðìóëû ψ;4. Ôîðìóëà ψ íå ÿâëÿåòñÿ ëîãè÷åñêèì ñëåäñòâèåì ôîðìóëû ϕ;Óïðàæíåíèå 1.33.Âûáåðèòå è îáîñíóéòå ïðàâèëüíûå âàðèàíòû ïðîäîëæåíèÿ ñëåäóþùåãîóòâåðæäåíèÿ. ¾Ôîðìóëà ϕ ëîãèêè ïðåäèêàòîâ ïåðâîãî ïîðÿäêà âûïîëíèìà òîãäà è òîëüêîòîãäà, êîãäà...¿1. â ëþáîì äåðåâå òàáëè÷íîãî âûâîäà äëÿ èñõîäíîé òàáëèöû T = h{ϕ}, ∅i êàæäàÿ âåòâüçàâåðøàåòñÿ çàêðûòîé òàáëèöåé;2.

 ëþáîì äåðåâå òàáëè÷íîãî âûâîäà äëÿ èñõîäíîé òàáëèöû T = h{ϕ}, ∅i õîòÿ áû îäíàâåòâü çàâåðøàåòñÿ çàêðûòîé òàáëèöåé;3. Õîòÿ áû â îäíîì äåðåâå òàáëè÷íîãî âûâîäà äëÿ èñõîäíîé òàáëèöû T = h{ϕ}, ∅i êàæäàÿâåòâü çàâåðøàåòñÿ çàêðûòîé òàáëèöåé;4. Õîòÿ áû â îäíîì äåðåâå òàáëè÷íîãî âûâîäà äëÿ èñõîäíîé òàáëèöû T = h{ϕ}, ∅i õîòÿ áûîäíà âåòâü çàâåðøàåòñÿ çàêðûòîé òàáëèöåé.Óïðàæíåíèå 1.34.Ïóñòü èçâåñòíî, ÷òî ìíîæåñòâî çàìêíóòûõ ôîðìóë Γ íå èìååò ìîäåëè.Êàêèå èç ïðèâåäåííûõ íèæå óòâåðæäåíèé ñïðàâåäëèâû è ïî÷åìó?1. Ñóùåñòâóåò óñïåøíûé òàáëè÷íûé âûâîä äëÿ èñõîäíîé òàáëèöû T = hΓ, ∅i;2.

Ñóùåñòâóåò óñïåøíûé òàáëè÷íûé âûâîä äëÿ èñõîäíîé òàáëèöû T = h∅, Γi;3. Íå ñóùåñòâóåò óñïåøíîãî òàáëè÷íîãî âûâîäà äëÿ èñõîäíîé òàáëèöû T = hΓ, ∅i;4. Íå ñóùåñòâóåò óñïåøíîãî òàáëè÷íîãî âûâîäà äëÿ èñõîäíîé òàáëèöû T = h∅, Γi.Óïðàæíåíèå 1.35.Ïóñòü èçâåñòíî, ÷òî ìíîæåñòâî ïðåäëîæåíèé Γ íå èìååò íè îäíîéìîäåëè, ïðåäìåòíîé îáëàñòüþ êîòîðîé ÿâëÿþòñÿ ñòðîêè êîíå÷íîé äëèíû, ñîñòîÿùèå èç 0 è1. Ìîæåò ëè â ýòîì ñëó÷àå ìíîæåñòâî ïðåäëîæåíèé Γ áûòü íåïðîòèâîðå÷èâûì?Äîêàæèòå, ÷òî ìíîæåñòâî ïðåäëîæåíèé Γ íåïðîòèâîðå÷èâî òîãäà èòîëüêî òîãäà, êîãäà íåïðîòèâîðå÷èâî êàæäîå êîíå÷íîå ïîäìíîæåñòâî Γ0 , Γ0 ⊆ Γ.Óïðàæíåíèå 1.36.Óïðàæíåíèå 1.37.1.5.Ðàâíîñèëüíûå ôîðìóëû è íîðìàëüíûå ôîðìû13Ïóñòü Γ íåêîòîðîå ìíîæåñòâî çàìêíóòûõ ôîðìóë ëîãèêè ïðåäèêàòîâ.

Âåðíî ëè, ÷òî Γ ÿâëÿåòñÿ íåïðîòèâîðå÷èâûì ìíîæåñòâîì òîãäà è òîëüêî òîãäà âñÿêàÿäèçúþíêöèÿ âèäà ¬ϕ1 ∨ ¬ϕ1 ∨ · · · ∨ ¬ϕn , ãäå ϕ1 , ϕ2 , . . . , ϕn ôîðìóëû èç Γ, íå ÿâëÿåòñÿîáùåçíà÷èìîé?Óïðàæíåíèå 1.38.Ïóñòü èçâåñòíî, ÷òî Γ ýòî íåêîòîðîå íåïóñòîå ìíîæåñòâî ëîãè÷åñêèõñëåäñòâèé çàìêíóòîé ôîðìóëû ϕ. Ïóñòü òàêæå èçâåñòíî, ÷òî ìíîæåñòâî ôîðìóë Γ íå èìååò íè îäíîé ìîäåëè ñ êîíå÷íîé èëè ñ÷åòíî-áåñêîíå÷íîé îáëàñòüþ èíòåðïðåòàöèè. Êàêèå èçïðèâåäåííûõ íèæå óòâåðæäåíèé íåâåðíû è ïî÷åìó?1. Ôîðìóëà ϕ íå èìååò íè îäíîé ìîäåëè ñ êîíå÷íîé èëè ñ÷åòíî-áåñêîíå÷íîé îáëàñòüþèíòåðïðåòàöèè.2. Ôîðìóëà ϕ íå èìååò âîîáùå íè îäíîé ìîäåëè.3.

Ëþáàÿ ôîðìóëà ψ ÿâëÿåòñÿ ëîãè÷åñêèì ñëåäñòâèå ôîðìóëû ϕ.Óïðàæíåíèå 1.39.Äîêàæèòå, ÷òî â òîì ñëó÷àå, êîãäà ñåìàíòè÷åñêàÿ òàáëèöà T = h Γ | ∆ iñîñòîèò èç áåñêâàíòîðíûõ ôîðìóë, ëþáîé òàáëè÷íûé âûâîä äëÿ T ÿâëÿåòñÿ êîíå÷íûì. Áóäåò ëè ýòî óòâåðæäåíèå âåðíûì è â òîì ñëó÷àå, êîãäà âñå ôîðìóëû òàáëèöû T ñîäåðæèò âñîâîêóïíîñòè íå áîëåå îäíîãî êâàíòîðà?Óïðàæíåíèå 1.40.1.5Ðàâíîñèëüíûå ôîðìóëû è íîðìàëüíûå ôîðìûÄâå ôîðìóëû ϕ è ψ íàçûâàþòñÿ ðàâíîâûïîëíèìûìè, åñëè äëÿ ëþáîé èíòåðïðåòàöèè I ôîðìóëà ϕ âûïîëíèìà â èíòåðïðåòàöèè I â òîì è òîëüêî òîèì ñëó÷àå,êîãäà ôîðìóëà ψ âûïîëíèìà â I .

Äîêàæèòå çàìêíóòûå ôîðìóëû ϕ è ψ ÿâëÿþòñÿ ðàâíîâûïîëíèìûìè òîãäà è òîëüêî òîãäà, êîãäà îíè ðàâíîñèëüíû. Îñòàåíåòñÿ ëè ýòî óòâåðæäåíèåñïðàâåäëèâûì è äëÿ ïðîèçâîëüíûõ ôîðìóë?Óïðàæíåíèå 1.41.Óïðàæíåíèå 1.42.Êàêîâî ìíîæåñòâî ôîðìóë, ðàâíîñèëüíûõ îáùåçíà÷èìîé ôîðìóëå ϕ?Èñïîëüçóÿ ïðàâèëà ðàâíîñèëüíûõ ïðåîáðàçîâàíèé ôîðìóë, ïðèâåñòèñëåäóþùèå ôîðìóëû ê ïðåäâàðåííîé íîðìàëüíîé ôîðìå.Óïðàæíåíèå 1.43.∃x∀y P (x, y) & ∀x∃y P (y, x);∀x ((∃y P (y, x) → ∃y P (x, y)) → Q(x)) → ∃x Q(x);¬∀y(∃xP (x, y) → ∀u(R(y, u) → ¬∀z(P (z, u) ∨ ¬R(z, y))));∃x∃y(P (x, y) → R(x)) → ∀x(¬∃yP (x, y) ∨ R(x));∃x∀y (P (x, y) → (¬P (y, x) → (P (x, x) ≡ P (y, y))));∃x(∀xP (x, x) ∨ ∃x¬R(x)) → ∃x(R(x) → ∃yP (f (x), y)).Ïðåäëîæèòå àëãîðèòì, êîòîðûé äëÿ ëþáîé çàìêíóòîé ôîðìóëûñòðîèò ðàâíîñèëüíóþ ÏÍÔ çà âðåìÿ O(N ), ãäå N äëèíà ôîðìóëû ϕ.Óïðàæíåíèå 1.44.ϕ14Ãëàâà 1.ÓÏÐÀÆÍÅÍÈßÏðèâåäèòå ïðèìåð çàìêíóòîé ôîðìóëû, ëþáàÿ ÏÍÔ êîòîðîé èìååòêâàíòîðíóþ ïðèñòàâêó, ñîñòîÿùóþ èç ÷åðåäóþùèõñÿ êâàíòîðîâ âñåîáùíîñòè è ñóùåñòâîâàíèÿ.

Äîêàæèòå, ÷òî íèêàêèå ðàâíîñèëüíûå ïðåîáðàçîâàíèÿ ôîðìóë íå ìîãóò óñòðàíèòü ýòî÷åðåäîâàíèå.Ñóùåñòâóþò ëè òàêèå ôîðìóëû, ïðåäâàðåííûå íîðìàëüíûå ôîðìûêîòîðûõ èìåþò ðàçíûå êâàíòîðíûå ïðèñòàâêè? Êàêèì óñëîâèÿì äîëæíà óäîâëåòâîðÿòü çàìêíóòàÿ ôîðìóëà, äëÿ òîãî ÷òîáû ëþáàÿ åå ÏÍÔ èìåëà îäíó è òó æå (ñ òî÷íîñòüþ äî ïåðåèìåíîâàíèÿ ïåðåìåííûõ) êâàíòîðíóþ ïðèñòàâêó.Èçâåñòíî, ÷òî çàìêíóòàÿ ôîðìóëà ϕ ðàâíîñèëüíà ôîðìóëå ψ. Êàêèåèç ïðèâåäåííûõ íèæå óòâåðæäåíèé âåðíû è ïî÷åìó?1.

Âñÿêîå ëîãè÷åñêîå ñëåäñòâèå ôîðìóëû ϕ ÿâëÿåòñÿ ëîãè÷åñêèì ñëåäñòâèåì ôîðìóëû ψ.2. Âñÿêàÿ ìîäåëü ôîðìóëû ϕ ÿâëÿåòñÿ ìîäåëüþ ôîðìóëû ψ.3. Ôîðìóëû ϕ è ψ èìåþò îäèíàêîâóþ ïðåäâàðåííóþ íîðìàëüíóþ ôîðìó.4. Ôîðìóëà ϕ îáùåçíà÷èìà òîãäà è òîëüêî òîãäà, êîãäà îáùåçíà÷èìà ôîðìóëà ψ.Óïðàæíåíèå 1.45.Óïðàæíåíèå 1.46.Óïðàæíåíèå 1.47.Èñïîëüçóÿ ïðàâèëî ñêîëåìèçàöèè, ïîñòðîéòå ñêîëåìîâñêèå ñòàíäàðòíûå ôîðìû äëÿ ñëåäóþùèõ ôîðìóë.Óïðàæíåíèå 1.48.∀x∃y∀z∃uR(x, y, z, u);¬∀x(∃yR(x, y) → ∀zP (z, x));¬∀y(∃xP (x, y) → ∀u(R(y, u) → ¬∀z(P (z, u) ∨ ¬R(z, y))));∃x∃y(P (x, y) → R(x)) → ∀x(¬∃yP (x, y) ∨ R(x));∃x∀y (P (x, y) → (¬P (y, x) → (P (x, x) ≡ P (y, y))));∃x(∀xP (x, x) ∨ ∃x¬R(x)) → ∃x(R(x) → ∃yP (f (x), y)).Ïóñòü èçâåñòíî, ÷òî ôîðìóëà ϕ0 ÿâëÿåòñÿ ÑÑÔ äëÿ ôîðìóë ψ1 è ψ2 .Âåðíî ëè, ÷òî â ýòîì ñëó÷àå ôîðìóëû ψ1 è ψ2 ñîâåðøåííî îäèíàêîâû?Ïóñòü èçâåñòíî, ÷òî ôîðìóëà ϕ ïðåäñòàâëåíà â ÏÍÔ, à ôîðìóëà ψÿâëÿåòñÿ ÑÑÔ, ñîîòâåòñòâóþùåé ôîðìóëå ϕ.

Êàêèå èç ïðèâåäåííûõ íèæå óòâåðæäåíèé âåðíûè ïî÷åìó?1. Åñëè ôîðìóëà ψ íåâûïîëíèìà, òî è ôîðìóëà ϕ òàêæå íåâûïîëíèìà, ïîòîìó ÷òî....2. Åñëè ôîðìóëà ψ âûïîëíèìà, òî è ôîðìóëà ϕ òàêæå âûïîëíèìà, ïîòîìó ÷òî....3. Åñëè ôîðìóëà ϕ îáùåçíà÷èìà, òî è ôîðìóëà ψ òàêæå îáùåçíà÷èìà, ïîòîìó ÷òî....4. Åñëè ôîðìóëà ψ îáùåçíà÷èìà, òî è ôîðìóëà ϕ òàêæå îáùåçíà÷èìà, ïîòîìó ÷òî....Óïðàæíåíèå 1.49.Óïðàæíåíèå 1.50.Ïóñòü èçâåñòíî, ÷òî ôîðìóëà ϕ ïðåäñòàâëåíà â ÏÍÔ, à ôîðìóëà ψÿâëÿåòñÿ ÑÑÔ, ñîîòâåòñòâóþùåé ôîðìóëå ϕ.

ßâëÿþòñÿ ëè ôîðìóëû ϕ è ψ ðàâíîñèëüíûìè?ßâëÿåòñÿ ëè îáùåçíà÷èìîé ôîðìóëà ϕ → ψ? ßâëÿåòñÿ ëè îáùåçíà÷èìîé ôîðìóëà ψ → ϕ?Óïðàæíåíèå 1.51.1.6.1.6Ýðáðàíîâñêèå èíòåðïðåòàöèè. Òåîðåìà Ýðáðàíà15Ýðáðàíîâñêèå èíòåðïðåòàöèè. Òåîðåìà ÝðáðàíàÏðè êàêèõ óñëîâèÿõ ýðáðàíîâñêèé óíèâåðñóì ñèãíàòóðû σ ÿâëÿåòñÿêîíå÷íûì ìíîæåñòâîì?Óïðàæíåíèå 1.52.Âåðíî ëè, ÷òî âñÿêàÿ ôîðìóëà ϕ ÿâëÿåòñÿ îáùåçíà÷èìîé òîãäà è òîëüêîòîãäà, êîãäà ϕ èñòèííà âî âñåõ ýðáðàíîâñêèõ èíòåðïðåòàöèÿõ?Óïðàæíåíèå 1.53.Âåðíî ëè, ÷òî âñÿêàÿ ôîðìóëà ϕ ñèãíàòóðû σ ÿâëÿåòñÿ âûïîëíèìîéòîãäà è òîëüêî òîãäà, êîãäà ϕ âûïîëíèìà â íåêîòîðîé ýðáðàíîâñêîé èíòåðïðåòàöèè ñèãíàòóðûσ?Óïðàæíåíèå 1.54.Ïóñòü ϕ ôîðìóëà ëîãèêè ïðåäèêàòîâ ñèãíàòóðû σ, ïðåäñòàâëåííàÿ âñêîëåìîâñêîé ñòàíäàðòíîé ôîðìå.

Êàêèå èç ïðèâåäåííûõ íèæå óòâåðæäåíèé âåðíû è ïî÷åìó?1. Åñëè ôîðìóëà ϕ âûïîëíèìà, òî ϕ âûïîëíèìà õîòÿ áû â îäíîé ýðáðàíîâñêîé èíòåðïðåòàöèè ñèãíàòóðû σ,2. Åñëè ôîðìóëà ϕ âûïîëíèìà õîòÿ áû â îäíîé ýðáðàíîâñêîé èíòåðïðåòàöèè ñèãíàòóðû σ,òî ôîðìóëà ϕ âûïîëíèìà.3. Åñëè ôîðìóëà ϕ âûïîëíèìà â êàæäîé ýðáðàíîâñêîé èíòåðïðåòàöèè ñèãíàòóðû σ, òîôîðìóëà ϕ îáùåçíà÷èìà.4. Åñëè ôîðìóëà ϕ íå èìååò ýðáðàíîâñêèõ ìîäåëåé, òî ôîðìóëà ϕ íå èìååò íèêàêèõ ìîäåëåé.Óïðàæíåíèå 1.55.Êàæäàÿ ýðáðàíîâñêàÿ èíòåðïðåòàöèÿ I ñèãíàòóðû ïîëíîñòüþ îïðåäåëÿåòñÿ ìíîæåñòâîì âñåõ òåõ îñíîâíûõ àòîìîâ ñèãíàòóðû σ, êîòîðûå âûïîëíÿþòñÿ â èíòåðïðåòàöèè I .  ïîñëåäóþùèõ óïðàæíåíèÿõ áóäåò èñïîëüçîâàòüñÿ òåîðåòèêî-ìíîæåñòâåííûéñïîñîá ïðåäñòàâëåíèÿ ýðáðàíîâñêèõ èíòåðïðåòàöèé, ïðè êîòîðîì ýðáðàíîâñêàÿ èíòåðïðåòàöèÿ I îòîæäåñòâëÿåòñÿ ñ òåì ìíîæåñòâîì îñíîâíûõ àòîìîâ, êîòîðûå â íåé âûïîëíÿþòñÿ,ò.

å.Óïðàæíåíèå 1.56.I = {A : A ∈ Bσ , I |= A}.Ïðåäïîëîæèì, ÷òî çàìêíóòàÿ ôîðìóëà ϕ èìååò ýðáðàíîâñêèå ìîäåëè I1 è I2 . Âåðíî ëè, ÷òîèíòåðïðåòàöèè I1 ∪ I2 è I1 ∩ I2 áóäóò òàêæå ÿâëÿòüñÿ ýðáðàíîâñêèìè ìîäåëÿìè äëÿ ôîðìóëûϕ?Ïðåäïîëîæèì, ÷òî çàìêíóòàÿ ôîðìóëà ψ ÿâëÿåòñÿ ñêîëåìîâñêîé ñòàíäàðòíîé ôîðìîé è èìååò ýðáðàíîâñêèå ìîäåëè I1 è I2 . Âåðíî ëè, ÷òî èíòåðïðåòàöèè I1 ∪ I2 èI1 ∩ I2 áóäóò òàêæå ÿâëÿòüñÿ ýðáðàíîâñêèìè ìîäåëÿìè äëÿ ôîðìóëû ψ ?Óïðàæíåíèå 1.57.Ïðè êàêèõ óñëîâèÿ îáå ýðáðàíîâñêèå èíòåðïðåòàöèè BH è ∅ áóäóòòàêæå ÿâëÿòüñÿ ýðáðàíîâñêèìè ìîäåëÿìè äëÿ ñèñòåìû äèçúþíêòîâ S ?Óïðàæíåíèå 1.58.Ïóñòü èçâåñòíî, ÷òî ϕ(x1 , x2 , .