Исчисление высказываний. Понятие формального исчисления. Определение исчисления высказываний

Ãëàâà III. Èñ÷èñëåíèå âûñêàçûâàíèé 1 Ãëàâà III. Èñ÷èñëåíèå âûñêàçûâàíèé Ÿ1. Ïîíÿòèå ôîðìàëüíîãî èñ÷èñëåíèÿ Áóäåì ãîâîðèòü, ÷òî çàäàíî èñ÷èñëåíèå I , åñëè âûïîëíÿþòñÿ ñëåäóþùèå óñëîâèÿ: I. Èìååòñÿ íåêîòîðîå íåïóñòîå ìíîæåñòâî ñèìâîëîâ A, êîòîðîå ìû áóäåì íàçûâàòü àëôàâèòîì èñ÷èñëåíèÿ I . Êîíå÷íûå ïîñëåäîâàòåëüíîñòè ñèìâîëîâ àëôàâèòà íàçûâàþòñÿ ñëîâàìè èëè âûðàæåíèÿìè èñ÷èñëåíèÿ I . Îáîçíà÷èì ÷åðåç S ìíîæåñòâî âñåõ ñëîâ èñ÷èñëåíèÿ I . II. Îïðåäåëåíî ìíîæåñòâî F ⊆ S , ýëåìåíòû êîòîðîãî áóäåì íàçûâàòü ôîðìóëàìè èñ÷èñëåíèÿ I . III. Îïðåäåëåíî ìíîæåñòâî Ax ⊆ F , ýëåìåíòû êîòîðîãî áóäåì íàçûâàòü àêñèîìàìè èñ÷èñëåíèÿ I . IV. Îïðåäåëåíî ìíîæåñòâî îòíîøåíèé ìåæäó ôîðìóëàìè R, ýëåìåíòû êîòîðîãî áóäåì íàçûâàòü ïðàâèëàìè âûâîäà èñ÷èñëåíèÿ I . Íàïðèìåð, ïóñòü A = {a, b}; ôîðìóëàìè ÿâëÿþòñÿ âñå ñëîâà àëôàâèòà A, ñîñòîÿùèå èç áîëåå ÷åì îäíîãî ñèìâîëà; àêñèîìàìè áóäóò ôîðìóëû, íà÷èíàþùèåñÿ ñ ñèìâîëà a è ñîñòîÿùèå èç áîëåå ÷åì äâóõ ñèìâîëîâ; ïðàâèëî âûâîäà ρ îïðåäåëèì ñëåäóþùèì îáðàçîì: Îïðåäåëåíèå. hΦ1 , Φ2 , Φ3 i ∈ ρ ⇐⇒ Φ3 Φ1 Φ2 , ãäå Φ1, Φ2, Φ3 ∈ F , òî åñòü ôîðìóëà Φ3 ïîëó÷àåòñÿ èç ôîðìóë Φ1 è Φ2 ïðèïèñûâàíèåì â êîíåö Φ1 ôîðìóëû Φ2. Ïîñëåäîâàòåëüíîñòü ôîðìóë Ψ1, . . . , Ψm ∈ F èñ÷èñëåíèÿ I íàçûâàåòñÿ âûâîäîì ôîðìóëû Φ èç ìíîæåñòâà ôîðìóë {Φ1, . . . , Φn} èñ÷èñëåíèÿ I , åñëè Ψm Φ è äëÿ ëþáîãî i 6 m âûïîëíÿåòñÿ îäíî èç ñëåäóþùèõ óñëîâèé: Îïðåäåëåíèå. 2 Êîíñïåêò ëåêöèé ïî ìàòåìàòè÷åñêîé ëîãèêå. Åôðåìîâ Å.Ë. 1) Ψi ∈ {Φ1, . . . , Φn}, 2) Ψi ∈ Ax, 3) Ψi ïîëó÷àåòñÿ èç Ψ1, . . . , Ψi−1 ñ ïîìîùüþ ïðàâèëà âûâîäà. Åñëè äëÿ ôîðìóëû Φ èñ÷èñëåíèÿ I ñóùåñòâóåò âûâîä èç ìíîæåñòâà ôîðìóë {Φ1, . . . , Φn} èñ÷èñëåíèÿ I , òî Φ íàçûâàåòñÿ âûâîäèìîé èç {Φ1 , . . . , Φn } â I . Ôîðìóëû Φ1 , . . . , Φn ïðè ýòîì íàçûâàþòñÿ ãèïîòåçàìè. Òîò ôàêò, ÷òî Φ âûâîäèìà èç ìíîæåñòâà {Φ1 , . . . , Φn }, áóäåì çàïèñûâàòü ñëåäóþùèì îáðàçîì: Φ1, . . . , Φn `I Φ.  ïðèâåä¼ííîì âûøå ïðèìåðå ôîðìóëà baaba âûâîäèìà èç ìíîæåñòâà {ba}: Ψ1 ba, Ψ2 aba, Ψ3 baaba. Âîïðîñ î òîì, ÿâëÿåòñÿ ëè êàêàÿ-òî ôîðìóëà âûâîäèìîé èç ìíîæåñòâà ôîðìóë, ÿâëÿåòñÿ öåíòðàëüíûì âîïðîñîì ëþáîãî èñ÷èñëåíèÿ. Èìåííî ýòîìó âîïðîñó áóäóò ïîñâÿùåíû íàøè ïðàêòè÷åñêèå çàíÿòèÿ ïî ýòîé òåìå. Î÷åâèäíî, â ñëó÷àå, êîãäà âûâîä ñîñòîèò èç áîëüøîãî êîëè÷åñòâà ôîðìóë, ïîíÿòü, îòêóäà êàêàÿ ôîðìóëà ïîëó÷èëàñü, íå âñåãäà ïðîñòî. Äëÿ ýòîãî áóäåì çàïèñûâàòü âûâîä ôîðìóëû, ðóêîâîäñòâóÿñü ïðàâèëàìè: 1. Íå áóäåì ¾íàçûâàòü¿ ôîðìóëû è ïèñàòü Ψ1 . . . Âìåñòî ýòîãî áóäåì çàïèñûâàòü òîëüêî ôîðìóëû â ïðîíóìåðîâàííûé ñïèñîê. 2. Ñðàçó ïîñëå íîìåðà ôîðìóëû áóäåì çàïèñûâàòü â êâàäðàòíûõ ñêîáêàõ ïðèìå÷àíèå, óêàçûâàþùåå íà ñïîñîá ïîëó÷åíèÿ ýòîé ôîðìóëû. Äëÿ çàïèñè ïðèìå÷àíèé áóäåì èñïîëüçîâàòü ñëåäóþùèå ñîêðàùåíèÿ:  ãèï  ãèïîòåçà,  An  àêñèîìà ñ íîìåðîì n,  ñâ. n (íîìåðà ôîðìóë)  ñâîéñòâî (ñôîðìóëèðîâàííîå íàìè â ïîñëåäóþùèõ ïàðàãðàôàõ óòâåðæäåíèå) ñ íîìåðîì n, êîòîðîå ïðèìåíèëè ê ôîðìóëàì ñ íîìåðàìè èç ( ),  ÏÂn (íîìåðà ôîðìóë)  ïðàâèëî âûâîäà ñ íîìåðîì n, êîòîðîå ïðèìåíèëè ê ôîðìóëàì ñ íîìåðàìè èç ( ). Îïðåäåëåíèå. Ãëàâà III. Èñ÷èñëåíèå âûñêàçûâàíèé 3 3.  ñëó÷àå çàìåí êàêèõ-ëèáî ýëåìåíòîâ àêñèîì è ñâîéñòâ áóäåì çàïèñûâàòü âåðõíèì èíäåêñîì çàìåíÿåìûé ýëåìåíò, íèæå ñîîòâåòñòâóþùèì íèæíèì èíäåêñîì  ýëåìåíò, íà êîòîðûé çàìåíÿåì. Ïðîäåìîíñòðèðóåì óêàçàííûå çàìå÷àíèÿ íà ðàññìîòðåííîì âûøå ïðèìåðå. Äëÿ ýòîãî îïèøåì àêñèîìû è ïðàâèëà âûâîäà áîëåå ñòðîãî. A1 aΦ äëÿ ëþáîé ôîðìóëû Φ èñ÷èñëåíèÿ I . Ôàêòè÷åñêè çäåñü ìû óêàçàëè íå ñàìó àêñèîìó, à òîëüêî ñõåìó. Ïðè ïîäñòàíîâêå âìåñòî Φ ëþáîé ôîðìóëû èñ÷èñëåíèÿ I ìû ïîëó÷èì àêñèîìó èñ÷èñëåíèÿ I . ÏÂ1: Φ1, Φ2 `I Φ1Φ2. Çàïèøåì âûâîä ôîðìóëû baaba èç ìíîæåñòâà {ba}, ðóêîâîäñòâóÿñü íàøèìè ïðàâèëàìè: 1. [ãèï] ba. 2. [A1] baΦ aba. 3. [ÏÂ1 (1, 2)] baaba. Ôîðìóëà èñ÷èñëåíèÿ I íàçûâàåòñÿ äîêàçóåìîé â I , èëè òåîðåìîé I , åñëè îíà âûâîäèìà èç ïóñòîãî ìíîæåñòâà ôîðìóë. Îïðåäåëåíèå. Ÿ2. Îïðåäåëåíèå èñ÷èñëåíèÿ âûñêàçûâàíèé I. Àëôàâèò ÈÂ: 1) ïðîïèñíûå áóêâû ëàòèíñêîãî àëôàâèòà (âîçìîæíî ñ èíäåêñàìè), êîòîðûå áóäåì íàçûâàòü ïðîïîçèöèîíàëüíûìè ïåðåìåííûìè : A, B, C, . . ., A1 , A2 , . . ., 2) ëîãè÷åñêèå ñâÿçêè : q, ∨, ∧, →, 3) ( , ). II. Ôîðìóëû È îïðåäåëèì èíäóêòèâíûì ñïîñîáîì: 1) ïðîïîçèöèîíàëüíàÿ ïåðåìåííàÿ  ôîðìóëà ÈÂ, 2) åñëè Φ, Ψ  ôîðìóëû ÈÂ, òî (Φ ∧ Ψ), (Φ ∨ Ψ), (Φ → Ψ), qΦ  ôîðìóëû ÈÂ. 4 Êîíñïåêò ëåêöèé ïî ìàòåìàòè÷åñêîé ëîãèêå. Åôðåìîâ Å.Ë. Ôîðìóëû èñ÷èñëåíèÿ âûñêàçûâàíèé ÿâëÿþòñÿ âñåãî ëèøü ïîñëåäîâàòåëüíîñòÿìè ñèìâîëîâ. Îíè íå íàäåëåíû êàêèì-ëèáî ñìûñëîì, íå ïðèíèìàþò íèêàêèõ çíà÷åíèé. Ôîðìóëû È íå åñòü ôîðìóëû ÀÂ, íåñìîòðÿ íà èõ î÷åâèäíóþ ñõîæåñòü. Òåì íå ìåíåå, ÷òîáû íå ïóòàòüñÿ â ñêîáêàõ, áóäåì îïóñêàòü ñêîáêè òàê, êàê ìû äåëàëè ýòî â ôîðìóëàõ ÀÂ. Íàïðèìåð, ôîðìóëó ((A ∧ B) → C) áóäåì çàïèñûâàòü êàê A ∧ B → C . III. Äëÿ ëþáûõ ôîðìóë È Φ, Ψ, Θ ñëåäóþùèå ôîðìóëû áóäåì ñ÷èòàòü àêñèîìàìè È : A1. Φ → (Ψ → Φ). A2. (Φ → Ψ) → ((Φ → (Ψ → Θ)) → (Φ → Θ)). A3. Φ ∧ Ψ → Φ. A4. Φ ∧ Ψ → Ψ. A5. (Φ → Ψ) → ((Φ → Θ) → (Φ → Ψ ∧ Θ)). A6. Φ → Φ ∨ Ψ. A7. Ψ → Φ ∨ Ψ. A8. (Φ → Θ) → ((Ψ → Θ) → (Φ ∨ Ψ → Θ)). A9. (Φ → Ψ) → ((Φ →qΨ) →qΦ). A10. qqΦ → Φ. IV. Åäèíñòâåííûì ïðàâèëîì âûâîäà È ÿâëÿåòñÿ ïðàâèëî çàêëþ÷åíèÿ : Φ, Φ → Ψ `È Ψ. Ïðàâèëî çàêëþ÷åíèÿ áîëüøå èçâåñòíî ïîä åãî ëàòèíñêèì íàçâàíèåì  modus ponens, â ñâÿçè ñ ÷åì â âûâîäå âìåñòî Ï áóäåì ïèñàòü MP. Åñòåñòâåííûìè êàæóòñÿ âîïðîñû:  Ïî÷åìó àêñèîìû è ïðàâèëà âûâîäà äëÿ È âûáðàíû èìåííî òàêèì îáðàçîì?  ×òî áóäåò, åñëè óáðàòü îäíó àêñèîìó?  Äëÿ êàæäîé ëè ôîðìóëû È ìîæíî îäíîçíà÷íî ñêàçàòü, äîêàçóåìà îíà èëè íåò? Ìû âåðí¼ìñÿ ê ýòèì âîïðîñàì ÷óòü ïîçæå. Îòìåòèì òîëüêî, ÷òî åñòü íåñêîëüêî îïðåäåëåíèé èñ÷èñëåíèÿ âûñêàçûâàíèé. Âñå ýòè îïðåäåëåíèÿ Ãëàâà III. Èñ÷èñëåíèå âûñêàçûâàíèé 5 îòëè÷àþòñÿ íàáîðîì àêñèîì. Ôîðìàëüíî îíè ðàçíûå, íî ñîäåðæàòåëüíî îíè î÷åíü ïîõîæè äðóã íà äðóãà. Âñþäó äàëüøå, åñëè íå îãîâîðåíî ïðîòèâíîå, ïîä ôîðìóëàìè áóäåì ïîíèìàòü ôîðìóëû èñ÷èñëåíèÿ âûñêàçûâàíèé. Òàêæå ñèìâîëàìè Φ, Ψ, Θ (âîçìîæíî ñ èíäåêñàìè) áóäåì îáîçíà÷àòü ôîðìóëû èñ÷èñëåíèÿ âûñêàçûâàíèé. Âìåñòî ñèìâîëà `È áóäåì ïèñàòü ïðîñòî `. ` Φ → Φ. Ñâîéñòâî 1. Äîêàçàòåëüñòâî. Ψ Θ (Φ → (Φ → Φ)) → ((Φ → ((Φ → Φ) → Φ)) → (Φ → Φ)). 1. [A2] Φ→Φ Φ 2. [A1] ΨΦ Φ → (Φ → Φ). 3. [MP (2, 1)] (Φ → ((Φ → Φ) → Φ)) → (Φ → Φ). Ψ 4. [A1] Φ→Φ Φ → ((Φ → Φ) → Φ). 5. [MP (4, 3)] Φ → Φ.  Φ, Ψ ` Φ ∧ Ψ. Ñâîéñòâî 2. Äîêàçàòåëüñòâî. 1. [ãèï] Φ. 2. [ãèï] Ψ. 3. [A5] ΨΦ ΨΘ (Φ → Φ) → ((Φ → Ψ) → (Φ → Φ ∧ Ψ)). 4. [ñâ. 1] Φ → Φ. 5. [MP (4, 3)] (Φ → Ψ) → (Φ → Φ ∧ Ψ). 6. [A1] ΨΦ ΨΦ Ψ → (Φ → Ψ). 7. [MP (2, 6)] Φ → Ψ. 8. [MP (7, 5)] Φ → Φ ∧ Ψ. 9. [MP (1, 8)] Φ ∧ Ψ.   äîêàçàòåëüñòâå ñâîéñòâà 2 ïîñòðîåí íå ñîâñåì âûâîä ôîðìóëû Φ∧Ψ. ×åòâ¼ðòàÿ ôîðìóëà â ñïèñêå  óæå èçâåñòíàÿ íàì äîêàçóåìàÿ ôîðìóëà èç ñâîéñòâà 1. Ìû ìîãëè áû âìåñòî ýòîé ôîðìóëû çàïèñàòü âñå 5 ôîðìóë âûâîäà, ïðèâåä¼ííîãî â äîêàçàòåëüñòâå ñâîéñòâà 1, òåì ñàìûì óäëèíèâ íàø âûâîä. Ïðè ðåøåíèè ïðàêòè÷åñêèõ çàäà÷ âûâîä ìîæåò ñîñòîÿòü èç îãðîìíîãî êîëè÷åñòâà ôîðìóë. Òàêîå óïðîùåíèå (èñïîëüçîâàíèå óæå èçâåñòíûõ 6 Êîíñïåêò ëåêöèé ïî ìàòåìàòè÷åñêîé ëîãèêå. Åôðåìîâ Å.Ë. íàì âûâîäèìûõ ôîðìóë) ïîçâîëÿåò ñîêðàòèòü ýòî êîëè÷åñòâî. Òàêîé ñïèñîê ôîðìóë íàçûâàåòñÿ êâàçèâûâîäîì. Ïîñëåäîâàòåëüíîñòü ôîðìóë Ψ1, . . . , Ψm ∈ F èñ÷èñëåíèÿ I íàçûâàåòñÿ êâàçèâûâîäîì ôîðìóëû Φ èç ôîðìóë {Φ1, . . . , Φn} èñ÷èñëåíèÿ I , åñëè Ψm Φ è äëÿ ëþáîãî i 6 m âûïîëíÿåòñÿ îäíî èç ñëåäóþùèõ óñëîâèé: 1) Ψi ∈ {Φ1, . . . , Φn}, 2) Ψi ∈ Ax, 3) Ψi âûâîäèìà èç Ψ1, . . . , Ψi−1. Êàê Âû íàâåðíÿêà çàìåòèëè, ëþáîå äîêàçàòåëüñòâî ìû íà÷èíàëè ñòðîèòü ñ òîãî, ÷òî èñêàëè àêñèîìó, êîòîðàÿ áû (ïðè íóæíûõ çàìåíàõ) çàêàí÷èâàëàñü íóæíîé ôîðìóëîé, à ïîñëå ýòîãî ïî îòäåëüíîñòè ïîëó÷àëè ïîñûëêè è óáèðàëè èõ ñ ïîìîùüþ modus ponens. Çà÷àñòóþ ýòà òàêòèêà ýôôåêòèâíà ïðè ðåøåíèè ïîäîáíûõ çàäà÷. Òàêæå ðåêîìåíäóåòñÿ ñíà÷àëà â âûâîä çàïèñàòü âñå èìåþùèåñÿ ãèïîòåçû. Îïðåäåëåíèå.