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
相关推荐：
loading