Question

离散数学的题目

这是一道一阶逻辑的题目、
(1)写出~E(E的否定）的前束范式，要求内部是合取范式。
(2)求第一问所得到的前束范式的skolem标准型。
(3)将第二问的结果用推理证明它是矛盾式。

另一道题
A是有限集合，P(A)是它的幂集，RP(A)是P(A)的二元关系，具体关系见上图
(1)是否自反的，对称的，反对称的？
(2)集合A的元素的个数为2个时，RP(A)的元素的个数？
(3)集合A的元素的个数为n个时，RP(A)的元素的个数?
(4)集合A的元素的个数为n个时，RP(A)的自反且传递闭包RP(A)*的元素的个数？

求各位大神写下解题过程，谢谢。





Answer 1

这么难的题目，悬赏分数为0，太抠了，步骤就不详细提供了，提供一下关键思路：
第1题
（1）先把¬E写成合取形式。
¬E ⇔ A∧B∧C∧¬D
然后把含量词公式代进去，求出前束范式。

（2）把上面谓词公式中所有存在量词消去之后,得到该谓词公式的Skolem标准型

（3）推理证明为假即可。

第2题
Rp(A)中a,b显然需要满足a⊆b和a、b之间最多相差1个元素

（1）显然是自反的，不是对称，是反对称的

（2）元素个数为2个，P(A)幂集元素个数是4个
Rp(A)中有(∅,{a}),(∅,{b}),({a},{a,b}),({b},{a,b})和等值关系中的四个元素，因此
共有8个元素

（3）元素个数为n时，P(A)幂集元素个数是2ⁿ个
Rp(A)中有(∅,{a}),(∅,{b})...,({a},{a,b}),({b},{a,b})...和等值关系中的2ⁿ个元素，因此
共有n+n(n-1)+Cn²(n-2) +...+Cnⁿ⁻²(2)+Cnⁿ⁻¹+ 2ⁿ个元素
即(∑Cnª(n-a)) +2ⁿ个元素

（4）自反闭包就是本事，再考虑传递关系，就等价于
Rp(A)中a,b满足a⊆b和a、b之间相差任意多个元素（不超过n），因此
考虑笛卡尔乘积（a固定好后，b是a的超集）的排列数，
共有2ⁿ+n2ⁿ⁻¹+Cn²2ⁿ⁻²+...+Cnⁿ⁻²2²+Cnⁿ⁻¹2+Cnⁿ
=（1+2）ⁿ 【根据二项式定理】
=3ⁿ