一阶逻辑定理证明

令A是PL的公式，x在A中自由出现：101，├xA（x）yA（y）101├xA（x）yA（y）102，├xA（x）xA（x）103，├xA（x）xA（x）104，├xA（x）xA（x）105，├xA（x）xA（x）令A，B是PL的公式，x在A，B中自由出现：106，├xyA（x，y）yxA（x，y）107，├xyA（x，y）yxA（x，y）108，├xyA（x，y）yxA（x，y）；反之不成立。令A，B是PL的公式，x在A，B中自由出现：109，├x（A∧B）xA∧xB110，├x（AB）xAxB111，├x（A→B）→（xA→xB），反之不成立。112，├x（AB）→（xAxB），反之不成立。113，├（xA∨xB）→x（A∨B）反之不成立。114，├x（A∧B）xA∧xB，反之不成立。令A，B是PL的公式，x在B中自由出现并且在A中非自由出现，则有：115，├x（A∨B）A∨xB116，├x（A∨B）A∨xB117，├x（A∧B）A∧xB118，├x（A∧B）A∧xB119，├x（A→B）（A→xB）120，├x（A→B）（A→xB）121，├x（B→A）（xB→A）122，├x（B→A）xB→A123，├x（A→A）124，├x（A∨A）125，├x（A∧A）证明102：├xA（x）xA（x）⑴xAP⑵xAP⑶A（a）P⑷xAP⑸A（a）⑷—⑹A（a）⑶R⑺xA⑷—（6）+⑻xA∧xA（1）（7）∧+⑼xA∧xA（2），（3）―（8）⑽xA（2）—（9）+⑾xAP⑿A（a）P，a要符号条件⒀xAP（12）+⒁xA11）R⒂A（a）（12）—（14）—⒃xA（x/a）（15）a要符合条件⒄xA（x）xA（x）（1）—（10），（11）—（16）+证明103：├xA（x）xA（x）⑴xA（x）P②A（a）P⑶xA（x）P⑷A（a）⑶—⑸A（a）⑵R⑹xA（x）⑶—⑸+⑺xA（x）⑴，⑵—⑹—⑻xA（x）P⑼xA（x）P⑽A（a）P（a不出现在（8）（9）（14）中⑾xA（x）（10）+⑿xA（x）（9）R⒀A（a）（10）—（12）+⒁xA（x）（13）+⒂xA（x）（8）R⒃xA（x）（9）—（15）—⒄xA（x）xA（x）（1）—（16）+证明104：├xA（x）xA（x）⑴xA（x） P⑵xA（x）P⑶A（a）P（a符合条件）⑷xA（x）P⑸A（a）⑷—⑹A（a）⑶R⑺xA（x）⑷—⑹+⑻xA（x）⑵，⑶—⑺—⑼xA（x）⑴R⑽xA（x）⑵—⑼+⑾xA（x）P⑿A（a）P（a符合条件）⒀xA（x）（12）+⒁xA（x）（11）R⒂A（a）（12）—（14）+（a符合条件）⒃xA（x）（13）+⒄xA（x）xA（x）（1）—（10），（11）—（16）+证明105：├xA（x）xA（x）⑴xA（x）P⑵A（a）P⑶xA（x）P⑷A（a）（3）—⑸A（a）（2）⑹xA（x）（3）—（5）+⑺xA（x）（1），（2）—（6）—⑻xA（x）P⑼xAP⑽A（a）P（a符合条件）⑾xA（x/a）（10）+⑿xA（9）R⒀A（a）（10）—（12）—⒁xA（x/a）（13）+（a符合条件）⒂xA（x）（8）R⒃xA（9）—（15）—⒄xA（x）xA（x）（1）—（7），（8）—（16）+下面的证明不再写出右面的依据，可以作为练习自己填入。证明106：├xyA（x，y）yxA（x，y）⑴xyA⑵yA（a，y）⑶A（a，b）⑷xA（x，b）⑸yxA（x，y）⑹yxA（x，y）⑺xA（x，b）⑻A（a，b）⑼yA（a，y）⑽xyA（x，y）⑾xyA（x，y）yxA（x，y）证明107：├xyA（x，y）yxA（x，y）⑴xyA（x，y）⑵yA（a，y）⑶A（a，b）⑷xA（x，b）⑸yxA（x，y）⑹yxA（x，y）⑺yxA（x，y）⑻yxA（x，y）⑼xA（x，b）⑽A（a，b）⑾yA（a，y）⑿yxA（x，y）⒀yxA（x，y）⒁yxA（x，y）⒂xyA（x，y）yxA（x，y）证明108：├xyA（x，y）yxA（x，y）；反之不成立。⑴xyA（x，y）⑵yA（a，y）⑶A（a，b）⑷xA（x，b）⑸yxA（x，y）⑹yxA（x，y）⑺xyA（x，y）yxA（x，y）反之不成立，是因为“所有的y同有的x之间有关系A的那个x”，不一定就是“同所有的y有关系A的那个x”。我们可以用一个解释证明yxA（x，y）xyA（x，y）是不成立的。令y是偶数，x是质数，A是y能x整除，yxA（x，y）的意思是“所有的偶数都能被某个质数整除”因此是真的命题，我们可以找到这个质数，即2。xyA（x，y）的意思是：“有一个质数，它能被所有的偶数整除”这显然是假命题。证明109：├x（A∧B）xA∧xB（自证）证明110：├x（AB）xAxB⑴x（AB）⑵A（a）B（a）⑶A（a）⑷xA（x/a）⑸xAxB⑹B（a）⑺xB（x/a）⑻xAxB⑼xAxB⑽xAxB⑾xAxB⑿xA⒀A（a）⒁A（a）B（a）⒂x（AB）⒃x（AB）⒄xB⒅B（a）⒆A（a）B（a）⒇x（AB）（21）x（AB）（22）x（AB）（23）x（AB）xAxB证明：111，├x（A→B）→（xA→xB），反之不成立。⑴x（A→B）⑵xA⑶A（a）→B（a）⑷A（a）⑸B（a）⑹xB⑺（xA→xB）⑻x（A→B）→（xA→xB）证（xA→xB）→x（A→B）是不成立的。这个命题等值于（xA→xB）→x（A∨B）。假如个体域是｛苏格拉底，康德｝，令A：x是单身汉，B：x是美国人。显然（xA→xB）真，因为苏格拉底不是单身汉，这个蕴涵语句前件假，不论后件是否真假，都是真的。但是x（A∨B）中，当A（X）的个体是康德的时候一定是假的，B（x）由于那个时候根本还没有美国，因此因此说“所有的x，x或者不是单身汉或者都是美国人”一定是假的。故（xA→xB）→x（A∨B）假。由真的前提推出假的结论，因此推理无效。证明：112，├x（AB）→（xAxB），反之不成立。⑴x（AB）⑵xA⑶A（a）⑷A（a）B（a）⑸B（a）⑹xB⑺xB⑻B（a）⑼B（a）B（a）⑽A（a）⑾xA⑿xAxB⒀x（AB）→（xAxB）反之不成立的证明自己找到一个解释的证明。证明：113，├（xA∨xB）→x（A∨B）反之不成立。（自己证明）xA∨xB）xAAaAa∨Bax（A∨B）xBx（A∨B）x（A∨B）证明：114，├x（A∧B）xA∧xB，反之不成立。⑴x（A∧B）⑵A（a）∧B（a）⑶A（a）⑷xA⑸B（a）⑹xB⑺xA∧xB⑻xA∧xB⑼x（A∧B）xA∧xB证明反之不成立：UD：｛3，4｝，A：x大于3，x=4，B：x是奇数，x=3。xA∧xB在此解释下真。但是x（A∧B）是假的。因为在UD=｛3，4｝中，x既大于3并且又是奇数的解释没有。因此xA∧xB→x（A∧B）是无效的。证明115，├x（A∨B）A∨xB⑴x（A∨B）A中没有自由个体变项出现Ｐ⑵（A∨xB）⑶A∧xB德摩根律⑷A（３）⑸xBＰ⑹xBＰ参考104⑺B（a）⑻A∨B（a）⑼B（a）⑼B（a）⑽xB⑾A∨xB⑿⒀（14）A∨xB（15）A（16）A∨B（a）（17）x（A∨B）（18）xB（19）B（a）（a符合使用+条件）（20）A∨B（a）（A中没有x出现）（21）x（A∨B）（22）x（A∨B）（23）x（A∨B）A∨xB这个证明使用了导出规则。如果不使用德摩根率，要考虑推出A∧xB的两个支公式。具体的思路是：假设A，推出A∨xB，构造矛盾。另一个半的推理类似。证明116，├x（A∨B）A∨xB⑴x（A∨B）A中没有自由个体变项出现⑵A∨B（a）p⑶A⑷A∨xB⑸B（a）⑹xB（x/a）⑺A∨xBA中没有自由个体变项出现⑻A∨xB⑼A∨xB另一部分A∨xB├x（A∨B）的证明略，自己证明证明117，├x（A∧B）A∧xB（自己证明）证明118，├x（A∧B）A∧xB（自己证明）证明119，├x（A→B）（A→xB）⑴x（A→B）A中没有自由个体变项出现⑵A⑶A→B（a）⑷B（a）⑸xB（x/a）⑹A→xB⑺A→xBA中没有自由个体变项出现，x不出现⑻A⑼A→B（a）⑽B（a）⑾A→B（x/a）⑿x（A→B）⒀x（A→B）（A→xB）证明120，├x（A→B）（A→xB）⑴x（A→B）A中没有自由个体变项出现⑵A⑶A→B（a）⑷B（a）⑸xB⑹xB⑺A→xB⑻A→xBA中没有自由个体变项出现，x不出现。⑼（A→B（a））⑽A∧B（a）导出规则命题定理42AxBB（a）(DD)B（a）B（a）DDDDA→B（a）x（A→B）x（A→B）（A→xB）注：（A→B（a））（A∧B（a））AB（a）A∧B（a）（A∧B（a））B（a）A→B（a）（A→B（a））A∧B（a）证明121，├x（B→A）（xB→A）⑴x（B→A）⑵xB⑶B（a）（a符合条件要求）⑷B（a）→A⑸A（无a出现）⑹A⑺xB→A⑻xB→AA中没有自由个体变项出现，x不出现⑼B（a）（a不在⑻出现）⑽xB（x/a）⑾A⑿B（a）→A⒀x（B→A）⒁x（B→A）（xB→A）证明122，├x（B→A）xB→A⑴x（B→A）⑵B（a）→A⑶xB⑷B（a）⑸A⑹xB→A⑺xB→A⑻xB→AA中没有自由个体变项出现，x不出现⑼B（a）→A⑽x（B→A）⑾x（B→A）xB→A证明123，├x（A→A）（自证）证明124，├x（A∨A）（自证）证明125，├x（A∧A）（自证）作业：1，101，├xA（x）yA（y）2，101′├xA（x）yA（y）3，├x（A→B）→（xA→xB），4，├yxA（x，y）→xy（（A（x，y）B（x，y））zB（x，z））⑴yxA（x，y）P⑵xy（A（x，y）B（x，y））P⑶xA（x，b）⑴—（b不出现⑴中，符合条件）⑷A（a，b）P⑸zB（e，z）P⑹