《離散數(shù)學(xué)及其應(yīng)用》全套教學(xué)課件

離散數(shù)學(xué)及其應(yīng)用全套可編輯PPT課件課程內(nèi)容第1篇數(shù)理邏輯第1章命題邏輯第2章謂詞邏輯第2篇結(jié)合論第3章集合與關(guān)系第4章函數(shù)課程內(nèi)容第3篇代數(shù)結(jié)構(gòu)第5章代數(shù)結(jié)構(gòu)第6章格與布爾代數(shù)第4篇圖論第7章圖第1篇數(shù)理邏輯全套可編輯PPT課件數(shù)理邏輯邏輯學(xué)分為辨證邏輯與形式邏輯兩種。用數(shù)學(xué)方法來研究推理的規(guī)律稱為數(shù)理邏輯

現(xiàn)代數(shù)理邏輯分為四論、兩演算四論：證明論，遞歸論（它們與形式語言語法有關(guān)），模型論，公理化集合論（它們與形式語言的語義有關(guān)）。兩演算：命題演算、謂詞演算

第1章命題邏輯

1.1命題及其表示1.2邏輯聯(lián)結(jié)詞全套可編輯PPT課件第1章命題邏輯－＞1.1命題及其表示

定義1.1.1能夠判斷真假的陳述句稱為命題（Proposition）。命題的判斷結(jié)果稱為命題的真值，常用1（或大寫字母T）表示真，用0（或大寫字母F）表示假。凡是與事實相符的陳述句即真值為真的命題稱為真命題，而與事實不符合的陳述句即真值為假的命題稱為假命題。從這個定義可以看出命題有兩層含義：(1)命題是陳述句。其他的語句，如疑問句、祈使句、感嘆句均不是命題；(2)這個陳述句表示的內(nèi)容可以分辨真假，而且不是真就是假，不能不真也不假，也不能既真又假。第1章命題邏輯－＞1.1命題及其表示例1：判斷下列語句是否為命題，若是并指出其真值。（1）北京是中國的首都。真命題（2）2是偶數(shù)且3也是偶數(shù)。假命題（3）2+2=5。假命題（4）請勿吸煙!不是命題（5）烏鴉是黑色的嗎？ 不是命題（6）這個小男孩多勇敢?。?不是命題（7）地球外的星球上存在生物。是命題，真假值客觀存在（8）1+101=110。二進制中為真命題，二進制中為假命題（9）x+y=5。不是命題（10）我正在說謊。悖論，不是命題第1章命題邏輯－＞1.1命題及其表示定義1.1.2不能被分解為更簡單的陳述語句的命題稱為原子命題(SimpleProposition)。由兩個或兩個以上原子命題通過聯(lián)結(jié)詞組合而成的命題稱為復(fù)合命題(CompoundProposition)。例1.1.1中的命題(1)(3)(7)(8)為原子命題，而命題(2)是復(fù)合命題，是由“2是偶數(shù)?！迸c“3是偶數(shù)?！眱蓚€原子命題由聯(lián)結(jié)詞“且”組成的，該命題的真值不僅依賴于這兩個組成它的命題，而且還依賴于這個聯(lián)結(jié)詞的意義。像這樣的聯(lián)結(jié)詞稱為邏輯聯(lián)結(jié)詞（logicalconnectives）。約定用大寫字母P，Q，R，S等表示原子命題（為了避免與真值T及F混淆，建議不用T及F表示原子命題）。例如，用P表示“北京是中國的首都”，Q表示“5可以被2整除”等。第1章命題邏輯－＞1.1命題及其表示定義1.1.3表示原子命題的符號稱為命題標(biāo)識符(Identifier)。定義1.1.4

用一個確定的命題代入一個命題標(biāo)識符（如P），稱為對P進行指派（賦值，或解釋）。如果命題標(biāo)識符P代表命題常元則意味它是某個具體原子命題的符號化，如果P代表命題變元則意味著它可指代任何具體原子命題。本書中如果沒有特別指明，通常來說命題標(biāo)識符P等是指命題變元，即可指代任何原子命題。第1章命題邏輯－＞1.2邏輯聯(lián)結(jié)詞

定義1.2.1

設(shè)P表示一個命題，P的否定(Negation)是一個新的命題，記為

P（讀作非P）。規(guī)定若P為1，則

P為0；若P為0，則

P為1。

P的取值情況依賴于P的取值情況，真值情況見表1-1。表1-1聯(lián)結(jié)詞“

”的定義P

P1001第1章命題邏輯－＞1.2邏輯聯(lián)結(jié)詞定義1.2.2

設(shè)P、Q為兩個命題，P和Q的合取(Conjunction)是一個復(fù)合命題，記為P∧Q（讀作P與Q），稱為P與Q的合取式。規(guī)定P與Q同時為1時，P∧Q為1，其余情況下，P∧Q均為0。日常用語中的“與”、“和”、“也”、“并且”、“而且”、“既…，又…”、“一面…，一面…”等可用合取詞表示。聯(lián)結(jié)詞“∧”的定義見表1-2。PQP∧Q000010100111第1章命題邏輯－＞1.2邏輯聯(lián)結(jié)詞定義1.2.3

設(shè)P、Q為兩個命題，P和Q的析取(Disjunction)是一個復(fù)合命題，記為P∨Q（讀作P或Q），稱為P與Q的析取式。規(guī)定當(dāng)且僅當(dāng)P與Q同時為0時，P∨Q為0，否則P∨Q均為1。日常用語中的“或”，“要么…要么…”等可用析取詞表示。表1-3聯(lián)結(jié)詞“∨”的定義PQP∨Q000011101111第1章命題邏輯－＞1.2邏輯聯(lián)結(jié)詞定義1.2.4

設(shè)P、Q為兩個命題，P和Q的條件(Conditional)命題是一個復(fù)合命題，記為P→Q（讀作若P則Q），其中P稱為條件的前件，Q稱為條件的后件。規(guī)定當(dāng)且僅當(dāng)前件P為1，后件Q為0時，P→Q為0，否則P→Q均為1。日常用語中的“若…則…”，“如果…那么…”，“只有…才…”等可用條件詞表示。表1-4聯(lián)結(jié)詞“→”的定義PQP→Q001011100111第1章命題邏輯－＞1.2邏輯聯(lián)結(jié)詞定義1.2.5

設(shè)P、Q為兩個命題，其復(fù)合命題P

Q稱為雙條件(Biconditional)命題，P

Q讀作P當(dāng)且僅當(dāng)Q。規(guī)定當(dāng)且僅當(dāng)P與Q真值相同時，P

Q為1，否則P

Q均為0。表1-5聯(lián)結(jié)詞“

”的定義PQP

Q001010100111第1章命題邏輯－＞1.3命題公式與翻譯定義1.3.1

