離散數(shù)學(xué)（古典數(shù)理邏輯）

命題邏輯

命題與公式

1.命題

一句有真假意義的話（陳述句），記作P。不能是悖論、祈使句、疑問(wèn)句、感嘆句，真值唯一
真命題：真值為真的命題
假命題：真值為假的命題
（當(dāng)前真值可能不確定，但不代表不唯一，只是暫時(shí)不確定是真命題還是假命題。例如“2050年元旦下大雪”，是一個(gè)命題）
條件不等式不能成為一個(gè)命題，恒成立不等式是一個(gè)命題。（\(x>1\) 不是命題，\(x^2+1>0\) 是命題）

命題的否定：記以 \(\lnot\)P

2.析取

P\(\lor\)Q 讀作“P或Q” 真值規(guī)定：P\(\lor\)Q是真的當(dāng)且僅當(dāng)P，Q中至少有一個(gè)是真的。注意可兼或。

3.合取

P\(\land\)Q 讀作“P且Q” 真值規(guī)定：P\(\land\)Q是真的當(dāng)且僅當(dāng)P和Q都是真的。

4.蘊(yùn)涵

P\(\rightarrow\)Q 讀作“P蘊(yùn)涵Q” 真值規(guī)定： P\(\rightarrow\)Q是假的當(dāng)且僅當(dāng)P是真的而Q是假的。

5.等價(jià)

P\(\leftrightarrow\)Q 讀作“P等價(jià)Q” 真值規(guī)定：P\(\leftrightarrow\)Q是真的當(dāng)且僅當(dāng)P，Q或者都是真的，或者都是假的。

例子：

除非他以書面或口頭的方式正式通知我，否則我不參加明天的會(huì)議。

令P：他書面通知我； Q：他口頭通知我； R：我參加明天的會(huì)議。

于是，上述語(yǔ)句可表示為(P\(\lor\)Q)\(\leftrightarrow\)R。

6.命題符號(hào)稱為原子。

例如，Q，S，…等都是原子。

7.命題公式

命題邏輯中的公式，是如下定義的一個(gè)符號(hào)串：
(1) 原子是公式；
(2) 0、1是公式；
(3) 若G，H是公式，則(\(\lnot\)G)，(G\(\lor\)H)， (G\(\land\)H)，(G\(\rightarrow\)H)，(G\(\leftrightarrow\)H)是公式；
(4) 所有公式都是有限次使用(1)，(2)，(3)得到的符號(hào)串。

規(guī)定：

公式(\(\lnot\) G)的括號(hào)可以省略，寫成\(\lnot\)G。
整個(gè)公式的最外層括號(hào)可以省略。
五種邏輯聯(lián)結(jié)詞的優(yōu)先級(jí)按如下次序遞增：\(\leftrightarrow \rightarrow \land \lor \lnot\)

8.解釋

第一種寫法：I1：\(\frac{P\,\, Q\,\,}{1 0}\)

第二種寫法：{P，\(\lnot\) Q}

第三種寫法：語(yǔ)言描述，P取1，Q取0

錯(cuò)誤寫法：P=1，Q=0

9.真值表

10.恒真、恒假、可滿足

公式G稱為恒真的(或有效的)，如果G在它的所有解釋下都是真的；
公式G稱為恒假的(或不可滿足的)，如果G在它的所有解釋下都是假的；
公式G稱為可滿足的，如果它不是恒假的

如果公式G在解釋I下是真的，則稱I滿足G；如果G在解釋I下是假的，則稱I弄假G

命題公式的等價(jià)關(guān)系和蘊(yùn)涵關(guān)系

1.公式的等價(jià)

公式G，H等價(jià) iff 公式G\(\leftrightarrow\)H恒真。
公式間的等價(jià)關(guān)系有自反性、對(duì)稱性、傳遞性。

基本等價(jià)式

證明命題公式恒真或恒假的兩個(gè)方法

方法一. 真值表方法。

方法二. 以基本等價(jià)式為基礎(chǔ)，通過(guò)反復(fù)對(duì)一個(gè)公式的等價(jià)代換，使之最后轉(zhuǎn)化為一個(gè)恒真式或恒假式，從而實(shí)現(xiàn)公式恒真或恒假的證明。

