习题 2.1
1．将下列命题符号化。
(1) 4不是奇数。
解：设A(x)：x是奇数。a：4。
“4不是奇数。”符号化为：?A(a)
(2) 2是偶数且是质数。
解：设A(x)：x是偶数。B(x)：x是质数。a：2。
“2是偶数且是质数。”符号化为：A(a)∧B(a)
(3) 老王是山东人或河北人。
解：设A(x)：x是山东人。B(x)：x是河北人。a：老王。
“老王是山东人或河北人。”符号化为：A(a) B(a)
(4) 2与3都是偶数。
解：设A(x)：x是偶数。a：2，b：3。
“2与3都是偶数。”符号化为：A(a)∧A(b)
(5) 5大于3。
解：设G(x,y)：x大于y。a：5。b：3。
“5大于3。”符号化为：G(a,b)
(6) 若m是奇数，则2m不是奇数。
解：设A(x)：x是奇数。a：m。b：2m。
“若m是奇数，则2m不是奇数。”符号化为：A(a)→A(b)
(7) 直线A平行于直线B当且仅当直线A不相交于直线B。
解：设C(x,y)：直线x平行于直线y。设D(x,y)：直线x相交于直线y。a：直线A。b：直线B。
“直线A平行于直线B当且仅当直线A不相交于直线B。”符号化为：C(a,b)??D(x,y)
(8) 小王既聪明又用功，但身体不好。
解：设A(x)：x聪明。B(x)：x用功。C(x)：x身体好。a：小王。
“小王既聪明又用功，但身体不好。”符号化为：A(a)∧B(a)∧?C(a)
(9) 秦岭隔开了渭水和汉水。
解：设A(x,y,z)：x隔开了y和z。a：秦岭。b：渭水。c：汉水。
“秦岭隔开了渭水和汉水。”符号化为：A(a,b,c)
(10) 除非小李是东北人，否则她一定怕冷。
解：设A(x)：x是东北人。B(x)：x怕冷。a：小李。
“除非小李是东北人，否则她一定怕冷。”符号化为：B(a)→?A(a)
2．将下列命题符号化。并讨论它们的真值。
(1) 有些实数是有理数。
解：设R(x)：x是实数。Q(x)：x是有理数。
“有些实数是有理数。”符号化为：(x)(R(x)∧Q(x))
它的真值为：真。
(2) 凡是人都要休息。
解：设R(x)：x是人。S(x)：x要休息。
“凡是人都要休息。”符号化为：("x)(R(x)→S(x))
它的真值为：真。
(3) 每个自然数都有比它大的自然数。
解：设N(x)：x是自然数。G(x,y)：x比y大。
“每个自然数都有比它大的自然数。”符号化为：("x)(N(x)→($y)(N(y)∧G(y,x)))
它的真值为：真。
(4) 乌鸦都是黑的。
解：设A(x)：x是乌鸦。B(x)：是黑的。
“乌鸦都是黑的。”符号化为：("x)(A(x)→B(x))
它的真值为：真。
(5) 不存在比所有火车都快的汽车。
解：设A(x)：x是汽车。B(x)：是火车。K(x,y)：x比y快。
“不存在比所有火车都快的汽车。”符号化为：?($x)(A(x)∧("y)(B(y)→K(x,y)))
它的真值为：真。
(6) 有些大学生不佩服运动员。
解：设S(x)：x是大学生。L(x)：是运动员。B(x,y)：x佩服y。
“有些大学生不佩服运动员。”符号化为：($x)(S(x)∧L(y)∧?B(x,y))
它的真值为：真。
(7) 有些女同志既是教练员又是运动员。
解：设W(x)：x是女同志。J(x)：x是教练员。L(x)：x是运动员。
“有些女同志既是教练员又是运动员。”符号化为：($x)(W(x)∧J(x)∧L(x))
它的真值为：真。
(8) 除2以外的所有质数都是奇数。
解：设A(x)：x是质数。B(x)：x是奇数。C(x,y)：x不等于y。
“除2以外的所有质数都是奇数。”符号化为：("x)(A(x)∧C(x,2)→B(x))
它的真值为：真。
3．指出一个个体域，使下列被量化谓词的真值为真，该个体域是整数集合的最大子集。在以下各题中，A(x)表示：x＞0，B(x)表示：x=5，C(x,y) 表示：x＋y=0
(1) ("x)A(x)
解：正整数集合Z+。
(2) ($x)A(x)
解：整数集合Z。
(3) ("x)B(x)
解：集合｛5｝。
(4) ($x)B(x)
解：整数集合Z。
(5) ("x)($y)C(x,y)
解：整数集合Z。
4．分别在全总个体域和实数个体域中，将下列命题符号化。
(1) 对所有的实数x，都存着实数y，使得x－y=0
解：设R(x)：x是实数。B(x,y)：x－y=0。
在实数个体域符号化为：("x)($y)B(x,y)
在全总个体域符号化为：("x)(R(x)→($y)(R(y)∧B(x,y)))
(2) 存在着实数x，对所有的实数y，都有x－y=0
解：设R(x)：x是实数。B(x,y)：x－y=0。
在实数个体域符号化为：($x)("y)B(x,y)
在全总个体域符号化为：($x)(R(x)∧("y)(R(y)→B(x,y)))
(3) 对所有的实数x和所有的实数y，都有x＋y=y＋x
解：设R(x)：x是实数。B(x,y)：x=y。
在实数个体域符号化为：("x)("y)B(x+y,y+x)
在全总个体域符号化为：("x)(R(x)→("y)(R(y)→B(x+y,y+x))) (4) 存在着实数x和存在着实数y，使得x＋y=100
解：设R(x)：x是实数。B(x,y)：x＋y=100。
在实数个体域符号化为：($x)( $y)B(x,y)
在全总个体域符号化为：($x)(R(x)∧($y)(R(y)∧B(x,y)))
习题2.2
1. 指出下列公式中的约束变元和自由变元。
(1) ("x)(P(x)→Q(y))
解：约束变元：x，自由变元：y
(2) ("x)(P(x)∧R(x))→(($x)P(x)∧Q(x))
解：约束变元：x，自由变元：x
(3) ("x)(P(x)∧($x)Q(x))∨(("x)R(x,y)∧Q(z))
解：约束变元：x，自由变元：y，z
(4) ($x)("y) (R(x,y)∧Q(z))
解：约束变元：x，y，自由变元：z
(5) ("z) (P(x)∧($x)R(x,z)→($y)Q(x,y))∨R(x,y)
解：约束变元：x，y，z，自由变元：x，y
2. 对下列谓词公式中的约束变元进行换名。
(1) ($x)("y)(P(x,z)→Q(x,y))∧R(x,y)
解：将约束变元x换成u：($u)("y)(P(u,z)→Q(u,y))∧R(x,y)
将约束变元y换成v：($x)("v)(P(x,z)→Q(x,v))∧R(x,y)
(2) ("x)(P(x)→(R(x)∨Q(x,y)))∧($x)R(x)→("z)S(x,z)
解：将前面的约束变元x换成u，后面的约束变元x换成v：
("u)(P(u)→(R(u)∨Q(u,y)))∧($v)R(v)→("z)S(x,z)
将约束变元z换成w：("x)(P(x)→(R(x)∨Q(x,y)))∧($x)R(x)→("w)S(x,w)
3. 对下列谓词公式中的自由变元进行代入。
(1) (($y)Q(z,y)→("x)R(x,y))∨($x)S(x,y,z)
解：将自由变元z用u代入：(($y)Q(u,y)→("x)R(x,y))∨($x)S(x,y,u)
将自由变元y用v代入：(($y)Q(z,y)→("x)R(x,v))∨($x)S(x,v,z)
(2) ("y)P(x,y)∧($z)Q(x,z)?($x)R(x,y)
解：将自由变元x用u代入：("y)P(u,y)∧($z)Q(u,z)?($x)R(x,y)
将自由变元y用v代入：("y)P(x,y)∧($z)Q(x,z)?($x)R(x,v)
4. 利用谓词公式对下列命题符号化。
(1) 每列火车都比某些汽车快。
解：设A(x)：x是火车。B(x)：x是汽车。C(x,y)：x比y快。
“每列火车都比某些汽车快。”符号化为：("x)(A(x)→($y)(B(y)∧C(x,y)))
(2) 某些汽车比所有火车慢。
解：设A(x)：x是火车。B(x)：x是汽车。C(x,y)：x比y快。
“某些汽车比所有火车慢。”符号化为：($x)(B(x)∧("y)(A(y)→C(y,x)))
(3) 对每一个实数x，存在一个更大的实数y。
解：设R(x)：x是实数。G(x,y)：x比y大。
“对每一个实数x，存在一个更大的实数y。”符号化为：("x)(R(x)→($y)(R(y)∧G(y,x)))
(4) 存在实数x，y和z，使得x与y之和大于x与z之积。
解：设R(x)：x是实数。G(x,y)：x比y大。
“存在实数x，y和z，使得x与y之和大于x与z之积。”符号化为：
($x)($y)($z)(R(x)∧R(y)∧R(z)∧G(x+y,xz))
(5) 所有的人都不一样高。
解：设R(x)：x是人。G(x,y)：x和y一样高。
“所有的人都不一样高。”符号化为：("x)("y)(R(x)∧R(y)→?G(x,y))
5. 自然数一共有下述三条公理：
a) 每个数都有惟一的一个数是它的后继数。
b) 没有一个数使数1是它的后继数。
c) 每个不等于1的数都有惟一的一个数是它的直接先驱数。
用两个谓词表达上述三条公理。
注：设n是不等于1的自然数，则n＋1是n的后继数，n－1是n的先驱数。
解：设A(x)：x是数。B(x,y)：x是y后继数(根据定义，也可理解为y是x先驱数)。
a) “每个数都有惟一的一个数是它的后继数。”符号化为：
("x)(A(x)→($y)(A(y)∧B(y,x))∧(($z)(A(z)∧B(z,x))→(z=y)))
b) “没有一个数使数1是它的后继数。”符号化为：?($x)(A(x)∧B(1,x))
c) “每个不等于1的数都有惟一的一个数是它的直接先驱数。”符号化为：
("x)(A(x)∧?(x=1)→($y)(A(y)∧B(x,y))∧(($z)(A(z)∧B(x,z))→(z=y)))
6. 取个体域为实数集R，函数f在a点连续的定义是：对每个ε＞0，存在一个δ＞0，使得对
所有
x，若|x－a|＜δ，则|f(x)－f(a)|＜ε。试把此定义用符号化的形式表达出来。
解：("ε) ((ε＞0)→(δ)( (δ＞0)∧("x) ((|x－a|＜δ)→(|f(x)－f(a)|＜ε))))
7.若定义惟一性量词($!x)为“存在惟一的一个x”，则($!x)P(x)表示“存在惟一的一个x使P(x)为真”。试用量词，谓词及逻辑运算符表示($!x)P(x)。
解：($!x)P(x)($x)P(x)∧(($y)P(y)→(y=x))
习题2.3
1. 设个体域为D=í1,2,3y，试消去下列各式的量词。
(1) ("x)P(x)
解：("x)P(x)P(1)∧P(2)∧P(3)
(2) ("x)P(x)→($y)Q(y)
解：("x)P(x)→($y)Q(y)(P(1)∧P(2)∧P(3))→(Q(1)∨Q(2)∨Q(3))
(3) ("x)P(x)∨($y)Q(y)
解：("x)P(x)∨($y)Q(y)(P(1)∧P(2)∧P(3))∨(Q(1)∨Q(2)∨Q(3))
(4) ("x)(P(x)?Q(x))
解：("x)(P(x)?Q(x))(P(1)?Q(1))∧(P(2)?Q(2))∧(P(3)?Q(3))
(5) ("x)?P(x)∨("y)Q(y)
解：("x)?P(x)∨("y)Q(y) (?P(1)∧?P(2)∧?P(3))∨(Q(1)∧Q(2)∧Q(3))
2. 求下列各式的真值。
(1) ("x)($y)H(x,y) 其中H(x,y)：x＞y，个体域为D=í4,2y
解：("x)($y)H(x,y)($y)H(2,y)∧($y)H(4,y)
(H(2,2)∨H(2,4))∧(H(4,2)∨H(4,4))
(0∨0)∧(1∨0)0∧10
(2) ($x)(S(x)→Q(a))∧p其中S(x)：x＞3，Q(x)：x=5，a：3，p：5＞3，个体域为D=í-1,3,6y
解：($x)(S(x)→Q(a))∧p((S(-1)→Q(3))∨(S(3)→Q(3))∨(S(6)→Q(3)))∧(5＞3)
((0→0)∨(0→0)∨(1→0))∧1
(1∨1∨0)∧11∧11
(3) ($x)(x2-2x+1=0) 其中个体域为D=í-1,2y
解：($x)(x2-2x+1=0)(((－1)2－2×(－1)＋1=0)∨(22－2×2＋1=0)
((4=0)∨(1=0)0∨00
3. 证明下列各式。其中：B是不含变元x的谓词公式。
(1) ($x)(S(x)→R(x))?("x)S(x)→($x)R(x)
证明：($x)(S(x)→R(x))?($x)(?S(x)∨R(x))
?($x)?S(x)∨($x)R(x)
??("x)S(x)∨($x R(x)
?("x)S(x)→($x)R(x)
(2) ("x)("y)(S(x)→R(y))?($x)S(x)→("y)R(y)
证明：("x)("y)(S(x)→R(y))?("x)("y)(?S(x)∨R(y))
?("x)?S(x)∨("y)R(y)
??($x)S(x)∨("y)R(y)
?($x)S(x)→("y)R(y)
(3) ($x)(A(x)→B)?("x)A(x)→B
证明：($x)(A(x)→B)?($x)(?A(x)∨B)?($x)?A(x)∨B
??("x)A(x)∨B?("x)A(x)→B
(4) ("x)(B→A(x))?B→("x)A(x)
证明：("x)(B→A(x))?("x)(?B∨A(x))??B∨("x)A(x)?B→("x)A(x)
(5) ("x)(A(x)→B(x))T("x)A(x)→("x)B(x)
证明：因为("x)(A(x)→B(x))，所以对于任意个体c，A(c)→B(c)和A(c)，从而有B(c)，由c的任意性有("x)B(x)，根据CP规则，("x)(A(x)→B(x))T("x)A(x)→("x)B(x)
(6) ("x)(A(x)?B(x))T("x)A(x)?("x)B(x)
证明：("x)(A(x)?B(x))?("x)((A(x)→B(x))∧(B(x)→A(x)))
?("x)(A(x)→B(x))∧("x)(B(x)→A(x))
("x)(A(x)→B(x))∧("x)(B(x)→A(x))T("x)(A(x)→B(x))T("x)A(x)→("x)B(x)同理，("x)(A(x)→B(x))∧("x)(B(x)→A(x))T("x)B(x)→("x)A(x)
所以，("x)(A(x)→B(x))∧("x)(B(x)→A(x))T(("x)A(x)→("x)B(x))∧(("x)B(x)→("x)A(x))
而(("x)A(x)→("x)B(x))∧(("x)B(x)→("x)A(x))?("x)A(x)?("x)B(x)
故有("x)(A(x)?B(x))T("x)A(x)?("x)B(x)
4. 判断下列证明是否正确。
("x) (A(x)→B(x))?("x) (?A(x)∨B(x))?("x)?(A(x)∧?B(x))
??($x) (A(x)∧?B(x))??(($x) A(x)∧($x)?B(x))
??(($x) A(x)∧?("x)B(x))??($x) A(x)∨("x)B(x))
?($x) A(x)→("x)B(x))
解：下列的推理是错的：?($x) (A(x)∧?B(x))??(($x)A(x)∧($x)?B(x))
习题2.4
1. 求下列各式的前束范式。
(1) ("x)P(x)∧($x)Q(x)
解：("x)P(x)∧($x)Q(x)?("x)P(x)∧("x)Q(x)?("x)(P(x)∧Q(x))
(2) ("x)P(x)∨($x)Q(x)
解：("x)P(x)∨($x)Q(x)?("x)P(x)∨("x)Q(x)
?("x)P(x)∨("y)Q(y)
?("x)("y) (P(x)∧Q(y))
(3) ("x)("y)((($z)A(x,y,z)∧($u)B(x,u))→($v)B(x,v))
解：("x)("y)((($z)A(x,y,z)∧($u)B(x,u))→($v)B(x,v))
?("x)("y)(($z)($u)(A(x,y,z)∧B(x,u))→($v)B(x,v))
?("x)("y)("z)("u)($v)((A(x,y,z)∧B(x,u))→B(x,v))
(4) ("x)("y)(($z)(A(x,z)∧B(x,z))→($u)R(x,y,u))
解：("x)("y)(($z)(A(x,z)∧B(x,z))→($u)R(x,y,u))
?("x)("y)("z)($u)((A(x,z)∧B(x,z))→R(x,y,u))
(5) ("x)(($y)A(x,y)→($x)("y)(B(x,y)∧("y)(A(y, x)→B(x,y))))
解：("x)(($y)A(x,y)→($x)("y)(B(x,y)∧("y)(A(y, x)→B(x,y))))
?("x)(($y)A(x,y)→($x)("y)(B(x,y)∧("z)(A(z,x)→B(x,z))))
?("x)(($y)A(x,y)→($u)("v)("z)(B(u,v)∧(A(z,u)→B(u,z))))
?("x)("y)($u)("v)("z)(A(x,y)→(B(u,v)∧(A(z,u)→B(u,z))))
?($x)($y)("u)($v)($z)(A(x,y)→(B(u,v)∧(A(z,u)→B(u,z)))) 2. 求下列各式的前束合取范式。
(1) ("x)(P(x)∨("z)Q(z,y)→("y)R(x,y))
解：("x)(P(x)∨("z)Q(z,y)→("y)R(x,y))
?("x)(("z)(P(x)∨Q(z,y))→($y)R(x,y))
?("x)(("z)(P(x)∨Q(z,y))→($u)R(x,u))
?("x)($z)($u)((P(x)∨Q(z,y))→R(x,u))
?("x)($z)($u)((P(x)∨Q(z,y))∨R(x,u))
?("x)($z)($u)((P(x)∧?Q(z,y))∨R(x,u))
?("x)($z)($u)((P(x)∨R(x,u))∧(?Q(z,y))∨R(x,u))) (2) (x)(y)(P(x,y)∧Q(y,z))∨(x) R(x,y)
解：(x)(y)(P(x,y)∧Q(y,z))∨(x) R(x,y)
?(x)(u)(P(x,u)∧Q(u,z))∨(v)R(v,y)
?(x)(u)(v)((P(x,u)∧Q(u,z))∨R(v,y))
?(x)(u)(v)((P(x,u)∨R(v,y))∧(Q(u,z))∨R(v,y))) (3) (($y)Q(z,y)→("x)R(x,y))∨($x)S(x,y,z)
解：(($y)Q(z,y)→("x)R(x,y))∨($x)S(x,y,z)
?(($u)Q(z,u)→("x)R(x,y))∨($v)S(v,y,z)
?("u)("x)($v)((Q(z,u)→R(x,y))∨S(v,y,z))
?("u)("x)($v)(Q(z,u)∨R(x,y)∨S(v,y,z))
3. 求下列各式的前束析取范式。
(1) ("x)(P(x)→("y)(("x)Q(x,y)→("z)R(x,y,z)))
解：("x)(P(x)→("y)(("x)Q(x,y)→("z)R(x,y,z)))
?("x)(P(x)→("y)(("x)Q(x,y)→($z)R(x,y,z)))
?("x)(P(x)→("y)($u)($z)(Q(u,y)→R(x,y,z)))
?("x)("y)($u)($z)(P(x)→(Q(u,y)→R(x,y,z)))
?("x)("y)($u)($z)(P(x)∨?Q(u,y)∨R(x,y,z))
(2) (x)(y)(P(x,y)∨Q(y,z))∧(x)R(x,y)
解：(x)(y)(P(x,y)∨Q(y,z))∧(x)R(x,y)
?(x)(u)(P(x,u)∨Q(u,z))∧(v)R(v,y)
?(x)(u)(v)((P(x,u)∨Q(u,z))∧R(v,y))
?(x)(u)(v)((P(x,u)∧R(v,y))∨(Q(u,z))∧R(v,y))) (3) (($y)Q(z,y)∧("x)R(x,y))∨($x)S(x,y,z)
解：(($y)Q(z,y)∧("x)R(x,y))∨($x)S(x,y,z)
?(($u)Q(z,u)∧("x)R(x,y))∨($x)S(x,y,z)
?($u)("x)(Q(z,u)∧R(x,y))∨($x)S(x,y,z)
?($u)("x)(Q(z,u)∧R(x,y))∨($v)S(v,y,z)
?($u)("x)($v)((Q(z,u)∧R(x,y))∨S(v,y,z))
习题2.5
1．证明下列各式。
(1) ("x)(F(x)→(G(y)∧R(x)))，($x)F(x)T($x)(F(x)∧R(x))
证明：
⑴($x)F(x) P
⑵F(c) ES⑴
⑶("x)(F(x)→(G(y)∧R(x))) P
⑷F(c)→(G(y)∧R(c)) US⑶
⑸G(y)∧R(c) T⑵⑷假言推理
⑹R(c) T⑸化简律
⑺F(c)∧R(c) T⑵⑹合取引入
⑻($x)(F(x)∧R(x)) EG⑺
(2) ("x)(F(x)→G(x))，("x)(R(x)→?G(x))T("x)(R(x)→? F(x))
证明：⑴("x)(R(x)→?G(x)) P
⑵R(c)→?G(c) US⑴
⑶("x)(F(x)→G(x)) P
⑷F(c)→G(c) US⑶
⑸?G(c)→?F(c) T⑷假言易位式
⑹R(c)→?F(c) T⑵⑸假言三段论
⑺("x)(R(x)→?F(x)) UG⑹
(3) ("x)(F(x)∨G(x))，("x)(G(x)→?R (x))，("x)R(x)T("x)F(x)
证明：
⑴("x)R(x) P
⑵R(c) US⑴
⑶("x)(G(x)→?R(x)) P
⑷G(c)→?R(c) US⑶
⑸?G(c) T⑵⑷拒取式
⑹("x)(F(x)∨G(x)) P
⑺F(c)∨G(c) US⑹
⑻F(c) T⑸⑺析取三段论
⑼("x)F(x) UG⑻
(4) ($x)F(x)→("y)((F(y)∨G(y))→R(y))，($x)F(x)T($x)R(x)
证明：
⑴($x)F(x) P
⑵F(c) ES⑴
⑶($x)F(x)→("y)((F(y)∨G(y))→R(y)) P
⑷("y)((F(y)∨G(y))→R(y)) T⑴⑶假言推理
⑸(F(c)∨G(c))→R(c) US⑷
⑹F(c)∨G(c) T⑵附加律
⑺R(c) T⑸⑹假言推理
⑻("x)R(x) UG⑺
2．用CP规则证明下列各式。
(1) ("x)(F(x)→R(x))T("x)F(x)→("x)R(x)
证明：
⑴("x)F(x) P(附加前提)
⑵F(c) US⑴
⑶("x)(F(x)→R(x)) P
⑷F(c)→R(c) US⑶
⑸R(c) T⑵⑷假言推理
⑹("x)R(x) UG⑸
⑺("x)F(x)→("x)R(x) CP
(2) ("x)(F(x)∨G(x))，?($x)(G(x)∧R(x))T("x)R(x)→("x)F(x)
证明：
⑴("x)R(x) P(附加前提)
⑵R(c) US⑴
⑶?($x)(G(x)∧R(x)) P
⑷("x)?(G(x)∧R(x)) T⑶量词否定等价式
⑸?(G(c)∧R(c)) US⑷
⑹?G(c)∨?R(c) T⑸德摩根律
⑺?G(c) T⑵⑹析取三段论
⑻("x)(F(x)∨G(x)) P
⑼F(c)∨G(c) US⑻
⑽F(c) T⑺⑼析取三段论
⑾("x)F(x) UG⑽
⑿("x)R(x)→("x)F(x) CP
(3) ("x)(F(x)→?G(x))，("x)(G(x)∨R(x)) T?("x)R(x)→($x)?F(x)
证明：
⑴?("x)R(x) P(附加前提)
⑵($x)?R(x) T⑴量词否定等价式
⑶?R(c) ES⑵
⑷("x)(G(x)∨R(x)) P
⑸G(c)∨R(c) US⑷
⑹G(c) T⑶⑸析取三段论
⑺("x)(F(x)→?G(x)) P
⑻F(c)→?G(c) US⑺
⑼?F(c) T⑹⑻拒取式
⑽($x)?F(x) EG⑼
⑾?("x)R(x)→($x)?F(x) CP
3．用归谬法证明下列各式。
(1) ("x)(F(x)∨G(x))T("x)F(x)∨($x)G (x)
证明：
⑴?(("x)F(x)∨($x)G (x)) P(附加前提)
⑵?("x)F(x)∧?($x)G (x)) T⑴德摩根律
⑶($x)?F(x)∧("x)?G (x)) T⑵量词否定等价式
⑷($x)?F(x) T⑶化简律
⑸?F(c) ES⑷
⑹("x)?G(x)) T⑶化简律
⑺?G(c) US⑹
⑻("x)(F(x)∨G(x)) P
⑼F(c)∨G(c) US⑻
⑽F(c) T⑺⑼析取三段论
⑾F(c)∧?F(c)(矛盾) T⑸⑽合取引入(2) ("x)(F(x)∨G(x))，("x)(G(x)→?R (x))，("x)R(x)T("x)F(x)
证明：
⑴?("x)F(x) P(附加前提)
⑵($x)?F(x) T⑴量词否定等价式
⑶?F(c) ES⑵
⑷("x)(F(x)∨G(x)) P
⑸F(c)∨G(c) US⑷
⑹G(c) T⑶⑸析取三段论
⑺("x)(G(x)→?R(x)) P
⑻G(c)→?R(c) US⑺
⑼?R(c) T⑹⑻假言推理
⑽("x)R(x) P
⑾R(c) US⑽
⑿R(c)∧?R(c)(矛盾) T⑼⑾合取引入(3) ("x)(F(x)→?G(x))，("x)(G(x)∨R(x))，($x)?R(x) T($x)?F(x)证明：
⑴($x)?R(x) P
⑵?R(c) ES⑴
⑶?($x)?F(x) P(附加前提)
⑷("x)F(x) T⑶量词否定等价式
⑸F(c) US⑷
⑹("x)(F(x)→?G(x)) P
⑺F(c)→?G(c) US⑹
⑻?G(c) T⑸⑺假言推理
⑼("x)(G(x)∨R(x)) P
⑽G(c)∨R(c) US⑼
⑾R(c) T⑻⑽析取三段论
⑿R(c)∧?R(c)(矛盾) T⑵⑾合取引入
4．证明下面推理。
(1) 每个有理数都是实数。有的有理数是整数。因此，有的实数是整数。
解：首先将命题符号化：
Q(x)：x是有理数。R(x)：x是实数。
Z(x)：x是整数。
本题要证明：(x)(Q(x)→R(x)), (x)(Q(x)∧Z(x))(x)(R(x)∧Z(x))
证明：
⑴(x)(Q(x)∧Z(x)) P
⑵Q(c)∧Z(c) ES⑴
⑶Q(c) T⑵化简律
⑷Z(c) T⑵化简律
⑸(x)(Q(x)→R(x)) P
⑹Q(c)→R(c) US⑸
⑺R(c) T⑶⑹假言推理
⑻R(c)∧Z(c) T⑷⑺合取引入
⑼($x)(R(x)∧Z(x)) EG⑻
(2) 有理数，无理数都是实数。虚数不是实数。因此，虚数既不是有理数，也不是无理数。解：首先将命题符号化：
Q(x)：x是有理数。R(x)：x是实数。
W(x)：x是无理数。X(x)：x是虚数。
本题要证明：(x)(Q(x)→R(x)), (x)(W(x)→R(x))，("x)(X(x)→?R(x))
("x)(X(x)→?Q(x))∧("x)(X(x)→?W(x))
证明：
⑴("x)(X(x)→?R(x)) P
⑵X(c)→?R(c) US⑴
⑶R(c)→?X(c) T⑵假言易位式
⑷(x)(W(x)→R(x)) P
⑸W(c)→R(c) US⑷
⑹W(c)→?X(c) T⑶⑸假言三段论
⑺X(c)→?W(c) T⑹假言易位式
⑻(x)(X(c)→?W(c)) UG⑺
⑼(x)(Q(x)→R(x)) P
⑽Q(c)→R(c) US⑼
第二次在线作业 1.（ 2.5分）代数系统是指由集合及其上的一元或二元运算符组成的系统 ?正确 ?错误 我的答案：正确此题得分：2.5分 2.（2.5分）设< L*1*2> 是代数系统，其中是*1*2二元运算符，如果*1*2都满足交换律、结合律，并且*1和*2满足吸收律，则称< L*1*2> 是格 ?正确 ?错误 我的答案：正确此题得分：2.5分 3.（2.5分）对实数的普通加法和乘法，0是加法的幂等元，1是乘法的幂等元 ?正确 ?错误 我的答案：正确此题得分：2.5分 4.（2.5分）零元是不可逆的 ?正确 ?错误 我的答案：正确此题得分：2.5分 5.（2.5分）群中每个元素的逆元都是惟一的 ?正确 ?错误 我的答案：正确此题得分：2.5分
6.（2.5分）设abc是阿贝尔群< G+> 的元素，则-(a+b+c)=(-a)+( -b)+( -c) ?正确 ?错误 我的答案：正确此题得分：2.5分 7.（2.5分） < {01234}MAXMIN> 是格 ?正确 ?错误 我的答案：正确此题得分：2.5分 8.（2.5分）一个图的哈密尔顿路是一条通过图中所有结点一次且恰好一次的路 ?正确 ?错误 我的答案：正确此题得分：2.5分 9.（2.5分）在有向图中，结点v的出度deg+(v)表示以v为起点的边的条数，入度deg-(v)表示以v为终点的边的条数 ?正确 ?错误 我的答案：正确此题得分：2.5分 10.（2.5分）一个图的欧拉回路是一条通过图中所有边一次且恰好一次的回路 ?正确 ?错误 我的答案：正确此题得分：2.5分
11.（2.5分）不含回路的连通图是树 ?正确 ?错误 我的答案：正确此题得分：2.5分 12.（2.5分）简单图邻接矩阵主对角线上的元素全为0 ?正确 ?错误 我的答案：正确此题得分：2.5分 13.（2.5分）树一定是连通图 ?正确 ?错误 我的答案：正确此题得分：2.5分 14.（2.5分）无向图的邻接矩阵是对称阵 ?正确 ?错误 我的答案：正确此题得分：2.5分 15.（2.5分）不与任何结点相邻接的结点称为孤立结点 ?正确 ?错误 我的答案：正确此题得分：2.5分
一、 选择题 1．下列四个公式正确的是 ①)()())()((x xB x xA x B x A x ?∧??∧? ②)()())()((x xB x xA x B x A x ?∨??∨? ③)()())()((x xB x xA x B x A x ?∨??∨? ④))()(()()(x B x A x x xB x xA ∧???∧? A.①③ B.①④ C.③④ D.②④ 2. 谓词公式)())()((x Q y yR x P x →?∨?中量词?x 的辖域是( ) (A) ))()((y yR x P x ?∨? (B) P (x ) (C ) )()(y yR x P ?∨ (D) )(x Q 3. 谓词公式))()(()(x xQ x Q x x xP ??→??→?的类型是（ ） (A ) 永真式 (B) 矛盾式 (C) 非永真式的可满足式 (D) 蕴涵式 4. 设个体域为整数集，下列公式中其真值为1的是( ) (A ) )0(=+??y x y x (B) )0(=+??y x x y (C))0(=+??y x y x (D) )0(=+???y x y x 5. 设个体域{,}A a b =，公式()()xP x xS x ?∧?在中消去量词后应为 ( ) (A) ()()P x S x ∧ (B ) ()()(()())P a P b S a S b ∧∧∨ (C) ()()P a S b ∧ (D) ()()()()P a P b S a S b ∧∧∨ 6. 在谓词演算中，下列各式正确的是( ) (A) (,)(,)x yA x y y xA x y ????? (B ) (,)(,)x yA x y y xA x y ????? (C) (,)(,)x yA x y x yA x y ????? (D) (,)(,)x yA x y y xA x y ????? 7.下列各式不正确的是( ) (A ) (()())()()x P x Q x xP x xQ x ?∨??∨? (B) (()())()()x P x Q x xP x xQ x ?∧??∧? (C) (()())()()x P x Q x xP x xQ x ?∨??∨? (D) (())()x P x Q xP x Q ?∧??∧
一、填空题 1. 设A = {1, 2}, B = {2, 3}, 则A - A =________, A – B =________, B – A =________. 2. 设N 是自然数集合, f 和g 是N 到N 的函数, 且f (n ) = 2n +1，g (n ) = n 2, 那么复合函数(f f ) (n )=________ , (f g ) (n )=________ , (g f ) (n ) =________. 3. 设|X | = n , P (X )为集合X 的幂集, 则| P (X )| = ________. 在代数结构(P (X ), ∪)中，则P (X ) 对∪运算的单位元是________, 零元是________ . 4. 在下图中， _______________________________是其Euler 路 . 5. 设有向图G = (V , E )，V = {v 1，v 2，v 3，v 4}，若G 的邻接矩阵A =???? ??????1001001111011010, 则v 1的出度deg +(v 1) =________, v 1的入度deg -(v 1) =________, 从v 2到v 4长度为2的路有________条. 二、单选题 1. 设A = {{1, 2, 3}, {4, 5}, {6, 7, 8}}, 下列选项正确的是( ) (A) 1∈A (B) {1, 2, 3}?A (C) {{4, 5}}?A (D) ?∈A . 2．集合A = {1, 2, …, 10}上的关系R ={(x , y )|x + y = 10, x , y ∈A }, 则R 的性质是 ( ) (A) 自反的 (B) 对称的 (C) 传递的、对称的 (D) 反自反的、传递的. 3．若R 和S 是集合A 上的两个关系，则下述结论正确的是( ) (A) 若R 和S 是自反的, 则R ∩S 是自反的 (B) 若R 和S 是对称的, 则R S 是对称的 (C) 若R 和S 是反对称的, 则R S 是反对称的 (D) 若R 和S 是传递的, 则R ∪S 是传递的. 4．集合A = {1, 2, 3, 4}上的关系 R = {(1, 4), (2, 3), (3, 1), (4, 3)}, 则下列不是．．t (R )中元素的是( ) (A) (1, 1) (B) (1, 2) (C) (1, 3) (D) (1, 4). 5．设p ：我们划船，q ：我们跑步, 则有命题“我们不能既划船又跑步”符号化为( ) (A) ? p ∧? q (B) ? p ∨? q
命题逻辑的基本概念 一、单项选择题 1．下列语句中不是命题的有（ ）. A 9+5≤12 B. 1+3=5 C. 我用的电脑CPU 主频是1G 吗D.我要努力学习。 2. 下列语句是真命题为( )． A. 1+2=5当且仅当2是偶数 B. 如果1+2=3，则2是奇数 C. 如果1+2=5，则2是奇数 D. 你上网了吗 3. 设命题公式)(r q p ∧→?,则使公式取真值为1的p ，q ，r 赋值分别是 ( ) 0,0,1)D (0 ,1,0)C (1 ,0,0)B (0 ,0,0)A ( 4. 命题公式q q p →∨ )(为 ( ) (A) 矛盾式 (B) 仅可满足式 (C) 重言式 (D) 合取范式 5. 设p:我将去市里,q ：我有时间． 命题“我将去市里，仅当我有时间时”符号化为为( ) q p q p q p p q ?∨??→→)D ()C ()B ()A (6．设P ：我听课,Q ：我看小说. “我不能一边听课，一边看小说”的符号为（ ） A. Q P ?→ ； B. Q P →?； C. P Q ?∧? ； D. )(Q P ∧? 二、判断下列语句是否是命题，若是命题是复合命题则请将其符号化 （1）中国有四大发明。 （2）2是有理数。 （3）“请进！” （4）刘红和魏新是同学。 （5）a+b （6）如果买不到飞机票，我哪儿也不去。 （8）侈而惰者贫，而力而俭者富。（韩非：《韩非子显学》） （9）火星上有生命。 （10）这朵玫瑰花多美丽啊！ 二、将下列命题符号化，其中p:2<1,q:3<2 （1）只要2<1，就有3<2。 （2）如果2<1，则32。 （3）只有2<1，才有32。 （4）除非2<1，才有32。 （5）除非2<1，否则32。
离散数学作业7 离散数学数理逻辑部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求2010年12月19日前完成并上交任课教师（不收电子稿）。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1．命题公式()P Q P →∨的真值是 1 ． 2．设P ：他生病了，Q ：他出差了．R ：我同意他不参加学习. 则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为 (PQ)R ． 3．含有三个命题变项P ，Q ，R 的命题公式PQ 的主析取范式是 (PQR) (PQR) ． 4．设P(x)：x 是人，Q(x)：x 去上课，则命题“有人去上课．” 可符号化为 (x)(P(x) →Q(x)) ． 5．设个体域D ＝{a, b},那么谓词公式)()(y yB x xA ?∨?消去量词后的等值式为 (A(a) A(b)) (B(a) B(b)) ． 6．设个体域D ＝{1, 2, 3}，A(x)为“x 大于3”，则谓词公式(x)A(x) 的真值为 ． 7．谓词命题公式(x)((A(x)B(x)) C(y))中的自由变元为 ． 8．谓词命题公式(x)(P(x) Q(x) R(x ，y))中的约束变元为 X ． 三、公式翻译题 1．请将语句“今天是天晴”翻译成命题公式． 1．解：设P ：今天是天晴； 则 P ． 2．请将语句“小王去旅游，小李也去旅游．”翻译成命题公式． 解：设P ：小王去旅游，Q ：小李去旅游， 则 PQ ． 3．请将语句“如果明天天下雪，那么我就去滑雪”翻译成命题公式． 解：设P:明天天下雪 。 Q:我去滑雪 则 P Q ． 4．请将语句“他去旅游，仅当他有时间．”翻译成命题公式． 7．解：设 P ：他去旅游，Q ：他有时间， 则 P Q ． 5．请将语句 “有人不去工作”翻译成谓词公式． 11．解：设P(x)：x 是人，Q(x)：x 去工作，
离散数学（第五版）清华大学出版社第2章习题解答 2.1 本题没有给出个体域,因而使用全总个体域. (1) 令F(x):x是鸟 G(x):x会飞翔. 命题符号化为 ?x(F(x)→G(x)). (2)令F(x):x为人. G(x):x爱吃糖 命题符号化为 ??x(F(x)→G(x)) 或者 ?x(F(x)∧?G(x)) (3)令F(x):x为人. G(x):x爱看小说. 命题符号化为 ?x(F(x)∧G(x)). (4) F(x):x为人. G(x):x爱看电视. 命题符号化为 ??x(F(x)∧?G(x)). 分析1°如果没指出要求什么样的个体域，就使用全总个休域，使用全总个体域时，往往要使用特性谓词。（1）-（4）中的F(x)都是特性谓词。 2°初学者经常犯的错误是，将类似于（1）中的命题符号化为 27 ?x(F(x)∧G(x)) 即用合取联结词取代蕴含联结词，这是万万不可的。将（1）中命题叙述得更透彻些，是说“对于宇宙间的一切事物百言，如果它是鸟，则它会飞翔。”因而符号化应该使用联结词→而不能使用∧。若使用∧，使（1）中命题变成了“宇宙间的一切事物都是鸟并且都会飞翔。”这显然改变了原命题的意义。
3°（2）与（4）中两种符号化公式是等值的，请读者正确的使用量词否定等值式，证明（2），（4）中两公式各为等值的。 2.2 (1)d (a),(b),(c)中均符号化为 ?xF(x) 其中F(x):(x+1)2=x2+2x+1,此命题在(a),(b),(c)中均为真命题。 （2）在(a),(b),(c)中均符号化为 ?xG(x) 其中G(x):x+2=0，此命题在（a）中为假命题，在(b)(c)中均为真命题。 （3）在(a),(b),(c)中均符号化为 ?xH(x) 其中H(x):5x=1.此命题在(a),(b)中均为假命题，在(c)中为真命题。 分析1°命题的真值与个体域有关。 2°有的命题在不同个体域中，符号化的形式不同，考虑命题 “人都呼吸”。 在个体域为人类集合时，应符号化为 ?xF(x) 这里，F(x):x呼吸，没有引入特性谓词。 在个体域为全总个体域时，应符号化为 ?x(F(x)→G(x)) 这里，F(x):x为人，且F(x)为特性谓词。G(x):x呼吸。 28 2．3 因题目中未给出个体域，因而应采用全总个体域。 （1）令：F(x):x是大学生，G(x):x是文科生，H(x):x是理科生，命题符号化为?x(F(x)→(G(x)∨H(x)) （2）令F(x):x是人，G(y):y是化，H(x):x喜欢，命题符号化为 ?x(F(x)∧?y(G(y)→H(x,y))) （3）令F(x):x是人，G(x):x犯错误，命题符号化为 ??x(F(x)∧?G(x)), 或另一种等值的形式为 ?x(F(x)→G(x)
2013年4月考试离散数学第二次作业 一、单项选择题（本大题共50分，共 25 小题，每小题 2 分） 1. 下列语句中为命题的是（） A. 暮春三月，江南草长. B. 这是多么可爱的风景啊！ C. 大家想做什么，就做什么，行吗？ D. 请勿践踏草地！ 2. 2.设G是n个顶点的无向简单图，则下列说法不正确的是（） A. 若G是树，则其边数等于n-1 B. 若G是欧拉图，则G中必有割边 C. 若G中有欧拉路，则G是连通图，且有零个或两个奇度数顶点 D. 若G中任意一对顶点的度数之和大于等于n-1，则G中有汉密尔顿路 3. 集合|A|=3，|B|=2，则A B上不同的函数个数为（）。 A. 3+2个 B. 32个 C. 2*3个 D. 23个 4. 设A-B=φ，则以下正确的是（）。 A. A＝B B. A?B C. B?A D. 以上都不对 5. 设R为实数集，函数f：R→R，f(x)=2x，则f是（） A. 满射函数 B. 入射函数 C. 双射函数 D. 非入射非满射 6. 设B={a,b,c},C={1,2,3,4}，以下哪个关系是从B到C的单射函数？（） A. f={<1,8>,<3,9>,<4,10>,<2,6>,<5,7>} B. f={<1,7>,<2,6>,<4,8>,<1,9>,<5,10>} C. f={<1,7>,<2,7>,<4,9>,<3,8>} D. f={<1,10>,<5,9>,<3,6>,<4,6>,<2,8>} E. f={<1,7>,<5,10>,<2,6>,<4,8>,<3,9>} 7. 下述*运算为实数集上的运算，其中可交换且可结合的运算是（）。 A. a*b=a+2b B. a*b=a+b-ab C. a*b=a D. a*b=|a+b| 8. 在下列命题中，为真的命题是（） A. 汉密顿图一定是欧拉图 B. 无向完全图都是欧拉图 C. 度数为奇数的结点个数为0个或2个的连通无向图G可以一笔画出 D. 有割点的连通图是汉密顿图 9. 设p:小李努力学习，q:小李取得好成绩，命题“只有小李努力学习，他才能取得好成绩”的符号化形式为（）。 A. B. C.
第2章习题解答 2.1 本题没有给出个体域,因而使用全总个体域. (1) 令x (是鸟 x F:) (会飞翔. G:) x x 命题符号化为 x F ?. G x→ ) ( )) ( (x (2)令x x (为人. F:) (爱吃糖 G:) x x 命题符号化为 x F x→ G ?? )) ( ) ( (x 或者 F x? x ∧ ? ) )) ( ( (x G (3)令x x (为人. F:) G:) (爱看小说. x x 命题符号化为 x F ?. G x∧ (x ( )) ( ) (4) x (为人. x F:) (爱看电视. G:) x x 命题符号化为 F x? ∧ ??. x G ( ) ( )) (x 分析 1°如果没指出要求什么样的个体域，就使用全总个休域，使用全总个体域时，往往要使用特性谓词。（1）-（4）中的) F都是特性谓词。 (x 2°初学者经常犯的错误是，将类似于（1）中的命题符号化为 F x ? G x∧ ( )) ( ) (x
即用合取联结词取代蕴含联结词，这是万万不可的。将（1）中命题叙述得更透彻些，是说“对于宇宙间的一切事物百言，如果它是鸟，则它会飞翔。”因而符号化应该使用联结词→而不能使用∧。若使用∧，使（1）中命题变成了“宇宙间的一切事物都是鸟并且都会飞翔。”这显然改变了原命题的意义。 3° （2）与（4）中两种符号化公式是等值的，请读者正确的使用量词否定等值式，证明（2），（4）中两公式各为等值的。 2.2 (1)d (a),(b),(c)中均符号化为 )(x xF ? 其中,12)1(:)(22++=+x x x x F 此命题在)(),(),(c b a 中均为真命题。 （2） 在)(),(),(c b a 中均符号化为 )(x xG ? 其中02:)(=+x x G ，此命题在（a ）中为假命题，在(b)(c)中均为真命题。 （3）在)(),(),(c b a 中均符号化为 )(x xH ? 其中.15:)(=x x H 此命题在)(),(b a 中均为假命题，在(c)中为真命题。 分析 1°命题的真值与个体域有关。 2° 有的命题在不同个体域中，符号化的形式不同，考虑命题 “人都呼吸”。 在个体域为人类集合时，应符号化为 )(x xF ? 这里，x x F :)(呼吸，没有引入特性谓词。 在个体域为全总个体域时，应符号化为 ))()((x G x F x →? 这里，x x F :)(为人，且)(x F 为特性谓词。x x G :)(呼吸。 2．3 因题目中未给出个体域，因而应采用全总个体域。
习题 1. 下列句子中，哪些是命题哪些不是命题如果是命题，指出它的真值。 ⑴中国有四大发明。 ⑵计算机有空吗 ⑶不存在最大素数。 ⑷21+3＜5。 ⑸老王是山东人或河北人。 ⑹2与3都是偶数。 ⑺小李在宿舍里。 ⑻这朵玫瑰花多美丽呀! ⑼请勿随地吐痰! ⑽圆的面积等于半径的平方乘以。 ⑾只有6是偶数，3才能是2的倍数。 ⑿雪是黑色的当且仅当太阳从东方升起。 ⒀如果天下大雨，他就乘班车上班。 解：⑴⑶⑷⑸⑹⑺⑽⑾⑿⒀是命题，其中⑴⑶⑽⑾是真命题，⑷⑹⑿是假命题，⑸⑺⒀的真值目前无法确定；⑵⑻⑼不是命题。 2. 将下列复合命题分成若干原子命题。 ⑴李辛与李末是兄弟。 ⑵因为天气冷，所以我穿了羽绒服。 ⑶天正在下雨或湿度很高。 ⑷刘英与李进上山。 ⑸王强与刘威都学过法语。 ⑹如果你不看电影，那么我也不看电影。 ⑺我既不看电视也不外出，我在睡觉。 ⑻除非天下大雨，否则他不乘班车上班。 解：⑴本命题为原子命题； ⑵p：天气冷；q：我穿羽绒服； ⑶p：天在下雨；q：湿度很高； ⑷p：刘英上山；q：李进上山； ⑸p：王强学过法语；q：刘威学过法语； ⑹p：你看电影；q：我看电影； ⑺p：我看电视；q：我外出；r：我睡觉； ⑻p：天下大雨；q：他乘班车上班。 3. 将下列命题符号化。 ⑴他一面吃饭，一面听音乐。 ⑵3是素数或2是素数。 ⑶若地球上没有树木，则人类不能生存。
⑷8是偶数的充分必要条件是8能被3整除。 ⑸停机的原因在于语法错误或程序错误。 ⑹四边形ABCD是平行四边形当且仅当它的对边平行。 ⑺如果a和b是偶数，则a+b是偶数。 解：⑴p：他吃饭；q：他听音乐；原命题符号化为：p∧q ⑵p：3是素数；q：2是素数；原命题符号化为：p∨q ⑶p：地球上有树木；q：人类能生存；原命题符号化为：p→q ⑷p：8是偶数；q：8能被3整除；原命题符号化为：pq ⑸p：停机；q：语法错误；r：程序错误；原命题符号化为：q∨r→p ⑹p：四边形ABCD是平行四边形；q：四边形ABCD的对边平行；原命题符号化为：pq。 ⑺p：a是偶数；q：b是偶数；r：a+b是偶数；原命题符号化为：p∧q→r 4. 将下列命题符号化，并指出各复合命题的真值。 ⑴如果3+3=6，则雪是白的。 ⑵如果3+3≠6，则雪是白的。 ⑶如果3+3=6，则雪不是白的。 ⑷如果3+3≠6，则雪不是白的。 ⑸3是无理数当且仅当加拿大位于亚洲。 ⑹2+3=5的充要条件是3是无理数。(假定是10进制) ⑺若两圆O1，O2的面积相等，则它们的半径相等，反之亦然。 ⑻当王小红心情愉快时，她就唱歌，反之，当她唱歌时，一定心情愉快。 解：设p：3＋3＝6。q：雪是白的。 ⑴原命题符号化为：p→q；该命题是真命题。 ⑵原命题符号化为：p→q；该命题是真命题。 ⑶原命题符号化为：p→q；该命题是假命题。 ⑷原命题符号化为：p→q；该命题是真命题。 ⑸p：3是无理数；q：加拿大位于亚洲；原命题符号化为：pq；该命题是假命题。 ⑹p：2+3＝5；q：3是无理数；原命题符号化为：pq；该命题是真命题。 ⑺p：两圆O1,O2的面积相等；q：两圆O1,O2的半径相等；原命题符号化为：pq；该命题是真命题。 ⑻p：王小红心情愉快；q：王小红唱歌；原命题符号化为：pq；该命题是真命题。 习题
------------------------------------------------------------------------------------------------------------------------------ 1.（2.5分）代数系统是指由集合及其上的一元或二元运算符组成的系统 正确 错误 正确答案： 2.（2.5分）设< L,*1,*2> 是代数系统，其中是*1,*2二元运算符，如果*1,*2都满足交换律、结合律，并且*1和*2满足吸收律，则称< L,*1,*2> 是格 正确 错误 正确答案： 3.（2.5分）对实数的普通加法和乘法，0是加法的幂等元，1是乘法的幂等元 正确 错误 正确答案： 4.（2.5分）零元是不可逆的 正确 错误 正确答案： 5.（2.5分）群中每个元素的逆元都是惟一的 正确 错误 正确答案： 6.（2.5分）设a,b,c是阿贝尔群< G,+> 的元素，则-(a+b+c)=(-a)+( -b)+( -c) 正确 错误 正确答案： 7.（2.5分） < {0,1,2,3,4},MAX,MIN> 是格 正确 错误 正确答案： 8.（2.5分）一个图的哈密尔顿路是一条通过图中所有结点一次且恰好一次的路 正确 错误 正确答案： 9.（2.5分）在有向图中，结点v的出度deg+(v)表示以v为起点的边的条数，入度deg-(v)表示以v为终点的边的条数 正确 错误 正确答案： 10.（2.5分）一个图的欧拉回路是一条通过图中所有边一次且恰好一次的回路 正确 错误 正确答案： 11.（2.5分）不含回路的连通图是树
离散数学作业7 离散数学数理逻辑部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求本学期第17周末前完成并上交任课教师（不收电子稿）。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1．命题公式()P Q P →∨的真值是 1或T ． 2．设P ：他生病了，Q ：他出差了．R ：我同意他不参加学习. 则命题“如 果他生病或出差了，我就同意他不参加学习”符号化的结果为 （P ∨Q ）→R ． 3．含有三个命题变项P ，Q ，R 的命题公式P ∧Q 的主析取范式是 (P ∧Q ∧R)∨(P ∧Q ∧?R) ． 4．设P (x )：x 是人，Q (x )：x 去上课，则命题“有人去上课．” 可符号化为 ?x(P(x) ∧Q(x)) ． 5．设个体域D ＝{a , b },那么谓词公式)()(y yB x xA ?∨?消去量词后的等值式为 (A(a) ∨A(b)) ∨((B(a) ∧B(b)) ． 6．设个体域D ＝{1, 2, 3}，A (x )为“x 大于3”，则谓词公式(?x )A (x ) 的真值为 0(F) ． 7．谓词命题公式(?x )((A (x )∧B (x )) ∨C (y ))中的自由变元为 y ． 8．谓词命题公式(?x )(P (x ) →Q (x ) ∨R (x ，y ))中的约束变元为 x ． 三、公式翻译题 1．请将语句“今天是天晴”翻译成命题公式． 设P ：今天是晴天。 姓 名： 学 号： 得 分： 教师签名：
离散数学练习题 第一章 一?填空 1?公式(p q) ( p q)的成真赋值为01; 10 2?设p, r为真命题，q, s为假命题，则复合命题(p q) ( r s)的真值为0 3?公式(p q)与(p q) ( p q)共同的成真赋值为01 ；10 4?设A为任意的公式，B为重言式，则A B的类型为重言式 5. 设p, q均为命题，在不能同时为真条件下，p与q的排斥也可以写成p与q的相容或。 二.将下列命题符合化 1. ■ 7不是无理数是不对的。 解：(p)，其中p：. 7是无理数；或p,其中p: . 7是无理数。 2?小刘既不怕吃苦，又很爱钻研。 解：p q,其中p:小刘怕吃苦，q :小刘很爱钻研 3?只有不怕困难，才能战胜困难。 解：q p，其中p:怕困难，q:战胜困难 或p q，其中p:怕困难，q:战胜困难 4?只要别人有困难，老王就帮助别人，除非困难解决了。 解：r (p q)，其中p:别人有困难，q:老王帮助别人，r:困难解决了 或：(r p) q，其中p：别人有困难，q:老王帮助别人，r:困难解决了 5?整数n是整数当且仅当n能被2整除。 解：p q，其中p:整数n是偶数，q:整数n能被2整除 三、求复合命题的真值 P：2能整除5, q：旧金山是美国的首都，r：在中国一年分四季
1. ((p q) r) (r (p q)) 2?((q p) (r p)) (( p q) r 解：p, q为假命题，r为真命题 1. (( p q) r) (r (p q))的真值为0 2. (( q p) (r p)) (( p q) r 的真值为1 四、判断推理是否正确 设y 2x为实数，推理如下： 若y在x=0可导，则y在x=0连续。y在x=0连续，所以y在x=0可导。 解：y 2x，x为实数，令p: y在x =0可导，q: y在x=0连续。P为假命题，q为真命题，推理符号化为：(p q) q p，由p, q得真值可知，推理的真值为0,所以推理不正确。 五、判断公式的类型 1，( (q p) ((p q) ( p q))) r 2. (p (q p)) (r q) 3. (p r) (q r)
离散数学作业布置 第1次作业（P15） 1.16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 解：（1）p∨(q∧r)=0∨(0∧1)=0 （2）（p?r）∧(﹁q∨s)=（0?1）∧(1∨1)=0∧1 =0 （3）（﹁p∧﹁q∧r）?(p∧q∧﹁r)=（1∧1∧1）? (0∧0∧0)=0 (4)（r∧s）→(p∧q)=（0∧1）→(1∧0)=0→0=1 1.17 判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2 也是无理数。另外只有6能被2整除，6才能被4整除。” 解：p: π是无理数 1 q: 3是无理数0 r: 2是无理数 1 s:6能被2整除 1 t: 6能被4整除0 命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。 1.19 用真值表判断下列公式的类型： （4）(p→q) →(﹁q→﹁p) （5）(p∧r) ? (﹁p∧﹁q) （6）((p→q) ∧(q→r)) →(p→r) 解：（4） p q p→q q p q→p (p→q)→( q→p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式，最后一列全为1 （5）公式类型为可满足式（方法如上例），最后一列至少有一个1 （6）公式类型为永真式（方法如上例，最后一列全为1）。 第2次作业（P38） 2.3 用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ﹁(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 解：(1) ﹁(p∧q→q) ?﹁(﹁(p∧q) ∨q) ?(p∧q) ∧﹁q?p∧(q ∧﹁q) ? p∧0 ?0 所以公式类型为矛盾式 (2)（p→(p∨q)）∨(p→r) ? (﹁p∨(p∨q))∨(﹁p∨r) ?﹁p∨p∨q∨r?1 所以公式类型为永真式 (3) (p∨q) → (p∧r) ?￢(p∨q) ∨ (p∧r) ? (￢p∧￢q) ∨(p∧r) 易见, 是可满足式, 但不是重言式. 成真赋值为: 000,001, 101, 111
习题 2.1 1．将下列命题符号化。 (1) 4不是奇数。 解：设A(x)：x是奇数。a：4。 “4不是奇数。”符号化为：?A(a) (2) 2是偶数且是质数。 解：设A(x)：x是偶数。B(x)：x是质数。a：2。 “2是偶数且是质数。”符号化为：A(a)∧B(a) (3) 老王是山东人或河北人。 解：设A(x)：x是山东人。B(x)：x是河北人。a：老王。 “老王是山东人或河北人。”符号化为：A(a)∨B(a) (4) 2与3都是偶数。 解：设A(x)：x是偶数。a：2，b：3。 “2与3都是偶数。”符号化为：A(a)∧A(b) (5) 5大于3。 解：设G(x,y)：x大于y。a：5。b：3。 “5大于3。”符号化为：G(a,b) (6) 若m是奇数，则2m不是奇数。 解：设A(x)：x是奇数。a：m。b：2m。 “若m是奇数，则2m不是奇数。”符号化为：A(a)→A(b) (7) 直线A平行于直线B当且仅当直线A不相交于直线B。 解：设C(x,y)：直线x平行于直线y。设D(x,y)：直线x相交于直线y。a：直线A。b：直线B。 “直线A平行于直线B当且仅当直线A不相交于直线B。”符号化为：C(a,b)??D(x,y) (8) 小王既聪明又用功，但身体不好。 解：设A(x)：x聪明。B(x)：x用功。C(x)：x身体好。a：小王。 “小王既聪明又用功，但身体不好。”符号化为：A(a)∧B(a)∧?C(a) (9) 秦岭隔开了渭水和汉水。 解：设A(x,y,z)：x隔开了y和z。a：秦岭。b：渭水。c：汉水。 “秦岭隔开了渭水和汉水。”符号化为：A(a,b,c) (10) 除非小李是东北人，否则她一定怕冷。 解：设A(x)：x是东北人。B(x)：x怕冷。a：小李。 “除非小李是东北人，否则她一定怕冷。”符号化为：B(a)→?A(a) 2．将下列命题符号化。并讨论它们的真值。 (1) 有些实数是有理数。 解：设R(x)：x是实数。Q(x)：x是有理数。 “有些实数是有理数。”符号化为：(?x)(R(x)∧Q(x))
离散数学作业5 离散数学图论部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求2010年12月5日前完成并上交任课教师（不收电子稿）。并在05任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 的边数是 15 ． 2．设给定图G (如右由图所示)，则图G 的点割集是 {}f {}c e ,． 3．设G 是一个图，结点集合为V ，边集合为E ，则 G 的结点 度数之和 等于边数的两倍． 4．无向图G 存在欧拉回路，当且仅当G 连通且 不含奇数度结点 ． 5．设G=
习题与解答 1. 将下列命题符号化： (1) 所有的火车都比某些汽车快。 (2) 任何金属都可以溶解在某种液体中。 (3) 至少有一种金属可以溶解在所有液体中。 (4) 每个人都有自己喜欢的职业。 (5) 有些职业是所有的人都喜欢的。 解 (1) 取论域为所有交通工具的集合。令 x x T :)(是火车， x x C :)(是汽车， x y x F :),(比y 跑得快。 “所有的火车都比某些汽车快”可以符号化为))),()(()((y x F y C y x T x ∧?→?。 (2) 取论域为所有物质的集合。令 x x M :)(是金属， x x L :)(是液体， x y x D :),(可以溶解在y 中。 “任何金属都可以溶解在某种液体中” 可以符号化为))),()(()((y x D y L y x M x ∧?→?。 (3) 论域和谓词与(2)同。“至少有一种金属可以溶解在所有液体中” 可以符号化为))),()(()((y x D y L y x M x →?∧?。 (4) 取论域为所有事物的集合。令 x x M :)(是人， x x J :)(是职业， x y x L :),(喜欢y 。 “每个人都有自己喜欢的职业” 可以符号化为))),()(()((y x L y J y x M x ∧?→? (5)论域和谓词与(4)同。“有些职业是所有的人都喜欢的”可以符号化为))),()(()((x y L y M y x J x →?∧?。 2. 取论域为正整数集，用函数+（加法），?（乘法）和谓词<，=将下列命题符号化： (1) 没有既是奇数，又是偶数的正整数。 (2) 任何两个正整数都有最小公倍数。 (3) 没有最大的素数。 (4) 并非所有的素数都不是偶数。 解 先引进一些谓词如下： x y x D :),(能被y 整除，),(y x D 可表示为)(x y v v =??。 x x J :)(是奇数，)(x J 可表示为)2(x v v =???。 x x E :)(是偶数，)(x E 可表示为)2(x v v =??。 x x P :)(是素数，)(x P 可表示为)1)(()1(x u u x u v v u x =∨=?=???∧=?。
离散数学作业答案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】
离散数学集合论部分形成性考核书面作 业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数 理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题 目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识 点，重点复习，争取尽快掌握。本次形考书面作业是第一次作业，大家要认真及时地 完成集合论部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答 过程，要求本学期第11周末前完成并上交任课教师（不收电子稿）。并在03任务界 面下方点击“保存”和“交卷”按钮，完成并上交任课教师。 一、填空题 1．设集合{1,2,3},{1,2} ==，则P(A)- A B P(B )={{3},{1,3},{2,3},{1,2,3}}，A? B={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3,2>} ． 2．设集合A有10个元素，那么A的幂集合P(A)的元素个数为 1024 ． 3．设集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R是A到B的二元关系， 则R的有序对集合为{<2,2>,<2,3>,<3,2>,<3,3>} ． 4．设集合A={1, 2, 3, 4 }，B={6, 8, 12}，A到B的二元关系 R＝} ∈ y x∈ y < > = {B , , x , 2 y A x 那么R－1＝{<6,3>,<8,4>} 5．设集合A=｛a, b, c, d｝，A上的二元关系R={
集合论部分： 1.若集合S的基数|S|=5，则S的幂集的基数|P(S)|=（）。 2.若A-B=Ф，则下列哪个结论不可能正确？( ) (1) A=Ф (2) B=Ф(3) A?B (4) B?A 3.判断下列命题哪几个为正确？( ) (1) {Ф}∈{Ф,{{Ф}}} (2) {Ф}?{Ф,{{Ф}}} (3) Ф∈{{Ф}} (4) Ф?{Ф} (5) {a,b}∈{a,b,{a},{b}} 4. 设A∩B=A∩C，A∩B=A∩C，则B( )C。 5. 设,, A B C是论述域U的任意子集，证明下列各式： (a) () A B A ； -=Φ (b) ()()() ； A B C A B A C -=-- 6.证明:() -⊕= ； A B B A B
7.某班有50名学生，第一次考试中26人成绩为优，第二次考试中21人成绩为优，已知两 次考试中都不为优的共17人。问两次考试中都为优的有多少人？ 8.试证明集合等式：A? (B?C)=(A?B) ? (A?C)． 二元关系部分： 1 请描述得到传递闭包的算法 2举出集合A上的既是等价关系又是偏序关系的一个例子。( ) 3 集合A上的等价关系的三个性质是什么？( ) 4 集合A上的偏序关系的三个性质是什么？( ) 5 设S={１,２,３,４}，Ａ上的关系Ｒ＝｛〈1,2〉，〈2,1〉，〈2,3〉，〈3,4〉｝求(1)R R (2) R-1 。
6 设Ａ＝｛1，2，3，4，5，6｝，Ｒ是A 上的整除关系，求R 。 7 设Ａ＝｛1,2,3,4,5,6｝，B={1,2,3}，从Ａ到B 的关系Ｒ＝｛〈x,y 〉|x=2y ｝，求(1)R (2) R-1 。 8 集合A={1,2,…,10}上的关系R={