析取合取

2.2析取范式与合取范式

一、析取范式与合取范式

定义2.2 命题变项及其否定统称作文字。

仅由有限个文字构成的析取式称为简单析取式。

仅由有限个文字构成的合取式称为简单合取式。

例如，文字：p,┐q,r,q.

简单析取式: p,q,p∨q,p∨┐p∨r,┐p∨q∨┐r.

简单合取式: p,┐r,┐p∧r,┐p∧q∧r,p∧q∧┐q.

定理2.1（1）一个简单析取式是重言式当且仅当它同时含某个命题变项及它的否定。

（2）一个简单合取式是矛盾式当且仅当它同时含某个命题变项及它的否定。

定义2.3（1）由有限个简单合取式构成的析取式称为析取范式。

（2）由有限个简单析取式构成的合取式称为合取范式。

（3）析取范式与合取范式统称为范式。

例如，析取范式：（p┐∧q）∨r, ┐p∧q∧r, p∨┐q∨r.

合取范式:(p∨q∨r)∧(┐q∨r), ┐p∧q∧r, p∨┐q∨r.

定理2.2（1）一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式。

（2）一个合取范式是重言式当且仅当它的每个简单析取式都是重言式。范式的特点：

（1）范式中不出现联结词→、?，求范式时可消去：

A→B?┐A∨B

A?B?(┐A∨B)∧(A∨┐B)

（2）范式中不出现如下形式的公式：

┐┐A, ┐(A∧B), ┐(A∨B)

因为：┐┐A?A

┐(A∧B)?┐A∨┐B

┐(A∨B)?┐A∧┐B

（3）在析取范式中不出现如下形式的公式：

A∧(B∨C)

在合取范式中不出现如下形式的公式：

A∨(B∧C)

因为：A∧(B∨C)?(A∧B)∨(A∧C)

A∨(B∧C)?(A∨B)∧(A∨C)

定理2.3 (范式存在定理)任一命题公式都存在着与之等值的析取范式与合取范式。

求范式的步骤：

1．消去联结词→、?；

2．消去否定号┐；

3．利用分配律。

命题公式的析取范式与合取范式都不是唯一的。

例2.7 求公式(p→q)?r的析取范式与合取范式。

解: (1)合取范式：

(p→q)?r ?(┐p∨q)? r

?((┐p∨q)→ r)∧(r→(┐p∨q))

?(┐(┐p∨q)∨r)∧(┐r∨(┐p∨q))

? ((p∧┐q)∨r)∧(┐p∨q∨┐r)

? (p∨r)∧(┐q∨r)∧(┐p∨q∨┐r)

(2) 析取范式

(p→q)?r ? ((p∧┐q)∨r)∧(┐p∨q∨┐r)

? (p∧┐q∧┐p)∨(p∧┐q∧q)∨(p∧┐q∧┐r)∨(r∧┐p)∨(r∧q)∨(r∧┐r)

? (p∧┐q∧┐r)∨(┐p∧r)∨(q∧r)

下面介绍命题公式的唯一规范化形式的范式：主析取范式与主合取范式。

二、主析取范式与主合取范式

1．极小（大）项

定义2.4极小项（极大项）：含n个命题变项的简单合取式（简单析取式），每个命题变项和它的否定式不同时出现，且二者之一必出现且仅出现一次。

由p, q两个命题变项形成的极小项与极大项由下表给出

由p, q, r三个命题变项形成的极小项与极大项由下表给出.

由上表可见:

(1)n个命题变项可组成2n个不同的极小项和2n个不同的极大项。

(2)每个极小项都有且仅有一个成真赋值，其成真赋值对应的二进制数转化为

十进制数为i，记该极小项为m i.

(3)每个极大项都有且仅有一个成假赋值，其成假赋值对应的二进制数转化为

十进制数为i，记该极大项为M i。

定理2.4 设m i和M i是p1，…，p n组成的极小项和极大项，则

┐m i?M i, ┐M i?m i

。

2．主析(合)取范式

定义2.5 主析取范式：全部由极小项组成的析取范式。

主合取范式：全部由极大项组成的合取范式。

如：（p∧q）∨(p∧┐q)?m2∨m3

(p∨q)∧(┐p∨q)∧(p∨┐q)?M0∧M2∧M1

定理2.5 任何命题公式都存在与之等值的主析取范式和主合取范式，且是唯一的。

用等值演算法求公式的主范式的步骤：

（1）先求析取范式（合取范式）

（2）将不是极小项（极大项）的简单合取式（简单析取式）化成与之等值的若干个极小项之析取（极大项之合取），利用的等值式为同一律（零律）、排中律（矛盾律）、分配律、幂等律等.

（3）极小项（极大项）用名称mi（Mi）表示，并按角标从小到大顺序排序.

例2.8 求公式(p→q)?r的主析(合)取范式。

解: (1)主析取范式

由例 2.7 知，(p→q)?r ?(p∧┐q∧┐r)∨(┐p∧r)∨(q∧r)

∵(┐p∧r)?┐p∧(┐q∨q)∧r

?(┐p∧┐q∧r)∨(┐p∧q∧r)

?m1∨m3

(q∧r) ?(┐p∨p)∧q∧r

?(┐p∧q∧r)∨(p∧q∧r)

?m3∨m7

（p∧┐q∧┐r) ?m4

∴(p→q)?r ?m1∨m3∨m4∨m7