2.完備集

設(shè)Q是邏輯運(yùn)算符號(hào)集合，若所有邏輯運(yùn)算都能由Q中元素表示出來(lái)，而Q的任意真子集無(wú)此性質(zhì)，則稱Q是一個(gè)完備集。

核心步驟：取兩次反

3.與非式

命題 “P與Q的否定”稱為P與Q的與非式，記作P\(\uparrow\)Q。

真值規(guī)定:P\(\uparrow\)Q為真 iff P,Q不同時(shí)為真。

備注：\(\uparrow\)是一個(gè)完備集

4.或非式

命題 “P或Q的否定”稱為P與Q的或非式，記作P\(\downarrow\)Q

真值規(guī)定：P\(\downarrow\)Q為真 iff P，Q同時(shí)為假。

備注：\(\downarrow\)是一個(gè)完備集

5.公式的蘊(yùn)涵

定理：設(shè)G，H是兩個(gè)公式。稱H是G的邏輯結(jié)果(或稱G蘊(yùn)涵H)，當(dāng)且僅當(dāng)對(duì)G，H的任意解釋I，如果I滿足G，則I也滿足H，記作G\(\Rightarrow\)H。

是一種部分序關(guān)系（自反、反對(duì)稱、傳遞）

G\(\Rightarrow\)H當(dāng)且僅當(dāng)G\(\rightarrow\)H是恒真的

6.共同蘊(yùn)含

定理：設(shè)G1, …, Gn，H是公式。稱H是G1, …,Gn的邏輯結(jié)果(或稱G1, …, Gn共同蘊(yùn)涵H)，當(dāng)且僅當(dāng) (G1\(\land\) …\(\land\) Gn) \(\Rightarrow\) H。
顯然，公式H是G1, …, Gn的邏輯結(jié)果 iff
公式((G1\(\land\) …\(\land\) Gn)\(\rightarrow\)H)是恒真的。

例如，P，P\(\rightarrow\)Q共同蘊(yùn)涵Q。

如果H1, …, Hm，P共同蘊(yùn)涵公式Q，則H1, …, Hm共同蘊(yùn)涵公式P\(\rightarrow\)Q。

7.演繹

定理：設(shè)S是公式集合，G是一個(gè)公式。于是，從S演繹出G的充要條件是G是S的邏輯結(jié)果。.

定理：設(shè)S是前提公式集合，G，H是兩個(gè)公式。如果從S∪{G}可演繹出H，則從S可演繹出G\(\rightarrow\)H。

基本蘊(yùn)含式：

8.公式間蘊(yùn)涵的證明方法

給出兩個(gè)公式G，H，證明G蘊(yùn)涵H。
（1）真值表法；
（2）證G\(\rightarrow\)H是恒真公式；
（3）利用一些基本等價(jià)式及蘊(yùn)涵式進(jìn)行推導(dǎo)；
（4）任取解釋I，若I滿足G，往證I滿足H；
（5）反證法，設(shè)結(jié)論假，往證前提假 (即證明\(\lnot\)H \(\Rightarrow\) \(\lnot\)G)

9.形式演繹法

根據(jù)一些基本等價(jià)式和基本蘊(yùn)涵式，從S出發(fā)，演繹出G，在演繹過(guò)程中遵循以下三條規(guī)則：
規(guī)則1. 可隨便使用前提。 (根據(jù)演繹定義)
規(guī)則2. 可隨便使用前面演繹出的某些公
式的邏輯結(jié)果。 (根據(jù)演繹的定義)
規(guī)則3. 如果需要演繹出的公式是P\(\rightarrow\)Q的形式，可將P做為附加前提使用，而力圖去演繹出Q。

范式

1、析取范式和合取范式

原子或原子的否定稱為文字(literal)

有限個(gè)文字的析取式稱為一個(gè)子句；

有限個(gè)文字的合取式稱為一個(gè)短語(yǔ)。

特別，一個(gè)文字既可稱為是一個(gè)子句，也可稱為是一個(gè)短語(yǔ)。