命題公式歸納定義如下：（1）單個命題變元是命題公式；（2）如果A是命題公式，則┐A也是命題公式；（3）如果A和B是命題公式，則(A∧B)，(A∨B)，(A→B)，(A

B)均是命題公式；（4）當(dāng)且僅當(dāng)能夠有限次地應(yīng)用（1）、（2）、（3）所得到的包含命題變元、聯(lián)結(jié)詞和括號的符號串是命題公式（又稱為合式公式，或簡稱為公式）。定義是以遞歸的形式給出的，其中（1）稱為基礎(chǔ)，（2）、（3）稱為歸納，（4）稱為界限。定義中的符號A,B不同于具體公式里的P、Q、R等符號（一般P、Q、R來表示原子命題標(biāo)識符），它可以用來表示任意的命題公式。第1章命題邏輯－＞1.3命題公式與翻譯命題公式是沒有真假的,如果把公式中的命題變元代以確定的命題命題，則該公式便是一個命題，才有確定的真值。因此，對復(fù)合命題的研究可化為對公式的研究，今后我們將以公式為主要研究對象。為了減少命題公式中使用括號的數(shù)量，規(guī)定：（1）邏輯聯(lián)結(jié)詞的優(yōu)先級別由高到低依次為┐、∧、∨、→、

。（2）具有相同級別的聯(lián)結(jié)詞，按出現(xiàn)的先后次序進行計算，括號可以省略。（3）命題公式的最外層括號可以省去。例1.3.1

（P

Q）

R也可以寫成P

Q

R，（P

Q）

R也可寫成P

Q

R，（（P

Q）

R）也可寫成（P

Q）

R，而P

（Q

R）中的括號不能省去。定義1.3.2

設(shè)B是命題公式A的一部分，且B也是命題公式，則稱B為A的子公式。第1章命題邏輯－＞1.3命題公式與翻譯把一個文字描述的命題相應(yīng)地寫成由命題標(biāo)識符、邏輯聯(lián)結(jié)詞和圓括號表示的命題形式稱為命題的符號化或翻譯。命題符號化的一般步驟：（1）明確給定命題的含義；（2）找出命題中的各原子命題，分別符號化。（3）使用合適的邏輯聯(lián)結(jié)詞，將原子命題分別連接起來，組成復(fù)合命題的符號化形式。把命題符號化，是不管具體內(nèi)容而突出思維形式的一種方法。注意在命題符號化時，要正確地分析和理解自然語言命題，不能僅憑文字的字面意思進行翻譯。第1章命題邏輯－＞1.3命題公式與翻譯例1.3.2

將下列用自然語言描述的命題符號化。（1）我和他既是弟兄又是同學(xué)。

解

令P：我和他是弟兄；Q：我和他是同學(xué)，則該語句可符號化為P∧Q。

（2）我和你之間至少有一個要去海南島。

解

令P：我去海南島；Q：你去海南島，則該語句可符號化為P∨Q。

（3）如果他沒來見你，那么他或者是生病了，或者是不在本地。

解

令P：他來見你；Q：他生??；R：他在本地，則該語句可符號化為┐P→(Q∨┐R)。

（4）n是偶數(shù)當(dāng)且僅當(dāng)它能被2整除。

解

令P：n是偶數(shù)；Q：n能被2整除，則該語句可符號化為P

Q。第1章命題邏輯－＞1.3命題公式與翻譯（5）只有你走，我才留下。解這個命題的意義也可以理解為：如果我留下了，那么你一定走了。令P：你走。Q：我留下。則該語句可符號化為：Q→P。與原命題類似的命題如：僅當(dāng)你走我才留下。我留下僅當(dāng)你走。當(dāng)我留下你得走。（6）僅當(dāng)天不下雨且我有時間，我才上街。解設(shè)P：天下雨。Q：我有時間。R：我上街。該語句可符號化為：R→（┐P∧Q）。第1章命題邏輯－＞1.3命題公式與翻譯（7）你將失敗，除非你努力。解這個命題的意義可以理解為：如果你不努力，那么你將失敗。令P：你努力。Q：你失敗。則該語句可符號化為：┐P→Q。含有“除非”的命題，“非…”是充分條件，譯成條件命題時，“非…”是條件的前件。（8）A中沒有元素，A就是空集。解令P：A中有元素。Q：A是空集。則該語句可符號化為：┐P

Q。（9）張三與李四是表兄弟。解此命題是一個原子命題，“…與…是表兄弟?！北硎緝蓚€對象之間的關(guān)系?！皬埲潜硇值堋！奔啊袄钏氖潜硇值?。”都不是命題。所以上述命題只能符號化為P的形式。其中P：張三與李四是表兄弟。第1章命題邏輯－＞1.4真值表與命題公式分類

定義1.4.1

設(shè)P1，P2，，…，Pn是出現(xiàn)在命題公式中的全部命題變元，給P1，P2，，…，Pn各指定一個真值，稱為對公式的一個賦值（或解釋或真值指派）。若指定的一組值使公式的真值為1，則這組值稱為公式的成真賦值。若指定的一組值使公式的真值為0，則這組值稱為公式的成假賦值。定義1.4.2

設(shè)A是含有n個命題變元的命題公式，將命題公式A在所有賦值之下取值的情況匯列成表，稱為命題公式A的真值表。為方便構(gòu)造真值表，特約定如下：

①命題變元按字典序排列。

②對每組賦值，以二進制數(shù)從小到大或從大到小順序列出。

③若公式較復(fù)雜，可先列出各子公式的真值(若有括號，則應(yīng)從里層向外層展開)，最后列出所求公式的真值。第1章命題邏輯－＞1.4真值表與命題公式分類

例1.4.1

利用真值表求命題公式

(P→(Q

R))的成真賦值和成假賦值。PQRQ

RP→(Q

R)

(P→(QR))000011110011001101010101011101111111011100001000第1章命題邏輯－＞1.4真值表與命題公式分類例1.4.2

利用真值表求命題公式

（P→Q）

Q的成真賦值和成假賦值。PQP→Q

（P→Q）

（P→Q）Q00100011001001011100第1章命題邏輯－＞1.4真值表與命題公式分類利用真值表求命題公式

（P

Q）

（

P

Q）的成真賦值和成假賦值。PQP

Q

（PQ）

P

Q

（PQ）（

P

Q）000111010111100111111001第1章命題邏輯－＞1.4真值表與命題公式分類定義1.4.3

設(shè)A為任一命題公式。

（1）若對公式A的命題變元所有賦值均是成真指派，則公式A稱為重言式或永真式；

（2）若對公式A的命題變元所有賦值均是成假指派，則公式A稱為矛盾式或永假式；

（3）若公式A中至少有一個成真賦值，則公式A稱為可滿足式。

從定義不難看出以下幾點：

1）重言式一定是可滿足式，但反之不真。因而，若公式A是可滿足式，且它至少存在一個成假指派，則稱A為非重言式的可滿足式。

2）真值表可用來判斷公式的類型：

①若真值表最后一列全為1，則公式為重言式；

②若真值表最后一列全為0，則公式為矛盾式；

③若真值表最后一列中至少有一個1，則公式為可滿足式。第1章命題邏輯－＞1.4真值表與命題公式分類例1.4.4

判斷下列公式的類型。

（1）(P

Q)→Q 重言式（2）(Q→P)

