电大离散数学形考任务1答案

1．求P?Q?R的析取范式，合取范式、主析取范式，主合取范式． P?Q?R??P?Q?R（析取范式）

?（?P?Q?R）（合取范式）

真值表： P 0 Q 0 R 0 ?P 原式 1 极小项 ?P??P??极大项 1 P 0 0 0 1 1 1 1

主析取范式（?P??P??P）?（?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?Q)的主析取范式、主合取范式． 真值表：

0 1 1 0 0 1 1 1 0 1 0 1 0 1 1 1 1 0 0 0 0 1 1 1 0 1 1 1 ?P??Q?R ?P?Q??R ?P?Q?R ? P??Q?R P?Q??R P?Q?R P?Q?R

P Q R ?R?Q 原式 极小项 极大项 （P?Q） 0 0 0 1 0 1 ?P??P?? P 0 0 0 1 1 1 1

主析取范式（?P??P??P）?（?P??Q?R）?（?P?Q??R）?（?P?Q?R）?（P??Q?R）?（P?Q??R）?（P?Q?R） 主合取范式（?P?Q?R）

3．设谓词公式(?x)(P(x,y)?(?z)Q(y,x,z))?(?y)R(y,z)． （1）试写出量词的辖域；

（2）指出该公式的自由变元和约束变元． 答：（1）?x的辖域为P（x,y）??zQ(x,y,z)

?z的辖域为Q(x,y,z)

0 1 1 0 0 1 1 1 0 1 0 1 0 1 1 0 0 0 0 0 0 1 1 1 0 1 1 1 1 1 1 0 1 1 1 ?P??Q?R ?P?Q??R ?P?Q?R ? P??Q?R P?Q??R P?Q?R P?Q?R ?y的辖域为R(y,z)

(2) 约束变元为

P（x,y）??zQ(x,y,z)中的x Q(x,y,z) 中的 z R(y,z)中的y 自由变元为

P（x,y）??zQ(x,y,z)中的y R(y,z)中的z

4．设个体域为D={a1, a2}，求谓词公式?y?xP(x,y)消去量词后的等值式；

答：谓词公式?y?xP(x,y)消去量词后的等值式为

=?xP（x,a1）??xP（x,a2）

=P (a1, a2）?P (a1, a2）?(P(a1, a2）?P (a1, a2))

五、证明题

1．试证明 (P?(Q??R))??P?Q与? (P??Q)等价． 证明：(P?(Q??R))??P?Q

??P?(Q??R))??P?Q ??P?Q ??（P??Q）

2．试证明?(A??B)?(?B?C)??C??A

证明：?(A??B)?(?B?C)??C

?(?A?B)?(?B?C)??C

?(?A?B)?(?B??C)?(C??C) ?(?A?B)?((?B??C)???0) ?(?A?B)?(?B??C)

?(?A? (?B??C))?(B?(?B??C)) ?(?A? (?B??C))?0 ??A? (?B??C) ??(A?B?C)

故由左边不可推出右边?A