有限個(gè)短語(yǔ)的析取式稱為析取范式；

有限個(gè)子句的合取式稱為合取范式。

特別，一個(gè)文字既可稱為是一個(gè)合取范式，也可稱為是一個(gè)析取范式。一個(gè)子句，一個(gè)短語(yǔ)既可看做是合取范式，也可看做是析取范式。

定理3.1.4 ：對(duì)于任意命題公式，都存在等價(jià)于它的析取范式和合取范式。

主析取范式：P、Q.....原始值為1

極小項(xiàng)：對(duì)于n個(gè)原子P1,…,Pn而言，其不同的解釋共有\(2^n\)個(gè)，對(duì)于P1,…,Pn的任一個(gè)極小項(xiàng)m，\(2^n\)個(gè)解釋中，有且只有一個(gè)解釋使m取1值。

主析取范式：設(shè)命題公式G中所有不同原子為P1,…,Pn，如果G的某個(gè)析取范式G’中的每一個(gè)短語(yǔ)，都是關(guān)于P1,…,Pn的一個(gè)極小項(xiàng)，則稱G’為G的主析取范式。

定理：在真值表中，使得公式為真的解釋所對(duì)應(yīng)的極小項(xiàng)的析取即為此公式的主析取范式。

用范式判定公式的恒真恒假性：

引理3.1.2：短語(yǔ)是恒假的當(dāng)且僅當(dāng)至少有一個(gè)原子及其否定（也稱互補(bǔ)對(duì)）同時(shí)在此短語(yǔ)中出現(xiàn)。

定理3.1.8：命題公式G是恒假的當(dāng)且僅當(dāng)在等價(jià)于它的析取范式中，每個(gè)短語(yǔ)均至少包含一個(gè)原子及其否定。

判定公式是否恒真的其它方法：

1.把公式化成主析取范式，公式恒假時(shí)，主析取范式?jīng)]有極小項(xiàng)；公式恒真時(shí)，主析取范式有全部極小項(xiàng)。

一種判定算法對(duì)任給要判定的命題公式G，設(shè)其中有原子P1,P2,…,Pn，令P1取1值，求G的真值，或?yàn)?，或?yàn)?，或成為新公式G1且其中只有原子P2,…, Pn，再令P2取0值，求G真值.如此繼續(xù)，到最終只含0或1為止，若最終結(jié)果全為1，則公式G恒真，若最終結(jié)果全為0，則公式G恒假，若最終結(jié)果有1，有0，則是可滿足的。

主合取范式：P、Q.....原始值為0

極大項(xiàng)

極小項(xiàng)與極大項(xiàng)性質(zhì)：

求主合取范式和主析取范式的方法：

方法一. 真值表法。主析取范式恰好是使得公式為真的解釋所對(duì)應(yīng)的極小項(xiàng)的析取組成，主合取范式恰好是使得公式為假的解釋所對(duì)應(yīng)的極大項(xiàng)的合取組成。

方法二. 公式推導(dǎo)法。

主合取范式與主析取范式的應(yīng)用：

1.利用主合取范式與主析取范式可求解判定問(wèn)題

2.證明等價(jià)式成立

若二者主范式相同，則給定的兩公式是等價(jià)的，否則，給定的兩公式不等價(jià)。

謂詞邏輯

謂詞邏輯的基本概念

定義3.2.1 ：可以獨(dú)立存在的物體稱為個(gè)體。(它可以是抽象的，也可以是具體的。)

定義3.2.2 ：設(shè)D是非空個(gè)體名稱集合，定義在\(\mathrm{D}^{\mathrm{n}}\)上取值于{1，0}上的n元函數(shù)，稱為n元命題函數(shù)或n元謂詞。其中表\(\mathrm{D}^{\mathrm{n}}\)示集合D的n次笛卡爾乘積。

定義3.2.3 ：語(yǔ)句 “對(duì)任意x”稱為全稱量詞，記以\(\forall\)x；語(yǔ)句 “存在一個(gè)x”稱為存在量詞，記以\(\exists\)x。

量詞的語(yǔ)義規(guī)定：

