離散數(shù)學(xué) 課件 第1、2章 命題邏輯、謂詞邏輯

離散數(shù)學(xué)離散數(shù)學(xué)與其他專業(yè)課的關(guān)系數(shù)理邏輯:人工智能、形式語義學(xué)集合:形式語言、編譯技術(shù)、計算復(fù)雜性關(guān)系:關(guān)系數(shù)據(jù)庫函數(shù):算法設(shè)計與分析、軟件形式化方法圖:數(shù)據(jù)結(jié)構(gòu)、網(wǎng)絡(luò)技術(shù)、人工智能代數(shù)系統(tǒng):數(shù)字電路設(shè)計、軟件形式化方法第1節(jié) 引言 第1章命題邏輯第2節(jié) 命題及命題邏輯聯(lián)結(jié)詞第3節(jié) 命題變元和合式的公式第4節(jié) 重言式（或永真式）和永真蘊(yùn)涵式第5節(jié) 對偶原理（略）

第6節(jié) 范式和判定問題第7節(jié) 命題演算的推論理論一、地位作用:二、研究對象:三、主要內(nèi)容:第1節(jié)、引言離散數(shù)學(xué)數(shù)學(xué)分支，計算機(jī)核心課程離散量結(jié)構(gòu)及相互關(guān)系數(shù)理邏輯、集合論、代數(shù)系統(tǒng)、圖論等1、命題的定義第1章命題邏輯第1節(jié) 基本概念第2節(jié)、命題及命題邏輯聯(lián)結(jié)詞5、原子命題2、命題的真值3、真值的表示4、命題標(biāo)識符6、原子變元7、分子命題（復(fù)合命題）8、邏輯聯(lián)結(jié)詞1、命題的定義 一個具有確定的真假意義的陳述句稱為命題；一般用英文大寫字母表示。疑問句,祈使句,感嘆句等均不是命題命題要么正確,要么錯誤2、命題的真值 一個命題的取值或真或假，這兩種可能的取值稱為命題的真值。正確錯誤3、真值的表示真值是真真值是假1T0FTrueFalse(1)上海是一個小山村。(2)抽煙的人均要得肺癌。(3)十是整數(shù)。(4)上課去！(5)你吃飯了嗎？

(6)今天天氣多好?。?7)蚊子是鳥類動物。(8)我正在說謊。(F)(F)(F)(T)(×)(×)(×)(×)例、判斷下列命題的真假關(guān)于悖論“我正在說謊?！?/p>

如果真值為“真”，則隱含著我正在說謊；真值不確定悖論如果真值為“假”，則隱含著我沒有說謊。4、命題標(biāo)識符 用英文大寫字母表示命題命題標(biāo)識符命題常量:命題變元:表示確定的命題表示任意的命題真值∈｛0，1｝或∈｛T，F(xiàn)｝5、原子命題 不能再分解成更簡單的命題本原命題6、原子變元 若命題變元表示原子命題時，該變元稱原子變元。例：命題變元是命題嗎？第1章命題邏輯第1節(jié) 基本概念解： 命題變元不是命題，因?yàn)槊}變元的真值不確定。 當(dāng)命題變元P用特定的命題取代時，P才能確定真值對P進(jìn)行真值指派7、分子命題 由原子命題通過邏輯聯(lián)結(jié)詞構(gòu)成的新命題復(fù)合命題邏輯聯(lián)結(jié)詞1、真值表的概念2、否定（

）3、合?。ā?，與）4、析取（∨，或）5、單條件（→）6、雙條件（?）7、命題符號化1、真值表的概念 在復(fù)合命題中，對命題變元的所有種可能的真值指派，復(fù)合命題都有一個確定的真值與其相對應(yīng)，形成一個表，稱為真值表。n個命題變元，2n種真值指派:兩個命題變元,22＝4種真值指派00011011(0～3)0～2n-12、否定（

） 一元運(yùn)算符，當(dāng)且僅當(dāng)P為真時，

P為假。真值表如表1.1所示。表1.1 邏輯聯(lián)結(jié)詞“

”的真值表P

P1001例、給出下列命題的否定命題（1）大連的每條街道都臨海。（2）天津是一個城市。并非大連的每條街道都臨海。大連的每條街道不都臨海。大連的每條街道都不臨海?！獭獭撂旖虿皇且粋€城市。注意：否定是對命題的部分否定。3、合?。ā?，與） 二元運(yùn)算符，當(dāng)且僅當(dāng)P、Q的真值均為真時，P∧Q的真值才為真。真值表如表1.2所示。表1.2 邏輯聯(lián)結(jié)詞“∧”的真值表PQP∧Q000110110001注意：

在數(shù)理邏輯中，只要P和Q的真值確定，P∧Q的真值即可確定，就可以成為新的命題，不管這個新命題在自然語言中是否有意義。將下列命題符號化(1)我雖然生病，但我仍去學(xué)校。(2)我雖然有錢，但我不去看電影。(3)張華與李明在吃飯。解：命題符號化過程及結(jié)果(1)我雖然生病，但我仍去學(xué)校。P：我生??；Q：我去學(xué)校；

(2)我雖然有錢，但我不去看電影。P：我有錢;Q：我去看電影;

(3)P:張華在吃飯;Q:李明在吃飯;注意：

用命題變元表示肯定的命題。P∧QP∧

QP∧Q第1章命題邏輯

第2節(jié) 邏輯聯(lián)結(jié)詞4、析取（∨，或、可兼或）

二元運(yùn)算符，當(dāng)且僅當(dāng)P、Q的真值均為假時，P∨Q的真值才為假。真值表如表1.3所示。表1.3 邏輯聯(lián)結(jié)詞“∨”的真值表PQP∨Q000110110111第1章命題邏輯第2節(jié) 邏輯聯(lián)結(jié)詞例:將下列命題符號化：（1）張三或李四可以做這件事。（2）我們不能既劃船又跑步。解：命題符號化過程及結(jié)果(1)張三或李四可以做這件事。P：張三可以做這件事；Q：李四可以做這件事；(2)我們不能既劃船又跑步。P：我們劃船;Q：我們跑步;

P∨Q

P∨

Q

(P∧Q)第1章命題邏輯

第2節(jié) 邏輯聯(lián)結(jié)詞5、單條件（→，善意的推定） 二元運(yùn)算符，當(dāng)且僅當(dāng)P為真，Q為假時，P→Q的真值才為假，否則，均為真。真值表如表1.5所示。善意的推定：當(dāng)條件為假時，無論后件為真為假，結(jié)論均為真。第1章命題邏輯

第2節(jié) 邏輯聯(lián)結(jié)詞PQP→

Q00011011表1.5 邏輯聯(lián)結(jié)詞“→”的真值表0111第1章命題邏輯第2節(jié) 邏輯聯(lián)結(jié)詞例:將下列命題符號化：（1）如果我生病，那么我不去學(xué)校。（2）如果我有錢，那么我就去看電影。解：命題符號化過程及結(jié)果(1)如果我生病，那么我不去學(xué)校。P：我生??；Q：我去學(xué)校；

(2)如果我有錢，那么我就去看電影。P：我有錢;Q：我去看電影;

P→

QP→Q第1章命題邏輯

第2節(jié) 邏輯聯(lián)結(jié)詞6、雙條件（?

） 二元運(yùn)算符，當(dāng)且僅當(dāng)P、Q的真值相同時，P?Q的真值才為真，否則，均為假。真值表如表1.6所示。第1章命題邏輯

第2節(jié) 邏輯聯(lián)結(jié)詞PQP?

