离散数学（第二版） 课件 邹丽娜 2.4 公式的范式

离散数学第2章命题逻辑((p→q)

p)→q与q

¬q

¬p是否等值，并判断两个公式的类型

公式的范式

((p→q)

p)→q

((¬p

q)

p

)→q

(¬p

p)

(q

p

)→q

(p

q)→q

¬(p

q)

q

(¬

p¬q)

qq

¬q¬p1重言式

q¬q

¬p

1

¬p

1

重言式判定问题：有限次步骤来判定命题公式是否为：

①永真式、永假式，可满足的;

②二个命题公式等价;目的：讨论范式和主范式就是为了进行判定。范式：把命题公式化归为一种标准的形式。

公式的范式

公式的范式例：设p、q为二个命题变元简单析取式：p，q，p∨p，q∨q，¬p∨q，

¬q∨¬p，p∨q，p∨¬q简单合取式：p，q，p∧p，q∧q，¬p∧q，

¬q∧¬p，p∧q，p∧¬q22

公式的范式(析取范式)定义2.16由有限个简单合取式构成的析取式称为析取范式。析取范式同时满足下列三个条件：(1)它是个析取式(2)式中的每个析取项是个合取式(3)每个合取式中只包含命题变元或其否定。例：p∨(q∧﹁r)∨r

(p∨q)∨(q→r)∨p是不是3范式存在定理定理2.2对于任何一个命题公式，都存在着与之等值的析取范式与合取范式。

()

()

(

)(

)

(

)

(

)

范式存在定理2.2：

任意命题公式都存在着与之等值的合取范式或析取范式。

求析取范式的步骤：

1.利用等值公式：化去“→”、“

”联结词，把命题公式变为与其等值的用{¬，∧，∨}表达的公式。

A→B

¬A∨B，A

B

(A→B)∧(B→A)

(¬A∨B)∧(¬B∨A)

(A∧B)∨(¬B∧¬A)2.将“¬”深入到原子命题变元前，使变元前最多只有一个“¬”。

¬(¬A∨¬B)

¬

¬A∧¬

¬B

A∧B3.利用“∧”对“∨”的分配，将公式化成为析取范式析取范式()()(

)求析取范式例2.25

求下列公式的析取范式：(1)化去→词(3)“∧”对“∨”分配，化为析取范式(2)将否定符深入到命题变元前：析取范式课后习题16(1)(4)析取范式课后习题16(2)析取范式课后习题16(3)析取范式课后习题16(5)析取范式课后习题16(6)公式的极小项((p→q)

q

¬p)→(q

¬p)

两个变元的析取范式由哪些合取项组成？(列出所有可能)

¬p

¬qp

q¬p

qp

¬q定义2.15【公式的极小项】1.设是n个互不相同的命题变元。4.由产生的极小项称为公式极小项。3.形如简单合取式是极小项。2.令原形或否定注意：对于由n个命题变元可以产生个极小项。公式的极小项例：求2个命题变元p，q生产的所以极小项。极小项

成真赋值

记法

p

q

pqp

qpq00011011m0

m1

m2

m3

极小项：每个合取式称为一个极小项。2个变元p

q可以产生22个极小项。

¬p

¬qp

q¬p

qp

¬q主析取范式定义2.16

设A是含n个命题变元的公式，B是A的一个析取范式，若B中每个简单合取式都是极小项，则称B是A的主析取范式。

¬p

¬qp

q¬p

qp

¬q主析取范式：

(1)它是个析取范式。

(2)在每个合取式中所有命题变元均出现（p

q

）。

(3)

命题变元或以其否定的形式出现，且仅出现一次。主析取范式命题公式化归主析取范式的过程

(1)化归为析取范式

(2)除去所有为永假的合取式。即﹁A∧A形式的项

(3)将相同命题变元化归为一个命题变元利用公式A∧A=A

(4)在合取式中补充变元令所有命题变元均出现用公式A=

A∧1=A∧(B∨﹁B)，应用分配律将其展开。

主析取范式例:试求(p∧(p→q))∨q的主析取范式(1)化归为析取范式：m11

m01(2)去除永假项：(3)补充不足的命题变元(p∧(p→q))∨q

