Расширенный сборник задач для самостоятельного решения (1161810), страница 3
Текст из файла (страница 3)
Òàáëèöà 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 , .
. . , xn ) áåñêâàíòîðíàÿ ôîðìóëà, â êîòîðîé íå ñîäåðæàòñÿ íè êîíñòàíòû, íè ôóíêöèîíàëüíûå ñèìâîëû. Äîêàæèòå, ÷òîÓïðàæíåíèå 1.59.16Ãëàâà 1.ÓÏÐÀÆÍÅÍÈß1. ôîðìóëà ∀x1 ∀x2 . . . ∀xn ϕ(x1 , x2 , . . . , xn ) îáùåçíà÷èìà òîãäà è òîëüêî òîãäà, êîãäà îíàèñòèííà â ëþáîé èíòåðïðåòàöèè, ïðåäìåòíàÿ îáëàñòü êîòîðîé ñîñòîèò èç n ýëåìåíòîâ;2. ôîðìóëà ∃x1 ∃x2 . . . ∃xn ϕ(x1 , x2 , . . . , xn ) îáùåçíà÷èìà òîãäà è òîëüêî òîãäà, êîãäà îíàèñòèííà â ëþáîé èíòåðïðåòàöèè, ïðåäìåòíàÿ îáëàñòü êîòîðîé ñîñòîèò èç îäíîãî ýëåìåíòà.Îòûùèòå íàèìåíüøåå ïðîòèâîðå÷èâîå ìíîæåñòâî îñíîâíûõ ïðèìåðîâäëÿ ñëåäóþùèõ ñèñòåì äèçúþíêòîâ (ïåðåìåííûå îáîçíà÷åíû çàãëàâíûìè áóêâàìè, à êîíñòàíòû è ôóíêöèîíàëüíûå ñèìâîëû ïðîïèñíûìè):1. S1 = { ¬P (X) ∨ Q(f (X), X), P (g(b)), ¬Q(Y, Z) };2. S2 = { P (X, a, f (X, b)) ∨ ¬Q(Y, f (b, Y )), ¬P (f (Y ), Z, Y ), Q(X, Y ) ∨ Q(a, Z) }.Óïðàæíåíèå 1.60.Ïðè ïîìîùè ïðàâèëà ðåçîëþöèè äîêàæèòå ïðîòèâîðå÷èâîñòü ñèñòåìîñíîâíûõ äèçúþíêòîâ1.
S1 = { ¬R, ¬Q, ¬P ∨ R, P ∨ Q ∨ R };2. S2 = { P ∨ Q, ¬P ∨ R, ¬P ∨ Q, ¬R }.Óïðàæíåíèå 1.61.1.7Çàäà÷à óíèôèêàöèèÄîêàæèòå, ÷òî ïîäñòàíîâêà θ = {x1 /t1 , x2 /t2 , . . . , xn /tn } ÿâëÿåòñÿ ïåðåèìåíîâàíèåì òîãäà è òîëüêî òîãäà, êîãäà {t1 , t2 , . . . , tn } = {x1 , x2 , . . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
