離散數(shù)學-數(shù)理邏輯課件

離散數(shù)學

DiscreteMathematics離散數(shù)學

DiscreteMathematics離散數(shù)學課程地位：計算機系核心課程信息類專業(yè)必修課程其它類專業(yè)的重要選修課程離散數(shù)學的后繼課程：數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、算法分析與設(shè)計、數(shù)據(jù)庫、c++語言……離散數(shù)學課程地位：

學習該課程的目的：

一方面，它給后繼課，如數(shù)據(jù)結(jié)構(gòu)、編譯系統(tǒng)、操作系統(tǒng)、數(shù)據(jù)庫原理、軟件工程與方法學、計算機網(wǎng)絡(luò)、程序設(shè)計等，提供必要的數(shù)學基礎(chǔ)；

另一方面，通過學習離散數(shù)學，可以培養(yǎng)和提高自己的抽象思維和邏輯推理能力，為以后的軟、硬件學習和研究開發(fā)工作，打下堅實的數(shù)學基礎(chǔ)。學習該課程的目的：教學要求：通過該課程的學習，學生應(yīng)當了解并掌握計算機科學中普遍采用的離散數(shù)學中的一些基本概念、基本思想、基本方法。自學要求：通過反復(fù)看書及做課后習題，來加深對該課程中的一些基本概念的理解，逐步提高自己的抽象思維和邏輯推理能力。教學要求：離散數(shù)學課程的學習方法:強調(diào)：邏輯性、抽象性；注重：概念、方法與應(yīng)用離散數(shù)學的學習要領(lǐng)：概念（正確）必須掌握好離散數(shù)學中大量的概念判斷（準確）根據(jù)概念對事物的屬性進行判斷推理（可靠）根據(jù)多個判斷推出一個新的判斷離散數(shù)學課程的學習方法:

離散數(shù)學的內(nèi)容第一部分數(shù)理邏輯：命題邏輯、謂詞邏輯第二部分集合論：集合、關(guān)系、函數(shù)第三部分代數(shù)系統(tǒng)：運算、代數(shù)系統(tǒng)、半群、群、環(huán)、域、格、布爾代數(shù)

第四部分圖論：點與邊、路與圈、最短路、

Euler圖、Hamilton圖、平面圖、樹

離散數(shù)學的內(nèi)容離散數(shù)學與計算機的關(guān)系第一部分數(shù)理邏輯

計算機是數(shù)理邏輯和電子學相結(jié)合的產(chǎn)物。第二部分集合論集合是一種重要的數(shù)據(jù)結(jié)構(gòu)關(guān)系，關(guān)系數(shù)據(jù)庫的理論基礎(chǔ)函數(shù)，所有計算機語言中不可缺少的一部分。第三部分代數(shù)系統(tǒng)

計算機編碼和糾錯碼理論數(shù)字邏輯設(shè)計基礎(chǔ)計算機使用的各種運算。第四部分圖論

數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、編譯原理計算機網(wǎng)絡(luò)原理的基礎(chǔ)。

離散數(shù)學與計算機的關(guān)系第一部分數(shù)理邏輯第一章命題邏輯數(shù)理邏輯是研究推理（即研究人類思維的形式結(jié)構(gòu)和規(guī)律）的科學，起源于17世紀，它采用數(shù)學符號化的方法，因此也稱為符號邏輯。從廣義上講，數(shù)理邏輯包括四論、兩演算——即集合論、模型論、遞歸論、證明論和命題邏輯演算、謂詞邏輯演算，但現(xiàn)在提到數(shù)理邏輯，一般是指命題邏輯和謂詞邏輯。本書也只研究這兩個邏輯演算。第一章命題邏輯數(shù)理邏輯是研究推理（即研究人類思維的形式結(jié)數(shù)理邏輯的創(chuàng)始人是Leibniz，為了實現(xiàn)把推理變?yōu)檠菟愕南敕?，他把?shù)學引入了形式邏輯。其后，又經(jīng)多人努力，逐漸使得數(shù)理邏輯成為一門專門的學科。上個世紀30年代以后，數(shù)理邏輯進入一個嶄新的發(fā)展階段，邏輯學不僅與數(shù)學結(jié)合，還與計算機科學等密切關(guān)聯(lián)。1931年Godel不完全性定理的提出，以及遞歸函數(shù)可計算性的引入，促使了1936年Turing機的產(chǎn)生，十年后，第一臺電子計算機問世。數(shù)理邏輯的創(chuàng)始人是Leibniz，為了實現(xiàn)把推理變?yōu)檠菟愕南霐?shù)理邏輯與計算機學、控制論、人工智能的相互滲透推動了其自身的發(fā)展，模糊邏輯、概率邏輯、歸納邏輯、時態(tài)邏輯等都是目前比較熱門的研究領(lǐng)域。本章和下一章我們只從語義出發(fā)，對數(shù)理邏輯中的命題邏輯與謂詞邏輯等作一簡單的、直接的、非形式化的介紹，將不涉及任何公理系統(tǒng)。數(shù)理邏輯與計算機學、控制論、人工智能的相互滲透推動了其自身的第一章命題邏輯1.命題及其表示命題：是指具有確定真值的陳述句或者能夠判斷真假的陳述句。命題的真值：命題的判斷結(jié)果。真值只取兩個值：真（1或T）、假（0或F）。真命題：真值為真的命題。假命題：真值為假的命題。判斷命題的兩個步驟：

1、是否為陳述句；

2、是否有確定的、唯一的真值。1.1節(jié)命題及聯(lián)結(jié)詞第一章命題邏輯1.命題及其表示1.1節(jié)命題及聯(lián)結(jié)詞

注意:

感嘆句、祈使句、疑問句都不是命題.陳述句中的悖論以及判斷結(jié)果不惟一確定的也不是命題。例1.1下列句子中那些是命題？

（1）重慶是直轄市。（2）教師是人類靈魂的工程師。（3）4是素數(shù)。（4）1+1＝2。（5）2100年的春節(jié)是晴天。（6）火星上有生物。（7）請安靜?。?）今天天氣多好啊!（9）現(xiàn)在是幾點鐘?（10）我正在說假話。（11）注意:感嘆句、祈使句、疑問句都不是命題.陳述句中（1）、（2）、（3）、（4）、（5）和（6）都是命題。其中（1）、（2）、（4）是真命題，（3）是假命題。至于（5）和（6）真假值是確定的，只是現(xiàn)在無法知道，因此它是命題。（7）、（8）、（9）、（10）、（11）都不是命題。原因在于（7）是祈使句，（8）是感嘆句，（9）是疑問句，而（10）是悖論，即若(10)的真值為真，即“我正在說假話”為真，也就是我說的是假話，因此（10）又是錯誤的；反之，若(10)的真值為假，即“我正在說假話”為假，也就是我在說真話，因此(10)的真值應(yīng)為真。像(10)這樣既不為真又不為假的陳述句不是命題，這種陳述句稱為悖論。凡是悖論都不是命題。（11）中的x、y的值不確定，某些x、y使為真，某些x、y使為假，即的真假隨x、y的變化而變化。因此，的真假無法確定，所以不是命題。