例求公式(p→?q)→r的主析取范式与主合取范式.

（1）求主析取范式

(p→?q)→r? (p∧q)∨r （析取范式）①

(p∧q)? (p∧q)∧(?r∨r)

? (p∧q∧?r)∨(p∧q∧r)

? m6∨m7②r? (?p∨p)∧(?q∨q)∧r

? (?p∧?q∧r)∨(?p∧q∧r)∨(p∧?q∧r)∨(p∧q∧r)

? m1∨m3∨m5∨m7③

②, ③代入①并排序，得

(p→?q)→r ? m1∨m3∨m5∨ m6∨m7（主析取范式）（2）求A的主合取范式

(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（主合取范式）例 2.9 求p→q 的主析取范式和主合取范式

解: (1) 主合取范式

p→q ?┐p∨q

?M2

(2) 主析取范式

p→q ?(┐p∨q )

?(┐p∧(┐q∨q ))∨((┐p∨p)∧q)

?(┐p∧┐q)∨(┐p∧q)∨(┐p∧q)∨(p∧q)

(┐p∧┐q)∨(┐p∧q)∨(p∧q)

m0∨m1∨m3

给出下面两个表：

由表中看出，p→q有三个成真赋值，其主析取范式有三个极小项，极小项的下标分别为三个成真赋值的十进制数；p→q有一个成假赋值，其主合取范式有一个极大项，极大项的下标为成假赋值的十进制数。由此，我们不难得到以下结论：含n个命题变项的公式，其主析取范式所含极小项的个数与其主合取范式所含极大项的个数之和为2n，并且极小项的下标分别为成真赋值的十进制数，极大项的下标分别为成假赋值的十进制数。可见，已求出公式的一个主范式后，可立即得到公式的另一个主范式。

例2.13 由公式的主析取范式，求其主合取范式：

(1)A?m1∨m2(A中含命题变项p,q)

(2)B?m1∨m2∨m3(B中含命题变项p,q,r)

解：(1)由题知，A的成真赋值为01,10,则其成假赋值为00，11，故

A?M0∧M3

(2)同理知，B的成真赋值为001，010，011，则其成假赋值为000，100，101，110，111，因此

B?M0∧M4∧M5∧M6∧M7

例, 求公式(p∧q)∨r的主析取范式及主合取范式。

主析取范式:

(p∧q)∨r

<==>(p∧q∧(r∨┐r))∨((p∨┐p)∧(q∨┐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)<==>∑(m1,m3,m5,m6,m7)

主合取范式

(p∧q)∨r

<==>(p∨r)∧(q∨r) <==>(p∨(q∧┐q)∨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)<==>∏(M0,M2,M4)

也就是:∑(m1,m3,m5,m6,m7)<==>∏(M0,M2,M4)

说明:∑:表示连续的合取;∏:表示连续的析取

例, 求公式(p∧q)∨r的主析取范式及主合取范式。

主析取范式:

(p∧q)∨r

<==>(p∧q∧(r∨┐r))∨((p∨┐p)∧(q∨┐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)<==>∑(m1,m3,m5,m6,m7)

主合取范式

(p∧q)∨r

<==>(p∨r)∧(q∨r)

<==>(p∨(q∧┐q)∨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)<==>∏(M0,M2,M4)

也就是:∑(m1,m3,m5,m6,m7)<==>∏(M0,M2,M4)

说明:∑:表示连续的合取;∏:表示连续的析取

1.4.1范式

1、简单析取式，简单合取式。

简单析取式：由有限个命题变项或其否定构成的析取式。

例如：，，，等都是简单析取式。

简单合取式：由有限个命题变项或其否定构成的合取式。

例如：，，，等都是简单合取式。

2、析取范式，合取范式。

定义：由有限个简单合取式构成的析取式称作析取范式。

由有限个简单析取式构成的合取式称作合取范式。

例如：为析取范式；

为合取范式。

显然，为合取范式；

为析取范式。

范式存在定理：任一命题公式都存在与之等值的析取范式和合取范式。

求范式步骤：

(1) 消去联结词(即利用

）。

(2) 否定消去或内移。

(3) 利用分配律。

例1、求公式的析取范式和合取范式。

解：原式

消去

内移

消去

分配律(对分配)

上式即原式的析取范式，再利用第三步的结论，即：

原式

分配律(对分配)

即原式的合取范式。

1.4.2主范

例2、求公式的主析取范式

解：由例1，的析取范式为

(吸收律)

例3、求公式的主合取范式。

解：由例1

合取范式

离散数学课后习题答案 (邱学绍)

第一章 命题逻辑 习题1.11．解 ⑴不是陈述句，所以不是命题。 ⑵x 取值不确定，所以不是命题。 ⑶问句，不是陈述句，所以不是命题。 ⑷惊叹句，不是陈述句，所以不是命题。 ⑸是命题，真值由具体情况确定。 ⑹是命题，真值由具体情况确定。 ⑺是真命题。 ⑻是悖论，所以不是命题。 ⑼是假命题。 2．解 ⑴是复合命题。设p ：他们明天去百货公司；q ：他们后天去百货公司。命题符号化为q p ∨。 ⑵是疑问句，所以不是命题。 ⑶是悖论，所以不是命题。 ⑷是原子命题。 ⑸是复合命题。设p ：王海在学习；q ：李春在学习。命题符号化为p ∧q 。 ⑹是复合命题。设p ：你努力学习；q ：你一定能取得优异成绩。p →q 。 ⑺不是命题。 ⑻不是命题 ⑼。是复合命题。设p ：王海是女孩子。命题符号化为：?p 。 3．解 ⑴如果李春迟到了，那么他错过考试。 ⑵要么李春迟到了，要么李春错过了考试，要么李春通过了考试。 ⑶李春错过考试当且仅当他迟到了。 ⑷如果李春迟到了并且错过了考试，那么他没有通过考试。 4．解 ⑴?p →(q ∨r )。⑵p →q 。⑶q →p 。⑷q → p 。 习题1.2 1．解 ⑴是1层公式。 ⑵不是公式。 ⑶一层： p ∨q ，?p 二层：?p ?q 所以，)()(q p q p ??→∨是3层公式。 ⑷不是公式。 ⑸(p →q )∧?(?q ?( q →?r ))是5层公式，这是因为 一层：p →q ，?q ，?r 二层：q →?r 三层：?q ?( q →?r ) 四层：?(?q ?( q →?r )) 2．解 ⑴A =(p ∨q )∧q 是2层公式。真值表如表2-1所示： 表2-1 ⑵p q p q A →→∧= )(是3层公式。真值表如表2-2所示：

利用真值表法求取主析取范式以及主合取范式的实现

#include #include #include #include using namespace std; char str[100]; //输入的命题公式 int tv[20] = {0}; //真值指派的数组 int length; //命题公式长度 char expression[100]; //将命题公式中的命题变元变为真值后的数组 int icp(const char c) //联结词的栈外优先级 { int result = -1; switch(c) { case '#': result = 0; break; case '(': result = 10; break; case '!': result = 9; break; case '&': result = 6; break; case '|': result = 4; break; case '>': result = 2; break; case ')': result = 1; } return result; } int isp(const char c) //联结词的栈内优先级 { int result = -1; switch(c) { case '#': result = 0; break; case '(': result = 1; break; case '!': result = 8; break; case '&': result = 7; break; case '|': result = 5; break; case '>': result = 3; break; case ')': result = 10; } return result; } void Plus(int a[],int q) //二进制加法指派真值

析取合取

2.2析取范式与合取范式 一、析取范式与合取范式 定义2.2 命题变项及其否定统称作文字。 仅由有限个文字构成的析取式称为简单析取式。 仅由有限个文字构成的合取式称为简单合取式。 例如，文字：p,┐q,r,q. 简单析取式: p,q,p∨q,p∨┐p∨r,┐p∨q∨┐r. 简单合取式: p,┐r,┐p∧r,┐p∧q∧r,p∧q∧┐q. 定理2.1（1）一个简单析取式是重言式当且仅当它同时含某个命题变项及它的否定。 （2）一个简单合取式是矛盾式当且仅当它同时含某个命题变项及它的否定。 定义2.3（1）由有限个简单合取式构成的析取式称为析取范式。 （2）由有限个简单析取式构成的合取式称为合取范式。 （3）析取范式与合取范式统称为范式。 例如，析取范式：（p┐∧q）∨r, ┐p∧q∧r, p∨┐q∨r. 合取范式:(p∨q∨r)∧(┐q∨r), ┐p∧q∧r, p∨┐q∨r. 定理2.2（1）一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式。 （2）一个合取范式是重言式当且仅当它的每个简单析取式都是重言式。范式的特点： （1）范式中不出现联结词→、?，求范式时可消去： A→B?┐A∨B A?B?(┐A∨B)∧(A∨┐B) （2）范式中不出现如下形式的公式： ┐┐A, ┐(A∧B), ┐(A∨B) 因为：┐┐A?A ┐(A∧B)?┐A∨┐B ┐(A∨B)?┐A∧┐B （3）在析取范式中不出现如下形式的公式：

A∧(B∨C) 在合取范式中不出现如下形式的公式： A∨(B∧C) 因为：A∧(B∨C)?(A∧B)∨(A∧C) A∨(B∧C)?(A∨B)∧(A∨C) 定理2.3 (范式存在定理)任一命题公式都存在着与之等值的析取范式与合取范式。 求范式的步骤： 1．消去联结词→、?； 2．消去否定号┐； 3．利用分配律。 命题公式的析取范式与合取范式都不是唯一的。 例2.7 求公式(p→q)?r的析取范式与合取范式。 解: (1)合取范式： (p→q)?r ?(┐p∨q)? r ?((┐p∨q)→ r)∧(r→(┐p∨q)) ?(┐(┐p∨q)∨r)∧(┐r∨(┐p∨q)) ? ((p∧┐q)∨r)∧(┐p∨q∨┐r) ? (p∨r)∧(┐q∨r)∧(┐p∨q∨┐r) (2) 析取范式 (p→q)?r ? ((p∧┐q)∨r)∧(┐p∨q∨┐r) ? (p∧┐q∧┐p)∨(p∧┐q∧q)∨(p∧┐q∧┐r)∨(r∧┐p)∨(r∧q)∨(r∧┐r) ? (p∧┐q∧┐r)∨(┐p∧r)∨(q∧r) 下面介绍命题公式的唯一规范化形式的范式：主析取范式与主合取范式。 二、主析取范式与主合取范式 1．极小（大）项 定义2.4极小项（极大项）：含n个命题变项的简单合取式（简单析取式），每个命题变项和它的否定式不同时出现，且二者之一必出现且仅出现一次。 由p, q两个命题变项形成的极小项与极大项由下表给出

析取范式与合取范式

1 析取范式与合取范式 这是命题公式的两种特殊的简明形式。一个重要的结论是，任何命题公式都可以等价地转化为这两种形式。我们将学习这种转化方法及其应用。 1. 析取范式 定义1.1 命题变元及其否定统称为文字（literal ）。由有限个文字组成的合取式称为简单合取式。由有限个简单合取式组成的析取式称为析取范式（disjunction normal form ），简称DNF 。 例1.2 求下列公式的析取范式。 (1) ()(2) () ()p q p p q p q →∧?∨∧?∧ 方法小结： （1） 将蕴含联结词→与等价联结词?都转化为析取与合取联结词。 （2） 用德摩根律将所有否定词转移到括号内，并用双重否定律消除双重 否定词。 （3） 用分配律将析取联结词移到括号之外。 （4） 最后化简，即消除简单合取式中重复出现的变元（用幂等律、矛盾 律、零律） 练习1.3 定理1.4 任何命题公式都有等值的析取范式。 2. 合取范式 定义2.1由有限个文字组成的析取式称为简单析取式，也称为子句（clause ）。 由有限个简单析取式组成的合取式称为合取范式（conjunction normal form ），简称CNF 。 例2.2 求下列公式的合取范式。 (1) ()(2) () ()p q p p q p q ?→∨∧∨?∨

方法小结： （1）将蕴含联结词→与等价联结词?都转化为析取与合取联结词。 （2）用德摩根律将所有否定词转移到括号内，并用双重否定律消除双重否定词。 （3）用分配律将合取联结词移到括号之外。 （4）最后化简，即消除简单析取式中重复出现的变元（用幂等律、排中律、同一律） 练习2.3 定理2.4 任何命题公式都有等值的合取范式。 3.极小项 为了进一步规范析取范式与合取范式，我们引入极小项与极大项这一对概念。 符号的次序：在符号表中，符号是有先后次序的。在一个命题逻辑语言中，所有的命题变元来自于一个符号表，称为命题变元符号表。我们约定：命题公式中所使用的英文字母在命题变元符号表中的次序与其在英文字母表中的次序相同。也可以用标识符作命题变元，标识符在符号表中的次序为字典序。 定义1.1满足下述两个条件的简单合取式称为极小项：（1）每个变元仅出现一次，（2）变元出现的先后次序与它们在符号表中的先后次序相同。含n 个变元的极小项称为n元极小项。 例如，等等都是极小项。等等都不是极小项。 提问：由n个不同变元组成的n元极小项共有多少个？ 回答：共有2n个。一个极小项有n个变元，每个变元前面可以有否定词也可以没有，所以共有2n个组合。 例如，p, q两个变元可以组成的极小项如下： ?∧??∧∧?∧ p q p q p q p q ,,, 极小项的名称：极小项的成真赋值是唯一的，并对应着一个唯一的二进制数。若该二进制数所对应的十进制是i，则该极小项记为m i。 例如，上述4个极小项分别记为m0, m1, m2, m3。三元极小项的例子见课本第25页表2.4左列。 2

利用真值表法求取主析取范式以及主合取范式的实现

#include "stdio.h" #include "stdlib.h" #include "string.h" #include "math.h" #define N 50 void pd(int b[N],int f); int H1 (char T1[N], char T2[N], int T3[N], int y); int H2 (char T1[N], char T2[N], int T3[N], int y); int main() { int i1,i2,d=1,T3[N],kh=0,jg,j=0,y; int w=0,hequ[N],h=0,x=0,xiqu[N]; char T1[N],T2[N],T10[N],s; hequ[0]=-1; xiqu[0]=-1; printf("#########################################\n"); printf("## 用!表示否定 ##\n"); printf("## 用&表示合取 ##\n"); printf("## 用|表示析取 ##\n"); printf("## 用^表示条件 ##\n"); printf("## 用~表示双条件 ##\n"); printf("#########################################\n\n"); printf("请输入一个合法的命题公式:\n"); gets(T1);

strcpy(T10,T1); for(i1=0;i1='a' && T1[i1]<='z' || T1[i1]>='A' && T1[i1]<='Z') { for(i2=0;i2

北京大学2017秋课件作业【离散数学】及答案

2017秋课件作业 第一部分集合论 第一章集合的基本概念和运算 1-1设集合A={{2，3,4}，5，1}，下面命题为真是（选择题）[A] A．1∈A；B．2∈A；C．3∈A；D．{3，2,1}?A。 1-2A,B,C为任意集合，则他们的共同子集是（选择题）[D] A．C；B．A；C．B；D．?。 1-3设S={N，Z，Q，R}，判断下列命题是否正确（是非题） （1）N?Q，Q∈S，则N?S，［错］（2）-1∈Z，Z∈S，则-1∈S。［错］ 1-4设集合B={4，3}∩?，C={4，3}∩{?}，D={3，4，?}，E={x│x∈R并且x2-7x+12=0}，F={4，?，3，3}，试问：集合B与那个集合之间可用等号表示（选择题）[A] A.C; B.D; C.E; D. F. 1-5用列元法表示下列集合：A={x│x∈N且3－x〈3}（选择题）[D] A.N; B.Z; C.Q; D.Z+ 1-6为何说集合的确定具有任意性?(简答题) 答：按研究的问题来确定集合的元素。我们所要研究的问题当然是随意的呗。之所以，集合的定义（就是集合成分的确定）当然带有任意性哪。 第二章二元关系 2-1设A={1，2，3}，A上的关系R={〈1，2〉，〈2，1〉}∪IA， 试求：（综合题） (1)domR=?;(2)ranR=?;(3)R的性质。 （4）商集A/R=？（5）A的划分∏=？（6）合成运算（R。R）=？ 答：R={<1,2>,<1,3>,<2,3>，<1，1>，<2，2>，<3，3>}； (1)DomR={R中所有有序对的x}={3,2,1}; (2)RanR={R中所有有序对的y}={2,1,3}； (3)R的性质:自反,反对称,传递性质.这时，R不是等价关系。 （4）商集A/R={{1，2，3}，{2，3}，{3}}。由于R不是等价关系，所以，等价类之间出现交集。这是不允许的。请看下面的划分问题。 （5）A的划分∏={{1，2，3}，{2，3}，{3}}；也由于R不是等价关系，造成划分的荒谬结果：出现交集。试问：让“3”即参加第一组，又参加第二组，她该如何分配呢！！！ 所以，关系R必须是等价关系。至于作业中，此两题应说：因为R不是等价关系，此题无解。 2-2设R是正整数集合上的关系，由方程x+3y=12决定，即 R={〈x，y〉│x，y∈Z+且x+3y=12}， 试给出dom（R。R）。（选择题）[B] A.3； B.{3}； C.〈3，3〉； D.{〈3，3〉}。

析取范式与合取范式

命题常项与命题变项 真值确定的命题称为命题常项或命题常元。 例如，下面的，都是命题常项。p：2是素数。q：雪是黑色的。 简单陈述句中，由于某个或某些成分取值不同而导致该句真值不确定，这种句子称为命题变项，它不是命题，但这个或这些元素成分一旦取值定下来，句子就成为命题。 例不是命题，但当给定与确定的值后，它的真值也就定下来了，它是命题 变项。命题变项也用表示之。一个符号，例如，它表示的是命题常 项还是命题变项，一般由上下文来确定。一个命题变项经符号化后，如符号化为，就可以表示任意的命题。 析取范式与合取范式 析取 用连词∨把几个公式连接起来所构成的公式叫做析取，而此析取式的每一组成部分叫做析取项。由一些合适公式所构成的任一析取也是一个合适公式。 合取 用连词∧把几个公式连接起来而构成的公式叫做合取，而此合取式的每个组成部分叫做合取项。一些合适公式所构成的任一合取也是一个合取公式。 定义 命题变项及其否定统称作文字。仅由有限个文字构成的析取式称为简单析取式。仅由有限个文字构成的合取式称为简单合取式。 例如，文字：p，┐q，r，q。 简单析取式：p，q，p∨q，p∨┐p∨r，┐p∨q∨┐r。 简单合取式：p，┐r，┐p∧r，┐p∧q∧r，p∧q∧┐q。 定理 （1）一个简单析取式是重言式当且仅当它同时含某个命题变项及它的否定。 （2）一个简单合取式是矛盾式当且仅当它同时含某个命题变项及它的否定。 矛盾式 contradictory（矛盾式或永假式） 设A为任一命题公式，若A在它的各种指派情况下，其取值均为假，则称A是矛盾式或永假式。 若命题公式A不是矛盾式，则称A为可满足式。 重言式 Tautology （重言式又称为永真式） 设A为任一命题公式，若A在它的各种赋值下取值均为真，则称A是重言式。 定义 （1）由有限个简单合取式构成的析取式称为析取范式。 （2）由有限个简单析取式构成的合取式称为合取范式。 （3）析取范式与合取范式统称为范式。 例如，析取范式：（p┐∧q）∨r，┐p∧q∧r，p∨┐q∨r。

北京大学离散数学教材 2

命题逻辑等值演算2学习目的 本章主要涉及命题演算中两个重要内容之一：等值演算。首先理解命题公式等值的含义，掌握构造真值表和不构造真值表两种方法证明等值式，熟练应用于命题公式的化简和范式表示 基本内容 z命题公式等值关系及其证明 z联结词的全功能集 z命题公式的范式表示

等值关系 基本概念 等值的两种定义： z如果两个逻辑形式对其中的命题变项的任何取值，都具有相同的值，则称它们是相等的。 z A、B等值是指等价式A?B为重言式，记为A?B。 可直接构造真值表证明两个命题形式的等值。 等值演算 根据已知的等值式，可以推演出另外许多的等值 式，这种推演过程称为等值演算。 这些已知等值式通常是经过证明了的常用等值式， 其中许多是布尔代数或逻辑代数的主要组成部分， 称为等值关系模式： (1) 双重否定律： A ???A (2) 等幂律：(2a) A ? A∧A (2b) A ? A∨A (3) 交换律：(3a) A∧B ? B∧A

(3b) A∨B ? B∨A (3c) A∨B ? B∨A (3d) A?B ? B?A (4) 结合律：(4a) (A∧B)∧C ? A∧(B∧C) (4b) (A∨B)∨C ? A∨(B∨C) (4c) (A∨B) ∨C ? A∨ (B∨C) (4d) (A?B) ?C ? A? (B?C) (5) 分配律：(5a) A∨(B∧C) ? (A∨B)∧(A∨C) (5b) A∧(B∨C) ? (A∧B)∨(A∧C) (5c) A∧(B∨C) ? (A∧B) ∨ (A∧C) (6) 德?摩根律：(6a) ?(A∧B) ??B∨?A (6b) ?(A∨B)??B∧?A (7) 吸收律：(7a) A∨(A∧B)?A (7b) A∧(A∨B)?A (7c) A∨(?A∧B)?A∨B (7d) A∧(?A∨B)?A∧B (7e) (A∧B) ∨ (?A∧C) ∨ (B∧C) ? (A∧B) ∨ (?A∧C) (8) 零律：(8a) A∨1 ? 1 (8b) A∧0 ? 0 (9) 同一律：(9a) A∨0 ? A (9b) A∨0 ? A (10)排中律：A∨?A ? 1 (11)矛盾式：A∧?A ? 0 (12)蕴涵等值式：A→B ??A∨B

利用真值表法求取主析取范式以及主合取范式的实现---副本

利用真值表法求取主析取范式以及主合取范式的实现---副本

#include "stdio.h" #include "stdlib.h" #include "string.h" #include "math.h" #define N 50 void pd(int b[N],int f); int H1 (char T1[N], char T2[N], int T3[N], int y); int H2 (char T1[N], char T2[N], int T3[N], int y); int main() { int i1,i2,d=1,T3[N],kh=0,jg,j=0,y; int w=0,hequ[N],h=0,x=0,xiqu[N]; char T1[N],T2[N],T10[N],s; hequ[0]=-1; xiqu[0]=-1; printf("####################################### ##\n"); printf("## 用!表示否定##\n"); printf("## 用&表示合取##\n");

printf("## 用|表示析取##\n"); printf("## 用^表示条件##\n"); printf("## 用~表示双条件##\n"); printf("####################################### ##\n\n"); printf("请输入一个合法的命题公式:\n"); gets(T1); strcpy(T10,T1); for(i1=0;i1='a' && T1[i1]<='z' || T1[i1]>='A' && T1[i1]<='Z') { for(i2=0;i2

北京大学1997年研究生入学考试离散数学试题共50分

北京大学1997年研究生入学考试离散数学试题（共50分） 1 (7分) 在一阶逻辑自然推理系统F中，构造下面推理的证明。个体域是人的集合。 “每位科学家都是勤奋的，每个勤奋又身体健康的人在事业中都会获得成功。存在着身体健康的科学家。所以，存在着事业获得成功的人或事业半途而废的人。” 2 (8分) 在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断： 甲说：王教授不是苏州人，是上海人。 乙说：王教授不是上海人，是苏州人。 丙说：王教授既不是上海人，也不是杭州人。 王教授听后，笑曰：你们3人中有一人全说对了，有一人全说错了，还有一人对错各半。 试用逻辑演算法判断王教授是哪里人？ 3 (3分) 设根树T有17条边，12片树叶，4个4度内点，1个3度内点。求T的树根的度数。 4 (7分) 设无向图G是n(n≥3)个顶点的极大平面图，证明G的对偶图G*的边连通度l(G)≥2，并且G*是3-正则图(Δ(G)=d(G)=k的无向图G称作k-正则图)。 5 (4分) 设R={| x,y?nùx+3y=12}，求R2。 6 (6分) 设A为集合，B=P(A)-{?}-{A}，且B≠?。 求偏序集的极大元，极小元，最大元和最小元。 7 (4分)

设A={1,2,3}，f?AA，且f(1)=f(2)=1，f(3)=2，定义G：A→P(A)，G(x)=f-1(x)。说明G有什么性质(单射、满射和双射)，计算值域ranG。 8 (4分) 设I是格L的非空子集，如果 (1) "a,b?I，有aúb?I， (2) "a?I，"x?L，有x≤aTx?I。 则称I是格L的理想。 证明：格L的理想是一个子格。 9 (7分) 设G为n阶群，a?G。令 H={xax-1|x?G}，N(a)={x|x?Gùax=xa}。 证明： ① |H|=[G:N(a)]； ②设C={x|x?Gù"y?G(xy=yx)}是群G的中心，且|C|=m，则|H|∣n/m。

重言式与矛盾式的主析取范式与主合取范式

重言式与矛盾式的主析取范式与主合取范式。 1、先看下列简单的问题： 命题公式P→（Q→P）的主合取范式为。 解：根据蕴涵词的意义，当P为假时，P→（Q→P）为真； 当P为真时，Q→P为真，因而P→（Q→P）为真，所以P→（Q→P）永远为真，即P→（Q→P）是一个重言式。P→（Q→P）中总共有两个命题变元P和Q，因而对应有个不同的极大项，每个极大项对应着使得P→（Q→P）为假的一种赋值。现在P→（Q→P）不可能为假，所以P→（Q→P）的主合取范式中不能含有极大项，因而其主合取范式只能是一个不含极大项的空范式。我们约定： 用1表示重言式的主合取范式。所以命题公式P→（Q→P）的主合取范式为1。 2、一般地，如果一个命题公式G中共有n个命题变元。每个变元有真和假两种不同的赋值。因而G总共有2n种不同的赋值。对应着每一种赋值，都有一个极小项和极大项，极小项在对应的赋值下为真，极大项在对应的赋值下为假。如果G正好在m种赋值下为真，在另外的种赋值下为假，那么使得G为真的m种赋值所对应的m个极小项的析取就是G的主析取范式，使得G为假的其他种赋值所对应的个极大项的合取就是G的主合取范式。 如果G是重言式，全部2n种赋值都使得G为真，因而所有的2n个极小项的析取是G的主析取范式。重言式G的主合取范式不含极大项，是空范式，就用1表示。 如果G是矛盾式，全部2n种赋值都使得G为假，因而所有的2n个极大项的合取是G的主合取范式。矛盾式G的主析取范式不含极小项，是空范式，就用0表示。 3、P→（Q→P）的主析取范式为 由P→（Q→P）对应的所有4个极小项的析取得到。 4、重言式和矛盾式的主析取范式和主合取范式，在教材中没有讲清楚，因而在做有关练习和考试题时，同学们感到茫然。现在，大家应该清楚了。这里也进一步明确了用真值表方法求主合取范式和主析取范式的依据和步骤。

离散数学主析取范式主合取范式

实验二 实验题目： 生成主析取范式和主合取范式 实验目的： 1.熟悉地掌握计算机科学技术常用的离散数学中的概念、性质和运算；通过实验提高学生编写实验报告、总结实验结果的能力；使学生具备程序设计的思想，能够独立完成简单的算法设计和分析。 2.掌握命题逻辑中的联接词、真值表、主范式等，进一步能用它们来解决实际问题。 实验内容： 利用计算机构造真值表来建立主析取范式和主合取范式 实验原理： 1.合取：二元命题联结词。将两个命题P、Q联结起来，构成一个新的命题P ∧Q。这个新命题的真值与构成它的命题P、Q的真值间的关系为只有当两个命题变项P 为真, Q为真时方可P∧Q为真, 而P、Q只要有一为假则P∧Q 为假。 2.析取：二元命题联结词。将两个命题P、Q联结起来，构成一个新的命题P ∨Q。这个新命题的真值与构成它的命题P、Q的真值间的关系为只有当两个命题变项P为假, Q为假时方可P∨Q为假, 而P、Q只要有一为真则P∨Q为真。 3.真值表:表征逻辑事件输入和输出之间全部可能状态的表格。列出命题公式真假值的表。通常以1表示真，0 表示假。命题公式的取值由组成命题公式的命题变元的取值和命题联结词决定，命题联结词的真值表给出了真假值的算法。真值表是在逻辑中使用的一类数学表，用来确定一个表达式是否为真或有效。 4.主析取范式：在含有n个命题变元的简单合取式中,若每个命题变元与其否定不同时存在,而两者之一出现一次且仅出现一次,称该简单合取式为小项。由若干个不同的小项组成的析取式称为主析取范式;与A等价的主析取范式称为A的主析取范式。任意含n个命题变元的非永假命题公式A都存在与其等价的主析取范式,并且是惟一的。 5.主合取范式：在含有n个命题变元的简单析取式中,若每个命题变元与其否定不同时存在,而两者之一出现一次且仅出现一次,称该简单析取式为大项。由若干个不同的大项组成的合取式称为主合取范式;与A等价的主合取范式称为A 的主合取范式。任意含n个命题变元的非永真命题公式A都存在与其等价的主合取范式,并且是惟一的。

北京大学16秋季《离散数学》课程作业教学内容

北京大学16秋季《离散数学》课程作 业

2016秋课件作业 第一部分集合论 第一章集合的基本概念和运算 1-1 设集合 A ={{2，3,4}，5，1}，下面命题为真是（选择题） [ ] A．1 ∈A； B．2 ∈ A； C．3 ∈A； D．{3，2,1} ? A。 1-2 A,B,C为任意集合，则他们的共同子集是（选择题） [ ] A．C； B．A； C．B； D．?。 1-3 设 S = {N，Z，Q，R}，判断下列命题是否正确（是非题） （1） N ? Q，Q ∈S，则 N ? S，［］（2）-1 ∈Z，Z ∈S，则 -1 ∈S 。［］ 1-4 设集合 B = {4，3} ∩?， C = {4，3} ∩{ ? }，D ={ 3，4，? }， E = {x│x ∈R 并且 x2 - 7x + 12 = 0}， F = { 4，?，3，3}， 试问：集合 B 与那个集合之间可用等号表示（选择题） [ ] A. C; B. D; C. E; D. F. 1-5 用列元法表示下列集合：A = { x│x ∈N 且 3－x 〈 3 }（选择题） [ ] A. N; B. Z; C. Q; D. Z+ 1-6 为何说集合的确定具有任意性 ? (简答题) 第二章二元关系 2-1 给定 A =（3, 2，1），R 是 A 上的二元关系，其表达式如下： R = {〈x，y〉x，y ∈A 且 x ＝ y } （综合题） 求：(1)domR =?; (2)ranR =?; (3)R 的性质。 （4）商集 A/R =？（5）A 的划分∏=？（6）合成运算（R 。R）=？2-2 设 R 是正整数集合上的关系，由方程 x + 3y = 12 决定，即 R = {〈x，y〉│x，y ∈Z+ 且 x + 3y = 12}， 试给出 dom（R 。R）。（选择题） [ ] A. 3； B. {3}； C. 〈3，3〉； D.{〈3，3〉}。 2-3 判断下列映射 f 是否是 A 到 B 的函数；以及函数的性质。最后指出 f：A→B 中的双射函数。（选择题） [ ] （1）A = {1，2，3}，B = {4，5}， f = {〈1，4〉〈2，4〉〈3，5〉}。（2）A = {1，2，3} = B， f = {〈1，1〉〈2，2〉〈3，3〉}。（3）A = B = R， f = x 。 （4）A = B = N， f = x2。 （5）A = B = N， f = x + 1 。 A.（1）和（2）； B.（2）和（3）； C.（3）和（4）； D.（4）和（5） 2-4 设ｆ(x)＝x+1，ｇ(x)＝x-1 都是从实数集合Ｒ到Ｒ的函数，则ｆ。ｇ＝ [ ] A．x+1； B．x-1； C．x； D．x2。

离散数学习题与解答

作业题与解答 第一章 19 (2)、(4) 、(6) 21 (1)、(2) 、(3) 19、(2) 解答: (p→┐p)→┐q 真值表如下: 所以公式(p→┐q)→┐q 为可满足式 19、(4) 解答: (p→q)→(┐q→┐p) 真值表如下: 所以公式(p→q)→(┐q→┐p)为永真式

19、(6)解答: ((p→q)∧(q→r))→(p→r) 真值表如下: 所以公式((p→q)∧(q→r))→(p→r)为永真式21、(1)解答: ┐(┐p∧q)∨┐r 真值表如下: 所以成假赋值为:011

21、(2) 解答: (┐q∨r)∧(p→q)真值表如下: 所以成假赋值为:010,100,101,110 21、(3)解答: (p→q)∧(┐(p∧r)∨p)真值表如下: 所以成假赋值为:100,101

第二章5、(1) (2) (3) 6、(1) (2) (3) 7、(1) (2) 8、(1) (2) (3) 5、求下列公式的主析取范式,并求成真赋值 (1) (┐p→q)→(┐q∨p) ?┐(┐p→q) ∨(┐q∨p) ?┐(┐(┐p) ∨q) ∨(┐q∨p) ?(┐p ∧┐q) ∨(┐q∨p) ?(┐p ∧┐q) ∨(p ∧┐q)∨(p ∧q) ?m0 ∨m 2∨m3， 所以00，10，11 为成真赋值。 (2) (┐p→q)∧(q∧r) ?(┐┐p∨q)∧(q∧r) ?(p∨q)∧(q∧r) ?(p∧q∧r)∨(q∧r) ?(p∧q∧r)∨(p∧q∧r)∨(┐p∧q∧r) ?(p∧q∧r)∨(┐p∧q∧r) ?m3∨m 7， 所以011，111 为成真赋值。 (3) (p∨(q∧r))→(p∨q∨r) ?┐(p∨(q∧r))∨(p∨q∨r) ?(┐p∧(┐q∨┐r))∨(p∨q∨r) ?(┐p∧┐q)∨(┐p∧┐r)∨(p∨q∨r) ?(┐p∧┐q)∨((┐p∧┐r)∨(p∨q∨r)) ?(┐p∧┐q)∨((┐p∨p∨q∨r)∧(┐r∨p∨q∨r) ) ?(┐p∧┐q)∨(1∧1) ?(┐p∧┐q)∨1

北京大学离散数学教材 1

命题逻辑基本概念1 逻辑是解决推理方法的学科，中心是推理，基本要素是命题，所以称为命题逻辑。 数理逻辑则是用数学方法研究推理。 学习目的 本章首先要深刻理解命题的概念，理解原子命题和符合命题的关系，在此基础之上理解逻辑联结词的定义，命题公式的定义和分类，最后熟练掌握并应用真值表的构造 基本内容： z命题概念； z逻辑联结词概念，复合命题和联结词的关系； z命题符号化和翻译 z合式公式概念及分类； z构造真值表判定公式类型

命题(statement, proposition) 概念 在二值逻辑中，命题是或真或假，而不会同时又真 又假的陈述句。 z陈述句； z或真或假，唯一真值； 例： (1) 地球是圆的；真的陈述句，是命题 (2) 2+3=5；真的陈述句，是命题 (3) 你知道命题逻辑吗？非陈述句，故非命题 (4) 3-x=5；陈述句,但真假随x的变化而变 化，非命题 (5) 请安静！非陈述句，故非命题 (6) 火星表面的温度是800°C； 现时不知真假的陈述句，但只能 要么真要么假，故是命题 (7) 明天是晴天；尽管要到第二天才能得知其真 假，但的确是要么真要么假，故 是命题 (8) 我正在说谎；无法得知其真假，这是悖论

注意: (4)不是命题，后续章节中会提到，这被称为谓词，命题函数或命题变项。 分类： z简单命题，通常用p, q, r,…,等表示命题变项，命题常项用1(T)，0(F)表示； z复合命题，由简单命题和联结词构成；

逻辑联结词和复合命题 多个命题变项由联结词联结起来成为复合命题。 否定式和否定联结词(negation) 命题p的非或否定，称为p的否定式，表示为?p； 符号?即为否定联结词。真值表： p? p T F F T 严格说，? p不是复合命题。 例：p：今天天气好；?p：今天天气不好 p：2+5>1；?p： 2+5≤1； 在此情形下，p为真，?p为假。 合取式和合取联结词(conjunction) p且q称为p, q的合取式，记为p∧q；符号∧即为合 取联结词。 这是逻辑“与”。