《離散數(shù)學(xué)》命題邏輯

第1章命題邏輯

命題邏輯

邏輯是研究推理的科學(xué)。

數(shù)理邏輯是用數(shù)學(xué)方法研究推理的形式結(jié)構(gòu)和推理規(guī)律的數(shù)學(xué)學(xué)科。由于它使用一套符號來表達各種推理的邏輯關(guān)系，因此數(shù)理邏輯又稱為符號邏輯。從廣義上講，數(shù)理邏輯包括集合論、模型論、遞歸論、證明論和命題演算、謂詞演算，但本書只研究兩個演算：命題演算和謂詞演算兩個演算。數(shù)理邏輯研究的中心問題是推理，而推理的前提與結(jié)論都是表達判斷的陳述句，因而表達判斷的陳述句構(gòu)成了推理的基本單位。數(shù)理邏輯稱之為命題。

第1章命題邏輯一、命題定義1.1

能判斷真假的陳述句叫做命題。

該定義有兩層含義：

(1)命題是陳述句。其他的語句，如疑問句、祈使句、感嘆句均不是命題；

(2)這個陳述句對事物的判斷是否符合客觀事實是可以給出結(jié)論的：不是真（符合客觀事實）就是假（不符合客觀事實），不能不真也不假，也不能既真又假，所以又稱二值邏輯。1.1命題符號化及聯(lián)結(jié)詞二、命題的真值命題所表示的判斷結(jié)果稱為命題的真值。⑴真值只取兩個值：真（判斷與事實相符）或假（判斷與事實不符）。通常用1（或字母T）表示真，用0（或字母F）表示假。⑵真命題：真值為真的命題。⑶假命題：真值為假的命題。1.1命題符號化及聯(lián)結(jié)詞例6.1.1

判斷下列語句是否為命題，并指出其真值。（1）北京是中國的首都。（2）5可以被2整除。（3）2+2=5。（4）請勿吸煙。祈使句（5）烏鴉是黑色的嗎？疑問句（6）這個小男孩多勇敢?。「袊@句（7）地球外的星球上存在生物。（8）我正在說謊。悖論注意：一個語句本身是否能分辨真假與我們是否知道它的真假是兩回事。也就是說，對于一個句子，有時我們可能無法判定它的真假，但它本身卻是有真假的，那么這個語句是命題，否則就不是命題。悖論不是命題。1.1命題符號化及聯(lián)結(jié)詞判斷一個句子是否為命題1、是否為陳述句2、真值是否唯一X+y>51+101=110真值是否唯一與我們是否知道它的真值是兩回事三、命題的分類原子命題（AutomicProposition）：不能再分解為更簡單的陳述句的命題；也稱簡單命題。復(fù)合命題（CompoundProposition）：由若干簡單命題用聯(lián)結(jié)詞聯(lián)結(jié)成的命題。例如：“雪是白的”是原子命題；“昨天下雨，而且打雷”，“如果明天天晴我就去打球或者游泳”都是復(fù)合命題。

1.1命題符號化及聯(lián)結(jié)詞四、命題的表示引進數(shù)學(xué)符號來表示命題。常用大寫英文字母A,B,…,P,Q或帶下標(biāo)的字母P1,P2,P3,

…,或數(shù)字(1),[2],…,等表示命題，稱之為命題標(biāo)識符。例如：

P：羅納爾多是球星。

Q：5是負數(shù)。

P3：明天天氣晴。

(2)：太陽從西方升起。皆為符號化的命題，其真值依次為1、0、1或0、0。1.1命題符號化及聯(lián)結(jié)詞命題標(biāo)識符有命題常量、命題變元和原子變元之分。命題常元：真值確定的命題標(biāo)識符。命題變元：真值不確定，僅表示任意命題的位置標(biāo)志。原子變元：當(dāng)命題變元表示原子命題時，該變元稱為原子變元如果命題符號P代表命題常元則意味它是某個具體命題的符號化，如果P代表命題變元則意味著它可指代任何具體命題。1.1命題符號化及聯(lián)結(jié)詞一、否定聯(lián)結(jié)詞“

”（或“

”）否定聯(lián)結(jié)詞是一元聯(lián)結(jié)詞。相當(dāng)于日常用語中的“非”，“不”，“無”，“沒有”等。

設(shè)P為一命題，P的否定是一個新的復(fù)合命題,稱為P的否定式，記作“

P”，讀作“非P”。

P為真當(dāng)且僅當(dāng)P為假。

P

P

0

1

1

01.1命題符號化及聯(lián)結(jié)詞例6.1.2.P:天津是一個城市.Q:3是偶數(shù).于是:┐P:天津不是一個城市.

┐Q:3不是偶數(shù).例6.1.3.P:蘇州處處清潔.Q:這些都是男同學(xué).┐P:蘇州不處處清潔(注意,不是處處不清潔).┐Q:這些不都是男同學(xué).1.1命題符號化及聯(lián)結(jié)詞二、合取聯(lián)結(jié)詞“∧”合取詞是二元聯(lián)結(jié)詞。相當(dāng)于自然語言中的“與”、“并且”、“而且”、“也”等。設(shè)P,Q為二命題，復(fù)合命題“P與Q”記作P∧Q。P∧Q為真當(dāng)且僅當(dāng)P和Q同時為真。

PQ

P∧Q

00

0

01

0

10

0

11

11.1命題符號化及聯(lián)結(jié)詞例6.1.4.

將下列命題符號化.(1)李平既聰明又用功.(2)李平雖然聰明,但不用功.(3)李平不但聰明,而且用功.(4)李平不是不聰明,而是不用功.解:

設(shè)P:李平聰明.Q:李平用功.則(1)P∧Q(2)P∧┐Q(3)P∧Q(4)┐(┐P)∧┐Q注意：不要見到“與”或“和”就使用聯(lián)結(jié)詞∧！例如:(1)李敏和李華是姐妹。

(2)李敏和張華是朋友。1.1命題符號化及聯(lián)結(jié)詞1.1命題符號化及聯(lián)結(jié)詞例6.1.5.

試生成下列命題的合取.(1)P:我們在6-503.Q:今天是星期二.