（1）、（2）、（3）、（4）、（5）和（6）都是命題。其中練習判斷下列句子是否為命題。1.100是自然數(shù)。2.太陽從西方升起。3.北京是中國的首都4.重慶是中國最大的城市5.關(guān)門!6.你去哪里?7.Howdoyoudo?8.凡石頭均可煉成金。9.x+3>910.皇馬中國之行沒有提升國家隊的水平。練習判斷下列句子是否為命題。命題表示在本書中，用大寫的英文字母P,Q,R,…，P1,P2,P3…，[1]，[2]等表示命題,用“1(或者T）”、“0（或者F）”分別表示真值的真、假。

如

P：太陽從東邊升起。

Q：5是負數(shù)。

[1]：2008北京舉辦奧運會

。其真值依次為1、0、1。命題表示命題的分類簡單/原子命題：由不能再分解為更簡單的陳述句的陳述句構(gòu)成。復(fù)合命題：由簡單命題通過聯(lián)結(jié)詞聯(lián)結(jié)而成的陳述句。如：命題“如果2是素數(shù)，則3也是素數(shù)”通過“如果……，則……”組合而成，是復(fù)合命題，而“2是素數(shù)”和“3是素數(shù)”是簡單命題。命題的分類2.命題聯(lián)結(jié)詞在日常語言中，一些簡單的陳述句，可以通過某些聯(lián)結(jié)詞聯(lián)結(jié)起來，組成較為復(fù)雜的語句。例如可以說：“如果下星期日是晴天，那么我就去春游?！边@里就是用：“如果……，那么……”把兩個陳述句“下星期日是晴天”和“我去春游”聯(lián)結(jié)起來組成的一個新復(fù)合命題。在日常語言中還有許多聯(lián)結(jié)詞，如“不”、“并且”、“或者”、“當且僅當”，“只要……就……”，“除非……否則……”等都是聯(lián)結(jié)詞。使用它們可以將一個命題加以否定或?qū)蓚€命題連接起來得到新的復(fù)合命題。下面介紹常用的5種常用的聯(lián)結(jié)詞。2.命題聯(lián)結(jié)詞在日常語言中，一些簡單的陳述句，可以通過某些（1）否定聯(lián)結(jié)詞設(shè)p為命題，復(fù)合命題“非P”（或“P的否定”）稱為P的否定式，記作P，符號稱為否定聯(lián)結(jié)詞。運算規(guī)則：屬于單目運算符（1）否定聯(lián)結(jié)詞（2）合取聯(lián)結(jié)詞設(shè)P,Q為二命題變元，復(fù)合命題“P并且Q”（或“P與Q”）稱為P與Q的合取式，記作P∧Q，符號∧稱為合取聯(lián)結(jié)詞。運算規(guī)則：屬于雙目運算符（2）合取聯(lián)結(jié)詞合取運算特點：

只有參與運算的二命題全為真時，運算結(jié)果才為真，否則為假。自然語言中的表示“并且”意思的聯(lián)結(jié)詞，如“既…又…”、“不但…而且…”、“雖然…但是”等都可以符號化為∧例如：將下列命題符號化(1)北京不僅是中國的首都而且是一個故都。解：設(shè)P：北京是中國的首都；Q：北京是一個故都；則原命題符號化為：P∧Q。合取運算特點：例如：將下列命題符號化（2）小麗既聰明，又能干。

解：設(shè)P：小麗聰明；Q：小麗能干；則原命題符號化為：P∧Q。（3）小剛聰明但不努力。解：設(shè)P：小剛聰明；Q：小剛努力；則原命題符號化為：P∧Q。（4）小剛和小明是同學。解：這是一個原子命題，不能分解為更細的命題。（2）小麗既聰明，又能干。（3）析取聯(lián)結(jié)詞

設(shè)P,Q為二命題變元，復(fù)合命題“P或Q”稱為P與Q的析取式，記作P∨Q，符號∨稱為析取聯(lián)結(jié)詞。

運算規(guī)則：屬于雙目運算符。（3）析取聯(lián)結(jié)詞

說明：聯(lián)結(jié)詞析取∨的意義與日常所使用的“或”意思并不完全相同。在日常生活中，“或”實際上分為“排斥或”和“可兼或”，還有一種是描述模糊數(shù)據(jù)。本書將析取表示“可兼或”?！芭懦饣颉庇玫葍r的聯(lián)結(jié)詞代替。說明：聯(lián)結(jié)詞析取∨的意義與日常所使用的“或”意思并不完例如:(1)今天晚上我在家看電視或聽音樂。解：設(shè)P：今天晚上我在家看電視；

Q：今天晚上我在家聽音樂；則原命題符號化為：P∨Q。（可兼或）（2）從重慶到北京的T10次列車是中午1點或1點半開。解：該命題中的“或”不是“可兼或”，不能用聯(lián)結(jié)詞析取。我們用一種等價形式來代替。設(shè)P：重慶到北京的T10次列車是中午1點開；

Q：重慶到北京的T10次列車是中午1點半開；則原命題符號化為：(P∧Q)∨(P∧Q).

例如:例如:（3）小剛是山東或山西人。解：設(shè)P：小剛是山東人；Q：小剛是山西人；則原命題符號化為：(P∧Q)∨(P∧Q).（排斥或）（4）小剛是有20或30歲。解：這是一個原子命題，這里的“或”表示一個模糊數(shù)據(jù)。

在遇到含有“或”的命題符號化時，要分清它是“可兼或”、“排斥或”、還是表示模糊數(shù)的“或”，析取聯(lián)結(jié)詞表示“可兼或”。

例如:（4）單條件聯(lián)結(jié)詞

設(shè)P,Q為二命題變元,復(fù)合命題“如果P,則Q”稱為P與Q的單條件（蘊涵式），記作PQ，并稱P為單條件的前件，Q為單條件的后件，符號稱為單條件結(jié)詞。

運算規(guī)則：屬于雙目運算符與自然語言的不同：前件與后件可以沒有任何內(nèi)在聯(lián)系?。?）單條件聯(lián)結(jié)詞說明：PQ的邏輯關(guān)系：Q為P的必要條件“如果P，則Q”的不同表述法很多：“若P，就Q”“只要P，就Q”“P僅當Q”“只有Q才P”“除非Q,才P”或“除非Q,否則非P”...等等。當P為假時，無論Q是什么，PQ均為真。

常出現(xiàn)的錯誤：不分充分與必要條件??！說明：PQ的邏輯關(guān)系：Q為P的必要條件例如：（1）如果天下雨，那么我們在室內(nèi)活動。解：設(shè)P：天下雨；Q：我們在室內(nèi)活動；原命題符號化為：PQ。（2）只要天下雨，我們就在室內(nèi)活動。解：設(shè)P：天下雨；Q：我們在室內(nèi)活動；原命題符號化為：PQ。（3）因為天下雨，所以我們在室內(nèi)活動。解：設(shè)P：天下雨；Q：我們在室內(nèi)活動；原命題符號化為：PQ。在實際的語言中，很多聯(lián)結(jié)詞可以轉(zhuǎn)化為用單條件，但是要注意前件和后件的關(guān)系。例如：（4）只有天下雨，我們才在室內(nèi)活動。解：設(shè)P：天下雨；Q：我們在室內(nèi)活動；原命題符號化為：QP。（5）僅當天下雨，我們在室內(nèi)活動。解：設(shè)P：天下雨；Q：我們在室內(nèi)活動；原命題符號化為：QP。（6）除非天下雨，否則我們不在室內(nèi)活動。解：設(shè)P：天下雨；Q：我們在室內(nèi)活動；原命題符號化為：QP，或者P

Q

。（4）只有天下雨，我們才在室內(nèi)活動。（5）雙條件聯(lián)結(jié)詞

設(shè)P,Q為二命題變元，復(fù)合命題“P當且僅當Q”稱為P與Q的雙條件，記作PQ，符號稱為雙條件聯(lián)結(jié)詞。說明:(1)PQ的邏輯關(guān)系:P與Q互為充分必要條件

