离散数学：1-3 命题逻辑

请交作业一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)_______共有________个三元真值函数。

A为重言式当且仅当A_________。(pq)

pq

()

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

()第1章命题逻辑

1.1命题符号化及联结词1.2命题公式及分类1.3等值演算1.4范式1.5联结词全功能集1.7推理理论1.4范式范式提出的背景与PQ

等值的公式有PQPQ

PQ(PQ)(PQ)(PQ)与

PQ

等值的公式有PQ

(PQ)(QP)PQ

(PQ)(PQ)PQ

(PQ)(PQ)可见同一公式可以有多种表示形式，能否有统一的规范等值式，使真值表相等的公式形式相同？——范式范式简单析取式

仅由有限个命题变项或其否定构成的析取式。如: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)否定联结词的内移或消去（德摩根定律）

(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个命题变项的简单合取式，其中每个命题变项与其否定不同时出现，而二者之一必出现且仅出现一次，这样的简单合取式称为极小项。如：两个命题变元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.将重复出现的命题变项、矛盾式及重复出现的极小项都“消去”。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)例：甲、乙、丙、丁四人参加考试，有人问他们，谁的成绩最好，甲说：“不是我”乙说：“是丁”丙说：“是