Question

离散数学一阶逻辑问题

1.非任意X存在Y F(x.y)等值于存在X任意Y非F(x.y)吗？
2.存在X任意Y A(x,y) 或 存在X任意Y B(x,y),能将前面的量词提出来吗？
3.量词辖域的放缩：任意X（A(x)蕴含B） 等值于 存在XA(x)蕴含B，这个等值中，全称量词为什么变成了客称量词？

Answer 1

你这些问题属于离散数学中较为复杂的一些，大体包括3方面的问题：
（1）【量词】与【否定（联结词）】的关系；
（2）【量词】与【其他联结词】的关系；
（3）【量词】与【量词】的关系；
它们分别有以下规律：
（1）任何时候：
　　①：改变【量词】与【否定】的位置，都必须也只需：改变量词；

（2）先考虑【合取】和【析取】两种联结词。一般形式为：
　　【量词】（【P】【联结词】【Q】）；——P、Q为任意【谓词公式】；
P、Q中均含【约束变元】时：
　　②：【全称量词】对【合取】满足“分配律”——明白“分配”的意思吧？
　　③：【存在量词】对【析取】满足“分配律”；

P、Q中有且只有一者含【约束变元】时：——不含【约束变元】的公式暂称为：“自由式”；
　　④：两种【量词】对两种【联结词】都满足“分配律”——记住：“自由式”前面的【量词】必须忽略不写，否则就不是正确的谓词公式了；

　　⑤：对于【条件联结词】或其他联结词，可以用｛否定、合取、析取｝等价转换得出。

（3）对于多个【量词】的情况，没有确定的等价关系式。你只要记住：
　　⑥：【量词】对变元的控制是【从左到右】的，且它们之间的顺序是不可以随便改变的，
　　⑦：【量词】之间有一定独立性，是可以【分别单独处理】的；简言之：
　　　　每个量词都有自己的作用域。对于其作用域，不管它的内容是什么，都可以用括号括起来；而对于括号中的内容，则可以按照前面的规律，单独分析。

你的问题。先定义符号：
　∑：存在量词；∏：全称量词；┐：非；∧：合取；∨：析取；→：条件；

1、┐∏(x)∑(y)F（x，y）；
　　根据①，直接将【否定】后移，得：
　　　　∑(x)∏(y)F（x，y）；
　　所以，本题答案是肯定的。

2、［∑(x)∏(y)A（x，y）］∨［∑(x)∏(y)B（x，y）］；
　　分析：根据⑥和⑦，上式可变化为：
　　　　∑(x)［∏(y)A（x，y）］∨∑(x)［∏(y)B（x，y）］；
　　该式是【存在量词】【分别控制】下的【析取】。再根据③，可得：
　　　　∑(x)［∏(y)A（x，y）∨∏(y)B（x，y）］；
　　中括号内，是【全称量词】【分别控制】下的【析取】，它们没有确定的等价关系。所以，不可等价得出你所说的那个结果，也就是不可以把两个量词都提取出来。（不过事实上，它可以【蕴含】你所说的结果）

3、∏(y)［A（x）→B］；
　　只能根据⑤慢慢推导；先利用【析取】与【条件】之间的关系，得：
＜＝＞∏(x)［┐A（x）∨B］；再根据④得：
＜＝＞∏(x)┐A（x）∨B；再根据①得：
＜＝＞┐∑(x)A（x）∨B；再利用一次【析取】与【条件】之间的关系，得：
＜＝＞∑(x)A（x）→B；
　　这就是【全称量词】变成【存在量词】的过程。