(2)PQ為真當且僅當P與Q同真或同假。

運算規(guī)則：屬于雙目運算符。（5）雙條件聯(lián)結(jié)詞例如：

(1)2+2＝4當且僅當3+3＝6.

解：設(shè)P：2+2＝4；Q：3+3＝6.；原命題符號化為：P

Q。（2）1+1=2當且太陽從東邊升起。

解：設(shè)P：1+1=2；Q：太陽從東邊升起；原命題符號化為：P

Q。

例如：命題公式與真值表將命題“如果明天天晴，且我有空，我就去踢球”符號化。設(shè)P：明天天晴；Q：我有空；R：我去踢球。本命題符號化為：

（PQR。

命題變元和聯(lián)結(jié)詞構(gòu)成復(fù)合命題的形式化描述，為了能夠更加準確的描述命題，本節(jié)主要討論命題公式及其命題公式的賦值。命題公式與真值表命題公式（1）單個命題變項是合式公式，并稱為原子命題公式。（2）若A是合式公式，則(A)也是合式公式。（3）若A，B是合式公式，則(A∧B)，(A∨B)，(AB)，(AB)也是合式公式。（4）只有有限次地應(yīng)用(1)、（2）、(3)形成的包含命題變元、聯(lián)結(jié)詞和圓括號的符號串是命題合式公式。

命題合式公式也稱為命題公式或命題形式，并簡稱為公式。命題公式例如：

(PQ)，(R∧S)∨Q，QP等均為合式公式;

而PQ∨S,(P,Q）R，(P∨∧Q)R，(PW)∧Q)等不是合式公式。

聯(lián)結(jié)詞之間的運算有不同的優(yōu)先級，聯(lián)結(jié)詞運算的優(yōu)先次序為:{，∧，∨，，}如果有括號，則先進行括號內(nèi)的運算。例如：真值表

設(shè)A是一個命題公式，P1，P2，...，Pn是出現(xiàn)在A中的所有命題變元，對這些命題變元賦予一個確定的真值稱為對命題公式的一種賦值。不同的賦值，命題公式有不同真值情況。將命題公式在所有的賦值下的真值情況匯成一個表，這個表就稱為真值表。如果一個命題公式有n個命題變元，每個命題變元有兩種真值情況，則共有n2種不同的賦值情況。

真值表設(shè)A是一個命題公式，P1，P2，.對公式A構(gòu)造真值表的具體步驟為：

(1)找出公式中所有的全體命題變項p1，

p2，

…，pn，列出2n個賦值。

(2)按從高到低（從低到高）的順序?qū)懗龉降母鱾€層次。

(3)對應(yīng)各個賦值計算出各層次的真值，直到最后計算出公式的真值。對公式A構(gòu)造真值表的具體步驟為：例如：求命題公式(PQ)∧R的真值表。例如：求命題公式(PQ)∧R的真值表。例如：求命題公式(P∧Q)R的真值表。例如：求命題公式(P∧Q)R的真值表。例如：求命題公式(PQ)(QP)的真值表。例如：求命題公式(PQ)(QP)的真值表。例如：求命題公式(PQ)∧Q的真值表。例如：求命題公式(PQ)∧Q的真值表。例如：求命題公式PQ和(P∧Q)的真值表。例如：求命題公式PQ和(P∧Q)的真值表。命題公式等值

設(shè)A,B是兩個命題公式，若A，B構(gòu)成的等價式AB為重言式，則稱A與B是等值的記作A

B.即A

B的充要條件是AB為重言式。判斷兩個公式等值的方法1：真值表法。命題公式等值設(shè)A,B是兩個命題公式，若A，B構(gòu)成的等價式例如：P(QR)與(P∧Q)R等價例如：P(QR)與(P∧Q)R等價離散數(shù)學-數(shù)理邏輯課件命題公式中有很多公式都是等價的；要記住大量的等價公式是困難的；然而一些基本的、重要的等價公式是應(yīng)該掌握的。下面列出一些最基本的等價公式。也稱命題定律。命題公式中有很多公式都是等價的；雙重否定律

:PP等冪律：PPP;PPP交換律:PQQP;PQQP結(jié)合律:(PQ)RP(QR)(PQ)RP(QR)分配律:P(QR)(PQ)(PR)P(QR)(PQ)(PR)雙重否定律:PP德·摩根律:(PQ)PQ

(PQ)PQ吸收律:P(PQ)P,P(PQ)P零律:P11,P00同一律:P0P,P1P排中律:PP1矛盾律:PP0等值蘊涵律:PQPQ假言異位律:PQQ

P等價等值律:PQ（PQ）（QP）德·摩根律:(PQ)PQ置換規(guī)則：若AB,則(B)(A)。用等值公式可以進行等值演算，證明等值公式、判定公式類型.下面舉例說明.試證:證明：置換規(guī)則：若AB,則(B)(A)。試證:證明：又如：驗證P(QR)

(P∧Q)R

右(P∧Q)∨RP∨Q∨RP∨(Q∨R)P∨（QR)P(QR)

又如：驗證P(QR)(P∧Q)R公式的分類

重言式：給定一個命題公式，若無論對其中的命題變元作何種賦值，其對應(yīng)的真值永為1，則稱該命題公式為重言式或永真式。

永假式：給定一個命題公式，若無論對其中的命題變元作何種賦值，其對應(yīng)的真值永為0，則稱該命題公式為矛盾式或永假式。

可滿足式：給定一個命題公式，若存在一種賦值使得公式的真值為1，則稱該命題公式為可滿足式。公式的分類重言式：給定一個命題公式，若無論對其中的命題變用等值演算法判斷公式Q(PQ)的類型。解：Q(PQ)

Q(PQ)

Q(PQ)

P(QQ)

P0

0該式為矛盾式.

用等值演算法判斷公式Q(PQ)的類型。用等值演算法判斷公式(PQ)(QP)的類型。解:(PQ)(QP)

(PQ)(QP)

(PQ)(PQ)1該式為重言式.用等值演算法判斷公式1.3命題公式的范式與主范式文字：命題變項及其否定統(tǒng)稱為文字。如：P,Q，Q等簡單析取式：僅有有限個文字組成的析取式。如：P，

Q，P∨Q，P∨Q∨R簡單合取式：僅有有限個文字組成的合取式。如：P，P，P∧Q，P∧Q∧R而P∧（Q∧R)不是簡單合取,（P∨R)不是簡單析取。1.3命題公式的范式與主范式文字：命題變項及其否定統(tǒng)稱為文顯然，簡單析取式是重言式當且僅當它含有同一個變元及其該變元的否定；簡單合取式是矛盾式當且僅當它含有同一個變元及其該變元的否定。命題公式是千變?nèi)f化的，這給研究命題演算帶來困難，這里我們研究如何由一個命題公式化歸為一個標準形式的問題，這種標準形式就叫范式和主范式。顯然，簡單析取式是重言式當且僅當它含有同一個變元及其該變元的離散數(shù)學-數(shù)理邏輯課件將一個命題公式轉(zhuǎn)化為析取范式和合取范式的主要方法是利用基本的命題等價公式如德摩根律、分配律、蘊涵等值律、同一律、排中律和吸收律等將公式轉(zhuǎn)化為要求的范式。將一個命題公式轉(zhuǎn)化為析取范式和合取范式的主要方法是利用基本的由此可以看出，一個命題公式總可以通過等值變化化為與之等值的析取范式和合取范式，但是一個命題公式的析取范式和合取范式分別有多個，不一定是惟一的。為了能夠惟一的表示一個命題公式，下面我們主要討論命題公式的主范式。由此可以看出，一個命題公式總可以通過等值變化化為與之等值的析離散數(shù)學-數(shù)理邏輯課件離散數(shù)學-數(shù)理邏輯課件說明：

