试题.习题—--离散数学复习资料-试卷-习题与答案全集.doc

离散试卷及答案
离散数学总复习资料
一、鸽笼原理与容斥原理
1．求证边长为1的正方形中放9个点，由这些点构成的三角形中，必有一个三角形面积小于。
证：把该正方形均分成四个相同的小正方形，则由鸽笼原理知，必有一个小正方形内存在三个点，且这三个点构成的三角形面积小于。#
2．对一列个不同整数，任意排列，证明一定存在长为的上升子序列或下降子序列。
证：设此序列为：，从开始上升子序列最长的长度为，下降子序列最长的长度为，每一个都对应了。若不存在长为的上升子序列或下降子序列，那么，形如的不同点对至多有个，而有个，则由鸽笼原理知，必有同时对应，由于，若，则至少比大1，若，则至少比大1，这均与矛盾。故原命题成立。#
3．求中不被3、4、5整除的个数。
解： 设表示中被3整除的数的集合，表示中被4整除的数的集合，表示中被5整除的数的集合，则
， ，进而有

故有
即中不被3、4、5整除的个数为40。#
4．有100个学生，其中60个爱看小说，30个爱下棋，10个既爱看小说，又爱下棋，5个既爱看小说，又爱跳舞，没有既爱下棋，又爱跳舞的，三种活动都不爱的有10个，问有几个学生爱跳舞？
解：设全体学生的集合为，爱看小说的学生集合为，爱下棋的学生集合为，爱跳舞的学生集合为，则依题意有， ，，从而，。另一方面，根据容斥原理，我们有，即有，故，即有15个学生爱跳舞。#

二、数理逻辑
5．求的主析取、主合取范式。
解：取真为：(1,1)，(0,0)，(0,1)；故的主析取范式为；取假为：(1,0)；故的主合取范式为：。
6．求的主析取、主合取范式。
解：取真为：(1,1,1)，(0,0,1)，(0,1,1)，(1,0,0)，(1,0,1)；故的主析取范式为
； 取假为：(1,1,0),(0,1,0),(0,0,0)；
故的主合取范式为：。
7．（1）将式子“并非跑的最快的马吃的最多”翻译成用谓词和量词表达的逻辑式子。(2)将式子“爱因斯坦于1952年写完‘狭义与广义相对论浅说’”翻译成用谓词和量词表达的逻辑式子。

解：（1）：马； ：跑的最快的马； ：吃的最多的马。
上式表示为：
（2）设：爱因斯坦； ：1952； ：‘狭义与广义相对论浅说’； ：于年写完；则原式子可翻译成逻辑式子。
8．求下述公式的前束范式和Skolem标准形。

解：=
=
=
=
=
=
故该公式的前束范式为；
Skolem标准形为。#
9．将下列命题符号化，并证明其论证是否正确。
不存在白色的乌鸦；北京鸭是白色的。因此，北京鸭不是乌鸦。
解：令是白色的；：是乌鸦；：是北京鸭。则上述命题可符号化为：
下面，我们证明上述命题是正确的。
（1） （P）
（2） （US）
（3） （CP）
（4） （分离规则）
（5） （量词转换律）
（6） （US）
（7） （T，（4））
（8）
（9） （UG）#

三、二元关系
10．(1)举出正整数集上一种关系,它是等价关系但不是偏序关系;(2) 举出正整数集上一种关系,它是偏序关系但不是等价关系。(3)画出集合上整除关系的Hasse图。（4）等价关系与划分关系
解：（1）正整数集上模3的同余关系。
（2）正整数集上的整除关系。
（3）
24
12
8
6
4 3
2
1
11．(1)举出正整数集上一种二元关系,它是等价关系又是偏序关系;(2) 画出的Hasse图 ,其中。
解：（1）正整数集上的恒等关系。
（2）
6
4 3
2
1

12．设，定义上的一个二元关系如下：

（1）画出的关系图，并写出的关系矩阵；（2）求，；（3）求，，。
解：（1）

（2）
（3）

又
故

13．设是正整数集关于整除关系作成的偏序集，的子集，求的极小元、极大元、上界、下界、最小上界、最大下界。
解：（略）