(?P

Q) 矛盾式(3)(P

?Q)→(?P

Q

R) 可滿足式從以上的討論可知，真值表不但能準(zhǔn)確地給出公式的成真賦值和成假賦值，而且能判斷公式的類型。但當(dāng)命題變元較多時，計算量大，在后面的章節(jié)中還要介紹其他的方法。第1章命題邏輯－＞1.5等價公式與蘊含式

定義1.5.1

給定兩個命題公式A和B，設(shè)P1，P2，…，Pn是出現(xiàn)在命題公式A和B中的全部命題變元，若對所有命題變元P1，P2，…，Pn任一組賦值，公式A和B的真值都對應(yīng)相同，則稱公式A與B等價或邏輯相等(Equivalence)，記作式A

B。定理1.5.1

對命題公式A和B，A

B當(dāng)且僅當(dāng)A

B是重言式。證明若A

B是重言式，則在任一解釋下，A

B的真值都為真。依A

B的定義知，當(dāng)A

B為真時，A和B必有相同的真值。于是，在任一解釋下，A和B都有相同的真值，從而有A

B。反過來，若A

B，則在任一解釋下A和B都有相同的真值，依A

B的定義知，此時A

B為真，從而A

B是重言式。第1章命題邏輯－＞1.5等價公式與蘊含式需要注意的是，“

”不是邏輯聯(lián)結(jié)詞，因而“A

B”不是命題公式，只是表示兩個命題公式之間的一種等價關(guān)系，即若A

B，A和B沒有本質(zhì)上的區(qū)別，最多只是A和B具有不同的形式而已?！?/p>

”具有如下的性質(zhì)：（1）自反性：A

A。（2）對稱性：若A

B，則B

A。（3）傳遞性：若A

B，B

C，則A

C。給定n個命題變元，根據(jù)公式的形成規(guī)則，可以形成許多個形式各異的公式，但是有很多形式不同的公式具有相同的真值表。因此引入公式等價的概念，其目的就是將復(fù)雜的公式簡化。第1章命題邏輯－＞1.5等價公式與蘊含式下面介紹兩種證明公式等價的方法。1．真值表法由公式等價的定義可知，利用真值表可以判斷任何兩個公式是否等價。例1.5.1

證明P

Q

(PQ)(QP)證明命題公式PQ與(PQ)(QP)的真值表見表1-12。由表1-12可知，在任意賦值下PQ與(PQ)(QP)兩者的真值均對應(yīng)相同。因此

P

Q

(PQ)(QP)表1-12PQ與(PQ)(QP)的真值表PQP

QQ

P(P

Q)(QP)P

Q001111011000100100111111第1章命題邏輯－＞1.5等價公式與蘊含式常用等價式（1）雙重否定律：

P

P（2）結(jié)合律：(P

Q)

R

P

(Q

R)，(P

Q)

R

P

(Q

R)，(P

Q)

R

P

(Q

R)（3）交換律：P

Q

Q

P，P

Q

Q

P，P

Q

Q

P（4）分配律：P

(Q

R)

(P

Q)

(P

R)，P

(Q

R)

(P

Q)

(P

R)（5）冪等律：P

P

P，P

P

P（6）吸收律：P

(P

Q)

P，P

(P

Q)

P（7）德.摩根律：

(P

Q)

P

Q，

(P

Q)

P

Q（8）同一律：P

0

P，P

1

P（9）零律：P

1

1，P

0

0第1章命題邏輯－＞1.5等價公式與蘊含式常用等價式（10）否定律：P

P

1，P

P

0（11）蘊含律：P

Q

P

Q（12）等價律：P

Q

(P

Q)

(Q

P)

P

Q（13）輸出律：(P∧Q)

R

P

(Q

R)（14）歸謬律：(P

Q)∧(P

Q)

P（15）逆反律：P

Q

Q

P第1章命題邏輯－＞1.5等價公式與蘊含式2．等值演算法定理1.5.2（代入規(guī)則）在一個永真式A中，任何一個原子命題變元R出現(xiàn)的每一處用另一個公式代入，所得的公式B仍為永真式。證明：因為永真式對于任何指派，其真值都是1，與每個命題變元指派的真假無關(guān)，所以，用一個命題公式代入到原子命題變元R出現(xiàn)的每一處，所得到的命題公式的真值仍為1。定理1.5.3（置換規(guī)則）設(shè)X是命題公式A的一個子公式，若X

Y，如果將公式中的X用Y來置換，則所得到的公式B與公式A等價，即A

B。證明：因為X

Y，所以在相應(yīng)變元的任一種指派情況下，X與Y的真值相同，故以Y取代X后，公式B與公式A在相應(yīng)的指派情況下真值也必相同，因此A

B。第1章命題邏輯－＞1.5等價公式與蘊含式有了上述的15組等價公式及代入規(guī)則和置換規(guī)則后，就可以推演出更多的等價式。由已知等價式推出另外一些等價式的過程稱為等值演算(EquivalentCalculation)。例1.5.3

證明下列公式等價。（1）(P

Q)

R

P

(Q

R)（2）(P

Q)

(

P

Q)

(P

Q)

(P

Q)證明（1）(P

Q)

R

P

Q

R

P

(

Q

R)

P

(Q

R)

P

(Q

R)（2）(P

Q)

(

P

Q)

((P

Q)

P)

((P

Q)

Q)

(P

P)

(

Q

P)

(P

Q)

(

Q

Q)

1

(

P

Q)

(P

Q)

1

(P

Q)

(

P

Q)

(P

Q)

(P

Q)第1章命題邏輯－＞1.5等價公式與蘊含式等值演算還可以用來解決常見的推理題。例1.5.4

某件事情是甲、乙、丙、丁4人中某一個人干的。詢問4人后回答如下：（1）甲說是丙干的；（2）乙說我沒干；（3）丙說甲講的不符合事實；（4）丁說是甲干的。若其中3人說的是真話，一人說假話，問是誰干的？例1.5.5A、B、C、D4人進行百米競賽，觀眾甲、乙、丙對比賽的結(jié)果進行預(yù)測。甲：C第一，B第二；乙：C第二，D第三；丙：A第二，D第四。比賽結(jié)束后發(fā)現(xiàn)甲、乙、丙每個人的預(yù)測結(jié)果都各對一半。試問實際名次如何（假如無并列者）？第1章命題邏輯－＞1.5等價公式與蘊含式蘊含式定義1.5.2

設(shè)A、B為兩個命題公式，若A

B為重言式，則稱“A蘊含(Implication)B”，記作A

B。蘊含關(guān)系具有如下的性質(zhì)：(1)A為重言式，A

B，則B必為重言式；(2)自反性A

A；(3)反對稱性若A

B且B

A則A

B；(4)傳遞性若A

B且B

C則A

C；(5)若A

B且A

C則A

B

C。(6)若A

B且C

B，故A

C

B。第1章命題邏輯－＞1.5等價公式與蘊含式定理1.5.4A

B的充分必要條件是A

B且B

A。證明：若A

B，則A

B為重言式，而A