(1)n個命題變項產(chǎn)生2n個極小項和2n個極大項,2n個極小項（極大項）均互不等值.(2)用mi表示第i個極小項，其中i是該極小項成真賦值的十進制表示.用Mi表示第i個極大項，其中i是該極大項成假賦值的十進制表示,mi(Mi)稱為極小項(極大項)的名稱.mi與Mi的關(guān)系:miMi,Mimi

說明：由p,q兩個命題變項形成的極小項與極大項

由p,q兩個命題變項形成的極小項與極大項由p,q,r三個命題變項形成的極小項與極大項

由p,q,r三個命題變項形成的極小項與極大項我們?nèi)菀讱w納得到極小項的如下性質(zhì)：每個極小項有且僅有一個成真賦值，該成真賦值與該極小項的編碼下標一致。任意兩個不同極小項的合取為矛盾式。全體極小項的析取為重言式。同樣，我們?nèi)菀椎玫綐O大項的如下性質(zhì)：每個極大項有且僅有一個成假賦值，該成假賦值與該極大項的編碼下標一致。任意兩個不同極大項的析取為重言式。全體極大項的合析取為矛盾式。我們?nèi)菀讱w納得到極小項的如下性質(zhì)：主析取范式與主合取范式主析取范式與主合取范式定理

任何命題公式都存在著與之等值的主析取范式和主合取范式,并且是惟一的.求公式的主范式的主要方法：

方法一（等值添項法）方法二（真值表法）定理任何命題公式都存在著與之等值的主析取范式和主合取范式,方法一（等值添項法）求主析取范式的主要步驟：第1步：將命題公式化為析取范式；第2步：在每個不是極小項的簡單合取式中用否定律增加缺少的文字；（注意按照一定順序添加）第3步：用分配律展開得到新的析取范式；如果還存在簡單合取式不是極小項時，重復(fù)第2步；第4步：刪除重復(fù)的極小項，得到主析取范式。求主合取范式的主要步驟：第1步：將命題公式化為合取范式；第2步：在每個不是極大項的簡單析取式中用否定律增加缺少的文字；（注意按照一定順序添加）第3步：用分配律展開得到新的合取范式；如果還存在簡單析取式不是極大項時，重復(fù)第2步；第4步：刪除重復(fù)的極大項，得到主合取范式。方法一（等值添項法）求主析取范式的主要步驟：離散數(shù)學-數(shù)理邏輯課件離散數(shù)學-數(shù)理邏輯課件方法二（真值表法）定理：一個命題公式的真值表中，成真賦值對應(yīng)的極小項的析取是該公式的主析取范式；成假賦值對應(yīng)的極大項的合取是該公式的主合取范式。真值表法求主析取范式的主要步驟：第1步：求公式的真值表；第2步:找出所有的成真賦值，并形成對應(yīng)的極小項的編碼；第3步:將極小項的編碼轉(zhuǎn)化成極小項，得到主析取范式。真值表法求主合取范式的主要步驟：第1步：求公式的真值表；第2步:找出所有的成假賦值，并形成對應(yīng)的極大項的編碼；（注意編碼的轉(zhuǎn)化問題）第3步:將極大項的編碼轉(zhuǎn)化成極大項，得到主合取范式。方法二（真值表法）定理：一個命題公式的真值表中，成真賦值對離散數(shù)學-數(shù)理邏輯課件離散數(shù)學-數(shù)理邏輯課件由真值表法很容易得到主范式的如下性質(zhì)：主析取范式和主合取范式具有互補性（即它們的編碼恰好構(gòu)成全體賦值情況），知道主析取范式可以得到主合取范式，知道主合取范式也可以得到主析取范式。重言式的主析取范式是全體極小項的析取，其主合取范式規(guī)定為1；矛盾式的主合取范式是全體極大項的合取，其主析取范式規(guī)定為0。如果兩個不同形式的公式等值，則它們的真值表相同，因而它們有相同的主范式。由真值表法很容易得到主范式的如下性質(zhì)：離散數(shù)學-數(shù)理邏輯課件離散數(shù)學-數(shù)理邏輯課件

一個公式的主范式是惟一的（除去極小項和極小項的順序外）。主范式的主要用途在于：規(guī)范命題公式的形式；求公式的成真和成假賦值；判定公式是否等值；實際應(yīng)用。一個公式的主范式是惟一的（除去極小項和極小項的順離散數(shù)學-數(shù)理邏輯課件

又例某公司要從趙、錢、孫、李、周五名新畢業(yè)的大學生中選派一些人出國學習.選派必須滿足以下條件：

(1)若趙去，錢也去；

(2)李、周兩人中至少有一人去；

(3)錢、孫兩人中有一人去且僅去一人；

(4)孫、李兩人同去或同不去；

(5)若周去，則趙、錢也去.

試用主析取范式法分析該公司如何選派他們出國？解此類問題的步驟為：①將簡單命題符號化②寫出各復(fù)合命題③寫出由②中復(fù)合命題組成的合取式④求③中所得公式的主析取范式又例某公司要從趙、錢、孫、李、周五名新畢業(yè)的大學生中解①設(shè)p：派趙去，q：派錢去，r：派孫去，s：派李去，u：派周去.②(1)(pq)(2)(su)(3)((qr)(qr))(4)((rs)(rs))(5)(u(pq))

③(1)-(5)構(gòu)成的合取式為

A=(pq)(su)((qr)(qr))((rs)(rs))(u(pq))解①設(shè)p：派趙去，q：派錢去，r：派孫

