离散数学练习题2 答案

1-1．都是命题： 1-2设

P：明天天气晴朗 Q：我们就去郊游

则 P Q：如果明天天气晴朗，我们就去郊游 1-3根据真值表求公式P (P∧(Q R ))的主析取范式。 解

表1.15

例1.42真值表

则

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 )

■

由于任意一组命题变元P1, P2, …, Pn的真值指派和它的极小项之间是一一对应的，故可以对极小项进行编码。首先需要规定变元在极小项中的排列次序，假设为P1, P2, …, Pn，用m表示极小项，若Pi出现在极小项中，则编码的第i个位置上的值为1，否则为0。比如变元P, Q, R（规定次序为P, Q, R）的极小项P∧﹁Q∧﹁R的编码为100，将此极小项记为m100。若将编码看作是一个二进制数，又可将例中的极小项记为m4。用此方法，可以简写所求得的

给定公式的主析取范式。

P (P∧(Q R )) m0∨m1∨m2∨m3∨m4∨m5∨m7（规定P, Q, R的次序为P, Q, R） 公式P (P∧(Q R ))的主析取范式。 解 P (P∧(Q R )) ﹁P∨(P∧(﹁Q∨R )) (﹁P∨P)∧(﹁P∨﹁Q∨R) (﹁P∨﹁Q∨R ) (﹁P∨﹁Q∨R )

1-4试证明(﹁P Q )∧(P R )∧(﹁Q∨S ) S∨R。 证明 （1）﹁P Q

（2）﹁Q∨S （3）Q S （4）﹁P S （5）﹁S P （6）P R （7）﹁S R

(6), I13

（8）﹁﹁S∨R

E16

（9）S∨R

P P T, (2), E16 T, (1), (3), I13 T, (4), E18 P T, (5),

T, (7),

T, (8), E1

1-5如果迈克有电冰箱，则或者他卖了洗衣机，或者他向别人借了钱。迈克没有向别人借钱，所以如果迈克没有卖掉洗衣机，则他没有电冰箱。

解 设

P：迈克有电冰箱 Q：迈克卖了洗衣机 R：迈克向别人借了钱。

则上述语句可翻译为命题关系式

（1）P Q∨R （2）﹁P∨Q∨R （3）﹁ (﹁P∨Q ) R （4）﹁﹁P∧﹁Q R （5）P∧﹁Q R （6）﹁R ﹁(P∧﹁Q ) （7）﹁R ﹁P∨Q （8）﹁R （9）﹁P∨Q （10）P Q

（11）﹁Q ﹁P

P Q∨R, ﹁R ﹁Q ﹁P P T, (1), E16 T, (2), E16 T, (3), E9 T, (4), E1 T, (5), E18 T, (6), E8 P

T, (7), (8), I11 T, (9), E16

T, (10), E18

1-6如果今天我没课，则我去机房上机或去图书馆查资料；若机房没有空机器，则我没法去上机；今天我没课，机房也没有空机器，所以我去图书馆查资料。

解 设

P：今天我没课 Q：我去机房上机

R：我去图书馆查资料 S：机房没有空机器

则上述语句可翻译为命题关系式

P Q∨R, S ﹁Q, P, S R

（1）﹁R P （2）P Q∨R P （3）﹁P∨Q∨R T, (2), E16 （4）R∨﹁P∨Q T, (3), E3 （5）﹁R ﹁P∨Q T, (4), E16 （6）﹁P∨Q T, (1), (5), I11 （7）P Q T, (6), E16 （8）S ﹁Q P （9）﹁﹁Q ﹁S T, (8), E18 （10）Q ﹁S T, (9), E1 （11）P ﹁S T, (7), (11), I13 （12）P P

（13）﹁S

T, (11), (12), I11

（14）S

P

（15）F

(13), (14)

1-7北京、上海、天津、广州四市乒乓球队比赛，三个观众猜测比赛结果。 甲说：“天津第一，上海第二。” 乙说：“天津第二，广州第三。” 丙说：“北京第二，广州第四。”

比赛结果显示，每人猜对了一半，并且没有并列名次。问：实际名次怎样排列？解 设 P2：北京第二 Q2：上海第二 R1：天津第一 R2：天津第二 S3：广州第三 S4：广州第四 由已知条件：

甲猜对了一半，(﹁R1∧Q2 )∨(R1∧﹁Q2 )在真值指派f下为T； 乙猜对了一半，(﹁R2∧S3 )∨(R2∧﹁S3 )在真值指派f下为T； 丙猜对了一半，(﹁P2∧S4 )∨(P2∧﹁S4 )在真值指派f下为T。 由事实知，每个城市只能得一个名次即R1∧R2, S3∧S4为永假式。

再由题意，没有并列名次可得：P2∧Q2, P2∧R2, R2∧Q2在真值指派f下为F。

以上8个方程组成的方程组可解得f为P2=T, Q2=F, R1=T, R2=F, S3=T, S4=F

因此，实际名次为：天津第一、北京第二、广州第三、上海第四。

2-1 说明下列各式中量词的辖域与变元约束的情况： （1）( x)A(y) （2）( x)(A(x) B(x)) （3）( x)(A(x) ( y)B(x, y))

（4）( x)( y)(A(x, y)∧B(y, z))∧( x)A(x, y) （5）( x)(A(x)∧( x)B(x, z) ( y)C(x, y))∨B(x, y) （6）( x)(A(x) B(x))∧( x)C(x)∧D(x)

解 （1）( x)的辖域是A(y)，其中x为约束出现，y为自由出现。 （2）( x)的辖域是A(x) B(x), x为约束出现。

（3）( x)的辖域是A(x) ( y)B(x, y), ( y)的辖域是B(x, y)，其中x, y都为约束出现。 （4）( x)的辖域是( y)(A(x, y)∧B(y, z))，( y)的辖域是A(x, y)∧B(y, z)，( x )的辖域是A(x, y)，其中在( x)( y)(A(x, y)∧B(y, z))中，x，y都为约束出现，z为自由出现，在( x)A(x, y)中，x为约束出现，y为自由出现。

（5）( x)的辖域是(A(x)∧( x)B(x, z) ( y)C(x, y))，其中x的3次出现都为约束出现，但第2次出现是受量词( x)的约束，而第1次、第3次出现是受量词( x)的约束，z为自由出现，( x)的辖域是B(x, z)。( y)的辖域是C(x, y)，其中y为约束出现，B(x, y)中的x, y都为自由出现。

（6）( x)的辖域是A(x) B(x)，x为约束出现，( x)的辖域是C(x), x也为约束出现，D(x)中x的出现为自由出现。

2-2将公式( x)P(x) ( x)Q(x)化成前缀范式。

解

( x)P(x) ( x)Q(x) ﹁( x)P(x)∨( x)Q(x)

( x)﹁P(x)∨( x)Q(x) ( x)(﹁P(x)∨Q(x))

2.3 将公式( x)( y)(( z)(P(x, z)∧P(y, z)) ( v)Q(x, y, v))化成前缀范式。

解

( x)( y)(( z)(P(x, z)∧P(y, z)) ( v)Q(z, y, v))

( x)( y)(﹁( z)(P(x, z)∧P(y, z))∨( v)Q(x, y, v)) ( x …… 此处隐藏：6935字，全部文档内容请下载后查看。喜欢就下载吧 ……