B

(A

B)

(B

A)，故A

B且B

A均為重言式，即A

B且B

A。反之，若A

B且B

A，則A

B且B

A均為重言式，于是(A

B)

(B

A)為重言式，即A

B為重言式，故A

B。要證明A

B，只需證明A

B為重言式即可。因此，前面介紹的真值表法和等值演算法均可應(yīng)用。第1章命題邏輯－＞1.5等價公式與蘊含式證明A

B的各種方法1．真值表法2．等值演算法3．邏輯分析法邏輯分析法包括以下兩種形式：（1）肯定前件法：假定前件A為真，推出后件B為真，則A

B。（2）否定后件法：假定后件B為假，推出前件A為假，則A

B。理由是：對于條件式A

B，根據(jù)條件聯(lián)結(jié)詞的運算規(guī)則可知：只有前件A為真，后件B為假時A

B為假，其余情況均為真。第1章命題邏輯－＞1.5等價公式與蘊含式因此有（1）若從假設(shè)前件A為真時能推導(dǎo)出后件B一定也為真，說明無論前件A為真為假，A

B都為真，即A

B為重言式，也即A

B。（2）若從假設(shè)后件B為假時能推導(dǎo)出前件A一定也為真，說明無論前件A為真為假，A

B都為真，即A

B為重言式，也即A

B。

第1章命題邏輯－＞1.5等價公式與蘊含式例1.5.8

邏輯證明下列蘊含式。（1）

Q

(P

Q)

P（2）P

(P

Q)

Q證明（1）假設(shè)前件

Q

(P

Q)為真，則

Q為真，P

Q為真；由此有Q為假，P為真。因此

Q

(P

Q)

P。（2）假設(shè)后件Q為假，若P為真，則P

Q為假，有P

(P

Q)為假。若P為假，則P

Q為真，有P

(P

Q)為假。綜上，若后件Q為假，無論P為真還是假，前件P

(P

Q)均為假。因此P

(P

Q)

Q。第1章命題邏輯－＞1.5等價公式與蘊含式常用的蘊含式(1)P

Q

P，P

Q

Q；(2)P

P

Q，Q

P

Q；(3)

P

P→Q；(4)Q

P→Q；(5)

(P→Q)

P；

(P→Q)

Q；(6)P

(P→Q)

Q；(7)

Q

(P→Q)

P；(8)

P

(P

Q)

Q；(9)(P→Q)

(Q→R)

P→R；(10)(P

Q)

(P→R)

(Q→R)

R；(11)(P→Q)

(R→S)

(P

R)→(Q

S)；(12)(P?Q)

(Q?R)

P?R第1章命題邏輯－＞1.7對偶與范式

對偶式定義1.7.1

在只含有邏輯聯(lián)結(jié)詞

，

，

的命題公式A中，若把將

換成

，

換成

，如果A中有T（或1）或者F（或0）就分別換成F（或0）或T（或1），所得到的新公式A*稱為A的對偶式(DualisticFormula)。顯然A*與A互為對偶式。例1.7.1寫出下列公式的對偶式。(1)(P→R)→(P

Q→R

Q)；(2)(P

Q)

F；(3)P

(Q

T)解

(1)令A(yù)=(P→R)→(P

Q→R

Q)，則A=

(

P

R)

(

(P

Q)

R

Q)。故A*=

(

P

R)

(

(P

Q)

R

Q)。(2)，(3)中二式的對偶式分別為(P

Q)

T，P

(Q

F)。第1章命題邏輯－＞1.7對偶與范式對偶原理

定理1.7.1設(shè)P1，P2，…，Pn

是公式A和A*中出現(xiàn)的原子命題變元，現(xiàn)采用函數(shù)記法分別為A(P1，P2，…，Pn)，A*(P1，P2，…，Pn)，則

A(P1，P2，…，Pn)

A*(

P1，

P2，…，

Pn)，A(

P1，

P2，…，

Pn)

A*(P1，P2，…，Pn)。定理1.7.2（對偶原理）設(shè)A，B為合式命題公式，若A

B，則A*

B*。證明：設(shè)P1，P2，…，Pn

是出現(xiàn)在A，B中的原子命題變元。因A(P1，P2，…，Pn)

B(P1，P2，…，Pn)，故A(P1，P2，…，Pn)

B(P1，P2，…，Pn)是重言式。即：A（

P1，

P2，…，

Pn）

B(

P1，

P2，…，

Pn)是重言式，故A(

P1，

P2，…，

Pn)

B(

P1，

P2，…，

Pn)。由定理1.7.1有A(

P1，

P2，…，

Pn)

A*(P1，P2，…，Pn)，B(

P1，

P2，…，

Pn)

B*(P1，P2，…，Pn)，由合式公式的等價具有傳遞性，可得

A*（P1，P2，…，Pn

）

B*(P1，P2，…，Pn)。從而A*

B*。第1章命題邏輯－＞1.7對偶與范式命題公式的范式

1．簡單析取式與簡單合取式定義1.7.2

單個的命題變元及其否定形式稱為文字。如P，

Q等。定義1.7.3

僅由有限個文字組成的析取式稱為簡單析取式。僅由有限個文字組成的合取式稱為簡單合取式。例如P

Q，P

Q，

P

Q，

P

Q，P，

Q等都是簡單析取式；P

Q，P

Q，

P

Q，

P

Q，P，

Q等都是簡單合取式。一個文字既是簡單析取式，又是簡單合取式。定理1.7.3簡單析取式是重言式當(dāng)且僅當(dāng)它同時含有某個命題變元及其否定形式。定理1.7.4簡單合取式是矛盾式當(dāng)且僅當(dāng)它同時含有某個命題變元及其否定形式。第1章命題邏輯－＞1.7對偶與范式2．析取范式與合取范式定義1.7.4由有限個簡單合取式組成的析取式稱為析取范式（DisjunctiveNormalForm）。亦即該公式具有形式A1

A2…

An，其中Ai(i=1,2,…,n)為簡單合取式。由有限個簡單析取式組成的合取式稱為合取范式（ConjunctiveNormalForm）。亦即該公式具有形式B1

B2…

Bm，其中Bj(j=1,2,…,m)為簡單析取式。析取范式與合取范式統(tǒng)稱為范式。定理1.7.5（范式存在定理）任何一個命題公式都存在著與之等價的析取范式和合取范式。第1章命題邏輯－＞1.7對偶與范式求任一公式的析取范式和合取范式的步驟：（1）利用蘊含等值式和等價等值式消去除

，

，

以外公式中出現(xiàn)的所有邏輯聯(lián)結(jié)詞。（2）利用德摩根律和雙重否定律將聯(lián)結(jié)詞“

”向內(nèi)深入，使之只作用于命題變元；（3）利用分配律、結(jié)合律將公式轉(zhuǎn)化為合取范式或析取范式。例1.7.4求

P→(P→Q)的合取和析取范式。解：

P→(P→Q)

P

(

P

Q)

P

(

P

Q)（合析取范式）

(P

P)

Q

T

Q（合析取范式）

T

P