④A(pqrsu)(pqrsu)結(jié)論：由④可知，A的成真賦值為00110與11001，因而派孫、李去（趙、錢、周不去）或派趙、錢、周去（孫、李不去）.A的演算過程如下:A(pq)((qr)(qr))(su)(u(pq))((rs)(rs))（交換律)B1=(pq)((qr)(qr))((pqr)(pqr)(qr))(分配律)④A(pqrsu)(pqB2=(su)(u(pq))((su)(pqs)(pqu))（分配律）B1B2(pqrsu)(pqrsu)(qrsu)(pqrs)(pqru)再令B3=((rs)(rs))得AB1B2B3(pqrsu)(pqrsu)B2=(su)(u(pq))離散數(shù)學-數(shù)理邏輯課件又如：某公司需要從A,B和C這3名骨干人員中派2名到國外考察，由于工作需要，選派時需要滿足以下條件：若A去，則C同去；若B去，則C不能去；若C不去，則A或B可以去。請問如何安排？又如：某公司需要從A,B和C這3名骨干人員中派2名到國外考察離散數(shù)學-數(shù)理邏輯課件4聯(lián)結(jié)詞的完備集4聯(lián)結(jié)詞的完備集離散數(shù)學-數(shù)理邏輯課件離散數(shù)學-數(shù)理邏輯課件離散數(shù)學-數(shù)理邏輯課件單元素聯(lián)結(jié)詞構(gòu)成的聯(lián)結(jié)詞完備集

人們還可構(gòu)造形式上更為簡單的聯(lián)結(jié)詞完備集。在計算機硬件設(shè)計中，用與非門或者或非門來設(shè)計邏輯線路時，就需要構(gòu)造新聯(lián)結(jié)詞完備集。單元素聯(lián)結(jié)詞構(gòu)成的聯(lián)結(jié)詞完備集

人們還可構(gòu)造形離散數(shù)學-數(shù)理邏輯課件離散數(shù)學-數(shù)理邏輯課件5命題推理理論

人工智能的重要研究內(nèi)容是知識的表示與推理，如果將知識用命題符號化的形式給出后，如何按照一定的規(guī)則推導(dǎo)出新的結(jié)論和知識是一個重要的內(nèi)容。本節(jié)將介紹一些經(jīng)典的命題推理規(guī)則和推理方法。一般說來，根據(jù)經(jīng)驗，如果前提是真的，根據(jù)提供的推理規(guī)則所推出的結(jié)論也應(yīng)該是真的。給出一些推理規(guī)則，從前提出發(fā)推導(dǎo)出結(jié)論，這種結(jié)論稱為有效結(jié)論，這種論證過程稱為有效論證。在數(shù)理邏輯中，重點研究的是推理的有效性，而不是通常所說的正確性。5命題推理理論人工智能的重要研究內(nèi)容是知識的表示與推理，

推理是從前提推出結(jié)論的思維過程，前提是指已知的命題公式，結(jié)論是從前提出發(fā)應(yīng)用推理規(guī)則推出的命題公式，前提可多個，由前提A1，A2，…Ak推出結(jié)論B的嚴格定義如下：有效結(jié)論（1）：若(A1∧A2∧…∧Ak)B為重言式，則稱A1，A2，…Ak，推結(jié)論B的結(jié)論正確，B是A1，A2，…Ak，的邏輯結(jié)論或有效結(jié)論，稱(A1∧A2∧…∧Ak)B為由前提A1，A2，…Ak推結(jié)論B的推理的形式結(jié)構(gòu)。推理是從前提推出結(jié)論的思維過程，前提是指已知的命題公式，離散數(shù)學-數(shù)理邏輯課件對于任一組賦值，前提和結(jié)論的取值有以下四種情況：

①{A1，A2，…Ak}為0，B為0。√②{A1，A2，…Ak}為0，B為1?！挞踸A1，A2，…Ak}為1，B為0。×④{A1，A2，…Ak}為1，B為1?！虒τ谌我唤M賦值，前提和結(jié)論的取值有以下四種情況：推理的另一種形式：命題公式A1，A2，…Ak推B的推理正確當且僅當

(A1∧

A2∧

…

∧Ak)B

為重言式。于是推理的一般形式可轉(zhuǎn)化為：

(A1

∧A2

∧

…

∧Ak)B推理正確轉(zhuǎn)化為：

A1

∧A2

∧

…

∧Ak

B推理的另一種形式：

證明(A1

∧A2

∧

…

∧Ak)B的方法有：

1、真值表法；2、等值演算法；3、主析取范式法。

但是，在前提和結(jié)論中，若命題變元的數(shù)目較大時，使用真值表的方法、等值演算、等值添項和主范式的方法都顯得很麻煩。此時可以采用推理的方法進行證明。因此，接下來引入構(gòu)造論證的方法，這種方法需要一些等值定律和推理規(guī)則。

證明(A1∧A2∧…∧Ak)B的方法有：等值定律等值定律離散數(shù)學-數(shù)理邏輯課件推理規(guī)則推理規(guī)則下面舉例說明推理定律和推理規(guī)則的應(yīng)用下面舉例說明推理定律和推理規(guī)則的應(yīng)用離散數(shù)學-數(shù)理邏輯課件

判定推理是否有效：如果今天是星期六，我們就要到西湖或大清谷去玩。如果西湖游人太多，我們就不到西湖去玩。今天是星期六。西湖游人太多。所以我們到大清谷玩。解：首先將命題符號化：

p:今天是星期六。q:我們到西湖去玩。

r:我們到大清谷去玩。s:西湖游人多。前提：p(q∨r),s

?q,p,s結(jié)論：r證明：①s

?q前提引入

②s前提引入

③?q①②假言推理

④p

前提引入

⑤p(q∨r)前提引入

⑥q∨r④⑤假言推理

⑦r③⑥析取三段論判定推理是否有效：以上兩個例子主要是直接證明的方法，下面討論兩種間接證明方法。（一）附加前提法（CP規(guī)則法）欲證明(A1∧A2∧

…

∧Ak)

(AB)，只需證明

(A1∧A2∧

…

∧Ak∧

A)B即可，因為:(A1∧A2∧

…

∧Ak)

(AB)(A1∧A2∧

…

∧Ak)∨

(AB)(A1∧A2∧

…

∧Ak)∨

(A∨B)(A1∨

A2∨

…

∨

Ak)∨

(A∨B)A1∨

A2∨

…

∨

Ak∨

A∨B(A1∨

A2∨

…

∨

Ak∨

A)∨B(A1∧A2∧

…

∧Ak∧A)∨

B(A1∧A2∧

…

∧Ak∧A)

B

注:ABA∨B(A∧B)A∨B

以上兩個例子主要是直接證明的方法，下面討論兩種間接證明方法。例：用附加前提證明法證明下面推理前提：p(qr),s∨p,q結(jié)論：s

r證明：①s∨p

前提引入

②s附加前提引入

③p①②析取三段論

④p(qr)前提引入

⑤qr③④假言推理

⑥q前提引入

⑦r⑤⑥假言推理

由附加前提證明法知(A1

∧A2

∧

…

∧Ak

)

(AB)可歸結(jié)為證明