(p∧(﹁p∨q))∨q

(p∧﹁p)∨(p∧q)∨q

(p∧q)∨q

(p∧q)∨(q∧1)

(p∧q)∨((p∨﹁p)∧q

)

(p∧q)∨((p

∧

q)∨(﹁p∧q)

)

(p

∧

q)∨(﹁p∧q)

(4)写出极小项主析取范式

(¬

p

q)

(¬

p

¬

q)m01

m00m0m1主析取范式(

p

q)

→¬

q¬(

p

q)

¬

q(¬¬

p

¬

q)

¬

q(p

¬

q)

¬

qp

¬

q是析取范式不是主析取范式p

¬

q

(p

(q

¬q

))

(

(p¬p

)

¬q))

(p

q

)

(p

¬q

)

(p

¬q

)

(

¬p

¬q)

(p

q

)

(p

¬q

)

(

¬p

¬q)m11

m10

m00m3

m2

m0三个变元的极小项列出所有可能的析取范式(合取式)组成？

¬p

¬q

¬r¬p

¬q

r¬p

q

¬r¬p

q

r

p

¬q

¬rp

¬q

rp

q

¬rp

q

r

极小项：每个合取式称为一个极小项。3个变元p

qr可以产生23个极小项。主析取范式：

(1)它是个析取范式。

(2)在每个合取式中所有命题变元均出现（p

qr

）。

(3)

命题变元或以其否定的形式出现，且仅出现一次。

极小项的真值极小项

成真赋值

记法

p

q

r

p

q

r

p

q

r

p

q

r

p

q

r

p

q

r

p

q

r

p

q

r

000001010011100101110111m0

m1

m2

m3

m4

m5

m6

m7

主析取范式是析取范式不是主析取范式例2.26例2.26例题2-27求公式(p→q)

r主析取范式真值表法pqrp→q

(p→q)

r0001000111010100111110001101001101011111m3m1m7m4例题2-27求公式(p→q)

r主析取范式((¬p

q)

r)((¬p

q)

¬r)

((¬p

r)(q

r))((p

q)

r)

(¬p

r)(q

r)(p

q

r)0

?1?11m3m1m7主析取范式为：

m1

m3

m4

m710

0m4例题2-28求公式¬(p→q)

r主析取真值表法pqrp→q

¬(p→q)

¬(p→q)

r000100001101010100011101100011101011110100111101m3m1m7m4m5例题2-28求公式¬(p→q)

r¬(¬p

q)

r

(p

q)

r

1

0?m3m1m7主析取范式为：

m1

m3

m4

m5

m7m4？？1m5主析取范式总结1.由极小项组成

极小项极小项极小项极小项包括所有变元的简单合取式

p

q

r

p

q

r

p

q

r

p

q

r

2.表示公式的成真赋值p

q

r

p

q

r

p

q

r

p

q

r

主析取范式总结3.主析取范式求法先演算为一般的析取范式再将每一项凑成极小项写出编号：P取1，

P取0例题2-28求公式¬(p→q)

r主析取范式¬(¬p

q)

r

(p

q)

r

1

0?？？1主析取范式为：

m1

m3

m4

m5

m7主析取范式的应用(pq)(p

q)(

pq)(

pq)

无(pq)(p

q)

练习42页182.6公式的范式(合取范式)定义2.14由有限个简单析取式构成的合取式称为合取范式。合取范式同时满足下列三个条件：(1)它是个合取式(2)式中的每个合取项是个析取式(3)每个析取式中只包含命题变元或其否定。范式存在定理定理2.2对于任何一个命题公式，都存在着与之等值的析取范式与合取范式。

()()(

)(

)

(

)

(

)

范式存在定理2.2：

任意命题公式都存在着与之等值的合取范式或析取范式。

求合取范式的步骤：

1.利用等值公式：化去“→”、“

”联结词，把命题公式变为与其等值的用{¬，∧，∨}表达的公式。A→B

¬A∨B，A↔B

(A→B)∧(B→A)

(¬A∨B)∧(¬B∨A)2.将“¬”深入到原子命题变元前，使变元前最多只有一个“¬”。

¬(¬A∨¬B)

¬

¬A∧¬