(2)S：李平在吃飯.R：張明在吃飯.解:(1)P∧Q:我們在6-503且今天是星期二.(2)S∧R:李平與張明在吃飯.三、析取聯(lián)結(jié)詞“∨”析取詞是二元聯(lián)結(jié)詞。相當(dāng)于自然語言中的“或”、“要么…要么…”等。設(shè)P,Q為二命題，復(fù)合命題“P或Q”，記作P∨Q。P∨Q為真當(dāng)且僅當(dāng)P與Q中至少有一個為真。

PQ

P∨Q

00

0

01

1

10

1

11

1在現(xiàn)代漢語中，“或”有“可兼或”和“排斥或”之分。這里只是“可兼或”。例6.1.6（1）小王愛打球或愛跑步。（可兼或）

設(shè)P：小王愛打球。Q：小王愛跑步。則上述命題可符號化為：P∨Q1.1命題符號化及聯(lián)結(jié)詞1.1命題符號化及聯(lián)結(jié)詞（2）林芳學(xué)過英語或法語。（可兼或）設(shè)P：林芳學(xué)過英語。Q：林芳學(xué)過法語。則上述命題可符號化為：P∨Q（3）派小王或小李中的一人去開會。（排斥或）

設(shè)P：派小王去開會。Q：派小李去開會。則上述命題可符號化為：(P∧┐Q)∨(┐P∧Q)四、蘊含聯(lián)結(jié)詞“

”蘊含詞是二元聯(lián)結(jié)詞。相當(dāng)于自然語言中的“若…則…”、“如果…就…”、“只有…才…”。設(shè)P,Q為二命題,復(fù)合命題“若P則Q”記作P

Q。并稱P為前件，Q為后件。P

Q為假當(dāng)且僅當(dāng)P為真且Q為假。

PQP

Q

00

1

01

1

10

0

11

11.1命題符號化及聯(lián)結(jié)詞例6.1.7

將下列命題符號化。1）天不下雨，則草木枯黃。

P：天下雨。Q：草木枯黃。則原命題可表示為：┐P→Q。2）如果小明學(xué)日語，小華學(xué)英語，則小芳學(xué)德語。

P：小明學(xué)日語.Q：小華學(xué)英語.R：小芳學(xué)德語.則原命題可表示為：(P∧Q)→R3）只要不下雨，我就騎自行車上班。

P：天下雨。Q：我騎自行車上班。則原命題可表示為：┐P→Q。1.1命題符號化及聯(lián)結(jié)詞4）只有不下雨，我才騎自行車上班。

P：天下雨。Q：我騎自行車上班。則原命題可表示為：

Q

→┐P。注意:

(1)與自然語言的不同：前件與后件可以沒有任何內(nèi)在聯(lián)系！

(2)在數(shù)學(xué)中，“若P則Q”往往表示前件P為真，則后件Q為真的推理關(guān)系.但數(shù)理邏輯中，當(dāng)前件P為假時，P→Q的真值為真。1.1命題符號化及聯(lián)結(jié)詞“如果p，則q”的不同表述法很多：

若p，就q

只要p，就qp僅當(dāng)q

只有q

才p

除非q,才p除非q,否則非p，1.1命題符號化及聯(lián)結(jié)詞

例：設(shè)p:天冷，q:小王穿羽絨服，將下列命題符號化

(1)只要天冷，小王就穿羽絨服.(2)因為天冷，所以小王穿羽絨服.(3)若小王不穿羽絨服，則天不冷.(4)只有天冷，小王才穿羽絨服.(5)除非天冷，小王才穿羽絨服.(6)除非小王穿羽絨服，否則天不冷.(7)如果天不冷，則小王不穿羽絨服.(8)小王穿羽絨服僅當(dāng)天冷的時候.注意：

p

q與

p

q

等值（真值相同）p

qp

qp

qp

qq

p

q

pq

pq

p1.1命題符號化及聯(lián)結(jié)詞五、等價聯(lián)結(jié)詞“

”等價聯(lián)結(jié)詞是二元聯(lián)結(jié)詞。相當(dāng)于自然語言中的“等價”、“當(dāng)且僅當(dāng)”、“充要條件”等，真值表如右圖。

設(shè)P,Q為二命題，復(fù)合命題“P當(dāng)且僅當(dāng)Q”記作P

Q。

P

Q為真當(dāng)且僅當(dāng)P，Q真值相同。

PQ

P

Q

00

1

01

0

10

0

11

11.1命題符號化及聯(lián)結(jié)詞注：（1）P僅當(dāng)Q可譯為P→QP當(dāng)Q可譯為Q→PP當(dāng)且僅當(dāng)Q譯為P

Q

（2）命題P

Q所表達的邏輯關(guān)系是,P與Q互為充分必要條件,相當(dāng)于(P

Q)∧(Q

P).

雙條件聯(lián)結(jié)詞連接的兩個命題之間可以沒有因果關(guān)系。例6.1.8分析下列命題的真值.(1)2+2=4當(dāng)且僅當(dāng)3是奇數(shù).(P

Q)P：2+2=4.Q：3是奇數(shù).

(2)2+2=4當(dāng)且僅當(dāng)3不是奇數(shù).(P

┐Q)(3)2+2≠4當(dāng)且僅當(dāng)3是奇數(shù).(┐P

Q)(4)2+2≠4當(dāng)且僅當(dāng)3不是奇數(shù).(┐P

┐Q)1.1命題符號化及聯(lián)結(jié)詞5種聯(lián)結(jié)詞類似5種運算符，稱之為邏輯運算符，有運算的優(yōu)先級順序：聯(lián)結(jié)詞的優(yōu)先順序為：

,

,

,

,;

如果出現(xiàn)的聯(lián)結(jié)詞同級，又無括號時，則按從左到右的順序運算;若遇有括號時，應(yīng)該先進行括號中的運算。1.1命題符號化及聯(lián)結(jié)詞一、概念定義1.3命題公式按下列規(guī)則生成：（1）單個命題常項或變項p,q,r,...,0,1是命題的公式；（2）如果α是命題公式，則

α也是命題公式；（3）如果α和β是命題公式，則α

β，α

β，α→β，α

β均是命題公式；（4）只有有限次地利用（1）—（3）形成的符號串才是命題公式。例如：

