精华内容
下载资源
问答
  • 通过讨论DNA计算的生物机理和表面DNA计算中的荧光标记策略的基本原理,利用表面DNA计算的思想,对数理逻辑中的命题推理进行了研究,给出了一种合适的DNA编码策略,提出了一种新的对一般的命题公式推理算法。...
  • 操作系统形式化验证实践教程(12) - 经典命题逻辑公式查错方法 第10节我们介绍了直觉一阶逻辑,它是不接受排中律的逻辑。在编程体感上,直觉一阶逻辑IFOL库,不支持auto,不支持sledgehammer,不能使用try0与try,...

    操作系统形式化验证实践教程(12) - 经典命题逻辑与公式查错方法

    第10节我们介绍了直觉一阶逻辑,它是不接受排中律的逻辑。在编程体感上,直觉一阶逻辑IFOL库,不支持auto,不支持sledgehammer,不能使用try0与try,基本上可以使用的就是simp或者手动推理。

    经典命题逻辑我们使用经典一阶逻辑库FOL,它是继承自IFOL的。

    经典一阶逻辑库FOL

    现在我们换成经典一阶逻辑的FOL库,现在可以使用auto了,我们看个例子:

    theory fol2
      imports FOL
    begin
    lemma D3: "⟦(¬A ⟹ B);(¬A ⟹¬B)⟧⟹ A"
    proof (auto)
    qed
    end
    

    我们来个复杂点的例子:

    lemma E1 : 
      assumes 1: ‹¬A ⟶ B›
    and 2: ‹¬B›
    and 3: ‹¬A›
    shows ‹¬B ⟶ A›
    

    从一堆公式中取出一个,可以采用local访问的方式,根据下标的不同来进行获取,比如取第n个可以用local.assms(n),也可以直接local.n,我们看例子:

    lemma E2_1: 
      assumes 1: ‹¬A ⟶ B›
    and 2: ‹¬B›
    and 3: ‹¬A›
    shows ‹¬A ⟶ B›
      by (rule local.assms(1))
    
    lemma E2_2:
      assumes 1: ‹¬A ⟶ B›
    and 2: ‹¬B›
    and 3: ‹¬A›
    shows ‹¬A›
      by (rule local.assms(3))
    
    lemma E2_3:
      assumes 1: ‹¬A ⟶ B›
    and 2: ‹¬B›
    and 3: ‹¬A›
    shows ‹¬B›
      by (rule local.assms(2))
    

    于是,按照《面向计算机科学的数理逻辑》中的写法,我们的公式推导可以写成下面这样:

    lemma E1 : 
      assumes 1: ‹¬A ⟶ B›
    and 2: ‹¬B›
    and 3: ‹¬A›
    shows ‹¬B ⟶ A›
    proof -
      from "1" "2" "3" have 1: ‹¬A ⟶ B› by (rule E2_1)
      from "1" "2" "3" have 3: ‹¬A› by (rule E2_2)
      from "1" "2" "3" have 2: ‹¬B› by (rule E2_3)
      from "1" "3" have 4: ‹B› by (rule mp)
      from "1" "2" "4" have 5: ‹A› by simp
      from "1" "5" show ‹¬B ⟶ A› by simp
    qed
    

    其中,from 1 3 have 4的过程是个小三段论:

    proof (prove)
    using this:
        ¬ A ⟶ B
        ¬ A
    
    goal (1 subgoal):
     1. B
    

    from 1 2 4 have 5,我们单独写个定理试试,有notE, notE’, contrapos_np等规则可以用:

    lemma Test1: "⟦(¬A ⟶ B);B;¬B⟧⟹A"
      by (rule contrapos_np)
    

    上节我们学习了,如果使用上一条的结论this,可以使用with来简化书写,我们把顺序调整一下:

    lemma E2 : 
      assumes 1: ‹¬A ⟶ B›
    and 2: ‹¬B›
    and 3: ‹¬A›
    shows ‹¬B ⟶ A›
    proof -
      from "1" "2" "3" have 1: ‹¬A ⟶ B› by (rule E2_1)
      from "1" "2" "3" have 2: ‹¬B› by (rule E2_3)
      from "1" "2" "3" have 3: ‹¬A› by (rule E2_2)
      with "1" have 4: ‹B› by (rule mp)
      with "1" "2" have 5: ‹A› by simp
      with "1" show ‹¬B ⟶ A› by simp
    qed
    

    因为我们的assumes其实可以直接使用,我们可以简化一下:

    lemma E2_v2 : 
      assumes 1: ‹¬A ⟶ B›
    and 2: ‹¬B›
    and 3: ‹¬A›
    shows ‹¬B ⟶ A›
    proof -
      from "1" "3" have 4: ‹B› by (rule mp)
      with "1" "2" have 5: ‹A› by simp
      with "1" show ‹¬B ⟶ A› by simp
    qed
    

    常用经典命题逻辑定理

    蕴含相关定理

    lemma H1_1 : "(A⟶B) ⟹ (A⟹B)"
      by(rule mp)
    
    lemma H1_2: "A ⟹ (B⟶A)"
      by simp
    
    lemma H1_3: "⟦A⟶B; B⟶C⟧ ⟹ (A⟶C)"
      by simp
    
    lemma H1_4: "⟦A⟶(B⟶C);A⟶B⟧⟹(A⟶C)"
      by simp
    

    除了可以用mp证明的第一条,其余三条在直觉逻辑IFOL中都没有证明。mp在IFOL中有实现。

    反证法相关定理

    经典逻辑与直觉逻辑最大的不同就是可以使用反证法了。

    lemma H2_1: "¬¬A ⟹ A"
      by (rule notnotD)
    
    lemma H2_2: "⟦(S⟹A) ⟹ B;(S⟹A) ⟹ ¬B⟧ ⟹ (S ⟹ ¬A)" 
      by auto
    
    lemma H2_3: "A ⟹ ¬¬A"
      by (rule HOL.cnf.clause2raw_not_not)
    
    lemma H2_4: "A⟹¬A ⟹ B"
      by (rule notE)
    
    lemma H2_5: "A ⟹ (¬A ⟶ B)"
      by simp
    
    lemma H2_6: "¬A ⟹ (A⟶B)"
      by simp
    

    这几条中,notE在IFOL中有实现,其余都不能用于IFOL.

    逆推相关定理

    lemma H3_1: "(A⟶B) ⟹ (¬B ⟶ ¬A)"
      by (rule Set.not_mono)
    
    lemma H3_2: "(A⟶¬B) ⟹ (B ⟶ ¬A)"
      by auto
    
    lemma H3_3: "(¬A⟶B) ⟹ (¬B ⟶ A)"
      by auto
    
    lemma H3_4: "(¬A ⟶ ¬B) ⟹ (B ⟶ A)"
      by auto
    

    化简相关定理

    lemma H4_1: "(¬A ⟶ A) ⟹ A"
      by (rule imp_elim)
    
    lemma H4_2: "(A ⟶ ¬A) ⟹ ¬A"
      by(rule impCE)
    
    lemma H4_3: "⟦(A⟶B); (A⟶¬B)⟧ ⟹ ¬A"
      by simp
    
    lemma H4_4: "⟦(A⟶B); (¬A⟶B)⟧ ⟹ B"
      by auto
    
    lemma H4_5: "¬(A⟶B) ⟹ A"
      by simp
    
    lemma H4_6: "¬(A⟶B) ⟹ ¬B"
      by simp
    

    合取相关定理

    lemma H5_1: "A∧B ⟹ (A ⟹ B)"
      by(rule conjE)
    
    lemma H5_2: "⟦A;B⟧ ⟹ A∧B"
      by (rule conjI)
    
    lemma H5_3: "(A ∧ B) ⟹ (B ∧ A) "
      by simp
    
    lemma H5_4: "(A∧B)∧C ⟹ A∧(B∧C)"
      by simp
    
    lemma H5_5: "¬(A∧B) ⟹ (A⟶¬B)"
      by simp
    
    lemma H5_6: "¬(A⟶B) ⟹ (A ∧ ¬B)"
      by (rule Meson.not_impD)
    

    最后一个H5_6,也可以写成by meson:

    lemma H5_6: "¬(A⟶B) ⟹ (A ∧ ¬B)"
      by meson
    

    经典命题逻辑的公理推演系统

    公理推演系统与自然推理系统是等价的,我们可以用公理推演系统的方法定义推理定理:

    lemma Ax1: "A⟶(B⟶A)"
      by simp
    
    lemma Ax2: "(A⟶(B⟶C)) ⟶ ((A⟶B)⟶(A⟶C))"
      by simp
    
    lemma Ax3: "(¬A ⟶ B)⟶((¬A ⟶ ¬B)⟶A)"
      by simp
    
    lemma Ax4: "A∧B ⟶ A"
      by simp
    
    lemma Ax5: "A∧B ⟶ B"
      by simp
    
    lemma Ax6: "A ⟶ (B⟶ A∧B)"
      by simp
    
    lemma Ax7: "A⟶A∨B"
      by simp
    
    lemma Ax8: "A ⟶ B∨A"
      by simp
    
    lemma Ax9: "(A⟶C) ⟶ ((B⟶C)⟶(A∨B⟶C))"
      by auto
    
    lemma Ax10: "(A⟷B)⟶(A⟶B)"
      by simp
    
    lemma Ax11: "(A⟷B) ⟶ (B⟶A)"
      by simp
    
    lemma Ax12: "(A⟶B) ⟶ ((B⟶A)⟶(A⟷B))"
      by auto
    

    其中需要注意的是Ax9,在FOL中需要使用auto, simp无法识别,但在HOL中可以使用simp.

    如何查找反例

    不知道大家淹没在公式的海洋中的体验如何,反正我写的时候经常写出错误的公式来。
    这时候我们需要的不是证明,而是先让系统帮我们搜索一下是不是有反例,我们的公式是不是写错了。

    quickcheck

    检查错误的第一个方法是使用quickcheck,直接当成语句写在IDE中即可。
    比如Ax12被我们写错了,写成Ax12_2这样子:

    lemma Ax12: "(A⟶B) ⟶ ((B⟶A)⟶(A⟷B))"
      by auto
    
    lemma Ax12_2: "(A⟶B) ⟶ ((A⟶B)⟶(A⟷B))"
      quickcheck
    

    系统就会给我们找一个反例:A=False, B=True

    Testing conjecture with Quickcheck-exhaustive... 
    Quickcheck found a counterexample:
      A = False
      B = True
    

    quickcheck的结果会弹对话框,同时在output窗口显示出来:

    quickcheck

    nitpick

    就像寻找定理证明方法可以用sledgehammer一样,检查反例也有专门的强大工具叫做nitpick。
    用法和quickcheck一样,在定理后面写一句nitpick就好:
    nitpick

    nitpick作为专门的工具,配置项有很多,我们后面会详细介绍,这里大家先把它和quickcheck用起来。
    如果公式已经错了,就不用为难sledgehammer去找证明了,先看看哪里写错了。

    小结

    不管是自然推理系统还是公理推演系统,在FOL和HOL证明定理时我们并不是用公理和推演规则进行推演的。公理和推演规则一般不对应FOL和HOL的公式,而是需要使用simp甚至auto进行证明的定理。
    但是,我们还是可以按照我们在数理逻辑中所学的方法进行思考和推演,然后使用HOL的工具帮助我们简化推理的过程,尤其是nitpick等查错工具和sledgehammer等定理搜索工具。

    展开全文
  • 基于条件概率的思想,利用赋值集的随机化方法,在Lukasiewicz n值命题逻辑系统中引入公式的条件随机真度,证明了条件随机真度的MP规则和HS规则。引入公式间的条件随机相似度和条件伪距离,建立了条件随机逻辑度量...
  • 命题逻辑推理理论

    万次阅读 2015-04-18 19:40:52
    所谓推理是指从前提出发推出结论的思维过程,而前提是已知命题公式集合,结论是从前提出发应用推理规则推出的命题公式。要研究推理就应该给出推理的形式结构,为此,首先应该明确什么样的推理是有效的或正确的。关于...

    主要内容

    1. 推理的形式结构:

    • ①推理的前提
    • ②推理的结论
    • ③推理正确
    • ④有效结论

    2. 判断推理是否正确的方法:

    • ①真值表法
    • ②等值演算法
    • ③主析取范式法

    3. 对于正确的推理,在自然推理系统P中构造证明

    4. ①自然推理系统P的定义
    ②自然推理系统P的推理规则:
        前提引入规则、结论引入规则、置换规则、假言推理规则、附加规则、化简规则、拒取式规则、假言三段式规则、构造性二难规则、合取引入规则。
    ③附加前提证明法
    ④归谬法 

    学习要求

    1. 理解并记住推理的形式结构的三种等价形式,即

    • ①{A1,A2,…,Ak}├B
    • ②A1∧A2∧…∧Ak→B
    • ③前提与结论分开写:
      •  前提:A1,A2,…,Ak
      •  结论:B

    在判断推理是否正确时,用②;在P系统中构造证明时用③。

    2. 熟练掌握判断推理是否正确的三种方法(真值表法,等值演算法,主析取范式法)。

    3. 牢记P系统中的各条推理规则。

    4. 对于给定的正确推理,要求在P系统中给出严谨的证明序列。

    5. 会用附加前提证明法和归谬法。

    ====================================================


    推理的形式结构

    有效推理

    数理逻辑的主要任务是用数学的方法来研究数学中的推理。所谓推理是指从前提出发推出结论的思维过程,而前提是已知命题公式集合,结论是从前提出发应用推理规则推出的命题公式。要研究推理就应该给出推理的形式结构,为此,首先应该明确什么样的推理是有效的或正确的。

    定义3.1 设A1,A2,…,Ak和B都是命题公式,若对于A1,A2,…,Ak和B中出现的命题变项的任意一组赋值,或者A1∧A2 ∧…∧Ak为假,或者当A1∧A2 ∧…∧Ak为真时,B也为真,则称由前提A1,A2,…,Ak推出B的推理是有效的正确的,并称B是有效结论

    关于定义3.1还需要做以下几点说明:

    • 1.由前提A1,A2,…,Ak推结论B的推理是否正确与诸前提的排列次序无关。因而前提的公式不一定是序列,而是一个有限的公式集合,若将这个集合记为Г,可将由Г推B的推理记为Г├ B。若推理是正确的,则记为ГB,否则记为ГB。这里,可以称Г├B和{ A1,A2,…,Ak}├ B 为推理的形式结构。
    • 2.设A1,A2,…,Ak,B中共出现n个命题变项,对于任何一组赋值α12,…,αni =0或者1,i=1,2,…,n),前提和结论的取值情况有以下四种:
      • (1) A1∧A2 ∧…∧Ak为0,B为0.
      • (2) A1∧A2 ∧…∧Ak为0,B为1.
      • (3) A1∧A2 ∧…∧Ak为1,B为0.
      • (4) A1∧A2 ∧…∧Ak为1,B为1.
    由定义3.1可知,只要不出现(3)中的情况,推理就是正确的,因而判断推理是否正确,就是判断是否会出现(3)中的情况
    • 3.由以上的讨论可知,推理正确,并不能保证结论B一定为真,这与数学中的推理是不同的。

    例3.1 判断下列推理是否正确:
        (1){p,p→q}q

        (2){p,q→p}q

         只要写出前提的合取式与结论的真值表,看是否出现前提合取式为真,而推论为假的情况。
        (1)由表3.1可知,没有出现前提合取式为真,而结论为假的情况,因而(1)中推理正确,即{p,p→q}q.

        (2)由表3.1可知,在赋值为10情况下,出现了前提合取式为真,而结论为假的情况,因而(2)推理不正确,即{p,q→p}q.

    表3.1

        对于本例这样简单的推理,不用写真值表也可以判断推理是否正确。在(1)中,当q为假时,无论p是真是假,p∧(p→q)均为假,因而不会出现前提合取式为真,结论为假的情况,因而推理正确。而在(2)中,当q为假,p为真时,出现了前提合取式为真,结论为假的情况,因而推理不正确。

    有效推理的等价定理

    定理3.1 命题公式A1,A2,…,Ak推B的推理正确当且仅当
                              (A1∧A2∧…∧Ak )→B
    重言式

         首先证明其必要性。若A1,A2,…,Ak推B的推理正确,则对于A1,A2,…,Ak,B中所含命题变项的任意一组赋值,不会出现A1∧A2∧…∧Ak为真,而B为假的情况,因而在任何赋值下,蕴涵式(A1∧A2∧…∧Ak )→B均为真,故它为重言式。

            再证明其充分性。若蕴涵式(A1∧A2∧…∧Ak)→B为重言式,则对于任何赋值此蕴涵式均为真,因而不会出现前件为真后件为假的情况,即在任何赋值下,或者A1∧A2∧…∧Ak为假,或者A1∧A2∧…∧Ak和B同时为真,这正符合定义3.1中推理正确的定义。

    由此定理知,推理形式:
        前提:A1,A2,…,Ak     
        结论:B

    是有效的当且仅当(A1∧A2∧…∧Ak)→B为重言式。(A1∧A2∧…∧Ak)→B称为上述推理的形式结构。从而推理的有效性等价于它的形式结构为永真式。于是,推理正确

                    {A1,A2,…,Ak}B

    可记为

                     A1∧A2∧…∧AkB

    其中一样是一种元语言符号,用来表示蕴涵式为重言式。

    而判断命题公式永真性有三个方法:

    • 1. 真值表法
    • 2. 等值演算法 
    • 3. 主析取范式法

    重言蕴涵式

    由上小节可以看出:形如A→B的重言式在推理中十分重要。若A→B为重言式,则称B为A的推论,记为AB,下面是几个重要的重言蕴涵式及其名称

    • 1. A(A∨B)                              附加律
    • 2. (A∧B)A                                  化简律 
    • 3. (A→B)∧AB                            假言推理
    • 4. (A→B)∧┐B┐A                        拒取式 
    • 5. (A∨B)∧┐BA                          析取三段论
    • 6. (A→B)∧(B→C)(A→C)                  假言三段论
    • 7. (AB)∧(BC)(AC)                等价三段论 
    • 8. (A→B)∧(C→D)∧(A∨C)(B∨D)          构造性二难
    •     (A→B)∧(┐A→B)∧(A∨┐A)B           构造性二难 (特殊形式) 
    • 9. (A→B)∧(C→D)∧(┐B∨┐D)(┐A∨┐C)                            破坏性二难

    这几个蕴涵式在下节中将起重要的作用。

    自然推理系统 P

    形式推理系统

    我们将前述推理用更严谨的形式推理系统描述出来。

    定义3.2 一个形式系统I由下面四个部分组成:
        (1) 非空的字符表集,记作A(I)。
        (2) A(I)中符号构造的合式公式集,记作E(I)。
        (3) E(I)中一些特殊的公式组成的公理集,记作AX(I)。
        (4) 推理规则集,记作R(I)。
    可以将I记为<A(I),E(I),AX(I),R(I)>.其中<A(I),E(I)>是I的形式语言系统,<AX(I),R(I)>为I的形式演算系统

        形式系统一般分为两类。一类是自然推理系统,它的特点是从任意给定的前提出发,应用系统中的推理规则进行推理演算,得到的最后命题公式是推理的结论(有时称为有效的结论,它可能是重言式,也可能不是)。另一类是公理推理系统,它只能从若干给定的公理出发,应用系统中推理规则进行推理演算,得到的结论是系统中的重言式,称为系统中的定理。

    自然推理系统 P

    P是一个自然推理系统,因而没有公理。故P只有三个部分。

    定义3.3 自然推理系统P定义如下:

        1.字母表
        (1) 命题变项符号:p,q,r,…,pi,qi,ri,…
        (2) 联结词符号:┐,∧,∨,→,
        (3) 括号和逗号:( , ),,

        2.合式公式 同定义1.6

        3.推理规则
        (1) 前提引入规则:在证明的任何步骤上都可以引入前提。
        (2) 结论引入规则:在证明的任何步骤上所得到的结论都可以作为后继证明的前提。
        (3) 置换规则:在证明的任何步骤上,命题公式中的子公式都可以用与之等值的公式置换,得到公式序列中的又一个公式。
        由九条推理定律和结论引入规则还可以导出以下各条推理定律。
        (4) 假言推理规则(或称分离规则):若证明的公式序列中已出现过A→B和A,则由假言推理定律(A→B)∧AB可知,B是A→B和A的有效结论。由结论引入规则可知,可将B引入到命题序列中来。用图式表示为如下形式:
            
      以下各条推理定律直接以图式给出,不再加以说明。
        (5) 附加规则:
            
        (6) 化简规则:
            
        (7) 拒取式规则:
            
        (8) 假言三段论规则:
            
        (9) 析取三段论规则:
            
        (10) 构造性二难推理:
            
        (11) 破坏性二难推理规则:
            
        (12) 合取引入规则:
            
    本条规则说明,若证明的公式序列中已出现A和B ,则可将A∧B引入序列中。
    这就完成了P的定义。

    P中的证明

    P中的证明就是由一组P中公式作为前提,利用P中的规则,推出结论。当然此结论也为P中公式。

    例3.3 在自然推理系统P中构造下面推理的证明:

        (1)前提:p∨q,q→r,p→s,┐s
           结论:r∧(p∨q)

        (2)前提:┐p∨q, r∨┐q ,r→s
           结论:p→s

       解  (1)证明:
        ① p→s      前提引入
        ② ┐s       前提引入
        ③ ┐p       ①②拒取式
        ④ p∨q      前提引入
        ⑤ q         ③④析取三段论
        ⑥ q→r      前提引入
        ⑦ r         ⑤⑥假言推理
        ⑧ r∧(p∨q) ⑦④合取

        此证明的序列长为8,最后一步为推理的结论,所以推理正确,r∧(p∨q)是有效结论。

        (2)证明:
        ① ┐p∨q    前提引入
        ② p→q      ①置换
        ③ r∨┐q    前提引入
        ④ q→r      ③置换
        ⑤ p→r      ②④假言三段论
        ⑥ r→s      前提引入
        ⑦ p→s      ⑤⑥假言三段论

        从最后一步可知推理正确,p→s是有效结论。

    可以在自然推理系统P中构造数学和日常生活中的一些推理,所得结论都是有效的,即当各前提的合取式为真时,结论必为真。

    例3.4 在自然推理系统P中构造下面推理的证明:
        若数a是实数,则它不是有理数就是无理数;若a不能表示成分数,则它不是有理数;a是实数且它不能表示成分数。所以a是无理数。

         首先将简单命题符号化:
        设 p:a是实数。      q:a是有理数。  r:a是无理数。     s:a能表示成分数。

        前提:p→(q∨r), ┐s→┐q, p∧┐s
        结论:r
        证明:

        ① p∧┐s    前提引入
        ② p         ①化简
        ③ ┐s       ①化简
        ④ p→(q∨r) 前提引入
        ⑤ q∨r      ②④假言推理
        ⑥ ┐s→┐q  前提引入
        ⑦ ┐q       ③⑥假言推理
        ⑧ r         ⑤⑦析取三段论

        P中证明的两个常用技巧:
         1.附加前提证明法
         2.归谬法

    附加前提法

    有时推理的形式结构具有如下形式
          (A1∧A2∧…∧Ak)→(A→B)         (3.5)
    (3.5)式中结论也为蕴涵式。此时可将结论中的前件也作为推理的前提,使结论只为B。即,将(3.5)化为下述形式

          (A1∧A2∧…∧Ak∧A)→B            (3.6)

    其正确性证明如下:
            (A1∧A2∧…∧Ak)→(A→B))
          ┐(A1∧A2∧…∧Ak)∨(┐A∨ B)
          ┐(A1∧A2∧…∧Ak∨┐A)∨B
          ┐(A1∧A2∧…∧Ak∧A)∨B
          (A1∧A2∧…∧Ak∧A)→B 

        因为(3.5)式与(3.6)式是等值的,因而若能证明(3.6)式是正确的,则(3.5)式也是正确的。用形式结构(3.6)式证明,将A称为附加前提,并称此证明法为附加前提证明法。

    例3.5 在自然推理系统P中构造下面推理的证明。
        如果小张和小王去看电影,则小李也去看电影;小赵不去看电影或小张去看电影;小王去看电影。所以,当小赵去看电影时,小李也去看电影。

         将简单命题符号化:
        设 p:小张去看电影。        q:小王去看电影。        r:小李去看电影。        s:小赵去看电影。
        前提:(p∧q)→r,┐s∨p,q
        结论:s→r
        证明:用附加前提证明法。
        ① s         附加前提引入
        ② ┐s∨p    前提引入
        ③ p         ①②析取三段论
        ④ (p∧q)→r 前提引入
        ⑤ q         前提引入
        ⑥ p∧q      ③⑤合取
        ⑦ r         ④⑥假言推理

        思考:不用附加前提证明法构造例3.5的证明

    归谬法

    在构造形式结构为

            (A1∧A2∧…∧Ak)→B

    的推理证明中,如果将┐B作为前提能推出矛盾来,比如说得出(A∧┐A),则说明推理正确。其原因如下:

            (A1∧A2∧…∧Ak)→B
          ┐(A1∧A2∧…∧Ak)∨B
          ┐(A1∧A2∧…∧Ak∧┐B)

    若(A1∧A2∧…∧Ak∧┐B)为矛盾式,正说明(A1∧A2∧…∧Ak)→B为重言式,即 (A1∧A2∧…∧Ak)B,

    故推理正确。

     例3.6自然推理系统P中构造下面推理的证明。

        如果小张守第一垒并且小李向B队投球,则A队将取胜;或者A队未取胜,或者A队获得联赛第一名;A队没有获得联赛的第一名;小张守第一垒。因此,小李没有向B队投球。

         先将简单命题符号化。

        设 p:小张守第一垒。
           q:小李向B队投球。
           r:A队取胜。
           s:A队获得联赛第一名。

        前提:(p∧q)→r,┐r∨s,┐s ,p
        结论:┐q
        证明:用归谬法

        ① q         结论的否定引入
        ② ┐r∨s    前提引入
        ③ ┐s       前提引入
        ④ ┐r       ②③析取三段论
        ⑤ (p∧q)→r 前提引人
        ⑥ ┐(p∧q)  ④⑤拒取式
        ⑦ ┐p∨┐q  ⑥置换
        ⑧ p         前提引入
        ⑨ ┐q       ⑦⑧析取三段论
        ⑩ q∧┐q    ①⑨合取

        由于最后一步q∧┐q0,即(((p∧q)→r)∧(┐r∨s)∧┐s∧p)∧q0,所以推理正确。

        思考:不用归谬法证明例3.6


    习题

    1.判断下面推理是否正确。先将简单命题符号化,再写出前提、结论、推理的形式结构(以蕴涵式的形式给出)和判断过程(至少给出两种判断方法):
      (1)若今天是星期一,则明天是星期三;今天是星期一。所以明天是星期三。
      (2)若今天是星期一,则明天是星期二;明天是星期二。所以今天是星期一。
      (3)若今天是星期一,则明天是星期三;明天不是星期三。所以今天不是星期一。
      (4)若今天是星期一,则明天是星期二;今天不是星期一。所以明天不是星期二。
      (5)若今天是星期一,则明天是星期二或星期三。
      (6)今天是星期一当且仅当明天是星期三;今天不是星期一。所以明天不是星期三。


    2.在自然推理系统P中构造下面推理的证明:
      (1)前提:p→(q→r), p, q
           结论:r∨s
      (2)前提:p→q, ┐(q∧r), r
           结论:┐p
      (3)前提:p→q
           结论:p→(p∧q)
      (4)前提:q→p, qs, st, t∧r
           结论:p∧q
      (5)前提:p→r, q→s, p∧q
           结论:r∧s
      (6)前提:┐p∨r, ┐q∨s, p∧q
           结论:t→(r∨s)

    3.在自然推理系统P中用附加前提法证明下面各推理:
      (1)前提:p→(q→r), s→p, q
           结论:s→r
      (2)前提:(p∨q)→(r∧s), (s∨t)→u
           结论:p→u

    4.在自然推理系统P中用归谬法证明下面推理:
      (1)前提:p→┐q, ┐r∨q, r∧┐s
           结论:┐p
      (2)前提:p∨q, p→r, q→s
           结论:r∨s

    5.在自然推理系统P中构造下面推理的证明。
      (1)如果小王是理科学生,他必学好数学;如果小王不是文科生,他必是理科生;小王没学好数学。所以,小王是文科生。
      (2)明天是晴天,或是雨天;若明天是晴天,我就去看电影;若我看电影,我就不看书。所以,如果我看书,则明天是雨天。



    ==========
    答案

    1.设p:今天是星期一,q:明天是星期二,r:明天是星期三。
      (1)推理的形式结构为     (p→r)∧p→r
     此形式结构为重言式,即     (p→r)∧pr
     所以推理正确。

      (2)推理的形式结构为     (p→q)∧q→p
     此形式结构不是重言式,故推理不正确。

      (3)推理形式结构为     (p→r)∧┐r→┐p
     此形式结构为重言式,即     (p→r)∧┐r┐p
     故推理正确。

      (4)推理形式结构为     (p→q)∧┐p→┐q
     此形式结构不是重言式,故推理不正确。

      (5)推理形式结构为     p→(q∨r)
     它不是重言式,故推理不正确。

      (6)推理形式结构为     (pr)∧┐p→┐r
     此形式结构为重言式,即     (pr)∧┐p┐r
     故推理正确。 

      推理是否正确,可用多种方法证明。证明的方法有真值表法、等式演算法。证明推理正确还可用构造证明法。

      下面用构造证明法证明(6)推理正确。
      前提: pr, ┐p
      结论: ┐r
      证明: ① pr                     前提引入
            ② (p→r)∧(r→p)            ①置换
            ③ r→p                      ②化简律
            ④ ┐p                       前提引入
            ⑤ ┐r                       ③④拒取式

      所以,推理正确。

    2. (1)证明:


    ①p→(q→r) 前提引入

    ②p 前提引入

    ③q→r ①②假言推理

    ④q 前提引入

    ⑤r ③④假言推理

    ⑥r∨s ⑤附加律
      (2)证明:

    ①┐(q∧r) 前提引入

    ②┐q∨┐r ①置换

    ③r 前提引入

    ④┐q ②③析取三段论

    ⑤p→q 前提引入

    ⑥┐p ④⑤拒取式
      (3)证明:

    ①p→q 前提引入

    ②┐p∨q ①置换

    ③(┐p∨q)∧(┐p∨p) ②置换

    ④┐p∨(p∧q) ③置换

    ⑤p→(p∧q) ④置换
      也可以用附加前提证明法,更简单些。
      (4)证明:

    ①st 前提引入

    ②(s→t)∧(t→s) ①置换

    ③t→s ②化简

    ④t∧r 前提引入

    ⑤t ④化简

    ⑥s ③⑤假言推理

    ⑦qs 前提引入

    ⑧(s→q)∧(q→s) ⑦置换

    ⑨s→q ⑧化简

    ⑩q ⑥⑨假言推理

    q→p 前提引入

    p 假言推理

    p∧q 合取

      (5)证明:

    ①p→r 前提引入

    ②q→s 前提引入

    ③p∧q 前提引入

    ④p ③化简

    ⑤q ③化简

    ⑥r ①④假言推理

    ⑦s ②⑤假言推理

    ⑧r∧s ⑥⑦合取

      (6)证明:

    ①t 附加前提引入

    ②┐p∨r 前提引入

    ③p∧q 前提引入

    ④p ③化简

    ⑤r ②④析取三段论

    ⑥r∨s ⑤附加

      说明:证明中,附加提前t,前提┐q∨s没用上。这仍是正确的推理。

    3.  (1)证明:


    ①s 附加前提引入

    ②s→p 前提引入

    ③p ①②假言推理

    ④p→(q→r) 前提引入

    ⑤q→r ③④假言推理

    ⑥q 前提引入

    ⑦r ⑤⑥假言推理
      (2)证明:

    ①p 附加前提引入

    ②p∨q ①附加

    ③(p∨q)→(r∧s) 前提引入

    ④r∧s ②③假言推理

    ⑤s ④化简

    ⑥s∨t ⑤附加

    ⑦(s∨t)→u 前提引入

    ⑧u ⑥⑦假言推理

    4.(1)证明:


    ①p 结论否定引入

    ②p→┐q 前提引入

    ③┐q ①②假言推理

    ④┐r∨q 前提引入

    ⑤┐r ③④析取三段论

    ⑥r∧┐s 前提引入

    ⑦r ⑥化简

    ⑧┐r∧r ⑤⑦合取

      ⑧为矛盾式,由归谬法可知,推理正确。

      (2)证明:

    ①┐(r∨s) 结论否定引入

    ②p∨q 前提引入

    ③p→r 前提引入

    ④q→s 前提引入

    ⑤r∨s ②③④构造性二难

    ⑥┐(r∨s)∧(r∨s) ①⑤合取

      ⑥为矛盾式,所以推理正确。

    5.(1)    令p:小王是理科生,q:小王是文科生,r:小王学好数学。
        前提:p→r, ┐q→p, ┐r
        结论:q
        证明:


    ①p→r 前提引入

    ②┐r 前提引入

    ③┐p ①②拒取式

    ④┐q→p 前提引入

    ⑤q ③④拒取式
      (2)   令p:明天是晴天,q:明天是雨天,r:我看电影,s:我看书。
       前提: p∨q, p→r, r→┐s
       结论: s→q
       证明:
      ①s 附加前提引入   ②r→┐s 前提引入   ③┐r ①②拒取式   ④p→r 前提引入   ⑤┐p ③④拒取式   ⑥p∨q 前提引入   ⑦q ⑤⑥析取三段论


    关于Discrete Mathematics更多讨论与交流,敬请关注本博客和新浪微博songzi_tea.

    展开全文
  • 通过引入赋值密度函数、边缘密度函数等概念,给出了连续值命题逻辑系统G?del中公式概率真度的定义,研究了概率真度的推理规则,在此基础上给出了三种相似度,讨论了其性质及关系,并由此定义了三种伪距离,讨论了...
  • 第三章命题逻辑推理理论 3.1推理的形式结构 数理逻辑的主要任务是用数学的方法研究推理.所谓推理是指从前提出发推出结论的思维过程,而前提是已知的命题公式集合,结论是从前提出发应用推理规则推出的命题公式...

    第三章命题逻辑的推理理论

     

    3.1推理的形式结构

     

    数理逻辑的主要任务是用数学的方法研究推理.所谓推理是指从前提出发推出结论的思维过程,而前提是已知的命题公式集合,结论是从前提出发应用推理规则推出的命题公式.为此, 首先应该明确什么样的推理是正确的.

    定义3.1设A1,A2,...Ak和B都是命题公式,若对于A1,A2,...,Ak和B中出现的命题变项的任意一组赋值,或者A1^A2^…^Ak为假,或者当A1^A2^…^Ak为真时B也为真,则称由前提A1,A2,…,Ak推出结论B的推理是有效的或正确的,并称B是有效的结论.

    关于定义3.1还需做以下几点说明

    1. 由前提A1,A2,…,Ak推结论B的推理是否正确与诸前提的排列次序无关,前提是一个有限的公式集合.设前提为集合Γ,将由Γ推B的推理记为Γ├B.若推理是正确的,则记为Γ╞ B,否则记为|≠B.这里称├B或{A1,A2,…,Ak}├B为推理的形式结构
    2. 设A1,A2,...,Ak,B中共出现n个命题变项,对于任一组赋值α1α2…αn(αi=0或1,i=1,2,…,n),前提和结论的取值情况有以下4种
    1. A1^A2^...Ak为0,B为0;
    2. A1^A2^...Ak为0,B为1;
    3. A1^A2^...Ak为1,B为0;
    4. A1^A2^...Ak为1,B为1;

    由定义3.1可知,只要不出现情况(3),推理就是正确的,因而判断推理是否正确,就是判断是否会出现情况(3)

    1. 由上面的讨论可知,推理正确并不能保证结论B一定成立,因为前提可能就不成立.这与人们通常对推理的理解是不同的,通常只能认为在正确的前提下推出正确的结论才是正确的.而在这里,如果前提不正确,不论结论正确与否,都说推理正确

    例3.1判断下列推理是否正确

    1. Ip,p→ql├q
    2. Ip,q→pl├q

    解:写出前提的合取式与结论的真值表,看是否出现前提合取式为真,而结论为假的情况

    1. 由表3.1,没有出现前提合取式为真,结论为假的情况,因而推理正确,即{p,p→q}|=q
    2. 由表3.1,当赋值为10时,前提的合取式为真,而结论为假,因而推理不正确,即{p,g→p}|≠q

     

    对于例3.1中这样简单的推理,不难通过直接观察判断推理是否正确。如在(1)中,当q为假时,无论p是真还是假,P^(q→p)均为假,因而不会出现前提合取式为真,结论为假的情况,故推理正确.而在(2)中,当q为假,P为真时,出现了前提合取式为真,结论为假的情况,因而推理不正确

    下面给出推理形式结构另一种等价的形式,为此,首先证明下面定理

    定理3.1命题公式A1,A2,…,Ak推B的推理正确当且仅当A1^A2^…^Ak→B为重言式

     必要性,若A1,A2,…,A,推B的推理正确,则对于A1,A2,…,Ak和B中所含命题变项的任意一组赋值,不会出现A1^A2^…^Ak为真且B为假的情况,因而在任何赋值下,蕴涵式A1^A2^…^Ak→B均为真,故它为重言式

    充分性,若蕴涵式A1^A2^…^A→B为重言式,则对于任何赋值此蕴涵式均为真,因而不会出现前件为真后件为假的情况,即在任何赋值下,或者A1^A2^…^A4为假,或者A1^A2^…^Ak和B同时为真,故A1,A2,...,Ak推B的推理正确

    由定理3.1,由前提A1,A2,…,Ak推B的推理的形式结构

    {A1,A2,...,Ak}|-B (3.1)

    等同于蕴涵式

    A1^A2^…^A→B (3.2)

    其中推理前提的合取式成了蕴涵式的前件,结论成了蕴涵式的后件.推理正确

    {A1,A2,...,Ak}|=B (3.3)

    等同于

    A1^A2^…^A=>B (3.4)

    其中=>同<=>个样是一种元语言符号,表示蕴涵式为重言式。

    今后把推理的形式结构写成:

    前提:A1,A2,...,Ak

    结论:B

    并且也把(3.2)式称作推理的形式结构,通过判断(3.2)式是否为重言式来确定推理是否正确.根据前2章的讨论,判断(3.2)式是否为重言式有下面3种方法

    1. 真值表法
    2. 等值演算法
    3. 主析取范式法

    现在可以将例3.1中的两个推理写成(3.5)的形式

    (1)

    前提:p,P→q

    结论:q

    推理的形式结构:(p^(P→q))→q

    (2)

    前提:p,q→q

    结论:q

    推理的形式结构:(p^(q→p))→q

    由例3.1已知,(1)正确,即(p^(p→q))→q;而(2)不正确,记为(P^(q→p))≠>q.

    例3.2判断下面推理是否正确

    1. 若a能被4整除,则a能被2整除,a能被4整除.所以,a能被2整除
    2. 若a能被4整除,则a能被2整除,a能被2整除.所以,a能被4整除
    3. 下午马芳或去看电影或去游泳,她没去看电影.所以,她去游泳了
    4. 若下午气温超过30℃,则王小燕必去游泳,若她去游泳,她就不去看电影了.所以,若王燕没去看电影,下午气温必超计了30℃

     解上述类型的推理问题,首先应将简单命题符号化,然后分别写出前提、结论、推理的形式结构,接着进行判断

    1. 设p:a能被4整除

    q:a能被2整除

    前提:p→q,p

    结论:q

    推理的形式结构:(p→q)^P→p (3.6)

    由例3此推理正确,即(p→q)^p=>p

    1. 设p,q的含义同(1)

    前提:p->q,q

    结论:p

    推理的形式结构:(p→q)^q→p (3.7)

    当然可用真值表法、等值演算、主析取范式等方法来判断(3.7)式是否为重言式,但在此推理中,容易看出,01是(3.7)式的成假赋值,所以此推理不正确

    p:马芳下午去看电影

    q:马芳下午去游泳

    前提:pVq,┓p

    结论:q

    推理的形式结构:((pVq)^┓p)→p (3.8)

    用等值演算法来判断(3.8)式是否为重言式

    ((pVq)^┓p)->q

    <=>((p^┓p)V(q^┓p))→q

    <=>(qA┓p)->q

    <=>┓qVPVq

    <=>1

    得证(3.8)式为重言式,所以推理正确

    p:下午气温超过30℃

    q:王小燕去游泳

    r:王小燕去看电影

    前提:p→q,q→┓r

    结论:┓r->p

    推理的形式结构:((p→q)^(q→┓r)→(┓r→p)

    用主析取范式法判(39)式是否为重言式

    ((p→q)^(q→┓r)→(┓r→p)

    <=>┓((┓pVq)^(┓V┓r))V(rVp)

    <=>((p∧q)V(q∧r))v(rVp)

    <=>pVr (用两次吸收律)

    <=>(p∧┓q∧┓r)V(P^┓q^r)V(p^q^┓r)

    ( p^q^r)V(┓p∧┓q^r)V(┓p^q∧r)

    V(P∧┓q∧r)V(P^q∧r)

    <=> m1,Vm3 Vm4Vm6 Vm7 (重排了序)

    可见(3.9)式不是重言式(主析取范式中缺2个极小项m0和m2),所以推理不正确

    有一些重要的重言蕴涵式,称为推理定律.下面给出9条推理定律,它们是:

     

    其中A,B,C,D等是元语言符号,表示任意的命题公式

    把具体的命题公式代入某条推理定律后就得到这条推理定律的一个代人实例.例如p=>pVq,p→q=>(p→q)Vr,p=> pvqvr等都是附加定律的代入实例,推理定律的毎一个代人实例都是重言式,可以使用这些推理定律证明推理正确.在下一节将看到,由这9条推理定律产生9条推理规则,构成一个推理系统中的推理规则集

    除上述9条推理定律外,2.1节给出的24个等值式中的每一个都能产生出两条推理定律例如,双重否定律A<=>┓┓A产生两条推理定律A=>┓┓A和┓┓A=>A.

     

     

    展开全文
  • 给出了相干命题逻辑自然推理系统NR的自动证明算法。首先将待证命题公式A的子公式组成一个初始集合P,对其中的元素采用系统NR的推理规则得到新的命题公式加入P,当得到秩为0的A时命题得证;然后对A的证明树进行整理即...
  • 命题逻辑详解

    2021-03-12 19:26:21
    命题逻辑公式的语法1.命题逻辑公式的归纳定义:2.抽象语法树3.子公式:4.语法性质5.命题逻辑公式的简写三.命题逻辑公式的语义1.命题逻辑公式的真值表2.命题逻辑公式的分类四.命题逻辑的等值演算1.逻辑等值定义:2....

    命题逻辑详解


    命题之间的真值关系是逻辑研究的基本问题。

    一.命题逻辑的基本概念

    1.命题与真值

    命题:是具有真假值的陈述句,或为真,或为假。

    注意:以下两种陈述句不是命题:

    ​ 1)含有变量的句子。(如:x是5的倍数)

    ​ 只有确定了x是某类事物中的具体个体,或对x使用量词进行量化之后才能得到命题。(如:存在整数x,使 x是5的倍数)

    ​ 2)被认为是悖论的句子。(如:我说的这句话是假的)这个句子就没有真值。

    真值:命题的真假值。一个为真,一个为假,即{0,1}或{F,T}

    2.原子命题与复合命题

    原子命题:其中没有逻辑联结词,不再进行分解。又称为简单命题。

    复合命题:可以分解出更简单的命题作为子命题,其真值由子命题的真值唯一确定。

    注意:原子命题的真值由它是否符合客观实际或是否符合人们的认知决定;复合命题的真值由原子命题的真值和逻辑联结词的性质决定。

    二.命题逻辑公式的语法

    命题逻辑公式的符号集包括元素: ∧和 , ∨或 , →蕴含 , ↔双蕴含 , ¬否 和左右圆括号(,)这两个辅助符号。

    1.命题逻辑公式的归纳定义:

    1)归纳基:每个命题变量都是命题逻辑公式;

    2)归纳步:(i)如果A是命题逻辑公式,则(¬A)(否定式)也是命题逻辑公式;(ii)如果A和B是命题逻辑公式,则(A∧B)(合取式),(A∨B)(析取式),(A →B)(蕴含式),(A↔B)(双蕴含式)都是命题逻辑公式。

    2.抽象语法树

    定义:将公式的构造用二叉树表示,称为抽象语法树,简称AST

    优点:可以快速判断公式类型(由最后一步所使用的逻辑运算符决定);可以容易的给出每一步的公式构造。

    3.子公式:

    定义:构造命题逻辑公式是用到的公式称为子公式,包括其本身。它的每个子公式对应抽象语法树里的一棵子树。

    4.语法性质

    1)任意命题逻辑公式包含的左圆括号数等于右圆括号数,等于公式的逻辑运算符数。(可由结构归纳法证明)

    2)如果一个命题逻辑公式不是命题变量,则作为符号串存在且仅存在一个点满足:这个位置的字符是逻辑运算符;它左边的子符号串以左圆括号开头,其中左圆括号比右圆括号多一个,其右边以右圆括号结束,其中右圆括号比左圆括号多一个。

    p.s.性质二给出了判断一个符号串是否为命题逻辑公式的方法:扫描找到该位置,分为左子串和右子串,再分别递归判定,直到不存在这样的位置。

    5.命题逻辑公式的简写

    为了避免使用圆括号,人们规定了运算符的优先级结合性

    1)逻辑运算符从高到低的顺序: ¬,∧ , ∨ , → , ↔

    2)规定:∧ , ∨ ,↔从左至右结合,→从右至左结合

    三.命题逻辑公式的语义

    这里所说的命题逻辑公式的语义是指如何确定命题逻辑公式的真值。

    一个命题逻辑公式的真值计算过程后序遍历抽象语法树的过程,即由叶子顶点的命题变量的真值得到它的父亲节点对应公式的真值,然后再得到上一层内部顶点对应公式的真值等,一直到根的对应公式,即整个公式的真值。

    1.命题逻辑公式的真值表

    定义:以表格的形式给出公式在任意真值赋值下的真值。

    性质:命题逻辑公式的真值只与它包含的命题变量得真值有关,因此含有n个命题变量的公式的真值表有2^n行

    **p.s.**关于蕴含式(易错):A →B,当A真值为假时,蕴含式的真值为真;当A的真值为真时,蕴含式的真值等于B的真值

    2.命题逻辑公式的分类

    从真值情况进行分类:1)永真式(重言式)2)矛盾式(永假式)3)偶然式(非永真的可满足式)

    判断一个命题逻辑公式是否为永真式的基本方法是构造该公式的真值表。若最后一列都为1,则是永真式。

    定理:设命题逻辑公式A是永真式,p是在A中出现的一个命题变量,则使用任意命题逻辑公式B替换A中出现的 所有p,得到的公式A’也是永真式。

    四.命题逻辑的等值演算

    命题逻辑的等值演算是判断这两个命题逻辑公式是否逻辑等值的基本方法。

    1.逻辑等值定义:

    对任意的真值赋值,命题逻辑公式A和B的真值都相同,则称A和B逻辑等值,简称等值,记为A ≡ B

    也称A ≡ B为逻辑等值式。(注意不是命题逻辑公式)

    例如:命题逻辑公式p→q与 ¬p∨q等值

    p.s.(技巧)

    1)验证两个命题逻辑公式是否逻辑等值的基本方法是构造这两个公式的真值表,比较在相同的真值赋值下真值是否相同

    2)逻辑运算或,与满足交换律结合律幂等律

    3)逻辑等值有传递性

    2.定理:

    1)A ≡ B当且仅当公式A↔B是永真式。

    2)设命题逻辑公式B是A的子公式,且B与B‘逻辑等值。假若使用B’置换公式A的一处或多处子公式B得到的式子是A‘,则A与A’逻辑等值。

    3.等值演算

    定义:为验证A ≡ B,只要将A变换到与它等值的A‘,再变换,直到变换为B;或从B等值变换为A;或将A和B都等值变换为C。这样的等值变换过程称为等值演算。

    4.命题逻辑公式的范式

    定义

    析取范式:是一个或多个合取式的析取,其中的合取式都是一个或多个文字的合取;文字指命题变量或命题变量的否定。这种一个或多个文字的合取的公式称为简单合取式。

    合取范式: 是一个或多个析取式的合取,其中的析取式都是一个或多个文字的析取。这种一个或多个文字的析取的公式称为简单析取式。

    注意:每个命题逻辑公式都有与它逻辑等值的析取范式和合取范式。而且是唯一的(化简以后更容易判断真值^^)

    极小项:若含有n个命题变量的合取式恰好是n个文字的合取,每个文字对应不同的命题变量,该合取式称为极小项。含有n个命题变量的主析取范式公式是零个或多个极小项的析取。

    极大项:若含有n个命题变量的析取式恰好是n个文字的析取,每个文字对应不同的命题变量,该析取式称为极大项。含有n个命题变量的主合取范式公式是零个或多个极大项的析取。

    p.s.永真式没有成假赋值,因此其主合取范式不含有任何极大项。

    ​ 可以说一个与公式逻辑等值的主析取范式与主合取范式是该公式的真值表的另一种表达形式

    ​ 公式包含的命题变量比较多时,列真值表的计算量大,利用等值演算可能更方便。

    ​ 极大项和极小项的概念可以类比线性代数中的最小线性无关向量集合等。

    公式的主析取范式的极小项编码与其主合取范式的极大项编码集互补。(看成二进制的互为反码)

    五.命题逻辑的推理理论

    推理:是从一组做为前提的命题得到一个作为结论的命题的过程。如果这个过程能够保证当前所有前提都为真的情况下得到的结论必然为真,则称推理是有效的。

    1.推理的有效性

    定义:称推理A,B,C,…,N X是有效的,若(AvB∧Cv…vN)→X是永真式。

    **注意:推理的有效性并不保证结论是真的!**因为不能保证前提是真的。

    2.命题逻辑的自然推理系统

    构造真值表法和等值演算法都可用于验证推理的有效性。

    但是构造真值表效率太低,等值演算法不贴近人们的日常生活,对人们的构造和分析有效推理缺乏指导意义。

    **命题逻辑的自然推理系统的特点:**1)引入中间结论进行分解。2)运用公理化思维方式,套用推理规则。

    推理规则的实例:分别使用具体的命题逻辑公式替换推理规则中的每个字母的所有出现后得到的推理。

    3.构造验证推理有效性的论证

    验证推理有效性的论证的构造从某种程度上就是归纳构造。利用中间结论,可以从推理论证开始进行分析。

    **注意:**只能利用具体的公式替换规则中的字母,不能替换规则中的子公式。

    **后序遍历:**遍历树的顶点时只要保证在所有以儿子顶点为根的子树遍历以后才遍历父亲顶点即可。

    **p.s.**推理的每一步应该清楚所用的规则或原理,以注释的形式标注(不能跳步!!!

    ​ 可以使用附加前提法反证法

    六.命题逻辑的应用

    1.自然语言命题的符号化

    自然语言命题转换为逻辑公式的过程也称为自然语言命题的符号化。命题逻辑公式由命题变量和逻辑运算符构成。

    转化过程:

    1)判定命题

    2)找原子命题

    3)不同的原子命题用不同的命题变量符号表示

    4)分析句子中逻辑联结词所表达的逻辑含义

    2.普通逻辑问题的符号化分析

    逻辑按照其历史发展阶段和类型可以分为传统逻辑和现代逻辑,从17世纪末德国哲学家莱布尼茨提出用数学方法处理演绎逻辑从而诞生数理逻辑之前的逻辑学称为传统逻辑学,数理逻辑诞生以来的逻辑学称为现代逻辑

    我们将在传统逻辑中用自然语言分析和求解的问题称为普通逻辑问题。

    常见的三种问题:

    1)给出一些条件,寻找满足这些条件的情况或方案。(利用等值演算法)

    2)给出从一些前提得到一个结论的推理,验证推理的有效性(利用推理理论)

    3)给出一些前提,讨论从这些前提出发通过有效的推理将得到怎样的结论(利用推理理论)

    3.算法性质的逻辑分析

    程序设计语言中的条件表达式就是逻辑公式。条件就是具有真假值的命题。

    辑**问题。

    常见的三种问题:

    1)给出一些条件,寻找满足这些条件的情况或方案。(利用等值演算法)

    2)给出从一些前提得到一个结论的推理,验证推理的有效性(利用推理理论)

    3)给出一些前提,讨论从这些前提出发通过有效的推理将得到怎样的结论(利用推理理论)

    3.算法性质的逻辑分析

    程序设计语言中的条件表达式就是逻辑公式。条件就是具有真假值的命题。

    展开全文
  • 模糊命题逻辑系统的计量化与近似推理,黎丽,,利用赋值集的随机化方法,在模糊命题逻辑系统中引入了命题公式的随机真度,同时引入了命题公式间的随机相似度和随机伪距离,建立
  • 第三章命题逻辑推理理论 1.推理的形式结构 (1)定义3.1:设A1,A2,A3...Ak和B都是命题公式,若对于A1,A2,A3...Ak和B中出现的命题变项的任意一组赋值,或者A1,A2,A3...Ak为假,或者当A1,A2,A3...Ak为真是,...
  • 通过引入赋值密度函数、边缘密度函数等概念给出了连续值命题逻辑系统中公式概率真度的定义,明确了概率真度在[0,1]中的分布情况,并得到了一些概率真度的推理规则;引入相似度,给出了伪距离的定义,确定了二者之间...
  • 离散数学-3 命题逻辑推理理论

    千次阅读 2018-03-15 12:34:05
    定义3.1 设A1, A2, …, Ak, B为命题公式. 若对于每组赋值,A1A2…Ak 为假,或当A1A2…Ak为真时,B也为真,则称由前提A1, A2, …, Ak推出结论B的...定理3.1 由命题公式A1, A2, …, Ak 推B的推理
  • 命题逻辑推理理论 一些笔记: 判断推理是否正确,就是判断是否会出现1推出0的情况,如出现则推理错误,否则正确。 命题公式A1,A2,...,AkA_1,A_2,...,A_kA1​,A2​,...,Ak​推出B的推理正确当且仅当 A1∧A2∧...,∧...
  • 利用势为3的非均匀概率空间的无穷乘积,在£ukasiewicz三值命题逻辑中引入了公式的概率真度概念,证明了全体公式的概率真度值之集在[0,1]中没有孤立点;利用概率真度定义了概率相似度和伪距离,进而建立了概率逻辑...
  • 基于条件概率的思想,在连续值命题逻辑系统中引入赋值密度函数概念,给出了公式的概率真度、数学期望、条件概率真度的定义,并得到了一些概率真度的推理规则。证明了Lukasiewicz逻辑系统中概率真度、条件概率真度在...
  • 一、 谓词逻辑相关概念、 ...二、 一阶谓词逻辑公式、 三、 两个基本公式、 1、 公式一、 2、 公式二、 四、 命题符号化技巧、 1、 命题符号化方法、 2、 谓词逻辑组合、 3、 当且仅当谓词逻辑、 五、 命题符号化示例、
  • tetradecane:数理逻辑(1)——命题逻辑的基本概念​zhuanlan.zhihu.com1. 等值的定义对于两个命题公式 和 ,而 是出现在 与 中的所有命题变项,那么公式 和 各有 个解释。若公式 和 的所有解释完全相同,称 和 是...
  • 命题逻辑公式集F(S)F(S)F(S) 三条公理 宽容律:L1:A→(B→A)L_{1}:A \to (B \to A)L1​:A→(B→A) 蕴含分配律:L2:(A→(B→C))→((A→B)→(A→C))L_{2}:(A \to (B \to C)) \to ((A \to B) \to (A \to C))L2​:(A→...
  • 基于某信息限制下若A则B的推理思想,以真度为基础,在二值命题逻辑系统中引入有限信息限制下的公式蕴涵度概念,由此定义了信息限制蕴涵度量,并通过信息限制蕴涵度量的真度表示式,给出一系列与有限理论结论集相关的...
  • 数理逻辑是研究推理的数学学科,它首先完成是对现象的一种符号化处理,基于符号化处理,它在将着重于推理过程以及推理的结果。 命题: 称所表达的判断式真或假但不能可真可假的陈述句为命题命题的符号...
  • tetradecane:数理逻辑(1)——命题逻辑的基本概念​zhuanlan.zhihu.com1. 等值的定义对于两个命题公式 和 ,而 是出现在 与 中的所有命题变项,那么公式 和 各有 个解释。若公式 和 的所有解释完全相同,称 和 是...
  • 公式真度为基础,给出了二值命题逻辑中基于条件真度的逻辑度量的真度表示式,提出了两类在信息Г下的误差不大于ε结论模式,证明了两类结论模式的等价性,并讨论了基于条件真度和真度的近似推理及其关系问题。
  • ContentChapter 1 命题逻辑逻辑符号证明规则 Chapter 1 命题逻辑 逻辑符号 negation: ¬p\neg p¬p disjunction: p∨qp \lor qp∨q conjunction: p∧qp \land qp∧q implication: p→qp \to qp→q 证明规则 通过将...
  • 离散数学第一章导学离散数学都...2.命题逻辑推理部分 3.谓词逻辑 二,集合论 1.集合 2.关系与函数 三,代数结构 1.代数系统的一般概念 2.格与布尔代数 四,图论 1.图 2.图的应用 命题及命题公式...
  • 提出了由信息Г下理论的相对偏差确定的公式是理论的III-型误差不大于ε的结论模式,并证明其与I,II-型误差不大于ε的结论模式是等价的,为从不同角度研究二值命题逻辑中基于条件真度的近似推理问题提供多样化工具。
  • 命题逻辑(数理逻辑)

    2009-03-23 19:43:23
    数理逻辑是用数学方法研究思维规律的一门学科。...本章介绍数理逻辑中最基本的内容命题逻辑。首先引入命题、命题公式等概念。然后,在此基础上研究命题公式间的等值关系和蕴含关系,并给出推理规则,进行命题演绎。
  • 在[n]值Lukasiewicz命题逻辑系统中,引入命题随机真度的概念,给出了随机真度的一个计算公式,研究了命题随机真度的若干性质。证明了命题逻辑的分离规则、三段论规则以及交推理规则在[n]值Lukasiewicz命题逻辑系统中...
  • 命题逻辑推理理论 2.1 命题逻辑基本概念 • 2.1.1 命题与联结词 – 命题与真值(简单命题, 复合命题) – 联结词(¬, , , , ) • 2.2.2 命题公式及其分类 – 命题公式及其赋值 – 真值表 – 命题公式的分类
  • 1. 推理的定义 2. 推理的判定定理 3. 推理的判定示例 4. 推理定律(基本蕴含关系:简化规则、添加规则、合取引入规则、选言三段论、假言推理规则、否定后件式、假言三段论、二难推理,共8种) 5...
  • 命题逻辑异或与精确表达异或精确表达:真值表需要精确对应命题公式的简化与命题等价命题公式的简化命题等价:真值表相同基础等价公式重言式(永真式)与矛盾式(永假式)重言蕴含式:基础重言蕴含式范式析取范式与合取范式...

空空如也

空空如也

1 2 3 4 5 6
收藏数 114
精华内容 45
关键字:

命题逻辑推理公式