Q00011011表1.6 邏輯聯(lián)結(jié)詞“?”的真值表1100第1章命題邏輯第2節(jié) 邏輯聯(lián)結(jié)詞例:將下列命題符號化：（1）只有在我生病的時候，我才不去學(xué)校。（2）當(dāng)且僅當(dāng)我有錢時，我才去看電影。解：命題符號化過程及結(jié)果(1)只有在我生病的時候，我才不去學(xué)校。P：我生?。籕：我去學(xué)校；

(2)當(dāng)且僅當(dāng)我有錢時，我才去看電影。P：我有錢;Q：我去看電影;

P?

QP?Q第1章命題邏輯邏輯聯(lián)結(jié)詞的優(yōu)先級∧

∨

→

?高低注意：

“∧”的優(yōu)先級比“∨”高，而不是相同。第1章命題邏輯7、命題符號化的原則：（1）“∧”：（并列、遞進(jìn)、轉(zhuǎn)折）同時、不但…而且、即…又、和（2）“∨”：（相容、選擇）或許、大概、可能（3）“→”：（條件）如果…則…、如果…那么…第1章命題邏輯命題符號化的原則（續(xù)）：（4）“?”：（等價）充分必要、當(dāng)且僅當(dāng)、只有…才能（5）“

”：（否定）非、不

第1章命題邏輯命題符號化的步驟：（1）找出原子命題；（2）用符號（大寫英文字母）定義原子命題；（3）使用正確的邏輯聯(lián)結(jié)詞，將自然語言變成與之等價的符號化語言。第1章命題邏輯例：將下列命題符號化：（1）如果明天上午7點(diǎn)不是雨加雪，則我去學(xué)校。（2）只有明天上午7點(diǎn)不下雨而且不下雪，我才去學(xué)校。解：命題符號化過程及結(jié)果(1)P:明天上午7點(diǎn)下雨；Q:明天上午7點(diǎn)下雪；R:我去學(xué)校；如果明天上午7點(diǎn)不是雨加雪，則我去學(xué)校。

(P∧Q)→R第1章命題邏輯(P 只有明天上午7點(diǎn)不下雨而且不下雪，我才去學(xué)校。R∧

Q)?第1章命題邏輯例：P：我生??；Q：我去學(xué)校；（1）我雖然生病，但我仍去學(xué)校。（2）只有在我生病的時候，我才不去學(xué)校。（3）如果我生病，那么我不去學(xué)校。P∧QP?

QP→

Q第1章命題邏輯命題公式（合式的公式）的遞歸定義

合式的公式（Wff）是由命題變元、邏輯聯(lián)結(jié)詞、圓括號組成的：(1)單個的命題變元是合式的公式；(2)如果A是Wff，則

