請交作業(yè)一P32:3(3)(7),5(1)(3)(5)(7)P32:6(1)(4)P33:7(1)(8),8(1)(2),9(1),11復習思考題2重要等值式填空：

AB

_______

AB

_____________________(AB)_______

(AB)_______共有________個三元真值函數(shù)。

A為重言式當且僅當A_________。(pq)

pq

()

p(qr)q(pr)()p(qr)(pq)r

()第1章命題邏輯

1.1命題符號化及聯(lián)結詞1.2命題公式及分類1.3等值演算1.4范式1.5聯(lián)結詞全功能集1.7推理理論1.4范式范式提出的背景與PQ

等值的公式有PQPQ

PQ(PQ)(PQ)(PQ)與

PQ

等值的公式有PQ

(PQ)(QP)PQ

(PQ)(PQ)PQ

(PQ)(PQ)可見同一公式可以有多種表示形式，能否有統(tǒng)一的規(guī)范等值式，使真值表相等的公式形式相同？——范式范式簡單析取式

僅由有限個命題變項或其否定構成的析取式。如:p，q，p，q，pq，p

q，pq

它是重言式當且僅當它同時含一個命題變項及其否定；如：p

p

q

是重言式。簡單合取式僅由有限個命題變項或其否定構成的合取式。如:p，q，p，q，p

q，p

q

它是矛盾式當且僅當它同時含一個命題變項及其否定。如：p

p

q

是矛盾式。

范式析取范式由有限個簡單合取式組成的析取式

A1

A2

….

An（n1，Ai

都是簡單合取式）

如：(p

qr)

(pq)q一個析取范式是矛盾式，當且僅當其每個簡單合取式都是矛盾式合取范式由有限個簡單析取式組成的合取式

A1

A2

….

An（n1,Ai都是簡單析取式）如：(p

qr)

(pq)q一個合取范式是重言式，當且僅當其每個簡單析取式都是重言式范式——析取范式與合取范式的總稱

.范式存在定理——任何命題公式都存在與之等值的析取范式與合取范式命題公式的范式

求公式A的范式的步驟：

(1)消去A中的,（若存在）

(2)否定聯(lián)結詞的內移或消去（德摩根定律）

(3)使用分配律

對分配（析取范式）

對分配（合取范式）注意：公式的范式必存在，但不惟一，這是它的局限性。

求公式的范式舉例1

例:

求下列公式的析取范式與合取范式(1)A=(pq)r解：A(pq)r

（消去）

pqr

（結合律）這是A的析取范式——由3個簡單合取式組成的析取式。這也是A的合取范式——由一個簡單析取式組成的合取式。求公式的范式舉例2(2)B=((pq)r)p解:

B

(

(pq)

r)p

（消去第一個）

((pq)r

)p

（消去第二個）

((pq)r

)p

（德摩根律）

((pq)p)

(r

p)

（分配律）

(pq)

(pr)

p(q

r)（合取范式）（析取范式）求公式的范式舉例3(3)C=(p(pq))

q解:

C

(p(pq))q

((pp)(pq))q

(pq)q(析取范式)

q(析取范式和合取范式)(pq)

q

(合取范式)注意:公式的析取范式與合取范式不惟一.吸收律——

A(AB)A

A(AB)A

極小項定義

n個命題變項的簡單合取式，其中每個命題變項與其否定不同時出現(xiàn)，而二者之一必出現(xiàn)且僅出現(xiàn)一次，這樣的簡單合取式稱為極小項。如：兩個命題變元p和q，其極小項為：

p

q，p

q，p

q，p

q說明n個命題變項產生2n個極小項，它們互不等值。用mi表示第i個極小項，每個小項的n個變元排序相同。（按下標或字典順序），分別記為其中i是該極小項成真賦值的十進制表示.

m11

m10

m01

m00

m3

m2

m1

m0