(P

Q)，P→(P

Q)等都是命題公式，而CP→Q，R→P等不是命題公式。1.2命題公式及分類注:

(1)命題公式也稱為合式公式，由命題常項、命題變項、聯(lián)結(jié)詞和括弧組成。

(2)如果把公式中的命題變元代以原子命題或復(fù)合命題，則該公式便是一個復(fù)合命題。因此，對復(fù)合命題的研究可化為對命題公式的研究。⑶命題公式一般不是命題,僅當(dāng)公式中的命題變元用確定的命題代入時，才得到一個命題。其真值依賴于代換變元的那些命題的真值。⑷日常生活中的推理問題是用自然語言描述的，因此要進行推理演算必須先把自然語言符號化（或形式化）成邏輯語言，即命題公式。然后再根據(jù)邏輯演算規(guī)律進行推理演算。1.2命題公式及分類二、命題符號化(1)分析出各簡單命題,將它們符號化;(2)使用合適的聯(lián)結(jié)詞,把簡單命題逐個的聯(lián)結(jié)起來,組成復(fù)合命題的符號化表示.例6.3.2

將下列用自然語言描述的命題符號化。（1）我和他既是弟兄又是同學(xué)。解令P：我和他是弟兄；Q：我和他是同學(xué)，則該語句可符號化為P∧Q。（2）我和你之間至少有一個要去海南島。解令P：我去海南島；Q：你去海南島，則該語句可符號化為P∨Q。1.2命題公式及分類（3）如果他沒來見你，那么他或者是生病了，或者是不在本地。解令P：他來見你；Q：他生??；R：他在本地，則該語句可符號化為?P→(Q∨?R)。（4）n是偶數(shù)當(dāng)且僅當(dāng)它能被2整除。解令P：n是偶數(shù)；Q：n能被2整除，則該語句可符號化為P?Q。1.2命題公式及分類三、公式的解釋或賦值設(shè)P1,P2,…,Pn是出現(xiàn)在公式G中的全部的命題變元,指定P1,P2,…,Pn的一組真值，則稱這組真值為G的一個賦值或解釋，記作I。公式G在I下的真值記作TI(G)。若指定的一組值使A的真值為真(假),稱這組值為A的成真(假)賦值。例如:對公式(P

Q)∧R，賦值011(即令P=0，Q=1，R=1)為(P

Q)∧R的成真賦值。

賦值011也可記作｛P,Q,

R｝。含有n個命題變元的公式共有2n組不同的賦值。1.2命題公式及分類四、真值表將命題公式G在其所有解釋下所取的真值列成一個表,稱做命題公式G的真值表。為方便構(gòu)造真值表，特約定如下：①命題變元按字典序排列。②對每個指派，以二進制數(shù)從小到大或從大到小順序列出。③若公式較復(fù)雜，可先列出各子公式的真值(若有括號，則應(yīng)從里層向外層展開)，最后列出所求公式的真值。1.2命題公式及分類PQRQ

RP

(Q

R)

(P

(Q

R))000001010011100101110111011101111111011100001000例6.3.1

利用真值表求命題公式

(P→(Q

R))的成真指派和成假指派。1.2命題公式及分類五、命題公式的分類重言式/永真式：若G在所有解釋下都是真的，則稱G為重言式或永真式。矛盾式/永假式：G在所有解釋下都是假的，則稱G為稱為矛盾式或永假式?？蓾M足式：若G不是恒假的。幾點說明

1）G是可滿足式的等價定義是：G至少存在一個成真指派。

2）重言式一定是可滿足式，但反之不真。1.2命題公式及分類

3）如何利用好真值表來判斷公式的類型：①若真值表最后一列全為1，則公式為重言式；②若真值表最后一列全為0，則公式為矛盾式；③若真值表最后一列中至少有一個1，則公式為可滿足式。1.2命題公式及分類例6.3.2

判斷下列公式的類型。(1)(P∧Q)

Q解令

=(P

Q)

Q

PQP

Q

00011011000111111.2命題公式及分類(2)(Q

P)∧(?P∧Q)解

令

=(Q

P)

(?P

Q)

PQQ

P?P

Q

000110111011010000001.2命題公式及分類(3)(P∨?Q)

(?P∧Q∧R)解

令

=(P

?Q)

(?P

Q

R)

PQRP

?Q?P

Q

R

0000010100111001011101111100111100010000001100001.2命題公式及分類一、公式等值（等價）問題：是否存在兩個命題公式G和H，在任意解釋下它們的真值都相同？若存在，怎樣用已有的概念描述上述現(xiàn)象？解答：存在，比如n=2的命題公式,P

Q與(PQ)在任意解釋下均有系統(tǒng)的真值。描述：GH是重言式給這種現(xiàn)象引入一個概念：數(shù)學(xué)上用〔相等，等價〕，這里用〔等價、等值〕。1.3等值演算定義1.10

設(shè)G，H是兩個命題公式，若G

H是重言式，則稱G與H等價（等值），記作G

H。⑴G

H當(dāng)且僅當(dāng)G

H為重言式。⑵

與

是兩個完全不同的符號。

不是命題聯(lián)結(jié)詞，而是公式間的關(guān)系符號，α

β不表示一個公式，即不代表命題，它表示公式α與公式β有等價關(guān)系，

是命題聯(lián)結(jié)詞，α

β是一個公式，表示某個命題。公式之間的等價關(guān)系的特點：自反的對稱的傳遞的1.3等值演算二、公式等價（等值）的判定方法（1)判斷兩個公式α與β是否等值，用真值表法判斷α

β是否為重言式。

例1.7

判斷

(P

Q)與

P

Q這兩個命題公式是否等值。PQ

(P

Q)

P

Q

(P

Q)

(

P

Q)00011011100010001111這一列可不要1.3等值演算三、公式等價的判定方法（2)根據(jù)已知的等價公式,推演出另外一些等價公式的過程稱為等值演算.常用的等價公式：（1）雙重否定律：α

(

α)

（2-3）等冪律：α

α

α，α

α

α（4-5）交換律：

α

β

β

α，α

β

β

α（6-7）結(jié)合律

(α

β)

γ

α

(β

γ)，

(α

β)

γ

α

(β

γ)1.3等值演算（8-9）分配律

α