P。第1章命題邏輯－＞1.7對偶與范式3．范式的應(yīng)用利用析取范式和合取范式可以判定一個命題公式是重言式還是矛盾式。定理1.7.6

一個析取范式是矛盾式當(dāng)且僅當(dāng)它的每個簡單合取式都是矛盾式。一個合取范式是重言式當(dāng)且僅當(dāng)它的每個簡單析取式都是重言式。第1章命題邏輯－＞1.7對偶與范式命題公式的主析取范式和主合取范式

1．主析取范式定義1.7.5

在含有n個命題變元的簡單合取式中，若每個命題變元與其否定不同時存在，而二者之一必出現(xiàn)且僅出現(xiàn)一次，且第i個命題變元或其否定出現(xiàn)在從左算起的第i位上(若命題變元無下標(biāo),則按字典順序排序)，則稱該簡單合取式為極小項。第1章命題邏輯－＞1.7對偶與范式表1-20兩個命題變元P和Q生成的4個極小項的真值表m（二進制）m00m01m10m11PQ

P

Q

P

QP

QP

Q001000010100100010110001m（十進制）m0m1m2m3第1章命題邏輯－＞1.7對偶與范式由真值表可得到極小項具有如下性質(zhì)：（1）各極小項的真值表都不相同。（2）每個極小項當(dāng)其真值指派與對應(yīng)的二進制編碼相同時，其真值為真，在其余2n-1種指派情況下，其真值均為假。（3）任意兩個極小項的合取式是矛盾式。例如m0

m1

(

P

Q)

(

P

Q)

0。（4）全體極小項的析取式為永真式。定義1.7.6由若干個不同的極小項組成的析取式稱為主析取范式(ThePrincipalDisjunctiveNormalForm)。與公式等價的主析取范式稱為的主析取范式。定理1.7.7任意含n個命題變元的非永假式命題公式都存在著與之等價的主析取范式，并且其主析取范式是唯一的。第1章命題邏輯－＞1.7對偶與范式一個命題公式的主析取范式可通過兩種方法求得，一是由公式的真值表得出，即真值表法；另一是由基本等價公式推出，即等值演算法。（1）真值表法定理1.7.8

在真值表中，命題公式A的真值為真的賦值所對應(yīng)的極小項的析取即為命題公式A的主析取范式。利用真值表法求主析取范式的基本步驟為：（1）列出公式的真值表。（2）將真值表中的最后一列中的1的賦值所對應(yīng)的極小項寫出。（3）將這些極小項進行析取。第1章命題邏輯－＞1.7對偶與范式例1.7.8利用真值表法求

（PQ）的主析取范式。解（PQ）的真值表見表1-21。表1-21

（PQ）的真值表PQ

（PQ）001011101110從表1-21中可以看出，該公式在其真值表的00行、01行、10行處取真值1，所以

（PQ）

m0

m1

m2

（

P

Q）（

P

Q）（PQ）。第1章命題邏輯－＞1.7對偶與范式例1.7.9用真值表法求

(P

Q)

R的主析取范式。解(PQ)

R的真值表見表1-22。表1-22(P

Q)

R的真值表PQRP

Q(P

Q)

R0000000101010000110110000

101011101111111從表1-22中可以看出，該公式在其真值表的001行、011行、101行、110行和111行處取真值1，所以(P

Q)

R

m1

m3

m5

m6

m7

(

P

Q

R)

(

P

Q

R)

(P

Q

R)

(P

Q

R)

(P

Q

R)。第1章命題邏輯－＞1.7對偶與范式（2）等值演算法除了用真值表法來求一個命題公式的主析取范式外，還可以利用公式的等值演算方法來推導(dǎo)。具體的求解步驟如下：（1）利用蘊含等值式和等價等值式消去公式中的聯(lián)結(jié)詞“→”和“

”；（2）利用德摩根律和雙重否定律將聯(lián)結(jié)詞“

”向內(nèi)深入，使之只作用于命題變元；（3）利用分配律將公式化為析取范式；（4）利用同一律消去矛盾的簡單合取式；（5）利用等冪律消去相同的簡單合取式以及簡單合取式中相同的合取項；（6）利用同一律、分配律將不包含某一命題變元的簡單合取式置換為包含這一命題變元的簡單合取式，直到每一簡單合取式成為極小項為止。例如P

Q

P

Q

(R

R)

(P

Q

R)

(P

Q

R)。并將極小項按順序排列。第1章命題邏輯－＞1.7對偶與范式例1.7.11求（P

Q）

Q的主析取范式。解（P

Q）

Q

（

P

Q）

Q

（

P

Q）

Q

（

P

Q）

((P

P)

Q)

（

P

Q）

(P

Q)

(

P

Q)

（

P

Q）

(P

Q)

m1

m3第1章命題邏輯－＞1.7對偶與范式例1.7.12求A=(P

Q)

(Q

R)

(

P

R)的主析取范式。解

A=(P

Q)

(Q

R)

(

P

R)

((P

Q)

Q)

((P

Q)

R))

(

P

R)（結(jié)合律，分配律）

(Q

(P

R)

(Q

R))

(

P

R)（吸收律，分配律）

(Q

(P

R))

(

P

R)（吸收律，交換律）

(Q

(

P

R))

((P

R)

(

P

R))（分配律）

(Q

P)

(Q

R)

(P

R

(

P

R))（分配律，結(jié)合律）

(Q

P)

(Q

R)

(P

R

P)

(P

R

R)（分配律）

(Q

P)

(Q

R)

(P

R)（吸收律）

(

P

Q

(R

R))

((P

P)

Q

R)

(P

(Q

Q)

R)(交換律，同一律)

(

P

Q

R)

(

P

Q

R)

(P

Q

R)

(

P

Q

R)

(P

Q

R)

(P

Q

R)

(

P

Q

R)

(

P

Q

R)

(P

Q

R)

(P

Q

R)

m2

m3

m5

m7第1章命題邏輯－＞1.7對偶與范式2．主合取范式定義1.7.7在含有n個命題變元的簡單析取式中，若每個命題變元與其否定不同時存在，而二者之一必出現(xiàn)且僅出現(xiàn)一次，且第i個命題變元或其否定出現(xiàn)在從左算起的第i位上(若命題變元無下標(biāo),則按字典順序排序)，則稱該簡單析取式為極大項。第1章命題邏輯－＞1.7對偶與范式表1-24兩個命題變元P和Q生成的4個極大項的真值表M（二進制）M00M01M10M11PQP

QP

Q

P

Q

P

Q000111011011101101111110M（十進制）M0M1M2M3第1章命題邏輯－＞1.7對偶與范式由真值表可得到極大項具有如下性質(zhì)：1）各極大項的真值表都不相同。2）每個極大項當(dāng)其真值指派與對應(yīng)的二進制編碼相同時，其真值為假，在其余2n-1種指派情況下，其真值均為真。3）任意兩個不同極大項的析取式是永真式。例如M0

M2

(P

Q)

(

P

Q)