四．图论
14．（1）画一个图，使它既有欧拉回路，又有哈密顿回路；（2）画一个回路图，使它既无欧拉回路，又无哈密顿回路。
解：（1）

（2）

或

15．（1）画一个图，使它有欧拉回路，无哈密顿回路；（2）画一个回路图，使它无欧拉回路，有哈密顿回路。
解：（1）

（2）

16．证明小于30条边的简单平面图至少有一个顶点的度数小于5。
证：（反证法）假设小于30条边的简单平面图中每一个顶点的度数大于等于5，从而此时顶点数与边数满足；另一方面，由于此时图的每一个区域至少由3条边围成，从而由Euler公式推论知，此时顶点数与边数满足；故有，进而有，这与已知条件产生矛盾。故小于30条边的简单平面图至少有一个顶点的度数小于5。#
17．证明具有6个顶点和12条边的连通简单平面图，它的每个区域都是由三条边围成。
证： 由题意及欧拉公式知，其区域数为。若有一个区域不是由三条边围成，则至少由4条边围成，从而8个区域至少需要25条边才能围成，即图中的边数不少于25/2=12.5, 这与已知条件12条边产生矛盾，故它的每个区域都是由三条边围成。#
18．设， 任意顶点的次（度）不少于2，且任意两个相邻区域只有一条公共边的简单平面图，证明其着色数不少于3。
解：（略）

19．用算法寻找下图中顶点到的最短路径。
g 2 h 2 i 2 j
2 1 1 2 2 1

d 2 e 2 f
2 1 1 2
b 1 c
2 1
a
解：从出发第一短的点为，距离为1，路径为；从出发第二短的点为或，距离为2，路径为或；从出发第四短的点为或，距离为3，路径为或；从出发第五短的点为或或，距离为4，路径为或（或）或。故顶点到的最短路径为。#
20．求分别用前序、中序、后序遍历（周游）下图。
6

2 10

1 4 7 11

3 5 9
8
解：前序6-2-1-4-3-5-10-7-9-8-11

中序1-2-3-4-5-6-7-8-9-10-11

后序1-3-5-4-2-8-9-7-11-10-6
21．求出下图的最小生成树。
2
1 1
2 1 2
2 1

3 3 2

解：
1 1 1 1
1 1 2
1 或 1
2 2
2

22．设7个字母在通讯中出现的频率如下， ，编一个相应的二元前缀码，使通讯中出现的符号尽可能少，并画出对应的二元树。解：该二元前缀码对应的Huffman树为：

100
40 60

20 20 25 35
10 10 10 15
5 5

从而对应的二元前缀码为：。#
23．（10分）给定树叶的权分别为1，4，9，16，25，36，49，64，81，100，试构造一棵最优树。
解：（略）
24.握手原理及其应用。
五．代数系统与布尔代数
24．讨论下表给出集合上的运算是否具有交换律、结合律，并求出零元、幂等元。
*
0
1
2
3
0
0
0
0
0
1
0
1
2
3
2
0
2
0
2
3
0
3
2
1
解：根据上表运算结果的对称性知,上述运算满足交换律,又由上表的第二行与第二列知0是其零元, 再由上表的第三行与第三列知1是其幺元，并由对角线上的具体结果知，仅有0与1是其幂等元。从而对，当中有一个为0或1时，均有；又，，，，，, ，，。故上述运算满足结合律。#
25．设是一个半群，,对中每个中存在元素满足，则中存在幺元。
证:依题意，存在满足。另一方面，任取中中存在元素满足，从而有

故有，进而有，即为中幺元。#
26．设是一个半群，证明如果是一个有限集，则在中存在元素，使得。
解：由于是一个有限集，取中元素，故由鸽笼原理知，存在正整数满足。令，则，进而对任意的，也有。另一方面由于，故存在正整数满足，从而，进而有。令，有。#
27．求的所有子群及陪集，其中。
解：其子群为。关于子群的陪集分别为；关于子群的陪集分别为；关于子群的陪集分别为；关于子群的陪集就是其自身。#
28．求证有限群中周期大于2的元素个数必为偶数。
证：因为根据群元素周期的定义知，每个元素与其逆元素的周期是一致的，而当该元素的周期大于2时，其逆元素与本身不同，故有限群中周期大于2的元素必是成对出现，从而其周期大于2的元素个数必为偶数。#
29．若是格中的元素，求证：。
证：；又；
进而有。#
30．若是格中的元素，求证：。
证： ；又；
进而有。#
31.分配格与模格的刻画与关系。