(β

γ)

(α

β)

(α

γ)（

對

的分配律）

α

(β

γ)

(α

β)

(α

γ)（

對

的分配律）（10-11）德摩根律

(α

β)

α

β，

(α

β)

α

β（12-13）吸收律

α

(α

β)

α，α

(α

β)

α（14-15）零律：α

1

1，α

0

0（16-17）同一律：α

0

α，α

1

α（18）排中律：α

α

1（19）矛盾律：α

α

01.3等值演算（20）蘊含等值式

α

β

α

β(21)等價（雙條件）等值式

α

β

(α

β)

(β

α)，

α

β

(α

β)

(

α

β)（22）假言易位

α

β

β

α（23）等價否定等值式

α

β

α

β（24）歸謬論

(α

β)

(α

β)

α1.3等值演算等值演算中的置換規(guī)則置換：用一個命題公式代換另一個命題公式中的一個子公式。

定理1.1（置換定理）設(shè)

(A)是含命題公式A的命題公式，

(B)是用命題公式B置換了

(A)中的A之后的得到的命題公式，如果A

B，則

(A)

(B)。

1.3等值演算例6.4.1

用等值演算法證明

(P

Q)→R

(P→R)

(Q→R)。證明(P

Q)

R

(P

Q)

R（蘊含等值式）

(

P

Q)

R（德摩根律）

(

P

R)

(

Q

R)（分配律）

(P

R)

(

Q

R)（蘊含等值式）

(P

R)

(Q

R)（蘊含等值式）

1.3等值演算例6.4.2

用等值演算法判斷下列公式的類型。（1）((P→Q)

P)→Q解

((P

Q)

P)

Q

((

P

Q)

P)

Q

((

P

Q)

P)

Q

(

(

P

Q)

P)

Q

(P

Q)

P)

Q

((P

P)

(

Q

P))

Q

(1

(

Q

P))

Q

(

Q

Q)

P

1

P

1

因此該公式是重言式。1.3等值演算（2）

(P→(P

Q))

R

解

(P

(P

Q))

R

(

P

P

Q)

R

(P

P

Q)

R

0

R

0因此該公式是矛盾式。1.3等值演算（3）P

(((P

Q)

P)→Q)

解P

(((P

Q)

P)

Q)

P

(

((P

Q)

P)

Q)

P

(

((P

P)

(Q

P))

Q)

P

(

(0

(Q

P))

Q)

P

(

Q

P

Q)

P

1

P

從最后結(jié)果可以看出該公式既不是重言式，也不是矛盾式，而是可滿足式。

1.3等值演算

例6.4.3

設(shè)有A，B，C，D四人做百米競賽，觀眾甲，乙，丙分別對比賽的名次進行了預(yù)測：甲說C第一，B第二；乙說C第二，D第三；丙說A第二，D第四；比賽結(jié)束后發(fā)現(xiàn)甲，乙，丙每人報告的情況都是各對一半，試問實際名次如何（無并列者）？

1.3等值演算解設(shè)Pi，Qi，Ri，Si分別表示A，B，C，D是第i（i=1,2,3,4）名，由于甲，乙，丙每人報告的情況都各對一半，故有下面三個等值式：①(R1

Q2)

(

R1

Q2)

1②(R2

S3)

(

R2

S3)

1③(P2

S4)

(

P2

S4)

1因為重言式的合取仍為重言式，所以①

②

1。即

1

((R1

Q2)

(

R1

Q2))

((R2

S3)

(

R2

S3))

(R1

Q2

R2

S3)

(R1

Q2

R2

S3)

(

R1

Q2

R2

S3)

(

R1

Q2

R2

S3)

1.3等值演算由于C不能既第一又第二，B和C不能并列第二，所以

R1

Q2

R2

S3

0

R1

Q2

R2

S3

0于是得④(R1

Q2

R2

S3)

(

R1

Q2

R2

S3)

1再將③與④合取得③

④

1，即1

((P2

S4)

(

P2

S4))

((R1

Q2

R2

S3)

(

R1

Q2

R2

S3))

(P2

S4

R1

Q2

R2

S3)

(P2

S4

R1

Q2

R2

S3)

(

P2

S4

R1

Q2

R2

S3)

(

P2

S4

R1

Q2

R2

S3)1.3等值演算由于A，B不能同時第二，D不能第三又第四，所以

P2

S4

R1

Q2

R2

S3

0

P2

S4

R1

Q2

R2

S3

0

P2

S4

R1

Q2

R2

S3

0于是可得⑤P2

S4

R1

Q2

R2

S3

1因此C第一，A第二，D第三，B第四。

1.3等值演算四、聯(lián)結(jié)詞全功能集前面已經(jīng)引入了五中聯(lián)結(jié)詞，邏輯設(shè)計中還常用到其它的一些聯(lián)結(jié)詞：異或（排斥或）聯(lián)結(jié)詞

與非聯(lián)結(jié)詞

或非聯(lián)結(jié)詞

在一個形式系統(tǒng)中引入多少聯(lián)結(jié)詞好？自然系統(tǒng)中越多越好，應(yīng)用方便公理系統(tǒng)中越少越好，研究方便一個聯(lián)結(jié)詞的集合應(yīng)該滿足什么條件？1.4聯(lián)結(jié)詞全功能集對于命題公式，我們關(guān)注的是它的真值情況。N個命題變元的命題公式，每個變元有兩種賦值情況，共有2N中賦值情況。而每種賦值，又有兩種結(jié)果，共有

種不同的賦值、取值情況。一個好的方法是，每種賦值、取值情況用一個聯(lián)結(jié)詞表示?？梢杂煤瘮?shù)的觀點來研究命題公式的變元賦值與最終命題公式的取值之間的關(guān)系1.4聯(lián)結(jié)詞全功能集定義

稱定義域為{00…0,00…1,…,11…1}，值域為{0,1}的函數(shù)是n元真值函數(shù)，定義域中的元素是長為n的0,1串.

常用F:{0,1}n

{0,1}表示F是n元真值函數(shù).

共有個n元真值函數(shù).例如F:{0,1}2

