離散數學_陳莉_第一篇數理邏輯

1、離 散 數 學電子教案電子教案西北大學西北大學信息科學與技術學院信息科學與技術學院緒 言 1 計算機科學與離散數學 介紹離散數學在計算機科學發(fā)展中的作用與關系，明確離散數學是掌握與研究計算機科學的基礎理論與工具。 2離散數學的特征 離散性 能行性 3離散數學的內容 離散數學的主要內容為： 數理邏輯 集合論 代數系統(tǒng) 圖論 第一篇 數理邏輯 數理邏輯是用數學方法研究形式邏輯演繹推理規(guī)則的科學，它是一門數學，是一門研究演繹推理規(guī)則的數學，在學習此部分時，主要要掌握如下幾個要點： 思維的形式化 指派法 公式推理 公理系統(tǒng) 范式 自動定理證明 本篇由命題邏輯、謂詞邏輯、公理化理論及非經典邏輯等四部分組

2、成，其中命題邏輯以命題為研究對象而謂詞邏輯則以謂詞為研究對象，而公理化理論則是數理邏輯中演繹推理的形式化思想的介紹，最后非經典邏輯則介紹若干種計算機科學中常用的一些特殊形式邏輯，以上四部分有機結合構成完整的整體。1.4 1.4 命題邏輯基本等式命題邏輯基本等式（6）命題邏輯42個基本等式。 交換律 PQQP； PQQP； PQQP 結合律 （PQ）RP（QR）； （PQ）RP（QR）； （PQ）RP（QR） 分配律 P（QR）（PQ）（PR）； P（QR）（PQ）（PR）；否定深入PP； （PQ）PQ； （PQ）PQ； （PQ）PQ；(14)（PQ）PQPQ；變元等同PPP； PPP； PPF

3、；PPT；PPT；PPP；PPP；PPT；PPPPF；常值與變元的聯(lián)結TPP； FPF； TPT；FPF；TPP； FPT； PTT；PFP；TPP； FPP； 聯(lián)結詞化歸PQ（PQ）； PQ（PQ）；PQPQ；PQ（PQ）（QP）其它PQQP(PQ)（PR）PQRP（PQ）PP（QR）PQRP（PQ）P1.5 1.5 對偶定理對偶定理（7）對偶公式定義（8）對偶公式性質：一個等式成立其對偶等式也成立1.6 1.6 命題邏輯基本蘊含式及推理規(guī)則命題邏輯基本蘊含式及推理規(guī)則（9）19個基本蘊含重言式 PQP； PQQ； P PQ； QPQ； PPQ； QPQ； （PQ） P； （PQ） Q； P