第1章 命题逻辑
本章重点：命题与联结词，公式与解释，真值表，公式的类型及判定, (主)析取(合取)范式，命题逻辑的推理理论.

一、重点内容
1. 命题
命题表述为具有确定真假意义的陈述句。命题必须具备二个条件：其一，语句是陈述句；其二，语句有唯一确定的真假意义.
2. 六个联结词及真值表
h“Ø”否定联结词，P是命题，ØP是P的否命题，是由联结词 Ø 和命题P组成的复合命题.P取真值1，ØP取真值0，P取真值0，ØP取真值1. 它是一元联结词.
h “Ù”合取联结词，PÙQ是命题P，Q的合取式，是“Ù”和P，Q组成的复合命题. “Ù”在语句中相当于“不但…而且…”，“既…又…”. PÙQ取值1，当且仅当P，Q均取1；PÙQ取值为0，只有P，Q之一取0.
h “Ú”析取联结词，“`Ú”不可兼析取(异或)联结词， PÚQ是命题P，Q的析取式，是“Ú”和P，Q组成的复合命题. P`ÚQ是联结词“`Ú”和P，Q组成的复合命题. 联结词“Ú”或“`Ú”在一个语句中都表示“或”的含义，前者表示相容或，后者表示排斥或不相容的或. 即“P`ÚQ”«“(ØPÙQ)Ú(PÙØQ)”. PÚQ取值1，只要P，Q之一取值1，PÚQ取值0，只有P，Q都取值0.
h “®”蕴含联结词， P®Q是“®”和P，Q组成的复合命题，只有P取值为1，Q取值为0时，P®Q取值为0；其余各种情况，均有P®Q的真值为1，亦即1®0的真值为0，0®1，1®1，0®0的真值均为1. 在语句中，“如果P则Q”或“只有Q，才P，”表示为“P®Q”.
h “«” 等价联结词，P«Q是P，Q的等价式，是“«”和P，Q组成的复合命题. “«”在语句中相当于“…当且仅当…”，P«Q取值1当且仅当P，Q真值相同.
3. 命题公式、赋值与解释，命题公式的分类与判别
h命题公式与赋值，命题P含有n个命题变项P1，P2,…,Pn，给P1，P2,…,Pn各指定一个真值，称为对P的一个赋值(真值指派). 若指定的一组值使P的真值为1，则这组值为P的真指派；若使P的真值为0，则称这组值称为P的假指派.
h命题公式分类，在各种赋值下均为真的命题公式A，称为重言式(永真式)；在各种赋值下均为假的命题公式A，称为矛盾式(永假式)；命题A不是矛盾式，称为可满足式；
判定命题公式类型的方法：其一是真值表法，任给公式，列出该公式的真值表，若真值表的最后一列全为1，则该公式为永真式；若真值表的最后一列全为0，则该公式是永假式；若真值表的最后一列既非全1，又非全0，则该公式是可满足式.其二是推导演算法. 利用基本等值式(教材P.16的十六个等值式或演算律)，对给定公式进行等值推导，若该公式的真值为1，则该公式是永真式；若该公式的真值为0，则该公式为永假式.既非永真，也非用假，成为非永真的可满足式.其三主析取(合取)范式法，该公式的主析取范式有2n个极小项(即无极大项)，则该公式是永真式；该公式的主合取范式有2n个极大项(即无极小项)，则该公式是永假式；该公式的主析取(或合取)范式的极小项(或极大项)个数大于0小于2n,，则该公式是可满足式.
h等值式AÛB，命题公式A，B在任何赋值下，它们的真值均相同，称A，B等值。
定理1 设F(A)是含命题公式A的命题，F(B)是用命题公式B置换F(A)中的A之后得到的命题公式. 如果AÛB，则F(A)ÛF(B).
4. 范式
h 析取(合取)范式，仅有有限个简单合取式(析取式)构成的析取式(合取式)，就是析取(合取)范式.
h 极小项(极大项)，n个命题变项P1,P2,…,Pn，每个变项或它的否定两者只有其一出现且仅出现一次，第i个命题变项或者其否定出现在从左起第i个位置上(无脚标时，按字典序排列)，这样的简单合取式(析取式)为极小项(极大项).
以两个命题变项为例，m00=ØPÙØQ，m01=ØPÙQ,m10=PÙØQ,m11=PÙQ是极小项;M00=PÙQ，M01=PÙØQ,M10=ØPÙQ,M11=ØPÙØQ是极大项.
h 主析取范式(主合取范式) 含有n个命题变项的命题公式，如果与一个仅有极小项(极大项)的析取(合取)构成的析取(合取)范式等值，则该等值式称为原命题公式的主析取(合取)范式。
每项含有n个命题变项(变项字母齐全)的合取式(析取式)的析取(合取)为主析取(合取)范式.
任意命题公式都存在与之等值的范式，存在与之等值的主范式，且是惟一的.
求范式，包括求析取范式、合取范式、主析取范式和主合取范式. 关键有两点：其一是准确掌握范式定义；其二是巧妙使用基本等值式中的分配律、同一律和摩根律，结果的前一步适当使用幂等律.
求析取(合取)范式的步骤：
① 将公式中的联结词都化成Ø，Ù，Ú(即消去个数中的联结词®，«，`Ú)；
② 将否定联结词Ø消去或移到各命题变项之前；
③ 利用分配律、结合律等，将公式化为析取(合取)范式.
求命题公式A的主析取(合取)范式的步骤
① 求公式A的析取(合取)范式；
② “消去”析取(合取)范式中所有永假式(永真式)的析取项(合取项)，如PÙØP(PÚØP)用0(1)替代. 用幂等律将析取(合取)范式中重复出现的合取项(析取项)或相同的变项合并，如PÙP(PÚP)用P替代，miÚmi(MiÙMi)用mi(Mi)替代.
③ 若析取(合取)范式的某个合取项(析取项)B不含有命题变项Pi或ØPi，则添加PiÚØPi(PiÙØPi)，再利用分配律展开，使得每个合取项(析取项)的命题变项齐全；
④ 将极小(极大)项按由小到大的顺序排列，用S(P)表示.
5. 命题演算的推理理论
h设A1,A2,…,An,C是命题公式，如果是重言式，称C是前提集合{ A1,A2,…,An}的有效结论或{A1,A2,…,An}逻辑地推出C。记作
掌握演绎或形式证明. 要理解并掌握14个重言蕴含式(即I1～I14)，17个等值式(E1～E17)；二是会使用三个规则(P规则、T规则和CP规则)。
推理方法有：
真值表法；等值演算法；主析取范式法，构造证明法(直接证明法、附加前提证明法和间接证明法)

