离散数学 第2章 习题解答

本文格式为Word版，下载可任意编辑——离散数学第2章习题解答

习题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)老王是山东人或XX人。

解：设A(x)：x是山东人。B(x)：x是XX人。a：老王。

“老王是山东人或XX人。〞符号化为：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,3，试消去以下各式的量词。

(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,2

解：(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,6解：(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)(x-2x+1=0)其中个体域为D=-1,2

解：(x)(x2-2x+1=0)(((－1)2－2(－1)＋1=0)∨(22－22＋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)∨(xR(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))

2

(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))(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))(x)A(x)→(x)B(x)

(6)(x)(A(x)B(x))(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))(x)(A(x)→B(x))(x)A(x)→(x)B(x)

同理，(x)(A(x)→B(x))∧(x)(B(x)→A(x))(x)B(x)→(x)A(x)

所以，(x)(A(x)→B(x))∧(x)(B(x)→A(x))((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))(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)(x)(F(x)∧R(x))

证明：

⑴(x)F(x)

⑵F(c)

⑶(x)(F(x)→(G(y)∧R(x)))

⑷F(c)→(G(y)∧R(c))

⑸G(y)∧R(c)

⑹R(c)

⑺F(c)∧R(c)

⑻(x)(F(x)∧R(x))PES⑴PUS⑶T⑵⑷假言推理T⑸化简律T⑵⑹合取引入EG⑺

(2)(x)(F(x)→G(x))，(x)(R(x)→G(x))(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)(x)F(x)

证明：

⑴(x)R(x)P

⑵R(c)

⑶(x)(G(x)→R(x))

⑷G(c)→R(c)

⑸G(c)

⑹(x)(F(x)∨G(x))

⑺F(c)∨G(c)

⑻F(c)

⑼(x)F(x)

US⑴PUS⑶T⑵⑷拒取式PUS⑹T⑸⑺析取三段论UG⑻

(4)(x)F(x)→(y)((F(y)∨G(y))→R(y))，(x)F(x)(x)R(x)

证明：

⑴(x)F(x)P

ES⑴

P

T⑴⑶假言推理

US⑷

T⑵附加律

T⑸⑹假言推理

UG⑺⑵F(c)⑶(x)F(x)→(y)((F(y)∨G(y))→R(y))⑷(y)((F(y)∨G(y))→R(y))⑸(F(c)∨G(c))→R(c)⑹F(c)∨G(c)⑺R(c)⑻(x)R(x)

2．用CP规则证明以下各式。

(1)(x)(F(x)→R(x))(x)F(x)→(x)R(x)

证明：

⑴(x)F(x)

⑵F(c)

⑶(x)(F(x)→R(x))

⑷F(c)→R(c)

⑸R(c)

⑹(x)R(x)P(附加前提)US⑴PUS⑶T⑵⑷假言推理UG⑸

⑺(x)F(x)→(x)R(x)CP

(2)(x)(F(x)∨G(x))，(x)(G(x)∧R(x))(x)R(x)→(x)F(x)

证明：

⑴(x)R(x)P(附加前提)

⑵R(c)

⑶(x)(G(x)∧R(x))

⑷(x)(G(x)∧R(x))US⑴PT⑶量词否定等价式

⑸(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))(x)R(x)→(x)F(x)

证明：

⑴(x)R(x)

⑵(x)R(x)

⑶R(c)

⑷(x)(G(x)∨R(x))

⑸G(c)∨R(c)

P(附加前提)T⑴量词否定等价式ES⑵PUS⑷

⑹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))(x)F(x)∨(x)G(x)

证明：

⑴((x)F(x)∨(x)G(x))

⑵(x)F(x)∧(x)G(x))

⑶(x)F(x)∧(x)G(x))

⑷(x)F(x)

⑸F(c)

⑹(x)G(x))P(附加前提)T⑴德摩根律T⑵量词否定等价式T⑶化简律ES⑷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)(x)F(x)

证明：

⑴(x)F(x)P(附加前提)

⑵(x)F(x)

⑶F(c)

⑷(x)(F(x)∨G(x))

⑸F(c)∨G(c)

⑹G(c)T⑴量词否定等价式ES⑵PUS⑷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)(x)F(x)

证明：

⑴(x)R(x)P

⑵R(c)

⑶(x)F(x)

⑷(x)F(x)

⑸F(c)

ES⑴P(附加前提)T⑶量词否定等价式US⑷

⑹(x)(F(x)→G(x))

⑺F(c)→G(c)

⑻G(c)PUS⑹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))⑵Q(c)∧Z(c)

⑶Q(c)

⑷Z(c)PES⑴T⑵化简律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