量詞的約束范圍

定義3.2.4 ：在一個(gè)由謂詞，量詞，邏輯聯(lián)結(jié)詞，括號(hào)組成的有意義的符號(hào)串（實(shí)際是指下一節(jié)將嚴(yán)格定義的公式）中，稱變量的出現(xiàn)是約束的，當(dāng)且僅當(dāng)它出現(xiàn)在使用這個(gè)變量的量詞范圍之內(nèi)；稱變量的出現(xiàn)是自由的，當(dāng)且僅當(dāng)這個(gè)出現(xiàn)不是約束的。

約束變量的改名規(guī)則：在由謂詞，量詞，邏輯聯(lián)結(jié)詞，括號(hào)組成的有意義的符號(hào)串（實(shí)際是下節(jié)定義的公式）中，可將其中出現(xiàn)的約束變量改為另一個(gè)約束變量，這種改名必須在量詞作用區(qū)域內(nèi)各處以及該量詞符號(hào)中實(shí)行，并且改成的新約束變量要有別于改名區(qū)域中的所有其它變量。
顯然改名規(guī)則不改變?cè)?hào)串的真值。

謂詞公式

謂詞公式的恒真、恒假、可滿足

定義3.2.10 ：公式G稱為可滿足的，如果存在解釋I，使G在I下取1值，簡(jiǎn)稱I滿足G。若I不滿足G，則簡(jiǎn)稱I弄假G。

定義3.2.11 ：公式G稱為是恒假的(或不可滿足的)，如果不存在解釋I滿足G；公式G稱為恒真的，如果G的所有解釋I都滿足G。

謂詞公式的等價(jià)關(guān)系和蘊(yùn)涵關(guān)系

公式間的等價(jià)：

定義3.2.12 ：公式G，H稱為等價(jià)，記以G=H，如果公式G\(\leftrightarrow\)H是恒真的。
顯然，公式G，H等價(jià)的充要條件是：對(duì)G，H的任意解釋I，G，H在I下的真值相同。

公式間的蘊(yùn)涵：

謂詞公式蘊(yùn)涵的證明方法 ：

范式

前束范式：

定義3.2.14：謂詞邏輯中公式G稱為前束范式，如果G有如下形狀：Q1x1…QnxnM 其中 Qixi或者是\(\forall\)xi，或者\(\exists\)xi，i=1，…，n，M是不含量詞的公式，Q1x1…Qnxn稱為首標(biāo)，M稱為母式。

對(duì)任意謂詞公式，量詞是不能隨便提前的。

引理3.2.1

公式的前束范式化：

引理3.2.2 ：

將公式G化成等價(jià)的前束范式：

使用基本等價(jià)式

? 2.德摩根率

? 3.如果必要的話，則將約束變量改名

? 4.使用引理3.2.1，3.2.2將所有量詞都提到公式的最左邊。

Skolem范式：

定義3.2.15：設(shè)G是一個(gè)公式，Q1x1…QnxnM是與G等價(jià)的前束范式，其中M為合取范式形式。
若Qr是存在量詞，并且它左邊沒(méi)有全稱量詞，則取異于出現(xiàn)在M中所有常量符號(hào)的常量符號(hào)c，并用c代替M中所有的xr，然后在首標(biāo)中刪除Qrxr。若Qs1, …, Qsm是所有出現(xiàn)在Qrxr左邊的全稱量詞(m?1,1?s1<s2<…<sm<r),則取異于出現(xiàn)在M中所有函數(shù)符號(hào)的m元函數(shù)符號(hào)f(xs1,…,xsm )，用f(xs1,…,xsm )代替出現(xiàn)在M中的所有xr，然后在首標(biāo)中刪除Qrxr，對(duì)首標(biāo)中的所有存在量詞做上述處理后，得到一個(gè)在首標(biāo)中沒(méi)有存在量詞的前束范式，這個(gè)前束范式就稱為公式G的Skolem范式。

白話：先把謂詞公式化為前束范式，然后看量詞符號(hào)，存在量詞x是標(biāo)志，用存在量詞左邊的全稱量詞作為函數(shù)自變量替換范式里的x