{0,1}，且F(00)=F(01)=F(11)=0，F(xiàn)(01)=1，則F為一個確定的2元真值函數(shù).1.4聯(lián)結(jié)詞全功能集對于任何一個含n個命題變項的命題公式A，都存在惟一的一個n元真值函數(shù)F為A的真值表.等值的公式對應(yīng)的真值函數(shù)相同.下表給出所有2元真值函數(shù)對應(yīng)的真值表,每一個含2個命題變項的公式的真值表都可以在下表中找到.

例如：p

q,

p

q,(

p

q)

(

(p

q)

q)等都對應(yīng)表中的1.4聯(lián)結(jié)詞全功能集2元真值函數(shù)對應(yīng)的真值表pq00011011

00000000000011110011001101010101

pq00011011

11111111000011110011001101010101

1.4聯(lián)結(jié)詞全功能集pq00011011

00000000000011110011001101010101

pq00011011

11111111000011110011001101010101

1.4聯(lián)結(jié)詞全功能集

0

p

q的非

pq

p的非

q異或

qq

p

pp

q

1聯(lián)結(jié)詞的全功能集

定義

在一個聯(lián)結(jié)詞的集合中，如果一個聯(lián)結(jié)詞可由集合中的其他聯(lián)結(jié)詞定義，則稱此聯(lián)結(jié)詞為冗余的聯(lián)結(jié)詞，否則稱為獨立的聯(lián)結(jié)詞.例如,在聯(lián)結(jié)詞集{

,

,

,

,

}中，由于

p

q

p

q,所以，

為冗余的聯(lián)結(jié)詞;類似地，

也是冗余的聯(lián)結(jié)詞.又在{

,

,

}中，由于

p

q(p

q)，所以，

是冗余的聯(lián)結(jié)詞.類似地，

也是冗余的聯(lián)結(jié)詞.1.4聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞的全功能集(續(xù))定義

設(shè)S是一個聯(lián)結(jié)詞集合，如果任何n(n

1)元真值函數(shù)都可以由僅含S中的聯(lián)結(jié)詞構(gòu)成的公式表示，則稱S是聯(lián)結(jié)詞全功能集.說明：若S是聯(lián)結(jié)詞全功能集，則任何命題公式都可用S中的聯(lián)結(jié)詞表示.

若S1,S2是兩個聯(lián)結(jié)詞集合，且S1

S2.若S1是全功能集，則S2也是全功能集.

若一個聯(lián)結(jié)詞的全功能集中不含冗余的聯(lián)結(jié)詞，則稱它是極小全功能集。1.4聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞的全功能集實例(6)S6={

}極小全功能集(7)S8={

}極小全功能集(8){

,

}極小全功能集

(1)S1={

,

,

,

}(2)S2={

,

,

,

,

}

(3)S3={

,

}(4)S4={

,

}(5)S5={

,

}

而{

},{

}等則不是聯(lián)結(jié)詞全功能集.

1.4聯(lián)結(jié)詞全功能集四、對偶原理定義

如果命題公式α中只出現(xiàn)命題變元、命題常元、命題聯(lián)結(jié)詞

、

和

，則稱α為限制性命題公式。

定義1.7

在限制性公式α中，將聯(lián)結(jié)詞

換成

，將

換成

，將0換成1，將1換成0，所得到的公式稱為α的對偶式，記為α*。1.5對偶與范式顯然，α和α*互為對偶式。例如，公式

((P

Q)

(

R))與公式

((P

Q)

(

R))互為對偶式。

定理1.2

設(shè)A和A*是互為對偶的兩個公式，P1,P2,…,Pn是其命題變元，并把A和A*寫成函數(shù)的形式，則：

A(P1,P2,…,Pn)

A*(

P1,

P2,…,

Pn)A(

P1,

P2,…,

Pn)

A*(P1,P2,…,Pn)

1.5對偶與范式定理1.3（對偶原理）設(shè)α(P1,P2,…,Pn)和β(P1,P2,…,Pn)是兩個公式，若α

β，則α*

β*。由對偶原理，A為重言式，則A*為矛盾式。如果P

(P

0)

1，則P

(P

0)

01.5對偶與范式一、簡單析?。ê先。┦胶唵挝鋈∈?僅由有限個命題變項及其否定構(gòu)成的析取式。如p,

q,p

q,p

q

r,…簡單合取式:僅由有限個命題變項及其否定構(gòu)成的合取式。如p,

q,p

q,p

q

r,…注意：（1）一個簡單析取式是重言式當(dāng)且僅當(dāng)它同時含有某個命題變元及其否定式,如p

p

q。（2）一個簡單合取式是矛盾式當(dāng)且僅當(dāng)它同時含有某個命題變元及其否定式，如p

p

r。1.5對偶與范式二、析?。ê先。┓妒蕉x1.19

僅由有限個簡單合取式構(gòu)成的析取式稱為析取范式。即：析取范式具有形式α1

α2

…

αn，其中αi(i=1,2,…,n)為簡單合取式。命題公式(P

Q)

(

P

Q)是析取范式。定義1.19僅由有限個簡單析取式構(gòu)成的合取式稱為合取范式。即：合取范式具有形式α1

α2

…

αn，其中αi(i=1,2,…,n)為簡單析取式。

(P

R)

(P

Q

R)

(

P

R)是合取范式。1.5對偶與范式定義

析取范式與合取范式統(tǒng)稱為范式。合(析)取范式的對偶式是析(合)取范式.一個析取范式是矛盾式它的每個簡單合取式都是矛盾式。一個合取范式是重言式它的每個簡單析取式都是重言式。定理1.4（范式存在定理）

任一命題公式都存在著與之等價的析取范式和合取范式。1.5對偶與范式下面給出求任一公式的析取范式和合取范式的步驟:

（1）利用蘊含等值式和等價等值式消去公式中的聯(lián)結(jié)詞“→”和“

”；

α→β??α∨β；

α?β?(α→β)∧(β→α)（2）利用德摩根律和雙重否定律將聯(lián)結(jié)詞“

”消去或內(nèi)移到各命題變元之前；

?(α∨β)??α∧?β；?(α∧β)??α∨?β；?(?α)?α（3）利用分配律、交換律、結(jié)合律將公式化為所需要的范式。

?(A∨B)

?A∧?B?(A∧B)

?A∨?B

1.5對偶與范式例1.14

求((P

Q)

R)