4、（PQ）Q； Q（PQ）P； P（PQ）Q； Q（PQ）P； (PQ)(QR) PR； (PQ)(RS) PRQS； (PQ)(PR)(QR)R； P(QPQ)； (PQ)(QR)(PR)； (P(QR)(Q(PR)； (PQ)(RQ)(PRQ) （10）11個推理規(guī)則 P，QP； P，QQ； PPQ； QPQ； P，QPQ； P，PQQ； P，PQQ； Q，PQP； PQ，QRP R； PQ，RSPR QS； PQ，PR，QRR； 1.7 1.7 范式范式 （11）范式命題公式的一種標準形式 （12）特異析取范式：該范式是一個析取式，每個析取項是所有命題變元式其否定的合取式。 （13）特異合

5、取范式：該范式是一個合取式，每個析取項是所有命題變元式其否定的析取式。 1.8 1.8 命題聯(lián)結詞的擴充與歸約命題聯(lián)結詞的擴充與歸約 （13）命題聯(lián)結詞的擴充異或：、與非：、或非：、蘊含否定：C （14）命題聯(lián)結詞的歸約命題聯(lián)結詞可歸約為如下形式之一： , , 第二章 謂詞邏輯 2.1 2.1 謂詞與個體謂詞與個體（1）個體 個體常量與個體變量 個體域與全總個體域（2）謂詞 一元謂詞刻劃個體性質 二元謂詞刻劃兩個個體間關系 n元謂詞刻劃n個個體間關系量詞量詞（3）存在量詞：x P (x)“有一些”之語義（4）全稱量詞：x P (x)“所有”之語義（5）量詞的轄域量詞所作用的范圍 函數函數（6）

6、函數個體間的特定關系稱函數，它是個體間的映射。 f (x)中X是個體而f為函數符號，f (x)為函數。 2.2 2.2 謂詞邏輯公式謂詞邏輯公式 （7）謂詞邏輯公式 項：個體是項，函數是項 原子公式：P（t1 , t2 ,tn）是原子公式（其中ti為項） 公式： 原子公式是公式； A，B是公式，則（A）,（AB）,（AB）,（AB），（AB）是公式； A是公式，x為個體變量，則（x）A，（x）A為公式； 公式由且僅由有限次使用前面三步而得。 2.3 2.3 自由變元與約束變元自由變元與約束變元 （8）謂詞公式中的自由變元與約束變元 謂詞公式中的自由變元與約束變元 約束變元的改名規(guī)則改名在量詞變

7、元及其轄域中該變元的約束出現處進行且該變元不在量詞轄域內出現過。 自由變元的代入規(guī)則代入在公式的自由變元出現的每一處進行且該代入變元不允許在式中以任何約束形式出現。 2.4 2.4 謂詞邏輯永真公式謂詞邏輯永真公式 （9）謂詞邏輯永真公式定義 謂詞公式的解釋與賦值 （10）謂詞邏輯永真公式定義公式在所有解釋下對所有賦值均為真 （11）謂詞邏輯永真公式等式： （xP（x）x（P（x） （x P（x）x（P（x） xP（x）Qx（P（x）Q） xP（x）Qx（P（x）Q）xP（x）Qx（P（x）Q）xP（x）Qx（P（x）Q）xyP（x , y）yx（P（x , y）xyP（x , y）yx（P（

8、x , y）x P（x）Qx（P（x）Q）x P（x）Qx（P（x）Q）Qx P（x）x（Q P（x）Qx P（x）x（Q P（x）x（P（x）Q（x）x（P（x）x Q（x）x（P（x）Q（x）x（P（x）x Q（x）（12）謂詞邏輯的蘊含永真公式xyP（x , y） yx（P（x , y）xP（x） P（x）P（x）x P（x）xP（x）x Q（x）x（P（x）Q（x）xP（x）x Q（x）x（P（x）Q（x）x（P（x）x（P（x）x（P（x）Q（x）x（P（x）x Q（x）x（P（x）Q（x）xP（x）x Q（x） 2.5 2.5 范式范式 （13）前束范式公式的所有量詞均非否定的出現

9、在公式最前面，它的轄域一直延伸至公式末尾，且公式中不出現與。 （14）斯科林范式前束范式的首標處僅出現全稱量詞且公式中不出現自由變元x1x2xnM（x1 , x2, x n）命題邏輯與謂詞邏輯的公理化理論命題邏輯與謂詞邏輯的公理化理論 （16）公理系統(tǒng)的組成 命題：P1，P2，Pn； 命題聯(lián)結詞：，； 個體常量：a，b，c，x，y，z； 個體變量：P，Q，R； 函 數：f，g，h； 謂 詞：，； 括 號：（，） 項： 個體常量是項； 個體變量是項； f是n元函數，t1，t2，,tn是項，則f(t1，t2，,tn)是項； 項由且僅由有限次使用、而得。 原子公式：P是n元謂詞，t1，t2，tn是項

10、，則P（t1，t2，tn)是原子公式。 命題邏輯公式： 命題是公式； P是公式則（P）是公式； P，Q是公式則（PQ），（PQ），（PQ），（PQ）是公式； 公式由且僅由有限次使用 ， ， 而得。 謂詞邏輯公式： 原子公式是公式； A，B是公式則：（A），（AB），（AB），（AB）,（AB）是公式； A是公式則（x）A，（x）B是公式； 公式由且僅由有限次使用、而得。 （17）公理系統(tǒng)的推理 1）公理 如P，Q，R為公式，則有下述的公理： PP； （P（QR）（Q（PR）； （PQ）（QR）（PR）； （P（PQ）（PQ）； （PQ）（PQ）； （PQ）（QP）； （PQ）（QP）（PQ）；

11、 PQQ； PQP； P（QPQ）； PPQ； QPQ； （QP）（RP）（QRP）； （PQ）（QP）； PP； 2）推理規(guī)則 分離規(guī)則：PQ，PQ。 3）證明（過程）與定理 證明（過程）給出了公理系統(tǒng)中定理生成的過程，它是一個公式序列：P1，P2，Pn，其中每個Pi（i1，2，n）必須滿足下條件之一。 Pi是公理； Pi是由Pk，Pr，（k，ri）施行分離規(guī)則而得。 最后，PnQ 即為定理。 （18）導出規(guī)則如有AB為定理則必有AB。 （19）推理定理設有設有A1，A2，AnB，則必有：A 1, A2, An-1 An B。 （20）謂詞邏輯公理系統(tǒng) 1系統(tǒng)組成部分 可見（16） 2推理部

12、分 1）公理 設P，Q，R為公式，則有公理如下： pp （P（QR）（Q（PR） （PQ）（QR）（PR） （P（PQ）（PQ） （PQ）（PQ） （PQ）（QP） （PQ）（QP）（PQ） PQQ PQP P（QPQ） PPQ QPQ （QP）（RP）（QRP） （PQ）（QP） PP xP（x）P（x） P（x）xP（x）。11121314151617 2）推理規(guī)則 分離規(guī)則：PQ，PQ. 全稱規(guī)規(guī)：QP（x）QxP（x） 存在規(guī)則：P（x）Qx P（x）Q 上面17個公理與3個規(guī)則中有15個公理與1個規(guī)則是命題邏輯公理系統(tǒng)的，真正屬謂詞邏輯的僅有2個公理與2個規(guī)則。 3）證明（過程）與定

13、理。 證明（過程）是一個公式序列：P1，P2，Pn，其中每個Pi（i1，2，n）必須滿足下條件之一： Pi是公理； Pi是由Pk，Pr，（k，ri）施行分離規(guī)則而得； Pi是由Pk（ki）施行全稱規(guī)則而得； Pi是由Pk（ki）施行存在規(guī)則而得。 最后，PnQ 即為定理。（21）謂詞邏輯中四個重要的推理規(guī)則 全稱指定規(guī)則：US x P（x）P（x） 全稱推廣規(guī)則：UG P（x）x P（x） 存在指定規(guī)則：ES x P（x）P（ x ） 存在推廣規(guī)則：EG P（x）x P（x） 2.6 2.6 數理邏輯公理化應用系統(tǒng)數理邏輯公理化應用系統(tǒng) （22）數理邏輯公理化應用系統(tǒng)的定義：數理邏輯公理系統(tǒng)學科式領域的公理與規(guī)則。公理化理論與計算機科學公理化理論與計算機科學 （23）公理化理論在計算機科學中的應用謂詞邏輯的自動定理證明謂詞邏輯的自動定理證明（24）子句與Horn子句（25）消解原理 將一公式化為Horn子句集 采用消解原理，即由S為公理證明E為定理的過程可改寫： 作SSUE為公理； 從E開始在S中不斷使用反駁法； 最后出現空子句口則結束； 如空子句出現則表示公式為真。PROLOGPROLOG語言簡介語言簡介（26）PROLOG語言第三章 非經典邏輯介紹 3.1 3.1 多值邏輯