A是Wff(3)如果A和B是Wff，則(A∧B)、(A∨B)、(A→B)、(A?B)都是Wff(4)當(dāng)且僅當(dāng)有限次地使用(1)、(2)、(3)所得到的包含命題變元、邏輯聯(lián)結(jié)詞、圓括號的符號串是Wff(遞歸基礎(chǔ)）；（遞歸方法）；（遞歸方法）。（遞歸界限）第3節(jié) 命題變元和合式的公式第1章命題邏輯去括號原則(1)最外層括號可??；(2)、∧、∨、→、?的優(yōu)先級由高到低，有的括號可?。坏?章命題邏輯例、根據(jù)定義判斷下列公式是否是合式公式(1)、((A∧B)→A) (2)、A→(∧B) (3)、(P∧Q) (4)、?(A→B) (5)、(P→(P∨?Q)) (6)、(((P→Q)∧(Q→R))?(S?T))(7)、(P→Q)→(∧Q) (8)、(P→Q (9)、(P∧Q)→Q) （√）（×）(∧

是二元運(yùn)算符

）（×)(括號不匹配）（×）括號不匹配（×)(∧

是二元運(yùn)算符）（√）（√）（√）（√）第1章命題邏輯1、永真式（重言式）

對于命題變元的所有種可能的真值指派，命題公式的真值均為真，稱該合式公式為永真式。第4節(jié) 重言式（或永真式）和永真蘊(yùn)涵式第1章命題邏輯例、構(gòu)造下列命題公式的真值表(1)、(P∧(P→Q))→Q(2)、P∨?P(3)((P∨Q)∧R)∨?((P∨Q)∧R)(4)P→Q、?P∨Q、?(P∧?

Q)表1.8(P∧(P→Q))→Q的真值表PQ00011011P→

QP∧(P→Q)(P∧(P→Q))→Q011110001111(P∧(P→Q))→Q是永真式第1章命題邏輯表1.9P∨?P的真值表P01?

PP∨?P1011P∨?P是永真式第1章命題邏輯表1.10((P∨Q)∧R)∨?((P∨Q)∧R)的真值表PQR000001010011100101110111P∨Q(P∨Q)∧R?((P∨Q)∧R)((P∨Q)∧R)∨?((P∨Q)∧R)00111111111000001110101011111111((P∨Q)∧R)∨?((P∨Q)∧R)是永真式第1章命題邏輯表1.10P→Q、?P∨Q、?(P∧?

Q)的真值表PQ

00011011注意：以上三個命題公式的真值表完全相同，稱這三個命題公式等價。P→Q0111?

P?

P∨Q11001101?

QP∧?

Q?(P∧?

Q)101000101101第1章命題邏輯第1章命題邏輯2、永假式（矛盾式） 給定一命題公式，若對任何的真值指派,其對應(yīng)的真值永為F，則稱該命題公式為矛盾式或永假式。第1章命題邏輯例、構(gòu)造下列命題公式的真值表(1)、P∧?P(2)、(P∧Q)∧?P表1.11P∧?P的真值表P01?

PP∧

?P1000P∧

?P是永假式第1章命題邏輯表1.12(P∧Q)∧

P的真值表PQ00011011第1章命題邏輯P∧Q

P(P∧Q)∧

P100011000000(P∧Q)∧?P是永假式第1章命題邏輯3、可滿足式

至少有一組真值指派使得命題公式取值為真，則稱該命題公式為可滿足式。注意：永真式是可滿足式的一種特例。第1章命題邏輯例、構(gòu)造下列命題公式的真值表1.P→(Q∨R)2.(P∨Q)?(Q∨P)表1.14

P→(Q∨R)的真值表PQR000001010011100101110111第1章命題邏輯Q∨RP→(Q∨R)0111011101111111P→(Q∨R)是可滿足式表1.15

(P∨Q)?(Q∨P)的真值表

PQ00011011第1章命題邏輯P∨QQ∨P(P∨Q)?(Q∨P)011101111111(P∨Q)?(Q∨P)是永真式第1章命題邏輯4、永真式的特點(diǎn)（1）永真式的否定為矛盾式，反之亦然；（2）永真式的“∧”、”∨”、”→”、”?”仍為永真式；（3）由永真式可以產(chǎn)生許多恒等式。等價式第1章命題邏輯5、 等價式的定義 給定兩個命題公式A和B,P1，P2，…，Pn為所有出現(xiàn)于A和B中的原子變元，若給n個命題變元P1，P2，…，Pn指派2n個可能的真值，命題公式A和B的真值都相同，則稱公式A等價公式B，或：如果A?BT，則A

B記作A

B。第1章命題邏輯例、利用真值表證明下列等價式1.

(P?Q)

(P∨Q)∧

(P∧Q)2.P→(Q∨R)

(P∧

Q)→R3.P∧(P∨Q)

P表1.17

(P?Q)、(P∨Q)∧

(P∧Q)的真值表

PQ00011011所以：(P?Q)

(P∨Q)∧

(P∧Q)第1章命題邏輯P?Q

(P?Q)11000110P∨Q0111P∧Q0001

(P∧Q)1110(P∨Q)∧

(P∧Q)0110表1.18P→(Q∨R)、(P∧

Q)→R

的真值表PQR000001010011100101110111所以：P→(Q∨R)

(P∧

Q)→R第1章命題邏輯Q∨R01110111P→(Q∨R)11110111

Q11001100P∧

Q00001100(P∧

Q)→R11110111表1.19P∧(P∨Q)的真值表PQ00011011所以：P∧(P∨Q)

P第1章命題邏輯P∨Q0111P∧(P∨Q)0011第1章命題邏輯常見的等價式（1）交換律；（2）結(jié)合律；（3）分配律；（4）否定深入；（5）變元等同；（6）常值與變元的聯(lián)結(jié)；（7）聯(lián)結(jié)詞的化歸；（8）吸收律；第1章命題邏輯（1）交換律（∧、∨、?）①P∧Q

Q∧P

Q∨P

Q?P③P?Q②P∨Q第1章命題邏輯（2）結(jié)合律（∧、∨、?）①(P∧Q)∧RP?(Q?R)

P∧(Q∧R)②(P∨Q)∨RP∨(Q∨R)③(P?Q)?R第1章命題邏輯（3）分配律（∧對∨、∨對∧、→對→

）①P∧(Q∨R)(P→Q)→(P→R)(P∧Q)∨(P∧R)②P∨(Q∧R)(P∨Q)∧(P∨R)③P→(Q→R)證明：P∧(Q∨R)(P∧Q)∨(P∧R)PQR000001010011100101110111所以：P∧(Q∨R)(P∧Q)∨(P∧R)Q∨R01110111P∧(Q∨R)00000111P∧Q00000011P∧R00000101(P∧Q)∨(P∧R)00000111第1章命題邏輯第1章命題邏輯（4）否定深入①雙重否定定律：PQ

P

P②德摩根定律：

(P∧Q)

P∨

Q

(P∨Q)

P∧

Q③(P?Q)

P?Q

P?Q證明：

(P∧Q)

P∨

Q

PQ00011011所以：

(P∧Q)

P∨

Q

P∧Q0001

(P∧Q)1110P1100

Q1010

P∨

Q1110第1章命題邏輯第1章命題邏輯（5）變元等同①等冪律：P∧P

PP∨P

P②P∧

P

FP∨

P

T③P→P

TP→P

PP→P

P④P?PTP?PP?PF第1章命題邏輯（6）常值與變元的聯(lián)結(jié)①同一律：P∨F

PP∧T

P②零律：P∨T

TP∧F

F③T→P

PF→PTP→TTP→F

P④P?TPP?FP第1章命題邏輯（7）聯(lián)結(jié)詞的化歸①P∧Q

P?Q(P∨Q)②P∨Q

(P∧Q)③P→Q

P∨Q④P?Q(P→Q)∧(Q→P)(P∨Q)∧(

Q∨P)(P∧Q)∨(P∧Q)證明：P?Q(P∧Q)∨(P∧Q)PQ00011011所以：P?Q(P∧Q)∨(P∧Q)P∧Q0001P1100

Q1010P∧

Q1000(P∧Q)∨(P∧

Q)1001P?Q1001第1章命題邏輯第1章命題邏輯（8）吸收律①P∧(P∨Q)

②P∨(P∧Q)

PP第1章命題邏輯說明：(1)Q→P稱為P→Q的逆換式；(2)?P→

?Q稱為P→Q的反換式；(3)?Q→

?P稱為P→Q的逆反式。注意：P→Q

Q→

P第1章命題邏輯6、 永真蘊(yùn)涵式A稱為B的邏輯前提,B稱為A的邏輯結(jié)果；由A能推出B，B是由A推出的。若A→B

TA永真蘊(yùn)涵B永真蘊(yùn)涵式AB第1章命題邏輯證明永真蘊(yùn)涵式的方法（1）真值表法:則AB；若A→BT，則AB；（2）假設(shè)前件A為真，若能證明后件B必為真，則AB；（3）假設(shè)后件B為假，若能證明前件A必為假，第1章命題邏輯例、試用不同的方法證明下列蘊(yùn)涵式P∧(P→Q)

Q證明P∧(P→Q)

Q方法1真值表法：PQ00011011即：P∧(P→Q)

QP→Q11010001P∧(P→Q)(P∧(P→Q))→Q1111第1章命題邏輯證明P∧(P→Q)

Q方法2假設(shè)前件為真，證明后件必為真假設(shè)前件P∧(P→Q)為真即：P∧(P→Q)

Q真真真第1章命題邏輯證明P∧(P→Q)

Q方法3假設(shè)后件為假，證明前件必為假假設(shè)后件Q為假則對前件P∧(P→Q)中的P進(jìn)行如下討論：即：P∧(P→Q)

Q（1）P為真時：P∧(P→Q)（2）P為假時：P∧(P→Q)真假假假真假第1章命題邏輯第1章命題邏輯常見的永真蘊(yùn)涵式（1）化簡式：P∧Q

P，P∧Q

Q（2）附加式：P

P∨Q，QP∨Q（3）析取三段論：

P，P∨Q

Q（4）假言推論：P，P→Q

Q（5）拒取式：Q，P→Q

P（6）假言三段論：P→Q，Q→R

P→R（7）二難推論：P∨Q，P→R，Q→RR

注意：，即∧證明：析取三段論：

P，P∨Q

Q

假設(shè)前件

P，P∨Q為真，證明后件Q為真即

P，P∨Q

Q

P為真P∨Q為真P必為假真第1章命題邏輯證明：假言三段論：P→Q，Q→R

P→R假設(shè)后件P→R為假,證明前件P→Q,Q→R必為假：即P→Q，Q→R

P→RP→R為假P必為真R必為假對Q進(jìn)行以下討論：(1)Q為真時:(2)Q為假時:P→Q為真Q→R為假(P→Q)∧(Q→R)必為假P→Q為假Q(mào)→R為真(P→Q)∧(Q→R)必為假第1章命題邏輯第1章命題邏輯7、 代入規(guī)則和替換規(guī)則（1）代入實(shí)例；（2）代入規(guī)則；（3）替換規(guī)則（置換定理）；（4）等價式的證明方法；（5）代入規(guī)則和替換規(guī)則的不同點(diǎn)。第1章命題邏輯（1）、 代入實(shí)例WffB(P1，P2，…，Pi,…，Pn)命題變元WffAi代換所有出現(xiàn)WffAWffB的代入實(shí)例。注意：（1）只能代換命題變元；（2）代換該命題變元的所有出現(xiàn)；代入實(shí)例舉例已知：命題公式(P∧Q)→(P∧R) 試用命題公式（A?B）代換P的所有出現(xiàn)，得到以下的命題公式：

第1章命題邏輯(∧Q)→(∧R)(A?B)(A?B)第1章命題邏輯（2）、 代入規(guī)則 永真式的任何代入實(shí)例仍為永真式。第1章命題邏輯第4節(jié) 等價式（恒等式）和永真蘊(yùn)涵式 代入規(guī)則舉例P∨

P為永真式； 以命題公式：Q∧R代換命題變元P的所有出現(xiàn)；得到的命題公式：(Q∧R)∨

(Q∧R)永真式第1章命題邏輯（3）、 替換規(guī)則（置換定理）WffAWffA′子公式WffA′

WffB′替換WffB

注意：（1）實(shí)現(xiàn)的是等價變換；（2）不需要代換所有出現(xiàn)；第1章命題邏輯（4）證明等價式的方法（1）真值表法；（2）利用置換定理產(chǎn)生等價序列；證明

(

P∨

Q)∨

(

P∨Q)P方法一真值表法：PQ00011011第1章命題邏輯第4節(jié) 等價式（恒等式）和永真蘊(yùn)涵式P1100

Q1010P∨

Q1110(P∨

Q)0001P∨Q1101(P∨Q)0010(P∨

Q)∨(P∨Q)0011

(

P∨

Q)∨

(

P∨Q)P證明

(

P∨

Q)∨

(

P∨Q)P方法二置換定理：

(

P∨

Q)∨

(

P∨Q)第1章命題邏輯(P∧Q)∨(P∧Q) (德摩根定律）P（分配率）P∧(Q∨Q) P∧T第1章命題邏輯（5）代入規(guī)則和替換規(guī)則的不同點(diǎn)（1）代入規(guī)則：被替換的是命題變元； 替換規(guī)則：被替換的可以是命題常量、命題 變元、合式公式；（2）替換規(guī)則：要求替換和被替換的合式公式必 須是等價的； 代入規(guī)則：不必；（3）代入規(guī)則：若對命題變元P使用代入規(guī)則， 則合式公式中所有P的出現(xiàn)均要 使用代入規(guī)則； 替換規(guī)則：不必。第1章命題邏輯例、證明下列等價式1.(A→D)∧(B→D)

(A∨B)→D2.((A∧B)→C)∧(B→(D∨C))

(B∧(D→A))→C3.P→(Q→R)

Q→(P→R)

?R→(Q→?P)證明：(A→D)∧(B→D)

(A∨B)→D左式

(A→D)∧(B→D)第1章命題邏輯(

A∨D)∧(

B∨D)

(A∨B)→D（分配率）(

A∧

B)∨D(德摩根定律）

(A∨B)∨D

右式證明：((A∧B)→C)∧(B→(D∨C))

(B∧(D→A))→C

左式

(

(A∧B)∨C)∧(

B∨(D∨C))

第1章命題邏輯

(B∧(D→A))→C(德摩根定律）

(

A∨

B∨C)∧(

B∨D∨C)（分配率）((

A∨

B)∧(

B∨D))∨C（分配率）(

B∨(

A∧D))∨C(德摩根定律）

(

B∨(A∨

D))∨C(德摩根定律)

(B∧(A∨

D))∨C

(B∧(D→A))∨C

右式證明：P→(Q→R)

Q→(P→R)

R→(Q→?P)

左式

P∨(

Q∨R)第1章命題邏輯

R→(Q→?P)

（交換率,結(jié)合律）

Q∨(

P∨R)

Q∨(P→R)

Q→(P→R)

Q∨

P∨R（交換率,結(jié)合律）

R∨(

Q∨

P)

R∨(Q→?P)第1章命題邏輯功能完備集 設(shè)有一個聯(lián)結(jié)詞集合A，如果：（1）用A中的聯(lián)結(jié)詞能夠表達(dá)任何命題公式；（2）刪除A中的任何聯(lián)結(jié)詞得到一個聯(lián)結(jié)詞集合A′，至少有一個公式不可能用僅含于A′中的邏輯聯(lián)結(jié)詞的等價式表達(dá)出來，則集合A稱為功能完備集。{?,∧},{?,∨}是功能完備集P→Q

P∨QP?Q(P∧Q)∨(P∧Q)P∧Q(P∨Q)P∨Q(P∧Q)第1章命題邏輯第1章命題邏輯例、寫出與下式等價并僅含{?，∧}的最簡式

P→(Q→R)

P∨(

Q∨R)(P∧Q∧

R)第1章命題邏輯第6節(jié) 范式和判定問題1、析取范式和合取范式2、主析取范式和主合取范式第1章命題邏輯1、析取范式和合取范式（1）基本積和基本和（2）析取范式（3）合取范式（4）求合取范式或析取范式的步驟第1章命題邏輯（1）基本積和基本和 合式公式中的一些變元和一些變元的否定的合取，稱為基本積； 合式公式中的一些變元和一些變元的否定的析取，稱為基本和；如：P∧

Q如：

P∨R∨

Q第1章命題邏輯（2）析取范式注意：一個命題公式的析取范式不唯一

WffA由基本積的和組成的公式

A的析取范式A

A1∨A2∨…∨Ann≥1記作：基本積第1章命題邏輯（3）合取范式注意：一個命題公式的合取范式不唯一

WffA由基本和的積組成的公式

A的合取范式A

A1∧

A2∧

…∧

Ann≥1記作：基本和(4)求合取范式或析取范式的步驟將公式中的聯(lián)結(jié)詞化歸成∧、∨、

；利用德?摩根定律將否定符號

直接移到各個命題變元之前；利用分配律、結(jié)合律將公式化為合取范式或析取范式。第1章命題邏輯析取范式和合取范式舉例求(P∧(Q→R))→S的合取范式求

(P∨Q)

?(P∧Q)的析取范式第1章命題邏輯求(P∧(Q→R))→S的合取范式基本和基本和第1章命題邏輯(P∧(Q→R))→S

(P∧(

Q∨R))∨S（德摩根定律）(P∨

(

Q∨R))∨S（德摩根定律）(P∨(Q∧

R))∨S（分配律）((P∨Q)∧(P∨

R))∨S（分配律）(P∨Q∨S)∧(P∨

R∨S)（合取范式）求

(P∨Q)?(P∧Q)的析取范式

(P∨Q)?(P∧Q)(P∧

Q)?(P∧Q)（德摩根定律）(()∧())∨(()∧

())

P∧

QP∧Q

P∧

QP∧Q(

P∧

Q∧P∧Q)∨((P∨Q)∧(

P∨

Q))F∨((P∨Q)∧(

P∨

Q))(P∨Q)∧(

P∨

Q)（合取范式）((P∨Q)∧

P)∨((P∨Q)∧

Q)（分配律）

(P∧

P)∨(Q∧

P)∨(P∧

Q)∨(Q∧

Q)（分配律）

(

P∧Q)∨(P∧

Q)（析取范式）第1章命題邏輯2、主析取范式和主合取范式（1）極小項(xiàng)（2）主析取范式（3）極大項(xiàng)（4）主合取范式（5）主析取范式和主合取范式的求法（6）主析取范式和主合取范式的關(guān)系（7）極大項(xiàng)和極小項(xiàng)的關(guān)系（8）主析取范式和主合取范式的作用第1章命題邏輯（1）極小項(xiàng)編碼原則：極小項(xiàng)中命題變元的否定對應(yīng)著“0”；命題變元本身對應(yīng)著“1”。

WffA中含有n個命題變元每個變元與其否定必出現(xiàn)且僅出現(xiàn)一次極小項(xiàng)基本積第1章命題邏輯例、寫出兩個命題變元的極小項(xiàng)及其真值表 兩個命題變元的極小項(xiàng)及真值表PQ極小項(xiàng)編碼mi00011011P∧Qm0P∧Qm1P∧Qm2P∧Qm3第1章命題邏輯例、寫出三個命題變元的極小項(xiàng)及其真值表 三個命題變元的極小項(xiàng)及真值表PQR極小項(xiàng)編碼mi000001010011100101110111P∧Q∧Rm0P∧Q∧Rm1P∧Q∧Rm2P∧Q∧Rm3P∧Q∧Rm4P∧Q∧Rm5P∧Q∧Rm6P∧Q∧Rm7第1章命題邏輯關(guān)于極小項(xiàng)的幾點(diǎn)說明：

①n個命題變元共有2n個可能極小項(xiàng)。②沒有兩個極小項(xiàng)是等價的。③每個極小項(xiàng)都只對應(yīng)一組真值指派，使 得該極小項(xiàng)的真值為T。例:P∧Q∧R100T第1章命題邏輯（2）主析取范式注意：除永假式外，任一Wff的主析取范式必存在 且唯一。WffWWffH由極小項(xiàng)的析取組成

WffW主析取范式第1章命題邏輯（3）極大項(xiàng)注意：極大項(xiàng)中命題變元的否定對應(yīng)著“1”；命題變元本身對應(yīng)著“0”。

WffA中含有n個命題變元每個變元與其否定必出現(xiàn)且僅出現(xiàn)一次極大項(xiàng)基本和第1章命題邏輯例、寫出兩個命題變元的極大項(xiàng)及其真值表 兩個命題變元的極大項(xiàng)及真值表PQ極大項(xiàng)編碼Mi00011011P∨QM0P∨

QM1P∨QM2P∨QM3第1章命題邏輯例、寫出三個命題變元的極大項(xiàng)及其真值表 三個命題變元的極大項(xiàng)及真值表PQR極大項(xiàng)編碼Mi000001010011100101110111P∨Q∨RM0P∨Q∨RM1P∨Q∨RM2P∨Q∨RM3P∨Q∨RM4P∨Q∨RM5P∨Q∨RM6P∨Q∨RM7第1章命題邏輯關(guān)于極大項(xiàng)的幾點(diǎn)說明：

①n個命題變元共有2n個可能的極大項(xiàng)。②沒有兩個極大項(xiàng)是等價的。③每個極大項(xiàng)都只對應(yīng)一組真值指派，使 得該極大項(xiàng)的真值為F。例:P∨Q∨R011F第1章命題邏輯（4）主合取范式注意：除永真式外，任一Wff的主合取范式必存在 且唯一。WffWWffH由極大項(xiàng)的合取組成

WffW的主合取范式第1章命題邏輯（5）主析取范式和主合取范式的求法①真值表法；②推導(dǎo)法；第1章命題邏輯①真值表法 主析取范式：一個Wff的真值表中真值為“1”的各種真值指派對應(yīng)的極小項(xiàng)的析取，為該Wff的主析取范式； 主合取范式：一個Wff的真值表中真值為“0”的各種真值指派對應(yīng)的極大項(xiàng)的合取，為該Wff的主合取范式；第1章命題邏輯例、用真值表法求下式的

主析取范式和主合取范式P→(Q∧R)P→(Q∧R)的真值表PQR極大(小)項(xiàng)編碼Mi(

mi)000001010011100101110111Q∧R00010001P→(Q∧R)11110001P∧Q∧Rm0P∧Q∧Rm1P∧Q∧Rm2P∧Q∧Rm3P∧Q∧Rm7P∨Q∨RM4P∨Q∨RM5P∨Q∨RM6第1章命題邏輯P→(Q∧R)的

主析取范式和主合取范式P→(Q∧R)

(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)

m0∨m1∨m2∨m3∨m7∑(m0,m1,m2,m3,m7)(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)

M4

∧M5∧M6∏(M4,M5,M6)第1章命題邏輯②推導(dǎo)法a、消去邏輯聯(lián)結(jié)詞→和?；b、化為析取范式或合取范式；c、添加缺少的命題變元；第1章命題邏輯(1)主析取范式合取一個缺少變元的永真式(如：

P∨P)，然后應(yīng)用分配律展開公式。添加缺少的命題變元Q∧R基本積WffA中含有P,Q,R三個命題變元缺少變元P

(Q∧R)∧(P∨P)

(P∧Q∧R)∨(P∧Q∧R)缺少變元P的永真式極小項(xiàng)第1章命題邏輯添加缺少的命題變元(2)主合取范式析取一個缺少變元的永假式(如：

P∧P)，然后應(yīng)用分配律展開公式Q∨R基本和WffA中含有P,Q,R三個命題變元缺少變元P

(Q∨R)∨(P∧P)

(P∨Q∨R)∧(P∨Q∨R)缺少變元P的永假式極大項(xiàng)第1章命題邏輯第6節(jié) 主析取范式和主合取范式例、用推導(dǎo)法求下式的

主析取范式和主合取范式P→(Q∧R)P∨(Q∧R)(P∨Q)∧(P∨R)((P∨Q)∨(R∧R))∧((P∨R)∨(Q∧Q))(P∨Q∨R)∧(P∨Q∨

R)∧(P∨R∨Q)∧(P∨RQ)(P∨Q∨R)∧(P∨Q∨

R)∧(P∨Q∨R)∧(P∨Q∨R)(P∨Q∨R)∧(P∨Q∨

R)∧(P∨Q∨R)

M4

∧M5∧M6∏(M4,M5,M6)(主合取范式)第1章命題邏輯（6）主析取范式和主合取范式的關(guān)系 二者是互補(bǔ)的關(guān)系，即如果某個mi在主析取范式中出現(xiàn)，則Mi一定不在主合取范式中出現(xiàn)。注意：只要求出主析取范式或主合取范式中的任何一種，另外一種范式根據(jù)互補(bǔ)關(guān)系就可以相應(yīng)寫出。第1章命題邏輯（7）極小項(xiàng)和極大項(xiàng)的關(guān)系mi

MiMi

mi例：m3：P∧Q∧R

m3(P∧Q∧R)P∨Q∨R

M3011第1章命題邏輯第6節(jié) 主析取范式和主合取范式（8）主析取范式和主合取范式的作用①判斷兩個公式是否等價：②判斷wff是否是永真式：③判斷wff是否是永假式：wffG的主合(析)取范式wffH的主合(析)取范式

G

H主析取范式中所有的極小項(xiàng)均出現(xiàn)不存在主合取范式主合取范式中所有的極大項(xiàng)均出現(xiàn)不存在主析取范式第1章命題邏輯例、求下式的主析取范式和主合取范式(1)(P∧Q)∨(

P∧R)(2)(P→Q∧R))∧(

P→(

Q∧

R))(3)(Q→P)∧(

P∧Q)(1)(P∧Q)∨(

P∧R)推導(dǎo)法第1章命題邏輯(P∧Q)∨(

P∧R)∧(

R∨R)∧(

Q∨Q)析取范式缺少變元R缺少變元Q

(P∧Q∧

R)∨(P∧Q∧R)∨(

P∧R∧

Q)∨(

P∧R∧Q)

(P∧Q∧

R)∨(P∧Q∧R)∨(

P∧

Q∧R)∨(

P∧Q∧R)

m6∨m7∨m1∨m3110111001011∑(m1,m3,m6,m7)

M0∧M2∧M4∧M5∏(M0,M2,M4,M5)(P∨Q∨R)∧(P∨

Q∨R)∧(P∨Q∨R)∧(P∨Q∨

R)000010100101(1)(P∧Q)∨(

P∧R)真值表法PQR000001010011100101110111第1章命題邏輯P∧Q00000011

P11110000

P∧R01010000(P∧Q)∨(

P∧R)01010011編碼M0M2M4M5m1m3m6m7第1章命題邏輯(2)(P→Q∧R))∧(

P→(

Q∧

R))推導(dǎo)法原式

(

P∨(Q∧R))∧(P∨(

Q∧

R))

(

P∨Q)∧(

P∨R)∧(P∨

Q)∧(P∨

R)

(

P∨Q)∧(

P∨R)∧(P∨

Q)∧(P∨

R)∨(

R∧R)∨(

Q∧Q)∨(

R∧R)∨(

Q∧Q)分配率析取范式析取缺少變元的永假式

(

P∨Q∨

R)∧(

P∨Q∨R)∧(

P∨R∨

Q)∧(

P∨R∨Q)∧(P∨

Q∨

R)∧(P∨

Q∨R)∧(P∨

R∨

Q)∧(P∨

R∨Q)分配率

M5∧M4∧M6∧M3∧M2∧M1∏(M1,M2,M3,M4,M5,M6)

m0∨m7∑(m0,m7)

(

P∧

Q∧

R)∨(P∧Q∧R)(2)(P→Q∧R))∧(

P→(

Q∧

R))真值表法

PQR000001010011100101110111第1章命題邏輯Q∧R00010001P→(Q∧R)11110001

P11110000

Q11001100

R10101010

Q∧

R10001000

P→(

Q∧

R)10001111原式10000001編碼m0m7M1M2M3M4M5M6(3)(Q→P)∧(

P∧Q)推導(dǎo)法

第1章命題邏輯原式

(

Q∨P)∧(

P∧Q)分配率

(

P∧Q∧

Q)∨(

P∧Q∧P)FF

F

M0∧M1∧M2∧M3

∏(M0,M1,M2,M3)

(P∨Q)∧(P∨

Q)∧(

P∨Q)∧(

P∨

Q)

(3)(Q→P)∧(

P∧Q)真值表法PQ00011011第1章命題邏輯Q→P1011

P1100

P∧Q01000000編碼(Q→P)∧(

P∧Q)M0M1M2M3第1章命題邏輯第7節(jié) 命題演算的推論理論第7節(jié) 命題演算的推論理論1、有效結(jié)論2、形式證明3、推論規(guī)則第1章命題邏輯第7節(jié) 命題演算的推論理論1、 有效結(jié)論H1，H2，…，Hn，C命題公式當(dāng)且僅當(dāng)H1∧H2∧…∧Hn

C時則C是{H1，H2，…，Hn}的有效結(jié)論。前提集合第1章命題邏輯第7節(jié) 命題演算的推論理論2、 形式證明

構(gòu)造命題序列來描述推理過程，命題序列中的命題或者是前提，或者是前提推出的中間結(jié)果，其中最后一個命題就是結(jié)論。(1)WffG1(2)WffG2(3)WffG3

……(n)WffC(前提Hi)(中間結(jié)果)（結(jié)論）第1章命題邏輯第7節(jié) 命題演算的推論理論3、 推論規(guī)則(1)P規(guī)則（前提引用規(guī)則）(2)T規(guī)則（結(jié)論引用規(guī)則）(3)CP規(guī)則（條件證明規(guī)則）(4)F規(guī)則（間接證明法）第1章命題邏輯第7節(jié) 命題演算的推論理論（1）、 P規(guī)則（前提引用規(guī)則） 在推理過程中從前提集合中任取且僅取一個前提稱使用一次P規(guī)則。第1章命題邏輯第7節(jié) 命題演算的推論理論（2）、 T規(guī)則（結(jié)論引用規(guī)則） 在推理過程中，使用前面推論過程中所得到的中間結(jié)果，稱使用一次T規(guī)則。注意：直接證明方法實(shí)質(zhì)上就是：假設(shè)前件為真 證明后件必為真的方法。注意：命題序列中均為真命題。第1章命題邏輯第7節(jié) 命題演算的推論理論例、使用推論規(guī)則證明結(jié)論的有效性

(P∧Q)，Q∨R，R

P

(P∧Q)，Q∨R，R

P第1章命題邏輯第7節(jié) 命題演算的推論理論(1)R

(P規(guī)則)(2)Q∨R(P規(guī)則)(3)Q(T規(guī)則,(1)(2))(4)

(P∧Q)

(P規(guī)則)(5)

P(T規(guī)則,(3)(4))FF第1章命題邏輯第7節(jié) 命題演算的推論理論例、符號化并證明結(jié)論的有效性（1）如果我學(xué)習(xí)，那么我不放松數(shù)學(xué)；（2）如果我不打籃球，那么我就學(xué)習(xí)；（3）我放松了數(shù)學(xué)；結(jié)論：我打籃球了。確定原子命題P:我學(xué)習(xí)；Q:我放松數(shù)學(xué);R:我打籃球第1章命題邏輯第7節(jié) 命題演算的推論理論符號化（1）如果我學(xué)習(xí)，那么我不放松數(shù)學(xué)；（2）如果我不打籃球，那么我就學(xué)習(xí)；（3）我放松了數(shù)學(xué)；結(jié)論：我打籃球了。第1章命題邏輯第7節(jié) 命題演算的推論理論P(yáng)→QR→PQR使用推論規(guī)則證明結(jié)論的有效性第1章命題邏輯第7節(jié) 命題演算的推論理論(1)QP→Q,R→P,Q

R(P規(guī)則)(2)P→Q(P規(guī)則)(3)P (T規(guī)則,(1)(2))(4)R→P(P規(guī)則)(5)R(T規(guī)則,(3)(4))FFFF第1章命題邏輯第7節(jié) 命題演算的推論理論（3）、 CP規(guī)則（條件證明規(guī)則）

設(shè)H1，H2，…，Hn，P，Q是命題公式，若:H1∧H2∧…∧Hn∧P注意：CP規(guī)則用在結(jié)論為單條件的情況下

Q則:H1∧H2∧…∧Hn

P→Q第1章命題邏輯第7節(jié) 命題演算的推論理論

CP規(guī)則的使用方法使用條件:結(jié)論為單條件P→Q使用方法:前提集合Q前提集合P→Q第1章命題邏輯第7節(jié) 命題演算的推論理論例、符號化并證明結(jié)論的有效性(a)或者是天晴，或者是下雨；(b)如果是天晴,則開運(yùn)動會；(c)如果開運(yùn)動會，則停課；結(jié)論:如果不停課，則天在下雨。確定原子命題P：天晴；Q：天下雨；R：開運(yùn)動會；S：停課；第1章命題邏輯符號化(a)或者是天晴，或者是下雨；

(b)如果是天晴,則開運(yùn)動會；

(c)如果開運(yùn)動會，則停課；結(jié)論:如果不停課，則天在下雨。第1章命題邏輯P∨QP→RR→S

S→Q使用CP規(guī)則證明結(jié)論的有效性第1章命題邏輯P∨Q,P→R,R→S

S→Q(1)

S(P規(guī)則，附加前提)(2)R→S(P規(guī)則)F(3)R(T規(guī)則,(1)(2))(4)P→R(P規(guī)則)F(5)P(T規(guī)則,(3)(4))(6)P∨Q(P規(guī)則)T(7)Q(T規(guī)則,(5)(6))(8)

S→Q(CP規(guī)則，(1)(7))第1章命題邏輯第7節(jié) 命題演算的推論理論一致性和非一致性H1，H2，…，Hn命題公式當(dāng)且僅當(dāng):真值指派使得H1∧H2∧…∧Hn的真值為T時，則稱:H1，H2，…，Hn是一致的；如果對于每一組真值指派均使得H1∧H2∧…∧Hn的真值為F則稱:H1,H2,…,Hn是非一致的。第1章命題邏輯第7節(jié) 命題演算的推論理論（4）、 F規(guī)則（間接證明法）注意：F規(guī)則用在由前提集合不能直接推出結(jié)論的情況命題公式集合{H1，H2，…，Hn}一致性的C命題公式若:集合{H1，H2，…，Hn，C}非一致的則C是前提集合{H1，H2，…，Hn}的有效結(jié)論若:H1∧H2∧…∧Hn∧C

F則:H1∧H2∧…∧Hn

C第1章命題邏輯第7節(jié) 命題演算的推論理論F規(guī)則的使用方法F規(guī)則的使用條件:前提很少由前提集合不能直接推出結(jié)論F規(guī)則的使用方法:結(jié)論

∧前提集合

FP∧P有效結(jié)論假設(shè)前提第1章命題邏輯第7節(jié) 命題演算的推論理論例、使用F規(guī)則證明結(jié)論的有效性(1)A→

B，

(B∨

C)

A(2)P∨Q，P→R，Q→S

S∨R(3)A→(B→C)，

D∨A，B

D→C(1)A→

B，

(B∨

C)

A第1章命題邏輯(1)

(B∨C)(P規(guī)則)(2)

B∧

C(T規(guī)則，(1))(3)

B (T規(guī)則，(2))(4)A→B(P規(guī)則)FF(5)

A (T規(guī)則，(3)(4))第1章命題邏輯(1)A→

B，

(B∨

C)

A(1)

A

(P規(guī)則，）假設(shè)前提(2)A(T規(guī)則，(1))(3)A→B(P規(guī)則)(4)B(T規(guī)則，(2)(3))(5)

(B∨C)(P規(guī)則)(6)

B∧

C(T規(guī)則，(5))(7)

B(T規(guī)則，(6))(8)B∧

B (T規(guī)則，(4)(7),)矛盾式(9)

A (F規(guī)則，(1)(8))(2)P∨Q，P→R，Q→S

S∨R第1章命題邏輯(1)(S∨R)

(P規(guī)則，）假設(shè)前提(2)

S∧

R(T規(guī)則，(1))(3)

S(T規(guī)則，(2))(4)

R(T規(guī)則，(2))(5)P→R(P規(guī)則）(6)

PF(T規(guī)則，(4)(5))(7)Q→S(P規(guī)則）(8)

QF(T規(guī)則，(3)(7))(9)P∨Q(P規(guī)則）(10)PF(T規(guī)則，(8)(9))(11)

P∧P(T規(guī)則，(6)(10),)矛盾式(12)S∨R(，(1)(11))F規(guī)則第1章命題邏輯(1)(D→C)

(P規(guī)則，）假設(shè)前提(2)(D∨C)(T規(guī)則，(1))(3)D∧

C(T規(guī)則，(2))(4)D(T規(guī)則，(3))(5)

C(T規(guī)則，(3))(6)

D∨A(P規(guī)則）(7)AF(T規(guī)則，(4)(6))(8)A→(B→C)(P規(guī)則）(9)B→C (T規(guī)則，(7)(8))(10)B(P規(guī)則）(11)C(T規(guī)則，(9)(10))(12)

C∧C(T規(guī)則，(5)(11),)矛盾式(13)D→C(，(1)(12))F規(guī)則第2章謂詞邏輯第2章謂詞邏輯第1節(jié)謂詞邏輯的基本概念第2節(jié)謂詞邏輯的合式公式（謂詞公式）第3節(jié)謂詞邏輯的等價式和永真蘊(yùn)涵式第4節(jié)謂詞邏輯中的推論理論第2章謂詞邏輯命題邏輯的弱點(diǎn)1、表達(dá)能力差2、推理能力差第2章謂詞邏輯1、表達(dá)能力差P：王強(qiáng)是大學(xué)生Q：張麗是大學(xué)生第2章謂詞邏輯2、推理能力差例：蘇格拉底三段論：凡人必死，蘇格拉底是人，故蘇格拉底必死。PQRPQR?第2章謂詞邏輯第1節(jié) 謂詞邏輯的基本概念第1節(jié)謂詞邏輯的基本概念1、個體2、謂詞3、命題函數(shù)4、個體域5、個體變元6、命題函數(shù)應(yīng)注意的三點(diǎn)7、將命題函數(shù)變成命題的方法8、全稱量詞9、存在量詞10、轄域11、量詞的含義第1節(jié) 謂詞邏輯的基本概念1、個體注意：個體間的次序不能隨意顛倒。獨(dú)立存在的事物抽象的具體的用小寫的英文字母表示第2章謂詞邏輯第1節(jié) 謂詞邏輯的基本概念個體舉例（1）李紅是大學(xué)生。（2）李紅和李蘭是姐妹。（3）上海位于南京和杭州之間。第2章謂詞邏輯第1節(jié) 謂詞邏輯的基本概念2、謂詞注意：單獨(dú)的謂詞不是完整的命題，只有加入個體才能成為命題。第2章謂詞邏輯用來刻劃個體的性質(zhì)或個體之間關(guān)系的詞。用大寫的英文字母表示一元謂詞：和一個個體相聯(lián)，刻劃個體的性質(zhì)；多元謂詞：和多個個體相聯(lián)，刻劃個體間的關(guān)系第1節(jié) 謂詞邏輯的基本概念謂詞邏輯的表示方法第2章謂詞邏輯(1)一元謂詞:“b是A”A(b)(2)二元謂詞:“a是小于b的”B(a,b)(3)n元謂詞:聯(lián)結(jié)n個個體A(a1,a2,…,an)第1節(jié) 謂詞邏輯的基本概念謂詞邏輯的舉例第2章謂詞邏輯謂詞:H：能夠到達(dá)山頂個體:l:李四；t:老虎；c:汽車；H(l):H(t):H(c):李四能夠到達(dá)山頂。老虎能夠到達(dá)山頂。汽車能夠到達(dá)山頂。第1節(jié) 謂詞邏輯的基本概念謂詞邏輯的舉例(續(xù))第2章謂詞邏輯H(l)、H(t)、H(c):表示三個不同的命題共同的形式H(x)H(x):個體變元x能夠到達(dá)山頂。S(x,y):x和y是姐妹。T(x,y,z):x在y和z之間。第1節(jié) 謂詞邏輯的基本概念3、命題函數(shù)第2章謂詞邏輯一個n元謂詞An個個體變元a1,a2,…,anA(a1,a2,…,an)命題函數(shù)第1節(jié) 謂詞邏輯的基本概念4、個體域、全總個體域個體的變化范圍稱為個體域。所有個體域的總和稱為全總個體域。第2章謂詞邏輯第1節(jié) 謂詞邏輯的基本概念5、個體變元以某個個體域?yàn)樽冇虻淖冊Q為個體變元。第2章謂詞邏輯第1節(jié) 謂詞邏輯的基本概念謂詞邏輯的舉例主謂結(jié)構(gòu)：我高興。主謂賓結(jié)構(gòu)：我有輛自行車。主謂賓賓結(jié)構(gòu)：我給他一本書。第2章謂詞邏輯S(x):x高興。H(x,y):x有y。G(x,y,z):x給y一個z。第1節(jié) 謂詞邏輯的基本概念謂詞邏輯的優(yōu)點(diǎn)（1）把內(nèi)涵表示出來了；（2）把同一類的命題用命題函數(shù)表示出來。第2章謂詞邏輯第1節(jié) 謂詞邏輯的基本概念6、命題函數(shù)應(yīng)注意的三點(diǎn)（1）命題函數(shù)不是命題，只有把特定的個體代入時才是命題；（2）個體變元的取值有一個范圍（個體域）；（3）個體變元的順序不能顛倒。第2章謂詞邏輯第1節(jié) 謂詞邏輯的基本概念個體變元的取值范圍舉例S(x):x是大學(xué)生。(1)若x的范圍是信息學(xué)院2017級學(xué)生(2)若x的范圍是大連海事大學(xué)的所有師生

(3)若x的范圍是大連海事大學(xué)的附校學(xué)生第2章謂詞邏輯S(x)是永真式S(x)是可滿足式S(x)是永假式第1節(jié) 謂詞邏輯的基本概念7、將命題函數(shù)變成命題的方法（1）用個體域中的特定的個體去替換所有的個體變元；（2）在個體域上將命題函數(shù)量化。量詞：全稱量詞、存在量詞第2章謂詞邏輯第1節(jié) 謂詞邏輯的基本概念引進(jìn)量詞的舉例（1）所有的大學(xué)生都要參加軍訓(xùn)；（2）有些大學(xué)生是三好優(yōu)秀生；第2章謂詞邏輯第1節(jié) 謂詞邏輯的基本概念符號化（1）所有的大學(xué)生都要參加軍訓(xùn)；謂詞：…參加軍訓(xùn)；個體：大學(xué)生；第2章謂詞邏輯MxM(x)：大學(xué)生要參加軍訓(xùn)；沒有表示出來第1節(jié) 謂詞邏輯的基本概念符號化（2）有些大學(xué)生是三好優(yōu)秀生；謂詞：…是三好優(yōu)秀生；個體：大學(xué)生；第2章謂詞邏輯大學(xué)生是三好優(yōu)秀生；HxH(x)：沒有表示出來第1節(jié) 謂詞邏輯的基本概念8、全稱量詞第2章謂詞邏輯(

x)(

x)P(x)謂詞個體變元對于個體域中的所有個體x，謂詞P(x)均為真(

x)“所有的”“每一個”“任何一個”第1節(jié) 謂詞邏輯的基本概念9、存在量詞第2章謂詞邏輯(

x)(

x)P(x)在個體域中存在某個個體x，使得謂詞P(x)為真(

x)“存在一個”“某一個”“有些”“某些”第1節(jié) 謂詞邏輯的基本概念10、轄域第2章謂詞邏輯(

x)P(x)(

x)的轄域作用范圍(

x)P(x)(

x)的轄域第1節(jié) 謂詞邏輯的基本概念特性謂詞

第2章謂詞邏輯限制個體變元取值范圍的謂詞特性謂詞的作用:全總個體域?qū)嶋H的個體域第1節(jié) 謂詞邏輯的基本概念特性謂詞與邏輯聯(lián)結(jié)詞的對應(yīng)關(guān)系第2章謂詞邏輯(

x)“→”(

x)(→)特性謂詞(

x)“∧”(

x)(∧)特性謂詞第1節(jié) 謂詞邏輯的基本概念例、將下列命題符號化（1）所有的大學(xué)生都要參加軍訓(xùn)；（2）有些大學(xué)生是三好優(yōu)秀生；（3）沒有不犯錯誤的人；（4）發(fā)光的不都是金子；（5）每一個有理數(shù)都是實(shí)數(shù)；（6）某些實(shí)數(shù)是有理數(shù)；第2章謂詞邏輯第1節(jié) 謂詞邏輯的基本概念（1）所有的大學(xué)生都要參加軍訓(xùn)；特性謂詞第2章謂詞邏輯S(x)：x是大學(xué)生；M(x):x要參加軍訓(xùn)；符號化結(jié)果：(

x)(→)S(x)M(x)個體域第1節(jié) 謂詞邏輯的基本概念（2）有些大學(xué)生是三好優(yōu)秀生；第2章謂詞邏輯特性謂詞:S(x)：x是大學(xué)生；G(x):x是三好優(yōu)秀生；符號化結(jié)果：(

x)(∧)S(x)G(x)個體域第1節(jié) 謂詞邏輯的基本概念（3）沒有不犯錯誤的人；第2章謂詞邏輯特性謂詞:P(x)：M(x):x是要犯錯誤的；符號化結(jié)果：

(

x)(∧)P(x)

M(x)(

x)(→)P(x)M(x)x是人；個體域第1節(jié) 謂詞邏輯的基本概念（4）發(fā)光的不都是金子；特性謂詞第2章謂詞邏輯個體域L(x)：x是發(fā)光的G(x)：x是金子；符號化結(jié)果：(

x)(∧)L(x)

G(x)第1節(jié) 謂詞邏輯的基本概念（5）每一個有理數(shù)都是實(shí)數(shù)；第2章謂詞邏輯特性謂詞Q(x)：x是有理數(shù)R(x)：x是實(shí)數(shù)；符號化結(jié)果：(

x)(→)Q(x)R(x)個體域第1節(jié) 謂詞邏輯的基本概念（6）某些實(shí)數(shù)是有理數(shù)；第2章謂詞邏輯特性謂詞個體域R(x)：x是實(shí)數(shù)；Q(x)：x是有理數(shù)符號化結(jié)果：(

x)(∧)R(x)Q(x)第1節(jié) 謂詞邏輯的基本概念例、判斷下列命題的真假值R(x):x是實(shí)數(shù)；P(x):x2-1=(x+1)(x-1)Q(x):x+3=2（1）(

x)(R(x)→P(x))（2）(

x)(R(x)∧Q(x))（3）(

x)(R(x)∧P(x))（4）(

x)(R(x)→Q(x))第2章謂詞邏輯第1節(jié) 謂詞邏輯的基本概念（1）(

x)(R(x)→P(x))(

x)(R(x)→P(x))表示： 對于任意的x，如果x是實(shí)數(shù)，則必有

x2-1=(x+1)(x-1)該命題是真命題。第2章謂詞邏輯第1節(jié) 謂詞邏輯的基本概念（2）(

x)(R(x)∧Q(x))(

x)(R(x)∧Q(x))表示： 存在x，x是實(shí)數(shù)，并且x+3=2該命題是真命題。第2章謂詞邏輯第1節(jié) 謂詞邏輯的基本概念（3）(

x)(R(x)∧P(x))(

x)(R(x)∧P(x))表示：

存在x，x是實(shí)數(shù)，并且x2-1=(x+1)(x-1)該命題是真命題。第2章謂詞邏輯第1節(jié) 謂詞邏輯的基本概念（4）(

x)(R(x)→Q(x))(

x)(R(x)→Q(x))表示： 對于任意的x，如果x是實(shí)數(shù)，則必有x+3=2該命題是假命題。第2章謂詞邏輯第1節(jié) 謂詞邏輯的基本概念11、量詞的含義設(shè)個體域x={a1,a2,…,an}則：第2章謂詞邏輯(

x)P(x)＝P(a1)P(a2)……P(an)∧∧∧(

x)P(x)＝P(a1)P(a2)……P(an)∨∨∨第1節(jié) 謂詞邏輯的基本概念量詞是不可交換的(

y)(

x)P(x，y)第2章謂詞邏輯(

x)(

y)P(x，y)第1節(jié) 謂詞邏輯的基本概念例、量詞不可交換性舉例個體域：人P(x,y):y是x的母親；(

y)(

x)P(x，y)：(

x)(

y)P(x，y)：第2章謂詞邏輯有一個人是所有人的母親任何人都有自己的母親。假真第2章謂詞邏輯第2節(jié) 謂詞邏輯的合式公式第2節(jié)謂詞邏輯的合式公式1、謂詞公式的遞歸定義2、約束變元3、自由變元4、約束變元的改名規(guī)則5、自由變元的代入規(guī)則第2章謂詞邏輯第2節(jié) 謂詞邏輯的合式公式1、謂詞公式的遞歸定義(1)原子謂詞公式是Wff;

(2)如果A是Wff，則

A是Wff；(3)如果A和B是Wff，則(A∧B)、(A∨B)、(A→B)、(A?B)都是Wff；