P的析取范式和合取范式。解（1）求合取范式((P

Q)

R)

P

(

(P

Q)

R)

P（消去

）

(

(P

Q)

R)

P

((

P

Q)

R)

P（

深入）

((

P

Q)

R)

P

((P

Q)

R)

P

(P

Q

P)

(

R

P)（

對

的分配律）再利用交換律和等冪律得

(P

Q

P)

(

R

P)

(P

Q)

(

R

P)

可見，(P

Q)

(

R

P)也是原公式的合取范式，這說明與某個命題公式等值的合取范式不是惟一的。

1.5對偶與范式（2）析取范式用

對

的分配律就可得到析取范式，即

((P

Q)

R)

P

((P

Q)

R)

P

(P

R)

(Q

R)

P(

對

分配律)

最后結(jié)果為原公式的析取范式。利用交換律和吸收律得P

(Q

R)，此公式也是原公式的析取范式，由此可見，與命題公式等價的析取范式也不是惟一的。注意：

(1)單個命題變元既是簡單合取式，又是簡單析取式；

(2)公式P∧Q∧R既可以看成是合取范式，也可以看成是析取范式1.5對偶與范式例6.5.2：求(P

Q)

R的析取范式與合取范式。解:原式

((P

Q)

R)∧(R

(P

Q))

(┐(P

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

Q))

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

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

((P∨R)∧(┐Q∨R)∧(┐R∨┐P∨Q)(合取范式)

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

(P∧┐Q∧┐R)∨(R∧┐P)∨(R∧Q)(析取范式)1.5對偶與范式

例6.5.2

判別公式((P→Q)

P)→Q是否為重言式或矛盾式。

解

((P

Q)

P)

Q

((

P

Q)

P)

Q

(

P

Q)

P

Q

(P

Q)

P

Q

(P

P

Q)

(

Q

P

Q)

在公式的合取范式中，每一個簡單析取式均含有互補對，為重言式，因此原式為重言式。

1.5對偶與范式定義

在含有n個命題變項的簡單合取式中，若每個命題變元與其否定不同時存在，而二者之一必須出現(xiàn)且僅出現(xiàn)一次，且第i（1

i

n）個命題變元或其否定出現(xiàn)在左起的第i位上（若命題變元無角標(biāo)，則按字典順序），這樣的簡單合取式為極小項.⑴n個命題變元共可產(chǎn)生2n個不同的極小項，其中每個極小項都有且僅有一個成真指派。(2)在極小項中，將命題變元看成1，命題變元的否定看成0，則每個極小項惟一地對應(yīng)一個二進制數(shù)，若該二進制數(shù)對應(yīng)的十進制數(shù)為i，則該極小項記作mi，1.5對偶與范式由三個命題變元P,Q,R共可產(chǎn)生8個極小項，分別為：?P∧?Q∧?R對應(yīng)000，記為m0?P∧?Q∧R對應(yīng)001，記為m1?P∧Q∧?R對應(yīng)010，記為m2?P∧Q∧R對應(yīng)011，記為m3P∧?Q∧?R對應(yīng)100，記為m4P∧?Q∧R對應(yīng)101，記為m5P∧Q∧?R對應(yīng)110，記為m6P∧Q∧R對應(yīng)111，記為m71.5對偶與范式定義1.21

設(shè)命題公式G中含n個命題變元，如果G的析取范式中的簡單合取式都是極小項，則稱該析取范式為G的主析取范式。定理

任何命題公式de主析取范都是存在的，并且是唯一的。1.5對偶與范式求公式的主析取范式的步驟：(1)先求析取范式①利用蘊含等值式和等價等值式消去公式中的聯(lián)結(jié)詞“→”和“

”；

②利用德摩根律和雙重否定律將聯(lián)結(jié)詞“

”消去或移到命題變元前；

③利用分配律將公式化為析取范式；

(2)若析取范式的某簡單合取式B中不含命題變元Pi,也不含

┐Pi，則添加(Pi

┐Pi),然后應(yīng)用分配律展開.即

B

B1B

(Pi

┐Pi)(B

Pi)(B

┐Pi).（3)將重復(fù)出現(xiàn)的命題變元、重復(fù)出現(xiàn)的極小項、矛盾式都消去;如P

P用P代，P

P用0代。(4)將極小項按由小到大的順序排列，并用

∑(I,j,k)形式表示。1.5對偶與范式例1.15：求((P

Q)

R)P的主析取范式。解:原式

┐(┐(P∨Q)∨R)∨P

P∨(Q∧┐R)(析取范式)

