Расширенный сборник задач для самостоятельного решения
Описание файла
PDF-файл из архива "Расширенный сборник задач для самостоятельного решения", который расположен в категории "". Всё это находится в предмете "математическая логика и логическое программирование" из 8 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст из PDF
Ãëàâà 1ÓÏÐÀÆÍÅÍÈß1.1Êëàññè÷åñêàÿ ëîãèêà ïðåäèêàòîâ ïåðâîãî ïîðÿäêà: ñèíòàêñèñ è ñåìàíòèêà êàæäîé èç ïðèâåäåííûõ íèæå ñîêðàùåííûõ çàïèñåé ôîðìóë ÊËÏâîññòàíîâèòå îïóùåííûå ñêîáêè, ðóêîâîäñòâóÿñü ñîãëàøåíèåì î ïðèîðèòåòå ëîãè÷åñêèõîïåðàöèé;îïðåäåëèòå îáëàñòü äåéñòâèÿ êàæäîãî êâàíòîðà;âûäåëèòå âñå ñâÿçàííûå âõîæäåíèÿ ïåðåìåííûõ, âñå ñâîáîäíûå âõîæäåíèÿ ïåðåìåííûõ.∃x P (x) → ∀y R(x, y);∃y ¬∃x P (x) ∨ ∀x P (x) → P (y);∀x (∃x P (x) → ∀y R(x, y) ∨ ¬P (y)).Óïðàæíåíèå 1.1.à)á)â)1.2.3.Äëÿ êàæäîãî èç ïðèâåäåííûõ íèæå âûñêàçûâàíèé, ñîñòîÿùèõ èç îäíîãîèëè áîëåå ïðåäëîæåíèéà) ñôîðìèðóéòå ïîäõîäÿùóþ ñèãíàòóðó, èñïîëüçóÿ êîíñòàíòû äëÿ îáîçíà÷åíèÿ èìåí ñîáñòâåííûõ è ïðåäèêàòíûå ñèìâîëû äëÿ îáîçíà÷åíèÿ ñâîéñòâ è îòíîøåíèé, ôèãóðèðóþùèõ â âûñêàçûâíèè;á) èñïîëüçóÿ âûáðàííóþ ñèãíàòóðó, ñîïîñòàâüòå âûñêàçûâàíèþ çàìêíóòóþ ôîðìóëó ÊËÏ,àäåêâàòíî âûðàæàþùóþ ñìûñë ýòîãî âûñêàçûâàíèÿ.1. Íå âñå òî çîëîòî, ÷òî áëåñòèò.2. Åñëè êàæäûé ëþáèò ñàì ñåáÿ, òî êòî-òî êîãî-òî ëþáèò.Óïðàæíåíèå 1.2.12Ãëàâà 1.ÓÏÐÀÆÍÅÍÈß3.4.5.6.7.8.9.Âàññàë ìîåãî âàññàëà íå ìîé âàññàë.Òîëüêî íå÷åñòíûå âîðû îáêðàäûâàþò äðóã äðóãà.Íåñóäèâøèå íåïîäñóäíû.Ìàëåíüêèå áîãîìîëû åäÿò äðóã äðóãà, à áîëüøèå íåò.Âñå ìîè äðóçüÿ çíàêîìû ñî ìíîé, õîòÿ íåêîòîðûå ìîè çíàêîìûå ñî ìíîé íå äðóæàò.Ìíå íðàâèòñÿ ëîãèêà è âñå òå, êîìó íðàâèòñÿ òî, ÷òî íðàâèòñÿ ìíå.Åñëè çàäà÷à èìååò ðåøåíèå, òî ìàòåìàòèê ìîæåò åå ðåøèòü.
ß - ìàòåìàòèê, íî íå ìîãóðåøèòü ýòîé çàäà÷è. Çíà÷èò, çàäà÷à íåðàçðåøèìà.10. Åñëè Âàñèëèñê ñóùåñòâóåò, òî åãî êòî-òî âèäåë. Âñÿêèé, êòî âèäåë Âàñèëèñêà, ñëåï.Ñëåïîé íè÷åãî íå âèäèò. Çíà÷èò, Âàñèëèñêà íå ñóùåñòâóåò.11. Âû ìîæåòå îáìàíûâàòü âñåõ èíîãäà, âû ìîæåòå îáìàíûâàòü êîãî-òî âñåãäà, íî âû íåìîæåòå îáìàíûâàòü âñåõ âñåãäà.Îáðàòèòå âíèìàíèå íà òî, ÷òî íåêîòîðûå èç ïðèâåäåííûõ âûñêàçûâàíèé ìîãóò ïîíèìàòüñÿíåîäíîçíà÷íî. Êàêèì îáðàçîì ýòà ìíîãîñìûñëåííîñòü ó÷èòûâàåòñÿ ïðè ïîñòðîåíèè ôîðìóëÊËÏ? Ïðîÿâëÿåòñÿ ëè îíà â ïîñòðîåííûõ ôîðìóëàõ? ýòîì ïðèìåðå íàñ áóäóò èíòåðåñîâàòü òîëüêî òàêèå èíòåðïðåòàöèè, âêîòîðûõ àòîìàðíûå ôîðìóëû âûðàæàþò ñëåäóþùèå ñâîéñòâà è îòíîøåíèÿ:• C(x) ¾x êâàäðàò¿;• S(x) ¾x øàð¿;• B(x) ¾x ÷åðíûé ïðåäìåò¿;• W (x) ¾x áåëûé ïðåäìåò¿;• U (x, y) ¾ïðåäìåò x ëåæèò íèæå ïðåäìåòà y ¿.Èñïîëüçóÿ ââåäåííûå ïðåäèêàòû, íàïèøèòå ôîðìóë ëîãèêè ïðåäèêàòîâ äëÿ ñëåäóþùèõ óòâåðæäåíèé:1.
¾Õîòÿ áû îäèí ïðåäìåò, ëåæàùèé íèæå âñåõ ÷åðíûõ êâàäðàòîâ, ÿâëÿåòñÿ øàðîì¿;2. ¾Íåò òàêîãî áåëîãî êâàäðàòà, êîòîðûé ëåæèò ïîä êàêèì-òî ÷åðíûì øàðîì¿;3. ¾Êàêîâ áû íè áûë ÷åðíûé ïðåäìåò, ëèáî îí ÿâëÿåòñÿ øàðîì, ëåæàùèì âûøå âñåõ áåëûõêâàäðàòîâ, ëèáî îí ÿâëÿåòñÿ êâàäðàòîì, ëåæàùèì íèæå êàêîãî-íèáóäü øàðà¿;4. ¾Íèêàêîé ÷åðíûé êâàäðàò è íèêàêîé áåëûé øàð íå ëåæàò äðóã íàä äðóãîì¿;5. ¾Åñëè âñå øàðû ÷åðíûå, òî áåëûõ êâàäðàòîâ íåò¿;6. ¾Âñÿêàÿ ôèãóðà, íå ÿâëÿþùàÿñÿ áåëûì êâàäðàòîì, ëåæàùèì õîòÿ áû ïîä îäíèì øàðîì,èìååò ÷åðíûé öâåò è ëåæèò íàä âñåìè áåëûìè ôèãóðàìè¿.Óïðàæíåíèå 1.3.1.1.Êëàññè÷åñêàÿ ëîãèêà ïðåäèêàòîâ ïåðâîãî ïîðÿäêà: ñèíòàêñèñ è ñåìàíòèêà3Êàêèå èç óòâåðæäåíèé, ñôîðìóëèðîâàííûå â óïðàæíåíèè 1.3, àäåêâàòíîâûðàæàþòñÿ ïðèâåäåííûìè íèæå ôîðìóëàìè:1.
∀x (S(x) & B(x) → ¬∃y (W (y) & S(y)));2. ∃x∀y (S(x) & B(x) → (¬W (y) ∨ ¬S(y)));3. ∀x ∀y (W (x) & C(x) → (¬B(y) ∨ ¬S(y) ∨ ¬U (x, y)));4. ¬∃x (W (x) & C(x) → ∃y(B(y) & S(y) & U (x, y))).Óïðàæíåíèå 1.4.Ðàññìîòðèì ñëåäóþùèå ÷åòûðå ïðåäèêàòà ãåîìåòðèè:• P (x) ôèãóðà x ýòî òî÷êà íà ïëîñêîñòè;• L(x) ôèãóðà x ýòî ïðÿìàÿ íà ïëîñêîñòè;• B(x, y) ôèãóðà x ëåæèò íà ôèãóðå y ;• E(x, y) ôèãóðà x ñîâïàäàåò ñ ôèãóðîé y .Çàïèøèòå çàìêíóòûå ôîðìóëû (ïðåêäëîæåíèÿ) ÊËÏ, âûðàæàþùèå ñëåäóþùèå óòâåðæäåíèÿïëàíèìåòðèè:1.
Âñå ïðÿìûå ïåðåñåêàþòñÿ äðóã ñ äðóãîì.2. Íà êàæäîé ïðÿìîé åñòü òî÷êà, íå ïðèíàäëåæàùàÿ íèêàêîé äðóãîé ïðÿìîé.3. ×åðåç ëþáûå äâå ðàçëè÷íûå òî÷êè ïëîñêîñòè ïðîõîäèò åäèíñòâåííàÿ ïðÿìàÿ.4. Êàêîâû áû íè áûëè ïðÿìàÿ è òî÷êå âíå ýòîé ïðÿìîé, èç âñåõ ïðÿìûõ, ïðîõîäÿùèõ ÷åðåççàäàííóþ òî÷êó, òîëüêî îäíà íå èìååò îáùèõ òî÷åê ñ çàäàííîé ïðÿìîé.Äëÿ êàæäîé ôîðìóëû ïîñòðîéòå äâå ãåîìåòðè÷åñêèå èíòåðïðåòàöèè, â îäíîé èç êîòîðûõäàííàÿ ôîðìóëà âûïîëíÿåòñÿ, à â äðóãîé - íåò.Çàïèøèòå ôîðìóëû ÊËÏ, âûðàæàþùèå ñëåäóþùèå ïðåäèêàòû:1. îòíîøåíèå ïàðàëëåëüíîñòè ïðÿìûõ;2. ñâîéñòâî ÷åòûðåõ òî÷åê îáðàçîâûâàòü ÷åòûðåõóãîëüíèê;Óïðàæíåíèå 1.5.Ïóñòü çàäàíà ñèãíàòóðà σ, ñîñòîÿùàÿ èç äâóõ òðåõìåñòíûõ ïðåäèêàòíûõ ñèìâîëîâ S (3) , P (3) .
Ïóñòü òàêæå çàäàíà èíòåðïðåòàöèÿ I =< N, S̄ (3) , P̄ (3) >. Ïðåäìåòíîéîáëàñòüþ èíòåðïðåòàöèè ÿâëÿåòñÿ ìíîæåñòâî íàòóðàëüíûõ ÷èñåë N = {0, 1, 2, . . . }.  ýòîéèíòåðïðåòàöèè ïðåäèêàòíûå ñèìâîëû âûðàæàþò ñëåäóþùèå îòíîøåíèÿ íà ìíîæåñòâå íàòóðàëüíûõ ÷èñåë:Óïðàæíåíèå 1.6.S̄ (3) (m, n, k) = trueP̄ (3) (m, n, k) = true⇐⇒⇐⇒m + n = k,m × n = k.Çàïèøèòå ôîðìóëó ñ îäíîé ñâîáîäíîé ïåðåìåííîé x, âûïîëíèìóþ â èíòåðïðåòàöèè I òîãäàè òîëüêî òîãäà, êîãäà1. çíà÷åíèåì ïåðåìåííîé x ÿâëÿåòñÿ íàòóðàëüíîå ÷èñëî 0;4Ãëàâà 1.ÓÏÐÀÆÍÅÍÈß2. çíà÷åíèåì ïåðåìåííîé x ÿâëÿåòñÿ íàòóðàëüíîå ÷èñëî 1;3.
çíà÷åíèåì ïåðåìåííîé x ÿâëÿåòñÿ íàòóðàëüíîå ÷èñëî 2;4. çíà÷åíèåì ïåðåìåííîé x ÿâëÿåòñÿ íàòóðàëüíîå ÷èñëî n;5. çíà÷åíèåì ïåðåìåííîé x ÿâëÿåòñÿ ÷åòíîå ÷èñëî;6. çíà÷åíèåì ïåðåìåííîé x ÿâëÿåòñÿ ïðîñòîå ÷èñëî.Çàïèøèòå ôîðìóëó ñ äâóìÿ ñâîáîäíûìè ïåðåìåííûìè x, y, èñòèííóþ â èíòåðïðåòàöèè I òîãäàè òîëüêî òîãäà, êîãäà1. çíà÷åíèÿ ïåðåìåííûõ x è y îäèíàêîâû;2.
çíà÷åíèå ïåðåìåííûé x ìåíüøå çíà÷åíèÿ ïåðåìåííîé y;3. çíà÷åíèå ïåðåìåííûé x êðàòíî çíà÷åíèþ ïåðåìåííîé y.Çàïèøèòå ôîðìóëó ñ òðåìÿ ñâîáîäíûìè ïåðåìåííûìè x, y, èñòèííóþ â èíòåðïðåòàöèè I òîãäà è òîëüêî òîãäà, êîãäà çíà÷åíèå ïåðåìåííîé z ÿâëÿåòñÿ íàèáîëüøèì îáùèì äåëèòåëåìçíàÿåíèé ïåðåìåííûõ x è y.Ïóñòü R äâóõìåñòíûé ïðåäèêàòíûé ñèìâîë, ñîîòâåòñòâóþùèé íåêîòîðîìó îòíîøåíèþ íà ìíîæåñòâå M . Èñïîëüçóÿ â ñëó÷àå íåîáõîäèìîñòè ïðåäèêàò ðàâåíñòâà=, çàïèøèòå ôîðìóëû, îïðåäåëÿþùèå ñëåäóþùèå ñâîéñòâà äâóõìåñòíîãî îòíîøåíèÿ;1. R ÿâëÿåòñÿ ðåôëåêñèâíûì îòíîøåíèåì;2. R ÿâëÿåòñÿ òðàíçèòèâíûì îòíîøåíèåì;3. R ÿâëÿåòñÿ ñèììåòðè÷íûì îòíîøåíèåì;4. R ÿâëÿåòñÿ àíòèñèììåòðè÷íûì îòíîøåíèåì;5.
R ÿâëÿåòñÿ àñèììåòðè÷íûì îòíîøåíèåì;6. R ÿâëÿåòñÿ îòíîøåíèåì ÷àñòè÷íîãî ïîðÿäêà;7. R ÿâëÿåòñÿ îòíîøåíèåì ýêâèâàëåíòíîñòè;8. R ÿâëÿåòñÿ ëèíåéíûì ïîðÿäêîì;9. R ÿâëÿåòñÿ ïëîòíûì ïîðÿäêîì;10. îòíîøåíèå R èìååò ìàêñèìàëüíûé ýëåìåíò.Óïðàæíåíèå 1.7.Ïðåäïîëîæèì, ÷òî çàäàíà ñèãíàòóðà σ, ñîñòîÿùàÿ èçêîíñòàíòû 0, ïðåäñòàâëÿþùåé äåéñòâèòåëüíîå ÷èñëî 0;1-ìåñòíîãî ôóíêöèîíàëüíîãî ñèìâîëà h, ïðåäñòàâëÿþùåãî ôóíêöèþ, âû÷èñëÿþùóþ ìîäóëü äåéñòâèòåëüíîãî ÷èñëà;Óïðàæíåíèå 1.8.1.1.Êëàññè÷åñêàÿ ëîãèêà ïðåäèêàòîâ ïåðâîãî ïîðÿäêà: ñèíòàêñèñ è ñåìàíòèêà52-ìåñòíûõ ôóíêöèîíàëüíûõ ñèìâîëîâ +, −, ×, ïðåäñòàâëÿþùèõ ôóíêöèè, âû÷èñëÿþùèå ñóììó, ðàçíîñòü è ïðîèçâåäåíèå äåéñòâèòåëüíûõ ÷èñåë;1-ìåñòíîãî ïðåäèêàòíîãî ñèìâîëà N , ïðåäñòàâëÿþùåãî ñâîéñòâà ìàòåìàòè÷åñêîãî îáúåêòà áûòü íàòóðàëüíûì ÷èñëîì;1-ìåñòíîãî ïðåäèêàòíîãî ñèìâîëà R, ïðåäñòàâëÿþùåãî ñâîéñòâà ìàòåìàòè÷åñêîãî îáúåêòà áûòü äåéñòâèòåëüíûì ÷èñëîì;1-ìåñòíîãî ïðåäèêàòíîãî ñèìâîëà S , ïðåäñòàâëÿþùåãî ñâîéñòâà ìàòåìàòè÷åñêîãî îáúåêòà áûòü ïîñëåäîâàòåëüíîñòüþ äåéñòâèòåëüíûõ ÷èñåë;2-ìåñòíûõ ïðåäèêàòíûõ ñèìâîëîâ <, >, ïðåäñòàâëÿþùèõ îòíîøåíèÿ ñðàâíåíèÿ äåéñòâèòåëüíûõ è íàòóðàëüíûõ ÷èñåë;ïðåäèêàòà ðàâåíñòâà =;2-ìåñòíîãî ïðåäèêàòíîãî ñèìâîëà L, âûðàæàþùåãî ñëåäóþùåå îòíîøåíèå: ÷èñëî x ÿâëÿåòñÿ ïðåäåëîì ïîñëåäîâàòåëüíîñòè y;2-ìåñòíîãî ïðåäèêàòíîãî ñèìâîëà A, âûðàæàþùåãî ñëåäóþùåå îòíîøåíèå: ÷èñëî x ÿâëÿåòñÿ ïðåäåëüíîé òî÷êîé ïîñëåäîâàòåëüíîñòè y;3-ìåñòíîãî ïðåäèêàòíîãî ñèìâîëà E , âûðàæàþùåãî ñëåäóþùåå îòíîøåíèå: ÷èñëî x ÿâëÿåòñÿ y-ì ýëåìåíòîì ïîñëåäîâàòåëüíîñòè z.Èñïîëüçóÿ êîíñòàíòíûå, ôóíêöèîíàëüíûå è ïðåäèêàòíûå ñèìâîëû ñèãíàòóðû σ, ïîñòðîéòåçàìêíóòûå ôîðìóëû ëîãèêè ïðåäèêàòîâ, âûðàæàþùóþ ñëåäóþùèå óòâåðæäåíèÿ ìàòåìàòè÷åñêîãî àíàëèçà.1.
Âñÿêàÿ ñõîäÿùàÿñÿ ïîñëåäîâàòåëüíîñòü äåéñòâèòåëüíûõ ÷èñåë îãðàíè÷åíà.2. Íèêàêàÿ ïîñëåäîâàòåëüíîñòü íåíóëåâûõ äåéñòâèòåëüíûõ ÷èñåë íå èìååò ïîëîæèòåëüíûõïðåäåëüíûõ òî÷åê.3. Ó ëþáîé ïîñëåäîâàòåëüíîñòè äåéñòâèòåëüíûõ ÷èñåë, ñîäåðæàùåé îòðèöàòåëüíîå ÷èñëî,åñòü õîòÿ áû îäíà íåïîëîæèòåëüíàÿ ïðåäåëüíàÿ òî÷êà.4. Êàêîâà áû íè áûëà ïîñëåäîâàòåëüíîñòü äåéñòâèòåëüíûõ ÷èñåë, íàéäåòñÿ îòðåçîê, ñîäåðæàùèé âñå åå ïðåäåëüíûå òî÷êè5.
Äëÿ ëþáîãî îòðåçêà [a,b] äåéñòâèòåëüíûõ ÷èñåë íåò íè îäíîé òàêîé ïîñëåäîâàòåëüíîñòè, ñîñòîÿùåé èç äåéñòâèòåëüíûõ ÷èñåë ýòîãî îòðåçêà, ó êîòîðîé áûëà áû õîòü îäíàïðåäåëüíàÿ òî÷êà âíå ýòîãî îòðåçêà.6. Ïðåäåë ñóììû ëþáûõ äâóõ ñõîäÿùèõñÿ ïîñëåäîâàòåëüíîñòåé äåéñòâèòåëüíûõ ÷èñåë ðàâåí ñóììå ïðåäåëîâ ýòèõ ïîñëåäîâàòåëüíîñòåé.7.
Êàêîâû áû íè áûëè äâå ïîñëåäîâàòåëüíîñòè äåéñòâèòåëüíûõ ÷èñåë, åñëè îäíà èç íèõñõîäèòñÿ ê íóëþ, à äðóãàÿ îãðàíè÷åíà, òî è ïðîèçâåäåíèå ýòèõ ïîñëåäîâàòåëüíîñòåéñõîäèòñÿ ê íóëþ.8. Íåò íè îäíîé òàêîé ñõîäÿùåéñÿ ïîñëåäîâàòåëüíîñòè, êîòîðóþ áûëî áû íåëüçÿ ïðåäñòàâèòü â âèäå ñóììû äâóõ ñõîäÿùèõñÿ ïîñëåäîâàòåëüíîñòåé.6Ãëàâà 1.ÓÏÐÀÆÍÅÍÈß9. Åñëè ïðîèçâîëüíàÿ îãðàíè÷åííàÿ ïîñëåäîâàòåëüíîñòü èìååò åäèíñòâåííóþ ïðåäåëüíóþòî÷êó, òî ýòà ïîñëåäîâàòåëüíîñòü ÿâëÿåòñÿ ñõîäÿùåéñÿ.10.
Êàêîâ áû íè áûë îòðåçîê [a, b] äåéñòâèòåëüíûõ ÷èñåë, åñëè ïî÷òè âñå ýëåìåíòû ïðîèçâîëüíîé ïîñëåäîâàòåëüíîñòè äåéñòâèòåëüíûõ ÷èñåë ëåæàò âíå ýòîãî îòðåçêà, òî è âñåïðåäåëüíûå òî÷êè ýòîé ïîñëåäîâàòåëüíîñòè òàêæå ëåæàò âíå ýòîãî îòðåçêà.11. Êàêîâà áû íè áûëà ïîñëåäîâàòåëüíîñòü äåéñòâèòåëüíûõ ÷èñåë è îòðåçîê [a, b] äåéñòâèòåëüíûõ ÷èñåë, åñëè áåñêîíå÷íî ìíîãî ýëåìåíòîâ ýòîé ïîñëåäîâàòåëüíîñòè ñîäåðæèòñÿâ äàííîì îòðåçêå, òî õîòÿ áû îäíà ïðåäåëüíàÿ òî÷êà äàííîé ïîñëåäîâàòåëüíîñòè òàêæåñîäåðæèòñÿ â ýòîì îòðåçêå.12. Åñëè íåêîòîðîå äåéñòâèòåëüíîå ÷èñëî âñòðå÷àåòñÿ áåñêîíå÷íî ÷àñòî â ïðîèçâîëüíîé ïîñëåäîâàòåëüíîñòè äåéñòâèòåëüíûõ ÷èñåë, òî äàííîå ÷èñëî ÿâëÿåòñÿ ïðåäåëüíîé òî÷êîéýòîé ïîñëåäîâàòåëüíîñòè.1.2Âûïîëíèìûå è îáùåçíà÷èìûå ôîðìóëûÂûÿñíèòå, êàêèå èç ïðèâåäåííûõ íèæå ôîðìóë ÿâëÿþòñÿ âûïîëíèìûìè,êàêèå ÿâëÿþòñÿ íåâûïîëíèìûìè, à êàêèå îáùåçíà÷èìûìè.1.