(A1

∧A2

∧

…

∧Ak

∧

A)B例：用附加前提證明法證明下面推理由附加前提證明法知(A1離散數(shù)學-數(shù)理邏輯課件例如果小張和小王去看電影，則小李也去看電影；小趙不去看電影或小張去看電影；小王去看電影。所以，當小趙去看電影時小李也去。判斷上述推理是否有效？例如果小張和小王去看電影，則小李也去看電影；小趙不去看電（二）歸謬法（反證法）欲證明(A1

∧A2

∧

…

∧Ak

)

B，只需將B作為前提能推出矛盾來即可。因為：(A1

∧A2

∧

…

∧Ak

)

B(A1

∧A2

∧

…

∧Ak

)

∨B(A1

∧A2

∧

…

∧Ak

∧

B）若(A1

∧A2

∧

…

∧Ak

∧

B）為矛盾式，則

(A1

∧A2

∧

…

∧Ak

)B為重言式，即

(A1

∧A2

∧

…

∧Ak

)=>B（二）歸謬法（反證法）例:構(gòu)造下面的推理證明前提：pq,r∨q,r∧s結(jié)論：p證明：①

p結(jié)論否定引入

②pq前提引入

③q①②假言推理

④r∨q前提引入

⑤r③④析取三段論

⑥r(nóng)∧s

前提引入

⑦r⑥化簡規(guī)則

⑧r∧r⑤⑦合取例:構(gòu)造下面的推理證明離散數(shù)學-數(shù)理邏輯課件

數(shù)理邏輯是用數(shù)學方法研究邏輯的學科。它的核心內(nèi)容為命題邏輯和謂詞邏輯。本章是命題邏輯的基礎(chǔ)知識，主要涉及命題邏輯的基本結(jié)構(gòu)以及自然語言的形式化方法。

本章中通過命題概念引出簡單命題，再通過5個常用的命題聯(lián)結(jié)詞構(gòu)成新的復(fù)合命題，從而構(gòu)成命題邏輯的理論基礎(chǔ)。由5個常用的命題聯(lián)結(jié)詞所定義的運算是數(shù)理邏輯中最基本最常用的邏輯運算。本章詳細介紹了這5個命題聯(lián)結(jié)詞的定義與真值表，并舉例說明了它們的使用方法。其中否定詞屬一元聯(lián)結(jié)詞，其它幾個均為二元聯(lián)結(jié)詞。聯(lián)結(jié)詞是由已有命題定義新命題的基本方法，是命題邏輯中最基本的內(nèi)容之一。本章小結(jié)數(shù)理邏輯是用數(shù)學方法研究邏輯的學科。它的核

命題邏輯中的許多問題都可以化為計算復(fù)合命題的真假值問題，因而真值表方法是命題邏輯中一個極為有力的工具。由命題公式列寫真值表以及下一章將介紹的由真值表列寫命題公式，都是學習命題邏輯需要熟練掌握的基本功。

聯(lián)結(jié)詞∧、∨、同構(gòu)成計算機的與門、或門和非門電路是相對應(yīng)的。下一章中還要講到的實際中常用的與非門和或非門電路則對應(yīng)著與非和或非聯(lián)結(jié)詞。從而命題邏輯是計算機硬件電路的表示、分析和設(shè)計的重要工具。也正是數(shù)理邏輯應(yīng)用于實際特別是應(yīng)用于計算機學科推動了數(shù)理邏輯的發(fā)展。

自然語句的形式化是研究命題邏輯的一個基本出發(fā)點和歸宿。本章在引入命題聯(lián)接詞后，對自然語句的形式化方法進行了介紹，不論是簡單自然語句還是較復(fù)雜的自然語句，都需要注意自然語言與命題邏輯符號表示的特點與差別。

命題邏輯中的許多問題都可以化為計算復(fù)合命題的第2章謂詞邏輯在命題邏輯中我們主要討論了命題和命題推理。在命題邏輯中，原子命題是不可再分解的。但是，命題之間還可能有些共同的性質(zhì)，可以作進一步的描述，同時命題邏輯的推理結(jié)構(gòu)還有很大的局限性，有些很簡單的論斷也不能用命題邏輯進行推證。例如：

“所有的人都是要死的。蘇格拉底是人。所以蘇格拉底是要死的。”這是著名的蘇格拉底三段論，它用命題推理無法完成這個簡單推證。

第2章謂詞邏輯在命題邏輯中我們主要討論了命題和命題推理。在用命題邏輯解釋邏輯學中著名的三段論.設(shè)p：所有的人都是要死的；q:蘇格拉底是人；r：蘇格拉底是要死。表示成復(fù)合命題有pqr由于上式不是重言式，所以不能由它判斷推理的正確性。究其原因，在于命題邏輯沒有研究命題內(nèi)部的邏輯結(jié)構(gòu)。事實上，原子命題實際上還可以作進一步地分解，分解出個體詞，謂詞和量詞，以達到表達出個體與總體的內(nèi)在聯(lián)系和數(shù)量關(guān)系，這就是一階邏輯所研究的內(nèi)容，本書稱為謂詞邏輯。謂詞邏輯在人工智能領(lǐng)域的知識表示、知識推理和機器證明等方面有重要的意義。用命題邏輯解釋邏輯學中著名的三段論.

在謂詞邏輯中，簡單命題分解成個體詞和謂詞兩部分。

個體詞是可以獨立存在的客體，它可以是具體事物或抽象的概念，如小張，房子，杭州，大米，思想，實數(shù)2等等。

謂詞是用來刻劃個體詞的性質(zhì)或事物之間的關(guān)系的詞。

在謂詞邏輯中，簡單命題分解成個體詞和謂詞兩部

我們知道，命題是具有真假意義的陳述句。從語法上分析，一個陳述句由主語和謂語兩部分組成。我們可以這樣做：為揭示命題內(nèi)部結(jié)構(gòu)及其不同命題的內(nèi)部結(jié)構(gòu)關(guān)系，就按照這兩部分對命題進行分析，并且把主語稱為個體或客體，把謂語稱為謂詞。我們知道，命題是具有真假意義的陳述句。從語法上１.個體詞和謂詞在原子命題中，所描述的對象稱為個體；用以描述個體的性質(zhì)或個體間關(guān)系的部分，稱為謂詞。個體：是指可以獨立存在的事物，它可以是具體的，也可以是抽象的，如張明，計算機，精神等。表示特定的個體，稱為個體常元，以a，b，c…或帶下標的ai，bi，ci…表示；表示不確定的個體，稱為個體變元，以x，y，z…或xi，yi，zi…表示。１.個體詞和謂詞一階邏輯命題符號化的基本概念：個體詞：可以獨立存在的具體的或抽象的客體個體常項：具體的或特定,一般用a,b,c,…表示個體變項：抽象的或泛指的，一般用x,y,z,…表示個體域：個體變項的取值范圍：全總個體域:宇宙間的一切事物組成個體域。一階邏輯命題符號化的基本概念：

謂詞:表示個體詞性質(zhì)或相互之間關(guān)系的詞

謂詞常項：F:…是人，F(xiàn)(a)：a是人

謂詞變項：F:…具有性質(zhì)F，F(xiàn)(x)：x具有性質(zhì)F

一元謂詞:表示事物的性質(zhì)多元謂詞(n元謂詞,n2):表示事物之間的關(guān)系，L(x,y)：x與y有關(guān)系L，L(x,y)：xy，…0元謂詞:不含個體變項的謂詞,即命題常項或命題變項

謂詞符號化:謂詞:表示個體詞性質(zhì)或相互之間關(guān)系的詞謂詞符號化:例:(1)

ln5是無理數(shù)；

(2)

牛啟飛比馬騰云高4cm；

(3)杭州位于北京和廣州之間。這是三個簡單命題,其中l(wèi)n5,牛啟飛，馬騰云，杭州，北京,廣州等都是個體詞,而“……是無理數(shù)”,“……比…高4cm”，“……位于……和……之間”等都是謂詞。

離散數(shù)學-數(shù)理邏輯課件

對于給定的命題，當用表示其個體的小寫字母和表示其謂詞的大寫字母來表示時，規(guī)定把小寫字母寫在大寫字母右側(cè)的圓括號()內(nèi)。例如，在命題“張明是位大學生”中，“張明”是個體，“是位大學生”是謂詞，它刻劃了“張明”的性質(zhì)。設(shè)P：是位大學生a：張明則“張明是位大學生”可表示為P(a)，或者寫成P(a)：張明是位大學生。對于給定的命題，當用表示其個體的小寫字母

又如，在命題“杭州位于北京和廣州之間”中，杭州、北京和廣州是三個個體，而“…位于…和…之間”是謂詞，它刻劃了杭州、北京和廣州之間的關(guān)系。設(shè)P：…位于…和…之間，

a：杭州，b：北京，c：廣州，則P(a，b，c)：杭州位于北京和廣州之間。注意：命題的謂詞形式中的個體出現(xiàn)的次序影響命題的真值，不是隨意變動，否則真值會有變化。如上述例子中，P(b,a,c)是假。又如，在命題“杭州位于北京和廣州之間”中，杭州、北京和如果個體常項a和個體變項x都具有性質(zhì)F，記作F(a)或F(x);個體常項a與b或個體變項x與y具有關(guān)系L,記作L(a,b)或L(x,y)。用F(a)表示a是無理數(shù)，其中a表示ln5，F(xiàn)表示的是“…是無理數(shù)”。則F(a)表示ln5是無理數(shù)。當F的含義不變時，則F(x)表示x是無理數(shù)，x是個體變項，F(xiàn)謂詞常項，F(xiàn)(x)不是命題，而是命題變項，F(xiàn)(a)是命題。用M(x,y,z)表示“z=x×y”，M(x,y,z)不是命題。

a表示3，b表示5，c表示15，M(a,b,c)表示“15＝3×5”。M(a,b,c)是命題，真值為1，若c=12，那么M(a,b,c)是命題，真值為0。如果個體常項a和個體變項x都具有性質(zhì)F，記作F(a)或F(x一般地，用

P(x1,x2,…,xn)

表示含有n個命題變項的n元謂詞，也可以看作是以個體域為定義域，以{0，1}為值域的n元函數(shù)或關(guān)系。

不帶任何個體變項的謂詞稱為0元謂詞一般地，用特別提醒：n元謂詞不是命題，只有其中的個體變元用特定個體或個體常元替代時，才能成為一個命題。但個體變元在哪些論域取特定的值，對命題的真值極有影響。例如：令S(x)：x是大學生。若x的論域為中醫(yī)藥大學信息技術(shù)學院的全體同學，則S(x)是真的；若x的論域是某中學的全體學生，則S(x)是假的；若x的論域是某劇場中的觀眾，且觀眾中有大學生也有非大學生的其它觀眾，則S(x)是真值是不確定的。特別提醒：n元謂詞不是命題，只有其中的個體變元用特定個體或個

注意，單獨的個體詞和謂詞不能構(gòu)成命題，將個體詞和謂詞分開不是命題。例將下列命題符號化：(1)丘華和李兵都是學生；(2)2既是偶數(shù)又是素數(shù)；(3)如果張華比黎明高，黎明比王宏高，則張華比王宏高。解

(1)設(shè)個體域是人的集合。

P(x)：:x是學生。

a：丘華

b：黎兵 該命題符號化為P(a)P(b)注意，單獨的個體詞和謂詞不能構(gòu)成命題，將個體詞(2)設(shè)個體域為正整數(shù)集合N＋。

F(x)：x是偶數(shù)，

G(x)：x是素數(shù)

a：2

該命題符號化為F(a)G(a)(3)

設(shè)個體域是人的集合。

L(x,y)：x比y高。

a：張華

b：黎明

c：王宏該命題符號化為L(a,b)L(b,c)L(a,c)

(2)設(shè)個體域為正整數(shù)集合N＋。例

令G(x，y)：“x高于y”，于是，G(x，y)是一個二元謂詞。將x代以個體“張三”，y代以個體“李四”，則G(張三，李四)就是命題：“張三高于李四”。隨便將x，y代以確定的個體，由G(x，y)都能得到一個命題。但是，G(x，y)不是命題，而是一個命題函數(shù)即謂詞。例

令G(x，y)：“x高于y”，于是，G(x，例用0元謂詞將命題符號化要求：先將它們在命題邏輯中符號化，再在一階邏輯中符號化墨西哥位于南美洲在命題邏輯中,設(shè)p:墨西哥位于南美洲符號化為p,這是真命題在一階邏輯中,設(shè)a：墨西哥，F(xiàn)(x)：x位于南美洲符號化為F(a)例用0元謂詞將命題符號化量詞利用n元謂詞和它的論域概念，有時還是不能用符號來很準確地表達某些命題。例如S(x)表示x是大學生，而x的個體域為某單位的職工，那么S(x)可表示某單位職工都是大學生，也可表示某單位有一些職工是大學生，為了避免理解上的歧義，需要引入用以刻劃“所有的”、“存在一些”等表示不同數(shù)量的詞，即量詞，其定義如下：量詞量詞:用來表示個體常項或變項之間數(shù)量關(guān)系的詞量詞分為兩種：全稱量詞：“一切”、“所有”、“凡”、“每一個”、“任意”等意，符號記作。如：x表示個體域內(nèi)所有的x。x稱為全稱量詞，稱x為指導(dǎo)變元。存在量詞：“有一個”、“有的”、“存在”、“至少有一個”等，符號記作。如:y表示個體域內(nèi)有的y。x稱為存在量詞，x稱為指導(dǎo)變元量詞:用來表示個體常項或變項之間數(shù)量關(guān)系的詞例將下列命題符號化(1)

每個母親都愛自己的孩子；(2)所有的人都呼吸；(3)有某些實數(shù)是有理數(shù)。解(1)設(shè)個體域是所有母親的集合。

M(x)：x表示愛自己的孩子；該命題符號化為（x）M(x)。

例將下列命題符號化(2)設(shè)個體域為人的集合。

H(x)：x表示要呼吸。 該命題符號化為（x）H(x)

或設(shè)個體域全總個體域，

M(x)：x是人。

H(x)：x表示要呼吸。 該命題符號化為（x）(M(x)H(x))(3)設(shè)個體域為數(shù)的集合。

R(x)：x表示實數(shù)

Q(x)：x表示有理數(shù)。 該命題符號化（x）(R(x)Q(x))。 (2)設(shè)個體域為人的集合。例用謂詞對下列命題符號化。（1）凡是人都呼吸。（2）有的人是左撇子。解當個體域為人類集合時：令F(x):x呼吸。G(x):x是左撇子。則（1）（x）F(x)(2)（x）G(x)

當個體域為全總個體域時：令F(x):x呼吸。G(x):x是左撇子；M(x):x是人。則(1)(x)(M(x)F(x))(2)(x)(M(x)∧

G(x))例用謂詞對下列命題符號化。說明：（1）在不同的個體域，同一命題的符號化形式可能相同也可能不同。（2）在不同的個體域，同一命題的真值可能相同也可能不同。（3）約定以后如不指定個體域，默認為全總個體域。說明：離散數(shù)學-數(shù)理邏輯課件離散數(shù)學-數(shù)理邏輯課件例：用謂詞將下列命題符號化。（1）所有的人都長頭發(fā)。（2）有的人吸煙。（3）沒有人登上過木星。（4）清華大學的學生未必都是高素質(zhì)的。解：令M(x):x是人。（1）令F(x):x長頭發(fā)。則符號化為：（x）(M(x)F(x))

例：用謂詞將下列命題符號化。（2）令S(x):x吸煙。則符號化為：（x）(M(x)∧S(x))

（3）令D(x):x登上過木星。則符號化為：

?（x）(M(x)∧D(x))

（4）令Q(x):x是清華大學的學生。

H(x):x是高素質(zhì)的。則符號化為：

?（x）(Q(x)H(x))（2）令S(x):x吸煙。則符號化為：例在一階邏輯中將下列命題符號化。（1）凡正數(shù)都大于零。（2）存在小于2的素數(shù)。（3）沒有不能表示成分數(shù)的有理數(shù)。（4）并不是所有參加考試的人都能取得好成績。解：（1）令F(x):x是正數(shù)。M(x):x大于零。則符號化為：(x)(F(x)M(x))

例在一階邏輯中將下列命題符號化。另外，全稱量詞和存在量詞不僅可以單獨出現(xiàn)，而且還可以以組合形式出現(xiàn)。下面我們給出幾個用二元謂詞進行命題符號化的例子。另外，全稱量詞和存在量詞不僅可以單獨出現(xiàn)，而且還可以以組合形離散數(shù)學-數(shù)理邏輯課件離散數(shù)學-數(shù)理邏輯課件謂詞公式

合式公式/謂詞公式/公式定義如下：（1）原子公式是合式公式。（2）若A是合式公式，則(?A)也是合式公式。（3）若A，B是合式公式,則(A∧B)，(A∨B)，(AB)，(AB)也是合式公式。（4）若A是合式公式，則(x)A,(x)A

，也是合式公式。(5)只有有限次應(yīng)用(1)-(4)構(gòu)成的符號串才是合式公式。謂詞公式合式公式/謂詞公式/公式定義如下：與命題公式一樣，約定最外層的括號可以省掉。但是，量詞后面有括號，則量詞后面的括號不能省略。與命題公式一樣，約定最外層的括號可以省掉。但是，量詞后面有括下面討論如何將一個用自然語言描述的命題符號化成謂詞公式，這在謂詞邏輯中是非常重要的，它是進行推理的基礎(chǔ)。下面討論如何將一個用自然語言描述的命題符號化成謂詞公式，這在離散數(shù)學-數(shù)理邏輯課件轄域、約束變元與自由變元

在公式（x）A和（x）A中，稱x為指導(dǎo)變元，A為相應(yīng)量詞的轄域。在（x）和（x）的轄域中，x的所有出現(xiàn)都稱為約束出現(xiàn)，這個變元成為約束變元；A中不是約束出現(xiàn)的其它變項均稱為是自由出現(xiàn)，這個變元成為自由變元。轄域、約束變元與自由變元在公式（x）A和（x）A中，稱例指出下列公式中指導(dǎo)變項、量詞的轄域、個體變項的自由出項和約束出現(xiàn)。（1）（x）(F(x)G(x,y))x是指導(dǎo)變元，量詞的轄域(F(x)G(x,y)),在轄域內(nèi)，x是約束出現(xiàn)兩次，y是自由出現(xiàn)一次。（2）（x）F(x,y)（y）G(x,y)x是指導(dǎo)變元，量詞的轄域F(x,y),在轄域內(nèi)，x是約束出現(xiàn)一次，y是自由出現(xiàn)一次;同時，y也是指導(dǎo)變元，量詞的轄域G(x,y),在轄域內(nèi)，y是約束出現(xiàn)一次，x是自由出現(xiàn)一次。（3）（x）（y）(F(x,y)∧G(y,z))∨（x）H(x,y,z)x、y是指導(dǎo)變元,對應(yīng)量詞、的轄域為(F(x,y)∧G(y,z)),其中x是約束出現(xiàn)一次,y是約束出現(xiàn)兩次,z是自由出現(xiàn)一次;后一個x也是指導(dǎo)變元,量詞的轄域為H(x,y,z),其中x是約束出現(xiàn)一次,y、z是自由出現(xiàn)一次.例指出下列公式中指導(dǎo)變項、量詞的轄域、個體離散數(shù)學-數(shù)理邏輯課件約束變元的換名與自由變元的替換在一個公式中，某個變元可以既是約束的，又是自由的。為了避免由于變元的約束與自由同時出現(xiàn)，引起概念上的混亂，可以對約束變元進行換名，原因是一個公式的約束變元和自由變元所使用的名稱符號是無關(guān)緊要的。約束變元的換名與自由變元的替換在一個公式中，某個變元可以既是對謂詞公式中的約束變元更改名稱符號，稱為約束變元換名。約束變元換名使得一個變元在一個公式中只呈現(xiàn)一種形式，即呈自由出現(xiàn)或呈約束出現(xiàn)。約束變元換名的規(guī)則為：

(1)換名時，更改的變元名稱范圍是量詞中的指導(dǎo)變元，以及該量詞轄域中該變元的所有出現(xiàn)。公式其余部分不便。

(2)換名時一定要更改為轄域中沒有出現(xiàn)的變元名稱。對謂詞公式中的約束變元更改名稱符號，稱為約束變元換名。注意：將量詞轄域中某個約束出現(xiàn)的個體變元及相應(yīng)指導(dǎo)變元，改成本轄域中未曾出現(xiàn)過的個體變元，其余不變。例（x）F(x)∧G(x,y)（z）F(z)∧G(x,y)(換名規(guī)則,將約束出現(xiàn)的x改成z)注意：將量詞轄域中某個約束出現(xiàn)的個體變元及相應(yīng)指導(dǎo)變元，改成

對公式中得自由變元也可以更改名稱符號，這種更改叫做替換。自由變元的替換規(guī)則是：

(1)對于公式中得自由變元，可以做替換，應(yīng)該注意需對公式中出現(xiàn)該自由變元得每一處都進行替換。

(2)用以替換的變元與原公式中所有變元得名稱不能相同。對某自由出現(xiàn)的個體變元可用個體常元或用與原子公式中所有個體變元不同的個體變元去代入，且處處代入。例（x）F(x)∧G(x,y)（x）F(x)∧G(z,y)(代替規(guī)則,將自由出現(xiàn)的x改成z)對公式中得自由變元也可以更改名稱符號，這種更改叫做替換。謂詞公式的賦值與分類在謂詞公式中常包含命題變元和客體變元，當客體變元由確定的客體取代，命題變元用確定的命題所取代或指派一真值時，一個謂詞公式就有確定的真值T和F。下面我們討論謂詞公式的賦值。

謂詞公式的賦值與分類在謂詞公式中常包含命題變元和客體變元，當離散數(shù)學-數(shù)理邏輯課件離散數(shù)學-數(shù)理邏輯課件謂詞公式的分類

設(shè)A為一謂詞公式，若A在任何賦值下均為真，則稱A為永真式。若A在任何賦值下均為假則稱A為矛盾式。若至少存在一個賦值使A為真則稱A是可滿足式。謂詞公式的分類設(shè)A為一謂詞公式，離散數(shù)學-數(shù)理邏輯課件離散數(shù)學-數(shù)理邏輯課件謂詞公式的等值演算

已經(jīng)得證的重要等值式：謂詞公式的等值演算已經(jīng)得證的重要等值式：離散數(shù)學-數(shù)理邏輯課件離散數(shù)學-數(shù)理邏輯課件

全稱量詞對合取運算滿足分配律，存在量詞對析取滿足分配律。但是全稱量詞對析取運算是否滿足分配律？存在量詞對合取運算是否滿足分配律？答案是否定的。但是：全稱量詞對合取運算滿足分配律，存在量詞對析取滿足分配律。離散數(shù)學-數(shù)理邏輯課件離散數(shù)學-數(shù)理邏輯課件謂詞公式的前束范式謂詞公式的前束范式定理任何一個謂詞公式都可以轉(zhuǎn)化為與之等價的前束范式。謂詞公式化為前束范式主要通過2.4節(jié)的等價公式，換名規(guī)則，替換規(guī)則和置換原理等。注意：一個謂詞公式的前束范式不一定惟一。定理任何一個謂詞公式都可以轉(zhuǎn)化為與之等價的前束范式。注意離散數(shù)學-數(shù)理邏輯課件離散數(shù)學-數(shù)理邏輯課件謂詞演算的推理理論謂詞演算的推理理論推理定律的來源

第一組：命題推理定律的代換實例。推理定律的來源第二組：基本等價公式生成的推理定律。第二組：基本等價公式生成的推理定律。

第三組：幾個非等價的重要推理定律。

第三組：幾個非等價的重要推理定律。第四組：消、添量詞定律。第四組：消、添量詞定律。離散數(shù)學-數(shù)理邏輯課件總的來說，我們常見的推理規(guī)則如下：前提引入規(guī)則；（相當于已知條件）結(jié)論引入規(guī)則；（相當于已證的結(jié)論）置換規(guī)則；（相當于等價公式）假言推理規(guī)則；附加規(guī)則；化簡規(guī)則；拒取式規(guī)則