逻辑学真值表及命题演算

第五章真值表方法与命题演算教学重点与要点完全真值表法的判定功用归谬赋值法的操作与判定命题演算证明方法的应用与构造一、真值联结词•定义：真值联结词是指仅仅表示复合命题与肢命题之间真假关系的联结词。•真值联结词主要有五个：•¬（否定）、∧（合取）、•∨（析取）、→（蕴涵）、•←→（等值）二、真值形式•定义：真值形式是指由真值联结词和命题变项所构成的形式结构。•五种基本的真值形式•否定式：¬p•合取式：p∧q•析取式：p∨q•蕴涵式：p→q•等值式：p←→q三、五种基本真值形式的真值表•定义，真值表是数理逻辑中用以定义命题联结词并确定复合命题真或假的一种图表。•T表示“真”、F表示“假”•1、¬pp¬pTFFT2、p∧qpqp∧qTTTTFFFTFFFF3、p∨qpqp∨qTTTTFTFTTFFF4、p→qpqp→qTTTTFFFTTFFT5、p←→qpqp←→qTTTTFFFTFFFT真值表判定程序的三个要求（1）程序的每一步都是由事先给定的规则明确规定好的；（2）对于所判定的对象是否具有某种性质，该程序能够给出唯一确定的结果；（3）该程序能够在有穷步骤结束。判定程序的特点：机械的、能行的、可判定的。完全真值表法完全真值表的作法三个步骤：1、找出已给命题公式的所有变项，并竖行列出这些变项的所有真值组合；2、根据命题公式的结构，由繁到简的依次横行列出，一次只引进一个连接词，直至列出该公式本身；3、依据基本真值表，有变项的真值逐步计算出每个部分的真值，最后列出整个公式得真值。完全真值表法的判定功能（1）命题公式的性质判定（2）推理形式有效性的判定（3）命题公式之间关系的判定重言式、矛盾式、可满足式的判定•1、重言式（又叫永真式）是指在一个命题形式中不论其中的变项取什么值，该命题形式的值总是真的。•如：p∨¬pp¬pp∨¬pTFTFTT•2、矛盾式（又叫永假式）是指在一个命题形式中不论其中的变项取什么值，该命题形式的值总是假的。•如：p∧¬pp¬pp∧¬pTFFFTF•3、可满足式（协调式）是指在一个命题形式中不论其中的变项取什么值，该命题形式的值至少在一种情况下是真的。•如：p∧qpqp∧qTTTTFFFTFFFF•真值表判定任一命题形式是否是重言式。•例1、（（p∨q）∧¬p）→qpq¬pp∨q(p∨q）∧¬p（（p∨q）∧¬p）→qTTFTFTTFFTFTFTTTTTFFTFFT•例2、（（p∨q）∧p）→¬qpq¬qp∨q(p∨q）∧p（（p∨q）∧p）→¬qTTFTTFTFTTTTFTFTFTFFTFFT真值表判定任意两个复合命题之间是否具有等值关系•例1、¬（p∧q）•¬p∨¬q•由真值表可知这两个命题之间具有等值关系。pq¬p¬q(p∧q)¬(p∧q)¬p∨¬qTTFFTFFTFFTFTTFTTFFTTFFTTFTT例2、¬（p∨q）；¬p∨¬qpq¬p¬q(p∨q)¬(p∨q)¬p∨¬qTTFFTFFTFFTTFTFTTFTFTFFTTFTT三、真值表帮助解决一些推理问题•例：列出A、B、C三命题的真值表，并回答当A、B、C三命题恰有一个为真时，甲是否是木工？•A、如果甲不是木工，则乙是泥工。•B、如果乙不是泥工，则甲不是木工。•C、甲不是木工，且乙不是泥工。•解设p表示“甲是木工”；q表示“乙是泥工”。•A：¬p→q•B：¬q→¬p•C：¬p∧¬qpq¬p¬q¬p→q¬q→¬p¬p∧¬qTTFFTTFTFFTTFFFTTFTTFFFTTFTT练习题•一、用真值表判定下列真值形式是否是重言式•1、（（P→q）∧¬p）→q•2、（（P∨q）∧¬q）→P•二、请用真值表判定下列各组命题形式之间是否具有等值关系。•1、¬（P→q）•P∧¬q•2、¬（P∧¬q）•¬P∨q•三、列出A、B两命题的真值表，并回答A、B恰有一个为假时，王军是否考上了大学？•A：如果王军考上了大学，那么李伟就没有考上大学。•B：王军没有考上大学。四、列出A、B、C三命题的真值表，并回答当A、B、C三命题恰有一真时，是否甲村所有人家都有彩电？•A、甲村所有人家都有彩电，并且乙村所有人家都有彩电。•B、或者甲村所有人家都有彩电，或者乙村所有人家都有彩电。•C、如果乙村所有人家都有彩电，那么甲村有些人家没有彩电。真值表法的局限性1、完全真值表法的局限性判定多变项命题公式过于繁琐。2、归谬赋值法的局限性仅能判定蕴涵式，3、真值树法的局限性判定结构复杂的公式时，树冠过大操作不便。4、问题：是否有一种方法既能解决命题逻辑有效性的判定问题又能解决有效性的推导问题？命题演算的证明方法一、命题演算方法概述1、命题演算方法在问题求解上的必要性认知2、命题演算与形式系统构造3、公理系统与自然演绎系统4、自然演绎法的基本思想5、具体推证方法的认知※直接证明法※间接证明法※反证法一、直接证明法1、直接证明法的特点认知勿需附加任何前提即可依规则从给定的前提推导出结论。2、直接证明法的操作步骤（1）依序编号排列前提，将结论写在最后一个前提的右侧并用“/∴”断开。（2）依据已知前提结合相关规则推出新的命题，依次编号写在下面。（3）在推出的新命题右侧括号内注明前提依据和规则依据。（4）证明结束写上证毕字样。推证实例分析1.AB2.CD3.ACBD直接证明法1.AB2.CD3.ACBD4.AC(3.等值)5.AD(4.2.连锁)6.BA(1.易位)7.BD(6.4.连锁)8.BD(7.等值)证毕。二、假设证明法1、间接推证法的特点认知给定前提不够，需要附加。2、假设证明法的基本思路附加假设，依据蕴涵引入的规则有条件的推出相关结论。3、假设证明法的模式构造解法二：假设证法1.AB2.CD3.ACBD4.B(假设)4.D(假设)5.A(1.4.销去)5.C(2.4.销去)6.C(3.5.销去)6.A(4.5.销去)7.D(2.6.销去)7.B(1.6.销去)8.BD(4－7.引入)8.DB(4－7.引入)9.BD(8.等值)9.DB(8.等值)证毕。10.BD(9.交换)证毕。三、反证法1、反证法的特点认知前提不够，需要附加。附加与结论相矛盾的命题作为假设依据规则进行推导寻求矛盾。找到矛盾后利用否定引入或销去规则反证结论成立。2、反证法的模式构造解法三：反证法1.AB2.CD3.ACBD4.(BD)(反设)5.BD(4.等值)6.B(5.销去)7.A(1.6.销去)8.C(3.7.销去)9.D(2.8.销去)10.D(5.销去)11.DD(9.10.引入)12.BD(4－11.销去)证毕。假设证明法与反证法的区别与综合应用一、假设证明法与反证法的区别二、假设证明法与反证法的综合应用1、在证明中的综合应用【例析4301】2、在推理中的综合应用【4302】三、命题逻辑定理的证明((p→q)∧p)→qpqp→q(p→q)∧p((p→q)∧p)→qTTTTTTFFFTFTTFTFFTFT画一个完全真值表实例分析2pqp∨﹁pq∧﹁qp∧qTTTFTTFTFTFTTFTFFTFF永真式永假式可真式**实例分析3：判断3p→q；﹁p∨q；p∧﹁q的真假关系pqp→q﹁p∨qp∧﹁qTTTTFTFFFTFTTTFFFTTF等值矛盾实例分析4：用归谬赋值法判定（（p→q）∧﹁q）→﹁P这个推理是否有效？（（p→q）∧﹁q）→﹁PFTFTTTFTT由上表可知：q的赋值出现矛盾，此命题形式是重言式，与之相对应的推理形式是有效式。运用归谬赋值法要注意：※由于给变项赋值过程中有先后的不同，因而具体矛盾的出现可能不同。※只有当赋值过程中矛盾不可避免的出现时，才能表明原公式是重言式，相应的推理有效。※赋值过程中，变项的值有时候不能惟一的确定，此时需要讨论。*返回*1.AB2.BC3.CD4.D/A5.C（3，4，销去）6.B（2，5，销去）7.A（1，6，销去）证毕。直接证明法（实例分析一）直接证法（实例分析二）1.(AB)C2.CD3.BD/A4.D（2，销去）5.C（2，销去）6.B（3，4，销去）7.(AB)（1，5，销去）8.AB（7，等值）9.A（6，8，销去）证毕。回溯思考方法1.A(BC)2.AD3.C(EF)4.DF/E(1)“回溯”思考，首先要考察待证结论与前提的关联性，待证结论处在命题的后件，要获证必须基于对前件C的肯定。(2)C与前提1关联，要获取必须基于主联结关系的销去。(3)前提1的销去，取决于对前提2中条件A的否定。(4)要获取对A的否定，必须基于对后件D的否定，而后件D的否定处在前提4之中，要获取D必先分解前提4。直接证明法：推导结论1.(BD)2.CD3.AB4.(EF)C5.AF6.A(5.销去)7.B(3.6.销去)8.BD(1.7.等值)9.D(7.8.销去)10.C(2.9.销去)11.(EF)(4.10.销去)12.EF(11.等值)13.F(5.销去)14.E(12.13.销去)直接证明法前提一致性判定1.AB2.BC3.DC4.AD5.D6.C7.B8.A9.A10.AA直接证明法前提一致性判定之021.AB2.BC3.DC4.AD5.A6.B7.C8.D假设证明法的模式构造1.给定前提2.3./∴pq4.p(假设）:：：10.q11.pq(4---10引入）1.BA2.B(AC)AC3.A(假设)4.B(1.3,销去)5.AC(2.4.销去)6.C(5.销去)7.AC(3.6.引入)证毕。假设证明法（实例分析一）1.AC2.C(E(HI))3.FIA(FE)4.A(假设)5.C(1.4.销去)6.E(HI)(2.5.销去)7.F(假设)8.I(3.7.销去)9.IH(8.引入)10.HI(9.交换)11.(HI)(10.等值)12.E(6.11.销去)13.FE(7－12.引入)14.A(FE)(4－13.引入)证毕。假设证明法（实例分析二）反证法的模式构造1.2.3./p4.p(反设):::9.qq10.p(4－9.销去)证毕。.1.2.3./p4.P(反设):::9.qq10.p(4－9.引入)证毕。1.AB2.CB3.(AC)/A4.AC(3.等值)5.A(反设)6.B(1.5.销去)7.C(2.6.销去)8.C(4.5.销去)9.CC(7.8.引入)10.A(5－9.引入)证毕。反证法（实例分析一）在证明中的综合应用1.ABC2.(AB)CBC3.C(假设)4.(AB)(2.3.销去)5.AB(4.等值)6.AB(1.3.销去)7.B(反设)8.A(5.7.销去)9.A(6.7.销去)10.AA(8.9.引入)11.B(7－10.销去)12.CB(3－11.引入)13.CB(12.等值)14.BC(13.交换)证毕。在推理中的综合应用1.(AB)C2.(BD)(AC)3.(BA)(CD)4.(BC)A5.B(假设)6.C(反设)7.BC(5.6.引入)8.A(4.7.销去)9.BA(5.8.引入)10.CD(3.9销去)11.D(6.10.销去)12.BD(5.11.引入)13.AC(2.12.销去)14.A(8.13.销去)15.AA(8.14.引入)16.C(6－15.销去)17.BC(5－16.引入)