(P∧(Q∨┐Q)∧(R∨┐R))∨((P∨┐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)∨(P∧┐Q∧┐R)∨(┐P∧Q∧┐R)(主析取范式)

m7∨m6∨m5∨m4∨m2

m2∨m4∨m5∨m6∨m7

∑(2,4,5,6,7)1.5對偶與范式主析取范式與真值表極小項mi的成真賦值為i對應(yīng)的二進制；依據(jù)命題公式主析取范式的極小項，可得到命題公式的成真賦值。由命題公式的主析取范式中沒有出現(xiàn)的極小項可確定命題公式的成假賦值。由上可畫出真值表反之，可有真值表得到主析取范式真值表的成真賦值決定全部極小項；由極小項得到主析取范式1.5對偶與范式求((P

Q)

R)P的真值表解答：由((P

Q)

R)P∑(2,4,5,6,7)有下表PQR((P

Q)

R)P000000100101011010011011110111111.5對偶與范式例

用真值表法求公式(

P→R)

(P

Q)的主析取范式。PQR

P

RP

Q(

P

R)

(P

Q)000001010011100101110111010111111100001101000011公式所在的列有三個1，它們分別對應(yīng)于編碼001，110，111，因此所求的主析取范式為：m1

m6

m7，即原式

∑(2,6,7)1.5對偶與范式主析取范式的用途(1)求公式的成真賦值和成假賦值例如(p

q)

r

m1

m3

m5

m6

m7，其成真賦值為001,011,101,110,111，其余的賦值000,010,100為成假賦值.(2)判斷兩個公式是否等值

任何命題公式的主析取范式都是唯一的，因而AB當(dāng)且僅當(dāng)A

B有相同的主析取范式。(3)判斷公式的類型

設(shè)A含n個命題變項，則

A為重言式

A的主析取范式含2n個極小項A為矛盾式

A的主析取范式為0A為非重言式的可滿足式

A的主析取范式中至少含一個且不含全部極小項1.5對偶與范式例

用主析取范式判斷下述兩個公式是否等值：⑴

p

(q

r)與

(p

q)

r⑵

p

(q

r)與

(p

q)

r解

p

(q

r)=m0

m1

m2

m3

m4

m5

m7

(p

q)

r

=m0

m1

m2

m3

m4

m5

m7(p

q)

r

=m1

m3

m4

m5

m7顯見，⑴中的兩公式等值，而⑵的不等值.

1.5對偶與范式

例

利用求主析取范式的方法判別公式((P→Q)

P)→Q的類型。

解求公式的主析取范式為：

((P

Q)

P)

Q

((

P

Q)

P)

Q

(

P

Q)

P

Q

(P

Q)

P

Q

(P

Q)

(

P

(

Q

Q))

((P

P)

Q)

(

P

Q)

(

P

Q)

(P

Q)

(P

Q)

m0

m1

m2

m3

由于公式的主析取范式包含了所有的極小項，因此原公式為重言式。1.5對偶與范式定義1.22極大項定義

在含有n個命題變元的簡單析取式中，若每個命題變元與其否定不同時存在，而二者之一必須出現(xiàn)且僅出現(xiàn)一次，且第i（1

i

n）個命題變元或其否定出現(xiàn)在左起的第i位上（若命題變元無角標(biāo)，則按字典順序），這樣的簡單析取式為極大項.⑴n個命題變元共可產(chǎn)生2n個不同的極大項，其中每個極大項都有且僅有一個成假指派。(2)在極大項中，將命題變元看成0，命題變元的否定看成1，則每個極大項惟一地對應(yīng)一個二進制數(shù)，若該二進制數(shù)對應(yīng)的十進制數(shù)為i，則該極大項記作Mi，1.5對偶與范式三個變元P,Q,R可以產(chǎn)生8個極大項，分別為：P∨Q∨R對應(yīng)000，記為M0P∨Q∨?R對應(yīng)001，記為M1P∨?Q∨R對應(yīng)010，記為M2P∨?Q∨?R對應(yīng)011，記為M3?P∨Q∨R對應(yīng)100，記為M4?P∨Q∨?R對應(yīng)101，記為M5?P∨?Q∨R對應(yīng)110，記為M6?P∨?Q∨?R對應(yīng)111，記為M71.5對偶與范式定義1.23

設(shè)命題公式G中含n個命題變元，如果G的合取范式中的簡單析取式都是極大項，則稱該合取范式為G的主合取范式。定理

任何命題公式的主合取范都是存在的，并且是唯一的。推演法求主合取范式的步驟：（1）求合取范式A’（2）若A’的某一個簡單析取式B中不含某變元pi，也不含

pi，則將B展開成

B

B

0

B

(pi

pi)

(B

pi)

(B

pi)

1.5對偶與范式例

求公式

A=(p

q)

r的主合取范式.(p

q)

r

(p

r)

(q

r)（合取范式）

①

p

r

p

(q

q)

r

(p

q

r)

(p

q

r)

M0

M2,

②q

r

(p

p)

q

r

(p

q

r)

(

p

q

r)

M0

M4③

②,③代入①并排序，得

(p

q)

r

M0

M2

M4

(0,2,4)1.5對偶與范式主合取范式的用途：

(1)求公式的成真賦值和成假賦值.極大項對應(yīng)成假賦值。缺項對應(yīng)成真賦值。(2)判斷公式的類型

設(shè)A含n個命題變項，則

A為重言式

A的主合取范式為1.A為矛盾式

A的主合析取范式含2n個極大項A為非重言式的可滿足式

A的主合取范式中至少含一個且不含全部極大項

1.5對偶與范式如何求主合取范式1、真值表法2、推演法3、利用主合取范式與主析取范式之間的關(guān)系。設(shè)mi和Mi是命題變元P1,P2,…,Pn形成的極小項和極大項，則

mi

Mi，

Mi

mi1.5對偶與范式

先求出主析取范式找出主析取范式中沒有的極小項求對應(yīng)的極大項寫主合取范式1.5對偶與范式某公式的主析取范式為：m1

m6

m7，其缺少的極小項有0,m2,m3,m4,m5.則對應(yīng)的大項為M0,M2,M3,M4,M5,故所求的主合取范式為：M0

M2

M3

M4

M5

，即

(0,2,3,4,5)1.5對偶與范式

總結(jié)：矛盾式的主析取范式是空公式，定義它為0，其主合取范式由所有極大項的合取構(gòu)成；重言式的主合取范式是空公式，定義它為1，其主析取范式必由所有極小項的析取構(gòu)成。利用一個公式的主范式可以判別這個公式是否為重言式或矛盾式。1.5對偶與范式例6.5.7：求((P

Q)

R)

P的主合取范式。解:原式

┐(┐(P∨Q)∨R)∨P

(P∨Q)∧(┐R∨P

)(合取范式)((P∨Q)∨(R∧┐R

))∧((┐R∨P

)∨(Q∧┐Q))

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

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

(主合取范式)

M0∧M1∧M3

(0,1,3)1.5對偶與范式例6.5.8：求(P

Q)

R的析取范式與合取范式。解:原式

(P∨R)∧(┐Q∨R)∧(┐R∨┐P∨Q)(合取范式)

((P∨R)∨(Q∧┐Q))∧((P∧┐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)∧(┐P∨Q∨┐R

)

(主合取范式)

M0∧M2∧M5∧M6

(0,2,5,6)1.5對偶與范式

例6.5.9

利用求主范式的方法判別公式((P→Q)

P)→Q是否為重言式或矛盾式。

解求公式的主析取范式為：

((P

Q)

P)

Q

((

P

Q)

P)

Q

(

P

Q)

P

Q

(P

Q)

P

Q

(P

Q)

(

P

(

Q

Q))

((P

P)

Q)

(

P

Q)

(

P

Q)

(P

Q)

(P

Q)

m0

m1

m2

m3

由于公式的主析取范式包含了所有的極小項，因此原公式為重言式。

1.5對偶與范式當(dāng)然，利用求主合取范式也可以得到同樣的結(jié)論，即：

((P

Q)

P)

Q

((

P

Q)

P)

Q

(

P

Q)

P

Q

(P

Q)

P

Q

(P

P

Q)

(

Q

P

Q)

1

1

1

由于公式的主合取范式是一個空公式，因此原公式為重言式。

1.5對偶與范式

例6.5.10

求公式(

P→R)

(P

Q)的主析取范式和主合取范式。

解令

=(

P

R)

(P

Q)

（1）求主合取范式

(P

R)

(

P

Q)

(P

Q)

(P

(Q

Q)

R)

(

P

Q

(R

R))

(P

Q

(R

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)

(

P

Q

R)

M0

M2

M3

M4

M5

此即

的主合取范式1.5對偶與范式

例6.5.17

某單位要在甲，乙，丙三人中選派1～2名出差，選派時需滿足如下條件：（1）若甲去，則丙同去；（2）若乙去，則丙不能去；（3）若丙不去，則甲或乙可以去。問有幾種選派方案？

解

設(shè)P：派甲去出差；Q：派乙去出差；R：派丙去出差。由已知條件可得公式

(P

R)

(Q

R)

(

R

(P

Q))

1.5對偶與范式經(jīng)過演算可得

(P

R)

(Q

R)

(

R

(P

Q))

(

P

Q

R)

(

P

Q

R)

(P

Q

R)

該公式主析取范式包含3個極小項，因此可知有3種選派方案:①丙去，甲和乙不去；②乙去，甲和丙不去；③甲和丙去，乙不去。1.5對偶與范式一、相關(guān)概念前提：已知的命題公式；結(jié)論：從前提出發(fā)應(yīng)用推理規(guī)則推出的命題公式；推理：從前提推出結(jié)論的思維過程。定義1.2.4

若(A1

A2

...

An)

B為重言式，則稱A1,A2,...,An推出B的推理正確，B是A1,A2,...,An的邏輯結(jié)論或有效結(jié)論。稱(A1

A2

...

An)

B為由前提A1,A2,...,An推出結(jié)論B的推理的形式結(jié)構(gòu)用“A

B”表示A

B是重言式，因而若有前提A1,A2,...,An推出結(jié)論B的推理正確，也記作

(A1

A2

...

An)

B?；蚯疤幔篈1,A2,...,An結(jié)論：B注意：“

”不是聯(lián)結(jié)詞，“G

H”也不是公式。1.6推理理論判斷對立是否正確即為判斷條件式是否是重言式，可用真值表法、等值演算法、主析取范式法、構(gòu)造證明法；當(dāng)命題變項比較少時，用前3個方法比較方便,此時采用形式結(jié)構(gòu)“A1ùA2ù…ùAk?B”.而在構(gòu)造證明時，采用如下形式：前提:A1,A2,…,Ak,結(jié)論:B例判斷下面推理是否正確(1)若今天是1號，則明天是5號.今天是1號.所以明天是5號.解：設(shè)p：今天是1號，q：明天是5號.證明的形式結(jié)構(gòu)為:(p?q)ùp?q

（*）證明（真值表法）真值表略真值表的最后一列全為1，因而(*)是重言式，所以推理真確。（用等值演算法）

(p?q)ùp?q??((?púq)ùp)úq?

?pú?qúq

?1得證推理正確。（主析取范式）

(p?q)ùp?q?(p

q)ú

púq

(p

q)ú(

p

(qú

q))ú((pú

q)

q)m0úm1úm2úm3?

(0,1,2,3)可見(*)是重言式，得證推理正確.二、判斷推理正確與否的構(gòu)造證明法注（1）由前提G1,G2,…,Gn

推結(jié)論H的推理是否正確與各前提的排列次序無關(guān)，因而常把前提中的公式寫成集合的形式。注（2）必須把推理的有效性和結(jié)論的真實性區(qū)別開。據(jù)G

H的定義，G為假時G

H為真，G、H都為真時，G

H為真。所以有效的推理不一定產(chǎn)生真實的結(jié)論。如果有效的推理中包含假的前提，則結(jié)論可能是假；當(dāng)如果前提為真，則結(jié)論一定為真。1.6推理理論

例6.6.1

寫出下述推理關(guān)系的推理形式。下午小王或去看電影或去游泳。他沒去看電影。所以，他去游泳了。

解設(shè)P：小王下午去看電影；Q：小王下午去游泳。前提：P

Q，

P

結(jié)論：Q

推理形式為:(P

Q)

P

Q

1.6推理理論推理定律（8個,也稱基本蘊涵公式）

A

T(AúB)附加律

(AùB)T

A

化簡律

(A?B)ùA

T

B

假言推理

(A?B)ù?B

T

?A

拒取式

(AúB)ù?B

T

A

析取三段論

(A?B)ù(B?C)T(A?C)假言三段論

(A?B)ù(B?C)T(A?C)等價三段論

(A?B)ù(C?D)ù(AúC)T(BúD)構(gòu)造性二難6.6公式的蘊涵與形式演繹

構(gòu)造性證明是一個描述推理過程的命題公式序列，其中的每個命題公式或者是已知的前提，或者是由前面的命題公式應(yīng)用推理規(guī)則得到的結(jié)論。推理規(guī)則

①前提引入規(guī)則－有的書上稱為規(guī)則P

在推理過程中，可以隨時引入已知的前提。

②結(jié)論引入規(guī)則－有的書上稱為規(guī)則D

在推理過程中，前面已推出的有效結(jié)論（本演繹的中間結(jié)論）都可作為后續(xù)推理的前提引用。1.6推理理論

③置換規(guī)則

在推理過程中，命題公式中的子公式都可以用與之等價的命題公式置換，得到證明的公式序列的另一公式。

④假言推理規(guī)則A

B，A|=B⑤附加規(guī)則A|=A

B⑥化簡規(guī)則A

B|=B⑦拒取式規(guī)則A

B,

B|=A⑧假言三段論規(guī)則A

B,B

C|=A

C⑨析取三段論規(guī)則A

B，

B|=A⑩構(gòu)造性二難規(guī)則A

B,C

D,A

C