二、实例
例1.1 判别下列语句是否命题？如果是命题，指出其真值.
(1) 中国是一个人口众多的国家. (2) 存在最大的质数.
(3) 这座楼可真高啊！ (4) 请你跟我走!
(5) 火星上也有人.
解 (1) 是命题，真值为1. (2) 是命题，真值为0.
(3), (4)不是命题因为不是陈述句.
(5) 是命题. 真值是唯一的，迟早会被指出.
例1.2 将下列命题符号化：
(1) 虽然交通堵塞，但是老王还是准时到达火车站；
(2) 张力是三好生，他是北京人或是天津人.
(3) 除非天下雨，否则我骑车上班.
解 (1) 设P：交通堵塞，Q：老王准时到达火车站.
该命题符号化为：PÙQ.
(2)设P：张力是三好生； Q：张力是北京人，R：张力是天津人.
该命题符号化为PÙ(Q`ÚR ).
(3)设P：天下雨，Q：我不骑车上班.
该命题符号化为：Q®P，义即“只有天下雨，我才不骑车上班”，不下雨是我骑车上班的必要条件。它的等价说法是“如果天不下雨，我就骑车上班”，即ØP®ØQ
“如果天下雨，我就不骑车上班”，这是蕴含关系，符号化为：P®Q
注：本例各小题都是复合命题。如“李枚和张樱花是好朋友”是简单命题，用字母P表示。显然P：李枚是好朋友，Q：张樱花是好朋友，符号化为QÙP是不通的.
例1.3 证明：P®(Q®R)ÛPÙQ®R.
证明 方法1 真值表法. 列公式P®(Q®R)与PÙQ®R的真值表如表1－1. .

表1－1 公式P®(Q®R)与PÙQ®R的真值表
P
Q
R
Q®R
P®(Q®R)
PÙQ
PÙQ®R
P®(Q®R)«PÙQ®R
0
0
0
1
1
0
1
1
0
0
1
1
1
0
1
1
0
1
0
0
1
0
1
1
0
1
1
1
1
0
1
1
1
0
0
1
1
0
1
1
1
0
1
1
1
0
1
1
1
1
0
0
0
1
0
1
1
1
1
1
1
1
1
1
由表可知，公式P®(Q®R)与PÙQ®R的真值完全相同，故P®(Q®R)ÛPÙQ®R..
或由表的最后一列可知，P®Q«ØPÚQ是重言式，故P®(Q®R)ÛPÙQ®R.
注：作为本例的证明可以不要最后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 (结合律)
ÛØ(PÙQ)ÚR (摩根律)
ÛPÙQ®R (等值蕴含式)
所以，P®（Q®R）Û(PÙQ)®R
例中等值演算的每一步都用到了置换规则. 由等值演算的传递性，可知第一个公式P®(Q®R)和最后一个公式PÙQ)®R等值.
方法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的主合取范式相同，故P®(Q®R)ÛPÙQ®R。
注：(1)容易写出P®(Q®R)与PÙQ®R的主析取范式均为m0Úm1Úm2Úm3Úm4Úm5Úm7即 (ØPÙØQÙØR)Ú(ØPÙØQÙR)Ú(ØPÙQÙØR)
Ú(ØPÙQÙR)Ú(PÙØQÙØR)Ú(PÙØQÙR)Ú (PÙQÙR)
(2) 由真值表求公式P®(Q®R)的主析取范式，先列出P®(Q®R)的真值表，见表1－1。主析取范式是公式P®(Q®R)真值为1的项的析取，真值为1的项，即极小项，有第1,2,3,4,5,6,8共7项. 而极小项是合取式，合取式为1，必定是每个变元或其否定为1，如表1－1中第1行P，Q，R均取1，所以这一项为ØPÙØQÙØR，类似地，7个极小项为：
Ø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)Ú(PÙØQÙØR)Ú(PÙØQÙR)Ú (PÙQÙR)
例1.4 用等值演算法判定公式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
Û(Ø(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ÚP)ÚQÚRÚ(QÙR)Ù1
Û1Ù1Û1
因此，P`Ú(QÙR)®PÚQÚR是永真式.
注：也可以用真值表法或主范式法.
例1.5 化简下式：
(AÙBÙC)Ú(ØAÙBÙC)
解 (AÙBÙC)Ú(ØAÙBÙC)

例1.6 求公式的主合取范式和主析取范式.
解 先将公式化为合取范式.

(去掉«)
(去掉®) (合取范式)
(添齐命题变项)

所求主析取范式为主合取范式的缺项所对应的三个极小项，即为
m1Úm6Úm7ÛÛ
或通过求析取范式求主析取范式.

(去掉«)
(去掉®) (合取范式)

注：也可以用列真值表的方法，求主析取或主合取范式，见例1.3的注.
试用P，Q和联结词Ø，®，Ù构造命题公式A，
使得A与F等值.
解 取真值表中F为1的成真赋值01,10的析取,即为

例1.7 已知P，Q，F的真值表如下表.

P
Q
F
0
0
0
0
1
1
1
0
1
1
1
0
即命题公式与F等值.
例1.8 试证明：
方法1 欲证明，只需证明

是重言式，即其真值是1.
证明

所以，推理正确。
方法2 构造推理附加前提证明法
(1) S CP规则
(2) ØSÚP P
(3) P (1),(2)析取三段论
(4) P®(Q®R) P
(5)Q®R (3),(4)假言推理
(6)Q P
(7)R (5),(6)假言推理
例1.9 填空题
1. 1.       设命题公式G＝PÙ(ØQÚR)，则使G的真
值为1的指派是 ， ， .
答案：(1,0,0,),(1,0,1),(1,1,1)
解答

P
Q
R
ØQ
G＝PÙ(ØQÚR)
由真值表知：P，Q，R的真值指派为
(1,0,0,),(1,0,1),(1,1,1)
则公式G的真值为1.
应填写(1,0,0,),(1,0,1),(1,1,1)

0
0
0
1
0
0
0
1
1
0
0
1
0
0
0
0
1
1
0
0
1
0
0
1
1
1
0
1
1
1
1
1
0
0
0
1
1
1
0
1
2. 已知命题公式为G＝(ØPÚQ)®R,则命题公式G的析取范式是
答案：(PÙØQ)ÚR
解答 (ØPÚQ)®RÛØ(ØPÚQ)ÚRÛ(PÙØQ)ÚR
故应填写(PÙØQ)ÚR.
注：一个命题公式的析取范式一般不唯一。如(PÙØQ)Ú(PÙR)Ú(ØPÙR)也是该公式的一个析取范式.
例1.10 单项选择题
1. 设命题公式Ø(PÙ(Q®ØP))，记作G，使G的真值指派为0的P，Q的真值是( )
(A) (0,0) (B) (0,1) (C) (1,0) (D) (1,1)
答案：(C)
解答 PÙ(Q®ØP)ÛPÙ(ØQÚØP)Û(PÙØQ)Ú(PÙØP)ÛPÙØQ
当P，Q取值(1，0)时， ØPÚQ取真值为0. 故选择(C).
2. 与命题公式P®（Q®R）等值的公式是( )
(A) (PÚQ)®R (B)(PÙQ)®R (C) (P®Q)®R (D) P®(QÚR)
答案：(B)
解答 P®（Q®R）ÛP®(ØQÚR)ÛØPÚØQÚRÛØ(PÙQ)ÚRÛ(PÙQ)®R
故应选择(B)
3. 命题公式(PÙQ）®P是( )
(A) 永真式 (B) 永假式 (C) 可满足式 (D) 合取范式
答案：(A)
解答 (PÙQ）®P
所以是永真式. 故选择(A).
4. 设命题公式，则公式G与H满足( )

答案：(D)
解答

，即为重言式.

或列真值表.
P
Q
ØP
ØQ
GÛØ(P®Q)
HÛP®(Q®ØP)
G®H
0
0
1
1
0
1
1
0
1
1
0
0
1
1
1
0
0
1
1
1
1
1
1
0
0
0
0
1
可见，GÞH，故应选择(D).

三、练习题
1. 判定下列语句是否为命题，若是命题，指出是简单命题或复合命题.
(1) 是无理数. (2) 5能被2整除.
(3) 现在开会吗？ (4) 2是素数当且仅当三角形有3条边.
(5) 如果雪是黑的，则太阳从东方升起.
2. 将第1题的命题符号化，并讨论其真值.
3. 设命题P,Q的真值为0，命题R,S的真值为1，求命题公式的真值.
4. 用多种方法判定命题公式的类型.
5. 用多种方法证明等值式成立.
6. 已知命题P，Q和真值函数F的真值，
(P,Q,F)Û(,00,0),(0,1,0),(1,0,1),(1,1,0).
试用P，Q和联结词Ø，Ú构造命题公式C，使得FÛC.
7. 求命题公式的主析取范式和主合取范式.
8. 试证明：
四、练习题答案
1. (1) , (2)是简单命题，(3) 不是命题，(4)，(5)是复合命题.
2. (1) P:是无理数,P是真命题，真值为1.
(2)P： 5能被2整除，P是假命题，真值为0
(4)P：2是素数，Q：三角形有3条边，原命题符号化为P«Q.，真值为1
(5) P：雪是黑的，Q：太阳从东方升起，原命题符号化为P®Q，其真值为1..
3. 真值为0.
4. 原式等值于，是非永真的可满足式。
5. 提示：用分配律、否定律、同一律.
6.
7 主析取范式：
主合取范式：
8. 前提： 结论：
证明 方法1，直接证明法
(1) ØQÚR P
(2) ØR P
(3) ØQ (1), (2)析取三段论
(4) Ø(PÙØQ〕 P
(5) ØPÚQ (4) 置换
(6) P®Q (5)置换
(7) ØP (3),(6) 拒取式
方法2，间接证明法
(1) Ø(ØP) 结论否定引入
(2) P (1)置换
(3) Ø(PÙØQ) P
(4) P®Q (3) 置换
(5) Q (2),(4)假言推理
(6) ØQÚR P
(7) R (5),(6)析取三段论
(8) ØR P
(9) RÙØR (7),(8) 合取引入
有(9)可知，构造推理是正确的.

¾¾第2章 谓词逻辑
本章重点：谓词与量词，公式与解释，前束范式，谓词逻辑推理证明.

一、重点内容
1. 谓词与量词
h谓词，在谓词逻辑中，原子命题分解成个体词和谓词. 个体词是可以独立存在的客体，它可以是具体事物或抽象的概念。谓词是用来刻划个体词的性质或事物之间关系的词.
个体词分个体常项(用a,b,c,…表示)和个体变项(用x,y,z,…表示)；谓词分谓词常项(表示具体性质和关系)和谓词变项(表示抽象的或泛指的谓词)，用F,G,P,…表示.
注意，单独的个体词和谓词不能构成命题，将个体词和谓词分开不是命题.
h量词，是在命题中表示数量的词，量词有两类：全称量词"，表示“所有的”或“每一个”；存在量词$，表示“存在某个”或“至少有一个”.
在谓词逻辑中，使用量词应注意以下几点：
(1) (1)    在不同个体域中，命题符号化的形式可能不同，命题的真值也可能会改变.
(2) (2)    在考虑命题符号化时，如果对个体域未作说明，一律使用全总个体域.
(3) (3)    多个量词出现时，不能随意颠倒它们的顺序，否则可能会改变命题的含义.
谓词公式只是一个符号串，没有什么意义，但我们给这个符号串一个解释，使它具有真值，就变成一个命题. 所谓解释就是使公式中的每一个变项都有个体域中的元素相对应.
在谓词逻辑中，命题符号化必须明确个体域，无特别说明认为是全总个体域。一般地，使用全称量词"，特性谓词后用®；使用存在量词$，特性谓词后用Ù.
2. 公式与解释
h谓词公式，由原子公式、联结词和量词可构成谓词公式(严格定义见教材). 命题的符号化结果都是谓词公式.
例如"x(F(x)®G(x))，$x(F(x)ÙG(x))，"x"y(F(x)ÙF(y)ÙL(x,y)®H(x,y))等都是谓词公式.
h变元与辖域，在谓词公式"xA和$xA中，x是指导变元，A是相应量词的辖域. 在"x和$x的辖域A中，x的所有出现都是约束出现，即x是约束变元，不是约束出现的变元，就是自由变元. 也就是说，量词后面的式子是辖域. 量词只对辖域内的同一变元有效.
h换名规则，就是把公式中量词的指导变元及其辖域中的该变元换成该公式中没有出现的个体变元，公式的其余部分不变.
h代入规则，就是把公式中的某一自由变元，用该公式中没有出现的个体变元符号替代，且要把该公式中所有的该自由变元都换成新引入的这个符号.
h解释(赋值)，谓词公式A的个体域D是非空集合，则
(1) 每一个常项指定D中一个元素；
(2) 每一个n元函数指定Dn到D的一个函数；
(3) 每一个n元谓词指定Dn到{0,1}的一个谓词；
按这个规