Расширенный сборник задач для самостоятельного решения (1161810), страница 2
Текст из файла (страница 2)
∃x P (x) → ∀x P (x);2. ¬(∃x P (x) → ∀x P (x));3. ∃x ∀y (Q(x, x)&¬Q(x, y));4. ∃x (P (x) & ∃x ¬P (x));5. (∀x P (x) → ∀x R(x)) → ∀x (P (x)&R(x));6. ∀x (P (x)&R(x)) → (∀x P (x) & ∀x R(x));7. (∀x P (x) & ∀x R(x)) → ∀x (P (x)&R(x));8. ∃x (P (x)&R(x)) → (∃x P (x) & ∃x R(x));9. (∃x P (x) & ∃x R(x)) → ∃x (P (x)&R(x));10.
∀x ∃y Q(x, y) → ∃y ∀x Q(x, y);11. ∃y ∀x Q(x, y) → ∀x ∃y Q(x, y);12. ∀x (P (x) → ¬R(x)) → ¬(∃x P (x) & ∀x R(x));13. ∀x ∃y ∀z (R(x, y) → R(y, z));14. ∃x ∀y ∃z (R(x, y) → R(y, z));15. ∃x ∀y ∃z ((R(y, z) → R(x, z)) → (R(x, x) → R(y, x)));16. ∀x ∃y P (x, y) & ∀x ∀y (P (x, y) → P (y, x))&∀x ∀y ∀z (P (x, y) → (P (y, z) → P (x, z))).Óïðàæíåíèå 1.9.1.2.Âûïîëíèìûå è îáùåçíà÷èìûå ôîðìóëûÓïðàæíåíèå 1.10.7Äîêàæèòå, ÷òî ôîðìóëà∃x∀y (P (x, y) → (¬P (y, x) → ((P (x, x) → P (y, y)) & (P (y, y)to P (x, x)))))èñòèííà â ëþáîé èíòåðïðåòàöèè, îáëàñòü êîòîðîé ñîäåðæèò íå áîëåå òðåõ ýëåìåíòîâ.Ñóùåñòâóåò ëè íåîáùåçíà÷èìàÿ ôîðìóëà, ÿâëÿþùàÿñÿ èñòèííîé â ëþáîé èíòåðïðåòàöèè, îáëàñòü êîòîðîé ñîäåðæèò íå ìåíåå òðåõ ýëåìåíòîâ?Óïðàæíåíèå 1.11.Çàïèøèòå íåîáùåçíà÷èìóþ ôîðìóëó, ÿâëÿþùóþñÿ èñòèííîé â ëþáîéèíòåðïðåòàöèè, îáëàñòü êîòîðîé ñîäåðæèò1. íå áîëåå îäíîãî ýëåìåíòà,2.
íå áîëåå äâóõ ýëåìåíòîâ,3. íå áîëåå n ýëåìåíòîâ, ãäå n íåêîòîðîå çàäàííîå íàòóðàëüíîå ÷èñëî.Óïðàæíåíèå 1.12.Ñóùåñòâóåò ëè òàêîå ïðåäëîæåíèå ϕ, ëîãè÷åñêèì ñëåäñòâèåì êîòîðîãî1. ÿâëÿåòñÿ ëþáàÿ çàìêíóòàÿ ôîðìóëà?2. íå ÿâëÿåòñÿ íè îäíà çàìêíóòàÿ ôîðìóëà?3. ÿâëÿåòñÿ òîëüêî êîíå÷íîå ÷èñëî çàìêíóòûõ ôîðìóë?Óïðàæíåíèå 1.13.Êàêèå ôîðìóëû ÿâëÿþòñÿ ëîãè÷åñêèìè ñëåäñòâèÿìè1. îáùåçíà÷èìîé ôîðìóëû ϕ?2. ïðîòèâîðå÷èâîé ôîðìóëû ϕ?Óïðàæíåíèå 1.14.Ïóñòü èçâåñòíî, ÷òî âûïîëíèìûå çàìêíóòûå ôîðìóëû ϕ è ψ íå èìåþòíè îäíîé îáùåé ìîäåëè. Êàêèå èç ïðèâåäåííûõ íèæå óòâåðæäåíèé âñåãäà âåðíû è ïî÷åìó?1.
Ñóùåñòâóåò ôîðìóëà χ, ëîãè÷åñêèì ñëåäñòâèåì êîòîðîé ÿâëÿþòñÿ îáå ôîðìóëû ϕ è ψ;2. Ñóùåñòâóåò ôîðìóëà χ, êîòîðàÿ ÿâëÿåòñÿ ëîãè÷åñêèì ñëåäñòâèåì îáåèõ ôîðìóë ϕ è ψ;3. Ôîðìóëû ¬ϕ è ¬ϕ òàêæå íå èìåþò íè îäíîé îáùåé ìîäåëè;4. Íè îäíà èç ôîðìóë ϕ, ψ íå ÿâëÿåòñÿ îáùåçíà÷èìîé.Óïðàæíåíèå 1.15.Ïóñòü Γ1 è Γ2 äâà ðàçëè÷íûõ íåïðîòèâîðå÷èâûõ ìíîæåñòâà çàìêíóòûõ ôîðìóë. Êàêèå èç ïðèâåäåííûõ íèæå óòâåðæäåíèé ñïðàâåäëèâû? Âûáîð îòâåòàîáîñíîâàòü.1. Îáúåäèíåíèå Γ1 ∪ Γ2 è ïåðåñå÷åíèå Γ1 ∩ Γ2 âñåãäà ÿâëÿþòñÿ íåïðîòèâîðå÷èâûìè ìíîæåñòâàìè.Óïðàæíåíèå 1.16.8Ãëàâà 1.ÓÏÐÀÆÍÅÍÈß2.
Îáúåäèíåíèå Γ1 ∪ Γ2 âñåãäà ÿâëÿåòñÿ íåïðîòèâîðå÷èâûì ìíîæåñòâîì, ïîòîìó ÷òî. . .Îäíàêî ïåðåñå÷åíèå Γ1 ∩ Γ2 ìîæåò îêàçàòüñÿ ïðîòèâîðå÷èâûì ìíîæåñòâîì.3. Ïåðåñå÷åíèå Γ1 ∩ Γ2 âñåãäà ÿâëÿåòñÿ íåïðîòèâîðå÷èâûì ìíîæåñòâîì, îäíàêî, îáúåäèíåíèå Γ1 ∪ Γ2 ìîæåò îêàçàòüñÿ ïðîòèâîðå÷èâûì ìíîæåñòâîì.4. Ñóùåñòâóþò ïðèìåðû òàêèõ íåïðîòèâîðå÷èâûõ ìíîæåñòâ Γ1 è Γ2 , êîãäà îáúåäèíåíèåΓ1 ∪ Γ2 è ïåðåñå÷åíèå Γ1 ∩ Γ2 îêàçûâàþòñÿ ïðîòèâîðå÷èâûìè ìíîæåñòâàìè.Ïóñòü Γ1 è Γ2 íåêîòîðûå ìíîæåñòâà ïðåäëîæåíèé. Îáîçíà÷èì ∆i ,, ìíîæåñòâî âñåõ çàìêíóòûõ ôîðìóë, ÿâëÿþùèõñÿ ëîãè÷åñêèìè ñëåäñòâèÿìè ìíîæåñòâà ïðåäëîæåíèé Γi . Êàêèì ìîæåò áûòü ìíîæåñòâî ëîãè÷åñêèõ ñëåäñòâèé ñîâîêóïíîñòèïðåäëîæåíèé1. Γ1 ∩ Γ2 ?2. Γ1 ∪ Γ2 ?Óïðàæíåíèå 1.17.i = 1, 2Ââåäåì íà ìíîæåñòâàõ çàìêíóòûõ ôîðìóë îòíîøåíèå ñëåäóþùèìîáðàçîì: îòíîøåíèå Γ1 Γ2 èìååò ìåñòî äëÿ äâóõ ìíîæåñòâ çàìêíóòûõ ôîðìóë Γ1 , Γ2 òîãäàè òîëüêî òîãäà, êîãäà ëþáàÿ ôîðìóëà ϕ, ϕ ∈ Γ1 , ÿâëÿåòñÿ ëîãè÷åñêèì ñëåäñòâèåì ìíîæåñòâàôîðìóë Γ1 .
Êàêèìè èç ïåðå÷èñëåííûõ ñâîéñòâ1. ðåôëåêñèâíîñòü,2. òðàíçèòèâíîñòü,3. ñèììåòðè÷íîñòü,4. òîòàëüíîñòü: äëÿ ëþáûõ ìíîæåñòâ çàìêíóòûõ ôîðìóë Γ1 , Γ2 âåðíî õîòÿ áû îäíî èçñîîòíîøåíèé Γ1 Γ2 èëè Γ2 Γ1 ,5. ∪-ìîíîòîííîñòü: Γ01 Γ02 ∧ Γ001 Γ002 ⇒ Γ01 ∪ Γ001 Γ02 ∪ Γ002 ,6. ∩-ìîíîòîííîñòü: Γ01 Γ02 ∧ Γ001 Γ002 ⇒ Γ01 ∩ Γ001 Γ02 ∩ Γ002 ,îáëàäàåò îòíîøåíèå ?Óïðàæíåíèå 1.18.1.3Òàáëè÷íûé âûâîäÄîêàæèòå îáùåçíà÷èìîñòü ïðèâåäåííûõ íèæå ôîðìóë, ïîñòðîèâ óñïåøíûé òàáëè÷íûé âûâîä äëÿ ñîîòâåòñòâóþùèõ ñåìàíòè÷åñêèõ òàáëèö.1. ∀x P (x) → ∀y P (y)2. ¬∃xP (x) → ∀x¬P (x);3.
∀x¬P (x) → ¬∃xP (x);4. ∀x (P (x)&R(x)) → (∀x P (x) & ∀x R(x));Óïðàæíåíèå 1.19.1.3.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.20.9Òàáëè÷íûé âûâîä;(∀x P (x) & ∀x R(x)) → ∀x (P (x)&R(x));(∃x P (x) ∨ ∃x R(x)) → ∃x (P (x) ∨ R(x));(∀x P (x) ∨ R(y)) → ∀x (P (x) ∨ R(y));∀x (P (x) ∨ R(y)) → (∀x P (x) ∨ R(y));∃y ∀x Q(x, y) → ∀x ∃y Q(x, y);∃x (P (x) ∨ R(x)) → (∃x P (x) ∨ ∃x R(x));∀x((∃x¬P (x) → ∃xR(x)) → ∃y(P (x) ∨ R(y)))∀x (P (x) → ∃y R(x, f (y))) → (∃x ¬P (x) ∨ ∀x∃zR(x, z));R(y, z));;∀x ∃y ∀z (R(x, y) → R(y, z))∃x ∀y ∃z (R(x, y) →∃x (R(x) & ∃x (P (x) → ¬R(x)) → ¬∀x P (x));;∃x ((∀y P (x, y) ∨ ∃x R(x)) → (∃x P (x, x) ∨ R(x)));∃x (∀x P (x) → ¬(R(x) & ∃x (P (x) → ¬R(x))));∃x (∃y ¬P (x, y) → ∀x R(x)) → ∀x (R(x) ∨ ∃x P (x, f (x)))∀x∃u (∃v∀y ((E(u, y) → H(y, v)) & ∃w∀x (H(w, y) → ¬H(x, v))) → ∃y ¬E(x, y))∀x (∀y∃v∀u ((A(u, v) → B(y, u)) & (¬∃w A(w, u) → ∀w A(w, v))) → ∃y B(x, y)).;Äîêàæèòå, ÷òî â òîì ñëó÷àå, åñëè äëÿ òàáëèöû T = h ϕ | ∅i ñóùåñòâóåòóñïåøíûé âûâîä, òî ôîðìóëà ϕ íåâûïîëíèìà.Ïóñòü Γ ⊆ CF orm è ϕ ∈ CF orm.
Äîêàæèòå, ÷òî ñóùåñòâîâàíèå óñïåøíîãî òàáëè÷íîãî âûâîäà äëÿ òàáëèöû T = h Γ | ϕ i ñâèäåòåëüñòâóåò î òîì, ÷òî ôîðìóëà ϕÿâëÿåòñÿ ëîãè÷åñêèì ìíîæåñòâà ôîðìóë Γ.Äîêàæèòå, ÷òî íåâûïîëíèìîñòü òàáëèöû h ϕ1 , . . . , ϕn | ψ1 , . . . , ψm iðàíîñèëüíà îáùåçíà÷èìîñòè ôîðìóëû (ϕ1 & . . . &ϕn ) → (ψ1 ∨ · · · ∨ ψm ).Äîêàæèòå, èñïîëüçóÿ èñ÷èñëåíèå ñåìàíòè÷åñêèõ òàáëèö, ÷òî ôîðìóëà∃z L(z, Äàøà) ëîãè÷åñêè ñëåäóåò èç ñîâîêóïíîñòè ïðåäëîæåíèéÓïðàæíåíèå 1.20.Óïðàæíåíèå 1.21.Óïðàæíåíèå 1.22.Óïðàæíåíèå 1.23.L(Äàøà, Ñàøà),L(Ñàøà, ïèâî),L(Ïàøà, ïèâî),∀x (∃y (L(Ïàøà, y)&L(x, y)) → L(Ïàøà, x)).Âûÿñíèòå, ïðèìåíÿÿ òàáëè÷íûé âûâîä, êàêèå èç ïðèâåäåííûõ íèæåôîðìóë ÿâëÿþòñÿ âûïîëíèìûìè, êàêèå ÿâëÿþòñÿ íåâûïîëíèìûìè, à êàêèå îáùåçíà÷èìûìè.Óïðàæíåíèå 1.24.10Ãëàâà 1.1.2.3.4.5.6.¬(∃x P (x) → ∀x P (x));∃x ∀y (Q(x, x)&¬Q(x, y));∀x (P (x) & ∀x ¬P (x));ÓÏÐÀÆÍÅÍÈß;∃x (P (x) & ∃x ¬P (x));∀x (P (x)&R(x)).(∃x P (x) & ∃x R(x)) → ∃x (P (x)&R(x))(∀x P (x) & ∀x R(x)) →Ïóñòü èçâåñòíî, ÷òî ñåìàíòè÷åñêàÿ òàáëèöà h Γ | ∅ i èìååò òàáëè÷íûéâûâîä, îäíà èç âåòâåé êîòîðîãî çàêàí÷èâàåòñÿ òàêîé ñåìàíòè÷åñêîé òàáëèöåé T = h Γ0 | ∆0 i,÷òî Γ0 ∩ ∆0 = ∅ è ïðè ýòîì íè îäíî ïðàâèëî òàáëè÷íîãî âûâîäà íå ïðèìåíèìî ê òàáëèöå T .Êàêèå èç ïðèâåäåííûõ íèæå óòâåðæäåíèé íàâåðíÿêà ñïðàâåäëèâû è ïî÷åìó?1.
Ìíîæåñòâî ôîðìóë Γ íå èìååò ìîäåëè;2. Ìíîæåñòâî ôîðìóë Γ èìååò ìîäåëü ñ áåñêîíå÷íîé ïðåäìåòíîé îáëàñòüþ;3.  ìíîæåñòâå ôîðìóë Γ îáÿçàòåëüíî åñòü õîòÿ áû îäíà îáùåçíà÷èìàÿ ôîðìóëà;4.  ìíîæåñòâå ôîðìóë Γ îáÿçàòåëüíî åñòü õîòÿ áû îäíà ïðîòèâîðå÷èâàÿ ôîðìóëà.Óïðàæíåíèå 1.25.Ïóñòü èçâåñòíî, ÷òî ñåìàíòè÷åñêàÿ òàáëèöà T = h Γ | ∆ i èìååò óñïåøíûé òàáëè÷íûé âûâîä. Êàêèå èç ïðèâåäåííûõ íèæå óòâåðæäåíèé ïðè ýòîì óñëîâèè áóäóòâñåãäà ñïðàâåäëèâû è ïî÷åìó?1. Õîòÿ áû îäíà ôîðìóëà èç ìíîæåñòâà ôîðìóë ∆ ÿâëÿåòñÿ îáùåçíà÷èìîé;2.
Õîòÿ áû îäíà ôîðìóëà èç ìíîæåñòâà ôîðìóë ∆ ÿâëÿåòñÿ âûïîëíèìîé;3. Õîòÿ áû îäíà ôîðìóëà èç ìíîæåñòâà ôîðìóë ∆ ÿâëÿåòñÿ ïðîòèâîðå÷èâîé;4. Ìíîæåñòâî ôîðìóë Γ èìååò ìîäåëü;5. Ìíîæåñòâî ôîðìóë Γ íå èìååò ìîäåëè.Óïðàæíåíèå 1.26.Èçâåñòíî, ÷òî ñåìàíòè÷åñêàÿ òàáëèöà T = h ϕ | ψ i íåâûïîëíèìà. Êàêèåèç ïðèâåäåííûõ íèæå óòâåðæäåíèé âñåãäà âåðíû äëÿ ëþáûõ çàìêíóòûõ ôîðìóë ϕ è ψ?1.
Ôîðìóëà ϕ ÿâëÿåòñÿ ëîãè÷åñêèì ñëåäñòâèåì ôîðìóëû ψ;2. Ôîðìóëà ψ ÿâëÿåòñÿ ëîãè÷åñêèì ñëåäñòâèåì ôîðìóëû ϕ;3. Íå ñóùåñòâóåò óñïåøíîãî òàáëè÷íîãî âûâîäà èç ñåìàíòè÷åñêîé òàáëèöû T ;4. Ôîðìóëà ϕ → ψ ÿâëÿåòñÿ ïðîòèâîðå÷èâîé.Óïðàæíåíèå 1.27.Êàêèå èç ïåðå÷èñëåííûõ íèæå ïðàâèë òàáëè÷íîãî âûâîäà T1T,0T2 è TT10ÿâëÿþòñÿ êîððåêòíûìè?Óïðàæíåíèå 1.28.1.4.1.h Γ, ϕ → ψ | ∆ ih Γ, ¬ϕ, ψ | ∆ i2.h Γ, ∀x ϕ(x) | ∆ ih Γ, ϕ(x) | ∆ i3.h Γ 1 , Γ 2 | ∆1 , ∆2 ih Γ1 | ∆1 i, h Γ2 | ∆2 i4.h Γ1 , Γ2 | ∆ ih Γ1 | ∆ i, h Γ2 | ∆ i;5.h Γ | ∆1 , ∆2 ih Γ | ∆1 i, h Γ | ∆2 i;6.h Γ 1 , Γ 2 | ∆1 , ∆2 ih Γ1 | ∆1 , Φ i, h Γ2 , Φ | ∆2 i1.411Ïîëíîòà òàáëè÷íîãî âûâîäà;;;;Ïîëíîòà òàáëè÷íîãî âûâîäàÈñïîëüçóÿ èñ÷èñëåíèå ñåìàíòè÷åñêèõ òàáëèö è ñòðàòåãèþ ïîñòðîåíèÿòàáëè÷íîãî âûâîäà, îïèñàííóþ â äîêàçàòåëüñòâå òåîðåìû ïîëíîòû, ïðîâåðüòå âûïîëíèìîñòüïðèâåäåííûõ íèæå ñåìàíòè÷åñêèõ òàáëèö.1.
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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