1。4）全體極大項的合取式必為永假式。定義1.7.8由若干個不同的極大項組成的合取式稱為主合取范式(ThePrincipalConjunctiveNormalForm)。與公式等價的主合取范式稱為的主合取范式。定理1.7.9任意含n個命題變元的非永真式命題公式都存在著與之等價的主合取范式，并且其主合取范式是唯一的。第1章命題邏輯－＞1.7對偶與范式與主析取范式的求解方法相類似，主合取范式同樣可通過真值表法或等值演算法求得。（1）真值表法定理1.7.10在真值表中，命題公式A的真值為假的賦值所對應(yīng)的極大項的合取即為命題公式A的主合取范式。證明方法與定理1.7.8的證明相類似。利用真值表法求主合取范式的基本步驟為：（1）列出公式的真值表。（2）將真值表中的最后一列中的0的賦值所對應(yīng)的極大項寫出。（3）將這些極大項進行合取。第1章命題邏輯－＞1.7對偶與范式（2）等值演算法具體的求解步驟如下：（1）利用蘊含等值式和等價等值式消去公式中的聯(lián)結(jié)詞“→”和“?”；（2）利用德摩根律和雙重否定律將聯(lián)結(jié)詞“?”向內(nèi)深入，使之只作用于命題變元；（3）利用分配律將公式化為合取范式；（4）利用同一律消去矛盾的簡單析取式；（5）利用等冪律消去相同的簡單析取式以及簡單析取式中相同的析取項；（6）利用同一律、分配律將不包含某一命題變元的簡單析取式置換為包含這一命題變元的簡單析取式，直到每一簡單析取式成為極大項為止。例如P

Q

P

Q

(R

R)

(P

Q

R)

(P

Q

R)。將極大項按順序排列。第1章命題邏輯－＞1.7對偶與范式3．主析取范式和主合取范式關(guān)系設(shè)Z為命題公式A的主析取范式中所有極小項的足標(biāo)集合，R為命題公式A的主合取范式中所有極大項的足標(biāo)集合，則有R＝｛0,1,2,…,2n-1｝－Z或Z＝｛0,1,2,…,2n-1｝－R。故已知命題公式A的主析取范式，可求得其主合取范式；反之亦然。事實上，注意到極小項mi與極大項Mi滿足

mi

Mi，mi

Mi。（例：m5：P

Q

R，M5：

P

Q

R）。如例1.7.14

中的主合取范式為M0

M2

M4

M5已求出，則主析取范式為m1

m3

m6

m7，然后寫出相應(yīng)的極小項即可。第1章命題邏輯－＞1.7對偶與范式4．主范式的應(yīng)用（1）命題公式等價性的判定由于每個命題公式都存在著與之等價的唯一的主析取范式和主合取范式，因此，如果兩個命題公式等價，則相應(yīng)的主范式也對應(yīng)相同。(2)命題公式類型的判定定理1.7.11設(shè)A是含n個命題變元的命題公式，則1）A為永真式當(dāng)且僅當(dāng)A的主析取范式中含有全部2n個極小項。2）A為矛盾式當(dāng)且僅當(dāng)A的主合取范式中含有全部2n個極大項。3）若A的主析取范式中至少含有一個極小項，則A是可滿足式。第1章命題邏輯－＞1.7對偶與范式（3）解決實際問題例1.7.18某科研所要從３名科研骨干A,B,C中挑選1～2名出國進修。由于工作原因，選派時要滿足以下條件：（１）若A去，則C同去。（２）若B去，則C不能去。（３）若C不去，則A或B可以去。問應(yīng)如何選派他們?nèi)ィ康?章命題邏輯－＞1.8命題邏輯的推理理論

數(shù)理邏輯的主要任務(wù)是用數(shù)學(xué)的方法來研究數(shù)學(xué)中的推理。推理就是由已知的命題得到新命題的思維過程。任何一個推理都是由前提和結(jié)論兩部分組成。前提就是推理所根據(jù)的已知命題，結(jié)論則是從前提出發(fā)應(yīng)用推理規(guī)則推出的新命題。定義1.8.1設(shè)H1，H2，…，Hn，C都是命題公式。若(H1

H2

…

Hn)→C是重言式，則稱由前提H1，H2，…，Hn推出C的推理是有效的或正確的，并稱C是H1，H2，…，Hn的有效結(jié)論或邏輯結(jié)果，記為H1，H2，…，Hn

C或H1

H2

…

Hn

C，記號H1

H2

…

Hn

C也稱為重言蘊含或推理形式。第1章命題邏輯－＞1.8命題邏輯的推理理論

說明：（1）由前提H1，H2，…，Hn推結(jié)論C的推理是否正確與各前提的排列次序無關(guān)，因而前提中的公式不一定是序列，而是一個有限公式集合。若推理是正確的，則記為H1

H2

…

Hn

C，否則記為H1

H2

…

Hn≠>C。（2）符號

與→是兩個完全不同的符號，它們的區(qū)別與聯(lián)系類似于

和

的關(guān)系。

不是命題聯(lián)結(jié)詞而是公式間的關(guān)系符號，而→是命題聯(lián)結(jié)詞。這兩者之間有密切的聯(lián)系，即A

B的充要條件是公式A→B為重言式。第1章命題邏輯－＞1.8命題邏輯的推理理論1.8.1推理規(guī)則在數(shù)理邏輯中，要想進行正確的推理，就必須構(gòu)造一個邏輯結(jié)構(gòu)嚴(yán)謹(jǐn)?shù)男问阶C明，這需要使用一些推理規(guī)則。下面就介紹人們在推理過程中常用到的幾條推理規(guī)則。1．前提引入規(guī)則(P)

在推理過程中，可以隨時引入已知的前提。2．結(jié)論引用規(guī)則(T)在推理過程中，前面已推出的有效結(jié)論都可作為后續(xù)推理的前提引用。第1章命題邏輯－＞1.8命題邏輯的推理理論3．置換規(guī)則(R)在推理過程中，命題公式中的子公式都可以用與之等值的命題公式置換，得到證明的公式序列的另一公式。(在1.5節(jié)介紹的常用等價式作為命題推理定律，在后面的推理演算中以大寫字母E加以引用)4．代入規(guī)則(S)在推理過程中，重言式中的任一命題變元都可以用一命題公式代入，得到的仍是重言式。第1章命題邏輯－＞1.8命題邏輯的推理理論1.8.2推理定律（1）化簡律

A

B

A，A

B

B（2）附加律

A

A

B，B

A

B（3）假言推理（又稱分離規(guī)則）

A

(A

B)

B（4）假言三段論

(A

B)

(B

C)

(A

C)（5）等價三段論

(A

B)

(B

C)

(A

C)（6）析取三段論

(A

B)

A

A第1章命題邏輯－＞1.8命題邏輯的推理理論1.8.2推理定律（7）拒取式

B

(A

B)

A（8）二難推理

(A

C)

(B

C)

(A

B)

C（9）合取引入

A，B

A

B（10）

A

A

B，B

A

B（11）

(A

B)

A，

(A

B)

β（12）(A

B)

(B

A)

(A

B)（13）A