¬B

A∧B3.利用“∨”对“∧”的分配，将公式化成为合取范式合取范式(

)

(

)

(

)例2.25

求下列公式的合取范式：求合取范式(1)化去→词(3)“∨”对“∧”分配，化为合取范式：(2)将否定符深入到命题变元前：公式的极大项列出所有可能的合取范式(析取项)组成？定义2.17【公式的极大项】1.设是n个互不相同的命题变元。4.由产生的极大项称为公式极大项。2.令原形或否定。注意：对于由n个命题变元可以产生个极大项。¬p

¬qp

q¬p

qp

¬q

3.形如简单析取式是极大项。练习例

求3个命题变元p,q,r产生的所有极大项。极大项

成0赋值

记法

p

q

r

p

q

rp

q

rp

q

r

p

q

r

p

q

r

p

q

r

p

q

r000001010011100101110111M0

M1

M2

M3

M4

M5

M6

M7

主合取范式¬p

¬qp

q¬p

qp

¬q

主合取范式：

(1)它是个合取范式。

(2)在每个析取式中所有命题变元均出现（p

q）。

(3)

命题变元或以其否定的形式出现，且仅出现一次。定义2.18

设A是含n个命题变元的公式，B是A的一个合取范式，若B中每个简单析取式都是极大项，则称B是A的主合取范式。主合取范式命题公式化归主合取范式的过程

(1)化归为合取范式

(2)除去所有为永真的析取项。即﹁A∨A形式的项

(3)将相同命题变元化归为一个命题变元利用公式A∨A=A

(4)在析取项中补充变元令所有命题变元均出现用公式A

=A∨0=A∨(B∧﹁B)，应用分配律将其展开。

主合取范式例试求公式(﹁p→r∨p)∧(q

p)的主合取范式(1)化归为合取范式：(﹁p→r∨p)∧(q

p)=(p∨r∨p)∧(﹁q∨p)∧(﹁p∨q)(2)去除永真项：无(3)在析取式中，将多个相同命题变元化归为一个命题变元(p∨r∨p)∧(﹁q∨p)∧(﹁p∨q)=(p∨r)∧(p∨﹁

q)∧(﹁p∨q)(4)补充不足的命题变元(p∨r)∧(p∨﹁

q)∧(﹁p∨q)

(p∨q∨r)∧(p∨﹁

q∨r)∧(﹁p∨q∨r)∧(p∨﹁q∨r)∧(p∨﹁

q∨﹁r)∧(﹁p∨q∨﹁r)公式的主合取范式与真值表之间的关系主合取范式极大项对应着真值表中使结果为0的赋值组合。主析取范式极小项对应着真值表中使结果为1的赋值组合。主析取范式和主合取范式的关系主析取范式为：主合取范式为：有主合取范式可以判断公式的成假赋值,而主析取范式可以判断公式的成真赋值，所以两种范式正好相反.课后练习主合取范式00?0?1001011

(p

q)

(p

¬r)0000019例题2-30求公式(p→q)

r主合取范式真值表法pqrp→q

(p→q)

r0001000111010100111110001101001101011111M2M0M6M5例题2-31求公式¬(p→q)

r主合取真值表法pqrp→q

¬(p→q)

¬(p→q)

r000100001101010100011101100011101011110100111101M2M0M6主合取范式总结1.由极大项组成

极大项极大项极大项极大项包括所有变元的简单析取式p

q

rp

q

rp

q

rp

q

r

2.表示公式的成假赋值

p

q

r

p

q

r

p

q

r

p

q

r主合取范式总结3.主合取范式求法先演算为一般的合取范式再将每一项凑成极大项写出编号：P取0，

P取1例题2-28求公式¬(p→q)

r主合取范式¬(¬p

q)

r

(p

q)

r(p

r)

(q

r)

0？0？10主析取范式为：

M0

M2

M6主合取范式的应用例29求（（p

q）

r）

p的成真赋值和成假赋值

（¬（p

q）

r）

p¬（¬（p

q）

r）

p

（p

q）

¬r）

p

（p

¬r

）

（

q

¬r

）

pm110

m101m010

m100m111m2m4m5m6m7

110.101.010.100.