極小項由p,q,r三個命題變項形成的極小項極小項成真賦值名稱?p?q?r000m0?p?qr001m1?pq?r010m2?pqr011m3p?q?r100m4p?qr101m5pq?r110m6pqr111m7主析取范式主析取范式若命題公式A的析取范式中的簡單合取式全是極小項，則稱該析取范式為A的主析取范式如：若命題變項為p,q,r時，主析取范式：

(pqr)(pqr)定理任何命題公式都存在著與之等值的主析取范式,并且是惟一的.

求主析取范式的方法等值演算法和真值表法

m1m3

用等值演算法求主析取范式的步驟1.求A的析取范式A′；2.若A′的某簡單合取式B中不含某命題變項或其否定，則將B展成如下形式：

B

B

1

B

(pi

pi)

(B

pi)(B

pi)3.將重復出現(xiàn)的命題變項、矛盾式及重復出現(xiàn)的極小項都“消去”。4.將極小項按由小到大的順序排列，并用Σ表示之，如m1

m2

m6

用(1,2,6)表示。求公式((pq)r)p的主析取范式解法1：

((pq)r)p

p(qr)

（析取范式）①

p

p

(qq)(rr)(pqr)(pqr)(pqr)(pqr)

m4m5m6m7

②(qr)

(qr)(pp)(pqr)(pqr)m2m6③②,③代入①并排序，得主析取范式：

((pq)r)p

m2m4m5

m6m7

(2,4,5,6,7)解法2：

((pq)r)p

p(qr)

（析取范式）

m1xx

mx10

(m100

m101

m110

m111)(m010

m110)

(2,4,5,6,7)求公式((pq)r)p的主析取范式求公式((pq)r)p的主析取范式

pqr

pq

(pq)r((pq)r)p000001010011100101110111

00111111

11010101

00101111

((pq)r)p

(2,4,5,6,7)主析取范式的用途1(1)求公式的成真賦值和成假賦值

如前面例子中得到

((pq)r)p

(2,4,5,6,7)其成真賦值為：

010,100,101,110,111則其余的賦值為成假賦值000,001,011主析取范式的用途2(2)判斷公式的類型

設A含n個命題變項，則

A為重言式A的主析取范式含2n個極小項如對含2個命題變項的重言式A

(0,1,2,3)A為矛盾式

A的主析取范式不含任何極小項

如A0A為可滿足式A的主析取范式中

至少含一個極小項如A

(0,1,3)[P20例1.17]

（1）(pq)q(p

q)

qp

q

q0（矛盾式）用主析取范式判斷公式的類型(2)

((pq)p)q((p

q)

p)q(p

q)

p

qm10m0x

mx1

m10m00m01

m01m11

m0m1m2m3

(0,1,2,3)（重言式）用主析取范式判斷公式的類型[P20例1.17]

（3）(pq)q

(pq)

q

qmx1m01

m11

(2,3)(可滿足式）用主析取范式判斷公式的類型吸收律：A(AB)A主析取范式的用途3(3)判斷兩個公式是否等值如pq

pq

m0x

mx1

m00m01m01m11

m0m1m3(0,1,3)

p(p

q)m0x

m11

m00m01m11

m0m1m3(0,1,3)所以pqp(p

q)主析取范式的應用舉例例：甲、乙、丙、丁四人參加考試，有人問他們，誰的成績最好，甲說：“不是我”乙說：“是丁”丙說：“是乙”丁說：”不是我”四人的回答只有一人符合實際，問是誰的成績最好？若只有一人成績最好，他是誰？解此類問題的步驟為：①

將簡單命題符號化②

寫出各復合命題③

寫出由②中復合命題組成的析取范式

④

求③中所得公式的主析取范式主析取范式的應用舉例解

①

設A：甲的成績最好

B：乙的成績最好，

C：丙的成績最好

D：丁的成績最好，②(1)(A

DBD)(2)(AD

BD)(3)(ADBD)(4)(ADBD)例：甲、乙、丙、丁四人參加考試，有人問他們，誰的成績最好，甲說：“不是我”乙說：“是丁”丙說：“是