B

(A

C)

(B

C)，A

B

(A

C)

(B

C)（14）A

B

A

B，A

B

B

A

第1章命題邏輯－＞1.8命題邏輯的推理理論1.8.3推理方法在命題邏輯中，常用的推理方法有三種：真值表法、直接證法和間接證法，下面分別介紹。1．真值表法設(shè)P1,P2,…,Pn是出現(xiàn)于前提H1,H2,…,Hn和結(jié)論C中的全部命題變元，對P1,P2,…,Pn的所有情況作完全指派，這樣能對應(yīng)地確定H1,H2,…,Hn和C的所有真值，列出這個真值表，即可判斷如下推理形式是否成立：

H1

H2

…

Hn

C或H1，H2，…，Hn

C若從真值表上找出H1，H2，…，Hn均為1的行，C對應(yīng)的行也為1，則上式成立。或者，若C為0的行，對應(yīng)的行中H1，H2，…，Hn至少有一個0，則上式也成立。第1章命題邏輯－＞1.8命題邏輯的推理理論2．直接證法利用前面的四條推理規(guī)則，根據(jù)已知的命題等價公式（1.5節(jié)中的15組公式）和推理定律，推演而得到有效的結(jié)論。例1.8.2

證明(PúQ)ù(P?R)ù(Q?S)TSúR證明（1）PúQ

P

（2）?P?Q

R,E,(1)

（3）Q?S

P

（4）?P?S

T,I,(2)(3)

（5）?S?P

R,E,(4)

（6）P?R

P

（7）?S?R

T,I,(5)(6)

（8）SúR

R,E,(7)

證畢。第1章命題邏輯－＞1.8命題邏輯的推理理論說明：上述推理過程中，最左邊的一列（1），（2）等代表推理的步驟，也是推導(dǎo)出來的命題公式的編號，最右邊的一列是說明每一步的依據(jù)。如P表示前提引入規(guī)則；R,E,(1)表示依據(jù)置換規(guī)則和命題定律中的命題等價公式，由（1）得到（2）；T,I,(2)(3)表示依據(jù)結(jié)論引用規(guī)則和推理定律，由（2），（3）兩式推得（4）。第1章命題邏輯－＞1.8命題邏輯的推理理論例1.8.3

證明W

R

V，V

C

S，S

U，

C

U

W證明

（1）

C

UP（2）

UT,I,(1)（3）S

UP（4）

ST,I,(2)(3)（5）

CT,I,(1)（6）

C

ST,I,(4)(5)（7）

(C

S)R,E,(6)（8）W

R

VP（9）V

C

SP（10）W

R

C

ST,I,(8)(9)（11）

(W

R)T,I,(7)(10)（12）

W

RR,E,(11)（13）

WT,I,(12)第1章命題邏輯－＞1.8命題邏輯的推理理論例1.8.4“如果下雨，春游就改期，如果沒有球賽，春游就不改期。結(jié)果沒有球賽，所以沒有下雨”，證明這是有效的論斷。證明：令A(yù)：天下雨B：春游改期C：沒有球賽。符號化推理中各命題得：

A→B，C→

B，C

A。(1)A→B

P(2)C→

B

P(3)B→

C

R,E,(2)(4)A→

CT,I,(1)(3)(5)C→

AR,E,(4)(6)C

P(7)

AT,I,(5)(6)第1章命題邏輯－＞1.8命題邏輯的推理理論3．間接證法間接證法主要有兩種，一種稱之為CP規(guī)則，還有一種是常用的反證法（也叫歸謬法）。（1）附加前提證明法（CP規(guī)則）由公式的等價性知H1

H2

…

Hn

（A

B）

（H1

H2

…

Hn

A）

B，所以要證明H1

H2

…

Hn

（A

B），只需證明（H1

H2

…

Hn

A）

B即可，這種方法稱為CP規(guī)則。第1章命題邏輯－＞1.8命題邏輯的推理理論例1.8.6

證明R→S是{P→(Q→S)，

R∨P，Q}的邏輯結(jié)果。證明(1)

R∨P

P(2)RP(附加前提)(3)PT,I,(1)(2)(4)P→(Q→S)P(5)Q→ST,I,(3)(4)(6)QP(7)ST,I,(5)(6)(8)R→SCP(2)(7)第1章命題邏輯－＞1.8命題邏輯的推理理論例1.8.7如果學(xué)生學(xué)習(xí)努力，他們的父親或母親就高興，若母親高興，學(xué)生就不努力學(xué)習(xí)，若老師只表揚學(xué)生，學(xué)生的父親就不高興，故如果學(xué)生學(xué)習(xí)努力，老師就不是只表揚學(xué)生。試證這是有效的結(jié)論。證明:令A(yù)：學(xué)生學(xué)習(xí)努力；B：學(xué)生的父親高興；C：學(xué)生的母親高興；D：老師只表揚學(xué)生。符號化推理中各命題得：第1章命題邏輯－＞1.8命題邏輯的推理理論A→B

C，C→

A，D→

B

A→

D(1)D→

BP(2)B→

DR,E,(1)(3)C→

AP(4)A→

CR,E,(3)(5)A→(B

C)P(6)A→(

C→B)R,E,(5)(7)AP(附加前提)(8)

CT,I,(4)(7)(9)

C→BT,I,(6)(7)(10)BT,I,(8)(9)(11)

DT,I,(2)(10)(12)A→

DCP所以這是有效的結(jié)論。第1章命題邏輯－＞1.8命題邏輯的推理理論（2）歸謬法歸謬法（反證法）是經(jīng)常使用的一種間接證明方法，是將結(jié)論的否定形式作為附加前提與給定的前提條件一起推證來導(dǎo)出矛盾。定義1.8.2

設(shè)P1，P2，…，Pn是A1，A2，…，Am中出現(xiàn)的原子命題變元，若對P1，P2，P3…，Pn

的一些真值指派，A1

A2

…

Am

取值為1，則稱A1，A2，…，Am

是相容的，若對P1，P2，P3…，Pn

的任何指派，A1

A2

…

Am

取值為0，則稱A1，A2，…，Am

是不相容的（矛盾的）。定理1.8.1A1

A2

…

Am

B當(dāng)且僅當(dāng)A1，A2，…，Am

，

B是不相容的。第1章命題邏輯－＞1.8命題邏輯的推理理論證明:A1

A2

…

Am

B當(dāng)且僅當(dāng)A1

A2

…

Am

B

T（重言式），當(dāng)且僅當(dāng)

(A1

A2

…

Am)

B

T，當(dāng)且僅當(dāng)A1

A2

…

Am

B

F(矛盾式)，當(dāng)且僅當(dāng)A1，A2，…，An，

B是不相容的。第1章命題邏輯－＞1.8命題邏輯的推理理論例1.8.8用歸謬法證明例1.8.2。證明

(1)

(S

R)P（附加前提）

(2)

S

RR,E,(1)(3)P

QP(4)

P→QR,E,(3)(5)Q→SP(6)

P→ST,I,(4)(5)(7)

S→PR,E,(6)(8)

S

R→

R

PT,I,(7)(9)

R

P

T,I,(2)(8)(10)P→R

P(11)

P

R

R,E,(10)(12)

(P

R）R,E,(11)(13)(P

R)

(P

R)

F

T,I,(9)(12)由（13）得出了矛盾，根據(jù)歸謬法說明原推理正確。本章小結(jié)命題邏輯是研究數(shù)理邏輯的基礎(chǔ)，它是數(shù)理邏輯的一部分。其主要內(nèi)容包括：命題符號化及聯(lián)結(jié)詞，命題公式及分類，等值演算，最小聯(lián)接詞全功能集，對偶與范式，推理理論。通過本章學(xué)習(xí)，主要熟悉命題的概念；熟悉命題公式演算；掌握命題的公式符號化應(yīng)用；熟悉真值表及其應(yīng)用；領(lǐng)會推理理論及其規(guī)則。第2章謂詞邏輯－＞命題邏輯不僅無法刻畫世界上事物之間的復(fù)雜的邏輯關(guān)系，甚至無法證明一些簡單而又常見的推理。例如，著名的蘇格拉底三段論：“所有的人都是要死的，蘇格拉底是人，所以蘇格拉底是要死的?！备鶕?jù)常識，我們知道上述推理是正確的，然而利用命題邏輯是無法推證的。因為，在命題邏輯中，令P、Q、R分別表示上述三個原子命題，則該推理可符號化為P

Q

R，即證明P

QR是永真式。然而，在命題邏輯中這是不可能的，如何能推證這個原子命題間的蘊涵關(guān)系呢？關(guān)鍵在于命題符號R與P，Q間的內(nèi)在關(guān)系未能表示出來，受到了原子命題的限制。因此，需要對原子命題再進行剖析，去掉命題邏輯不能很好推理的局限性。因此從推理的角度看，也有必要擴充命題邏輯。第2章謂詞邏輯－＞2.1個體、謂詞和量詞

2.1.1個體和謂詞定義2.1.1在原子命題中，所陳述的對象稱之為個體，它可以是獨立存在的具體事物，也可以是一個抽象的概念。如王平，李明，計算機，離散數(shù)學(xué)，精神等都可以作為個體。定義2.1.2將表示具體的或確定的個體稱為個體常元，而將表示抽象的或泛指的（或者說取值不確定的）個體稱為個體變元。個體常元一般用小寫英文字母a,b,c…或帶下標(biāo)的ai,bi,ci…表示，個體變元一般用小寫英文字母x,y,z…或帶下標(biāo)的xi,yi,zi…表示。第2章謂詞邏輯－＞2.1個體、謂詞和量詞

定義2.1.3用以描述單個個體所具有的性質(zhì)或多個個體之間關(guān)系的詞稱為謂詞。定義2.1.4

表示具體性質(zhì)或關(guān)系的謂詞稱為謂詞常元，表示抽象的或泛指的性質(zhì)或關(guān)系的謂詞稱為謂詞變元。無論是謂詞常元或變元都用大寫英文字母P,Q,R…或帶下標(biāo)的Pi,Qi,Ri…表示，要根據(jù)上下文區(qū)分。第2章謂詞邏輯－＞2.1個體、謂詞和量詞定義2.1.5一個原子命題用一個謂詞(如P)和n個有次序的個體常元(如a1，a2，…，an)表示成P(a1，a2，…，an)，稱它為該原子命題的謂詞形式或命題的謂詞形式。定義2.1.6

由一個謂詞(如P)和n個個體變元(如x1，x2，…，xn)組成的P(x1，x2，…，xn)，稱它為n元原子謂詞或n元命題函數(shù)，簡稱n元謂詞。例如令P表示謂詞“…是大學(xué)生”，則用P(x)表示“x是大學(xué)生”；令G表示謂詞“…比…大”，則用G(x，y)可表示“x比y大”。當(dāng)n=1時，稱一元謂詞；當(dāng)n=2時，稱為二元謂詞，…。一元謂詞表達了個體的性質(zhì)，而元謂詞表達了個個體之間的關(guān)系。特別地，當(dāng)n=0，稱為零元謂詞，即不帶個體變元的謂詞為零元謂詞。零元謂詞是命題，這樣命題與謂詞就得到了統(tǒng)一，因而可將命題看成特殊的謂詞。第2章謂詞邏輯－＞2.1個體、謂詞和量詞例2.1.1分析下列命題的個體和謂詞（1）2是質(zhì)數(shù)。（2）上課認真聽講是好習(xí)慣。（3）李強比王飛高。（4）5大于3。（5）x與y具有關(guān)系R。解：(1)“2”是個體常元，“…是質(zhì)數(shù)”是謂詞，記為P。這里的謂詞是一元謂詞，屬于謂詞常元，是描述個體的性質(zhì)。(2)“上課認真聽講”是個體常元，“是好習(xí)慣”是謂詞，記為Q。這里的謂詞也是一元謂詞，屬于謂詞常元，也是描述個體的性質(zhì)。第2章謂詞邏輯－＞2.1個體、謂詞和量詞(3)“李強”與“王飛”是個體常元，分別記為a，b，“…比…高”是謂詞，記為H。這里的謂詞是二元謂詞，屬于謂詞常元，是描述兩個個體間的關(guān)系。(4)“5”與“3”是個體常元，分別記為c，d，“…大于…”是謂詞，記為G。這里的謂詞也是二元謂詞，屬于謂詞常元，也是描述兩個個體間的關(guān)系。(5)“x”與“y”是個體變元，謂詞為R。這里的謂詞是二元謂詞，屬于謂詞變元。第2章謂詞邏輯－＞2.1個體、謂詞和量詞例2.1.2用個體，謂詞表示下列命題。(1)張華是大學(xué)生。（2）武漢位于重慶和上海之間。（3）平方為-1的數(shù)不是實數(shù)。（4）小王愛好籃球或排球。（5）張三與李四都是三好學(xué)生。（6）如果你不出去，我就不進來。第2章謂詞邏輯－＞2.1個體、謂詞和量詞解（1）令a：張華；S(x)：x是大學(xué)生。整個命題可表示為：S(a)。（2）令a：武漢；b：重慶；c：上海；P(x,y,z)：x位于y和z之間。整個命題可表示為P(a,b,c)。(3)令a：平方為-1的數(shù)；R(x)：x是實數(shù)。整個命題可表示為R(a)。(4)令a：小王；B(x)：x愛好籃球；V(x):x愛好排球。整個命題可表示為B(a)

V(a)。(5)令a：張三；b：李四；S(x)：x是三好學(xué)生。整個命題可表示為S(a)

S(b)。(6)令a：你；b：我；G(x)：x出去；C(x)：x進來。整個命題可表示為

G(a)

C(b)。第2章謂詞邏輯－＞2.1個體、謂詞和量詞以該例的(1)為例分析命題的真值，若x的個體域為某大學(xué)計算機系的全體學(xué)生，則S(a)為真；若x的個體域為某中學(xué)的全體學(xué)生，則S(a)為假；若x的個