zsych01命题逻辑.ppt

命题逻辑谓词逻辑非经典逻辑,数理逻辑,第1章命题逻辑,命题逻辑研究的是以原子命题为基本单位的推理演算，其特征在于，研究和考查逻辑形式时，我们把一个命题只分析到其中所含的原子命题成分为止。通过这样的分析可以显示出一些重要的逻辑形式，这种形式和有关的逻辑规律就属于命题逻辑。,第1章命题逻辑,内容提要：1.命题逻辑的基本概念、命题联结词2.命题公式、自然语言的形式化3.命题公式的等值和蕴含4.范式5.联结词的完备集6.推理理论7.命题逻辑在计算机科学中的应用,1.1命题与联结词,1.1.1命题与命题变元定义1.1能够分辨真假的陈述句叫做命题（Proposition）。该定义有两层含义：(1)命题是陈述句。其他的语句，如疑问句、祈使句、感叹句均不是命题；(2)这个陈述句表示的内容可以分辨真假，而且不是真就是假，不能不真也不假，也不能既真又假,1.1命题与联结词,作为命题的陈述句所表示的判断结果称为命题的真值，真值只取两个值：真或假。凡是与事实相符的陈述句是真命题，而与事实不符合的陈述句是假命题。通常用1（或字母T）表示真，用0（或字母F）表示假。,1.1命题与联结词,（1）北京是中国的首都。（2）5可以被2整除。（3）2+2=5。（4）请勿吸烟。（5）乌鸦是黑色的吗？（6）这个小男孩多勇敢啊！（7）地球外的星球上存在生物。（8）我正在说谎。,例1.1判断下列语句是否为命题，并指出其真值。,1.1命题与联结词,命题的分类原子命题（AutomicProposition）：是指不能再分解为更简单命题的命题；复合命题（CompoundProposition）：是指由若干命题用联结词组成的新命题。例如：“雪是白的”是原子命题；“昨天下雨，而且打雷”，“如果明天天晴我就去打球或者游泳”都是复合命题。,1.1命题与联结词,定义1.2真值确定的原子命题称为命题常元（PropositionalConstant），真值不确定的原子命题称为命题变元（PropositionalVariable）。命题常元、命题变元有相对的过程和环境，在这个过程和环境下，例如：C只表示:中国的首都是北京B只表示:中国的首都是南京P可以是：中国的首都是北京，中国的首都是南京，中国的首都是武汉，中国的首都是南望山等,1.1命题与联结词,1.1.2命题联结词及真值表否定词“”（或“”）否定词（Negation）是一元联结词。相当于自然语言中的“非”、“不”等，真值表如右图。,1,0,1.1命题与联结词,合取词“”合取词（Conjunction）是二元联结词。相当于自然语言中的“与”、“并且”、“而且”、“也”等，真值表如右图。,0,0,0,1,1.1命题与联结词,析取词“”析取词（Disjunction）是二元联结词。相当于自然语言中的“或”、“要么要么”等，真值表如右图。,1.1命题与联结词,蕴含词“”蕴含词（Implication）是二元联结词。相当于自然语言中的“若则”、“如果就”、“只有才”，真值表如右图。,1,0,1,1,1.1命题与联结词,等价词“”等价词（Equivalence）是二元联结词。相当于自然语言中的“等价”、“当且仅当”、“充要条件”等，真值表如右图。,1.1命题与联结词,我们给联结词规定优先级顺序：的优先级最高，接着，和最低同级从左到右结合括号强制结合。(PQR)(RS),1.2命题公式,1.2.1命题公式与命题符号化定义1.3命题公式（PropositionalFormula）归纳定义如下：（1）0、1、命题常元、命题变元是命题公式；（2）如果是命题公式，则也是命题公式；（3）如果和是命题公式，则，均是命题公式；（4）只有有限次地利用（1）（3）形成的符号串才是命题公式。,1.2命题公式,例如，(PQ)，P(PQ)等都是命题公式，而CPQ，RP等不是命题公式。命题逻辑里讨论的对象是命题公式，而日常生活中的推理问题是用自然语言描述的，因此要进行推理演算必须先把自然语言符号化（或形式化）成逻辑语言，即命题公式。然后再根据逻辑演算规律进行推理演算。,1.2命题公式,例1.2将下列用自然语言描述的命题符号化。（1）我和他既是弟兄又是同学。（2）我和你之间至少有一个要去海南岛。（3）如果他没来见你，那么他或者是生病了，或者是不在本地。（4）n是偶数当且仅当它能被2整除。,P:我和他是弟兄,Q:我和他是同学,PQ,P:我去海南岛,Q:你去海南岛,PQ,P:他没来见你,Q:他是生病了,R:他不在本地,P(QR),P:n是偶数,Q:n能被2整除,PQ,1.2命题公式,从以上例子中可以看出，所谓命题符号化是指把一个用自然语言叙述的命题相应地写成由命题变元、联结词和圆括号表示的命题公式。符号化应该注意下列事项：确定给定句子是否为命题。句子中连词是否为命题联结词。要正确地表示原子命题和适当选择命题联结词。,1.2命题公式,1.2.2命题公式的分类变元组：设n元公式中所含有的不同命题元为P1,P2,Pn，我们把这些命题变元组成的变元组(P1,P2,Pn)称为的变元组。完全指派：的变元组(P1,P2,Pn)的任意一组确定的值都称为该公式关于该变元组(P1,P2,Pn)的完全指派。,1.2命题公式,部分指派：如果仅对变元组中部分变元赋以确定的值，其余变元没有赋以确定的值，则这样的一组值称为该公式关于该变元组(P1,P2,Pn)的部分指派。例1.3设=(P(QR)S，其变元组为(P,Q,R,S)。(P,Q,R,S)=(1,0,1,1)为的完全指派，(P,Q,R,S)=(0,0,1,S)为的部分指派。,1.2命题公式,定义1.4对于任一公式，凡使得为真的指派，不管是完全指派还是部分指派，都称为的成真指派，凡使得为假的指派，也不管是完全指派还是部分指派，都称为的成假指派。例1.4设=(P(QR)(RS)，则(P,Q,R,S)=(0,1,0,1)，(0,1,0,S)，(1,0,1,0)成真指派：(0,1,0,1)，(0,1,0,S)成假指派：(1,0,1,0),1.2命题公式,子公式（SubFormula）：设为命题公式，为中的一个连续的符号串，且为命题公式，则称为的子公式。例如，设公式=(PQ)(P(QR)，则(PQ)，(QR)，(P(QR)是的子公式(PQ)，(P(Q，(QR)不是的子公式QP？,1.2命题公式,用归纳法不难证明，对于含有n个命题变元的公式，有2n个完全指派，即在该公式的真值表中有2n行。为方便构造真值表，特约定如下：命题变元按字典序排列。对每个指派，以二进制数从小到大或从大到小顺序列出。若公式较复杂，可先列出各子公式的真值(若有括号，则应从里层向外层展开)，最后列出所求公式的真值。,1.2命题公式,例1.5利用真值表求命题公式(P(QR)的成真指派和成假指派。,00001000,11110111,01110111,1.2命题公式,重言式/永真式（Tautology）：若公式的所有完全指派均是成真指派，则公式称为重言式或永真式。矛盾式/永假式（Absurdity）：若公式的所有完全指派均是成假指派，则公式称为矛盾式或永假式。可满足式（Contingency）：若公式中有成真指派，则公式称为可满足式。,1.2命题公式,对定义的几点说明1）是可满足式的等价定义是：至少存在一个成真指派。2）重言式一定是可满足式，但反之不真。因而，若公式是可满足式，且它至少存在一个成假指派，则称为非重言式的可满足式。,1.2命题公式,3）真值表可用来判断公式的类型：若真值表最后一列全为1，则公式为重言式；若真值表最后一列全为0，则公式为矛盾式；若真值表最后一列中至少有一个1，则公式为可满足式。,1.2命题公式,例1.6判断下列公式的类型。(1)(PQ)Q解令=(PQ)Q,0001,1111,1.2命题公式,(2)(QP)(PQ)解令=(QP)(PQ),1011,0100,0000,1.2命题公式,(3)(PQ)(PQR)解令=(PQ)(PQR),11001111,00010000,00110000,1.3等值演算,1.3.1等值式定义1.8设，是两个命题公式，若，构成的等价式为重言式，则称公式与是等值（Equivalent）的，记作。,1.3等值演算,注意：定义中给出的符号与是两个完全不同的符号。不是命题联结词而是公式间的关系符号，不表示一个公式，即不代表命题，它表示公式与公式有等值关系，而是命题联结词，是一个公式，表示某个命题。然而这两者之间有密切的联系，即的充要条件是公式为重言式。,1.3等值演算,判断两个公式与是否等值，其中最直接的方法是用真值表法判断是否为重言式。例1.7判断(PQ)与PQ这两个命题公式是否等值。,1.3等值演算,下面给出16组重要的等值式（在后面的推理演算中以大写字母E加以引用），这些等值式也称作命题定律，其正确性可以用真值表加以证明。（1）双重否定律()（2）等幂律，,1.3等值演算,（3）交换律，（4）结合律()()，()()（5）分配律()()()（对的分配律）()()()（对的分配律）,1.3等值演算,（6）德摩根律()，()（7）吸收律()，()（8）零一律11，00,1.3等值演算,（9）同一律0，1（10）排中律1（11）矛盾律0（12）蕴含等值式,1.3等值演算,（13）假言易位（14）等价等值式()()，()()（15）等价否定等值式（16）归谬论()(),1.3等值演算,例1.8证明蕴含等值式。证明,1.3等值演算,1.3.2等值演算及几个重要定理由已知的等值式推演出另外一些等值式的过程称为等值演算。定义1.9设是一个命题公式，P1,P2,Pn是其中出现的所有命题变元。（1）用某些公式代换中的某些命题变元；（2）若用公式A代换Pi，则必须用A代换中所有的Pi。那么，由此而得到的新公式叫做公式的一个代换实例。,1.3等值演算,例如，设公式=P(RP)用QS代换其中P，可得公式=(QS)(R(QS)，公式是的一个代换实例。定理1.1（代入定理）对于重言式中的任一命题变元出现的每一处均用同一命题公式代入，得到的仍是重言式。,1.3等值演算,于是，若对于等值式中的任一命题变元出现的每一处均用同一命题公式代入，则仍得到等值式。定理1.2（置换定理）设A是公式的一个子公式且AB。如果将公式中的子公式A置换成公式B之后，得到的公式是，则。,1.3等值演算,比较代入定理和置换定理的区别:,1.3等值演算,例1.9用等值演算法证明(PQ)R(PR)(QR)。证明(PQ)R(PQ)R（蕴含等值式，置换定理）(PQ)R（德摩根律，置换定理）(PR)(QR)（分配律，置换定理）(PR)(QR)（蕴含等值式，置换定理）(PR)(QR)（蕴含等值式，置换定理）,1.3等值演算,例1.10用等值演算法判断下列公式的类型。（1）(PQ)P)Q解(PQ)P)Q(PQ)P)Q(PQ)P)Q(PQ)P)Q(PQ)P)Q(PP)(QP)Q(1(QP)Q(QQ)P1P1因此该公式是重言式。,1.3等值演算,（2）(P(PQ)R解(P(PQ)R(PPQ)R(PPQ)R0R0因此该公式是矛盾式。,1.3等值演算,（3）P(PQ)P)Q)解P(PQ)P)Q)P(PQ)P)Q)P(PP)(QP)Q)P(0(QP)Q)P(QPQ)P1P从最后结果可以看出该公式既不是重言式，也不是矛盾式，而是可满足式。,1.3等值演算,练习化简公式(PQ)(PQ),1.3等值演算,例1.11设有A，B，C，D四人做百米竞赛，观众甲，乙，丙分别对比赛的名次进行了预测：甲说C第一，B第二；乙说C第二，D第三；丙说A第二，D第四；比赛结束后发现甲，乙，丙每人报告的情况都是各对一半，试问实际名次如何（无并列者）？,1.3等值演算,解设Pi，Qi，Ri，Si分别表示A，B，C，D是第i（i=1,2,3,4）名，由于甲，乙，丙每人报告的情况都各对一半，故有下面三个等值式：(R1Q2)(R1Q2)1(R2S3)(R2S3)1(P2S4)(P2S4)1因为重言式的合取仍为重言式，所以1。即1(R1Q2)(R1Q2)(R2S3)(R2S3)(R1Q2R2S3)(R1Q2R2S3)(R1Q2R2S3)(R1Q2R2S3),1.3等值演算,由于C不能既第一又第二，B和C不能并列第二，所以R1Q2R2S30R1Q2R2S30于是得(R1Q2R2S3)(R1Q2R2S3)1再将与合取得1，即1(P2S4)(P2S4)(R1Q2R2S3)(R1Q2R2S3)(P2S4R1Q2R2S3)(P2S4R1Q2R2S3)(P2S4R1Q2R2S3)(P2S4R1Q2R2S3),1.3等值演算,由于A，B不能同时第二，D不能第三又第四，所以P2S4R1Q2R2S30P2S4R1Q2R2S30P2S4R1Q2R2S30于是可得P2S4R1Q2R2S31因此C第一，A第二，D第三，B第四。,1.3等值演算,定义1.10如果命题公式中只出现命题变元、命题常元、命题联结词、和，则称为限制性命题公式。定义1.11在限制性公式中，将联结词换成，将换成，将0换成1，将1换成0，所得到的公式称为的对偶式，记为*。,1.3等值演算,显然，和*互为对偶式。例如，公式(PQ)(R)与公式(PQ)(R)互为对偶式。定理1.3设和*是互为对偶的两个公式，P1,P2,Pn是其命题变元，则(P1,P2,Pn)*(P1,P2,Pn)定理1.4（对偶定理）设(P1,P2,Pn)和(P1,P2,Pn)是两个公式，若，则*。,1.4范式,原子命题“P”及其否定“P”统称文字。文字或者一些文字的合取称为质合取式。文字或者一些文字的析取称为质析取式(或称子句)。P与P称为互补对。例如，P，P，PQ，PQR等都是质合取式，P，Q，PQ，PQR等都是质析取式。,1.4范式,定理1.5（1）质合取式为矛盾式的充要条件：它包含有一个互补对；（2）质析取式为重言式的充要条件：它包含有一个互补对。,1.4范式,1.4.1析取范式与合取范式定义1.12若干个质合取式的析取式称为析取范式。亦即该公式具有形式12n，其中i(i=1,2,n)为质合取式。定义1.13若干个质析取式的合取式称为合取范式。亦即该公式具有形式12n，其中i(i=1,2,n)为质析取式。,1.4范式,例如，命题公式(PQ)(PQ)是析取范式，而命题公式(PR)(PQR)(PR)是合取范式。,1.4范式,定理1.6（范式存在定理）任一命题公式都存在着与之等值的析取范式和合取范式。下面给出求任一公式的析取范式和合取范式的步骤:（1）利用蕴含等值式和等价等值式消去公式中的联结词“”和“”；（2）利用德摩根律和双重否定律将联结词“”向内深入，使之只作用于命题变元；（3）利用分配律将公式化为所需要的范式。,1.4范式,例1.12求(PQ)R)P的析取范式和合取范式。解（1）求合取范式(PQ)R)P(PQ)R)P（消去）(PQ)R)P(PQ)R)P（深入）(PQ)R)P(PQ)R)P(PQP)(RP)（对的分配律）再利用交换律和等幂律得(PQP)(RP)(PQ)(RP)可见，(PQ)(RP)也是原公式的合取范式，这说明与某个命题公式等值的合取范式不是惟一的。,1.4范式,（2）析取范式用对的分配律就可得到析取范式，即(PQ)R)P(PQ)R)P(PR)(QR)P(对分配律)最后结果为原公式的析取范式。利用交换律和吸收律得P(QR)，此公式也是原公式的析取范式，由此可见，与命题公式等值的析取范式也不是惟一的。,1.4范式,利用析取范式和合取范式可以判定一个命题公式是重言式还是矛盾式。定理1.7（1）公式为重言式的充要条件是：的合取范式中每一质析取式至少包含一个互补对；（2）公式为矛盾式的充要条件是：的析取范式中每一质合取式至少包含一个互补对。,1.4范式,例1.13判别公式(PQ)P)Q是否为重言式或矛盾式。解(PQ)P)Q(PQ)P)Q(PQ)PQ(PQ)PQ(PPQ)(QPQ)在公式的合取范式中，每一个质析取式均含有互补对，因此原式为重言式。,1.4范式,1.4.2主析取范式与主合取范式定义1.14在含n个命题变元的质合取式（质析取式）中，若每个命题变元与其否定不同时存在，而二者之一必出现且仅出现一次，且第i个命题变元或其否定出现在从左算起的第i位上(若命题变元无下标,则按字典顺序排序)，这样的质合取式（质析取式）称为极小项（极大项）。,1.4范式,n个命题变元共可产生2n个不同的极小项，其中每个极小项都有且仅有一个成真指派。若在极小项中，将命题变元看成1，命题变元的否定看成0，则每个极小项惟一地对应一个二进制数，若把该二进制数转化成十进制数为i，并将所对应极小项记作mi，类似地，n个命题变元共可产生2n个不同的极大项，每个极大项只有一个成假指派，将其对应的十进制数i做极大项的下标，记作Mi。,1.4范式,例如，两个命题变元P,Q共可产生4个极小项，也可以产生4个极大项。类似地，由三个命题变元P,Q,R共可产生8个极小项，也可以产生8个极大项。定理1.8设mi和Mi是命题变元P1,P2,Pn形成的极小项和极大项，则miMi，Mimi,1.4范式,定义1.15设命题公式中含n个命题变元，如果的析取范式（合取范式）中的质合取式（质析取式）都是极小项（极大项），则称该析取范式（合取范式）为的主析取范式（主合取范式）。,1.4范式,例1.15求公式(PR)(PQ)的主析取范式和主合取范式。,1.4范式,公式所在的列有三个1，它们分别对应于编码001，110，111，因此所求的主析取范式为：m1m6m7即(PQR)(PQR)(PQR)。公式所在的列有五个0，它们分别对应于编码000，010，011，100，101，因此所求的主合取范式为：M0M2M3M4M5即(PQR)(PQR)(PQR)(PQR)(PQR)。,1.4范式,定理1.9任何一个不为矛盾式（重言式）的命题公式都存在着与之等值的主析取范式（主合取范式），并且是惟一的。从定理中可看出，矛盾式的主析取范式是空公式，定义它为0，其主合取范式必由所有极大项的合取构成，同理重言式的主合取范式也是空公式，定义它为1，其主析取范式必由所有极小项的析取构成。因此，利用一个公式的主范式可以判别这个公式是否为重言式或矛盾式。,1.4范式,求一个给定公式的主析取范式和主合取范式除了可以用真值表法，还可以用类似于求范式的方法，下面给出求解步骤：（1）利用蕴含等值式和等价等值式消去公式中的联结词“”和“”；（2）利用德摩根律和双重否定律将联结词“”向内深入，使之只作用于命题变元；（3）利用分配律将公式化为析取范式或合取范式；,1.4范式,（4）利用同一律消去矛盾的质合取式(重言的质析取式)；（5）利用等幂律消去相同的质合取式(质析取式)以及质合取式(质析取式)中相同的合取项(析取项)；（6）利用同一律、分配律将不包含某一命题变元的质合取式(质析取式)置换为包含这一命题变元的质合取式(质析取式)，直到每一质合取式(质析取式)成为极小项(极大项)为止。例如PQPQ(RR)(PQR)(PQR)。,1.4范式,例1.15利用求主范式的方法判别公式(PQ)P)Q是否为重言式或矛盾式。解求公式的主析取范式为：(PQ)P)Q(PQ)P)Q(PQ)PQ(PQ)PQ(PQ)(P(QQ)(PP)Q)(PQ)(PQ)(PQ)(PQ)m0m1m2m3由于公式的主析取范式包含了所有的极小项，因此原公式为重言式。,1.4范式,当然，利用求主合取范式也可以得到同样的结论，即：(PQ)P)Q(PQ)P)Q(PQ)PQ(PQ)PQ(PPQ)(QPQ)111由于公式的主合取范式是一个空公式，因此原公式为重言式。,1.4范式,例1.16求公式(PR)(PQ)的主析取范式和主合取范式。解令=(PR)(PQ)（1）求主合取范式(PR)(PQ)(PQ)(P(QQ)R)(PQ(RR)(PQ(RR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)M0M2M3M4M5此即的主合取范式,1.4范式,（2）求主析取范式显然，余下的极大项的合取式便是的主合取范式，即(PQR)(PQR)(PQR)对求否定并利用定理1.8，便得到的主析取范式为：()(PQR)(PQR)(PQR)m1m6m7由上可以看出，公式既不是重言式也不是矛盾式，因而是一个可满足式。,1.4范式,例1.17某单位要在甲，乙，丙三人中选派12名出差，选派时需满足如下条件：（1）若甲去，则丙同去；（2）若乙去，则丙不能去；（3）若丙不去，则甲或乙可以去。问有几种选派方案？解设P：派甲去出差；Q：派乙去出差；R：派丙去出差。由已知条件可得公式(PR)(QR)(R(PQ),1.4范式,经过演算可得(PR)(QR)(R(PQ)(PQR)(PQR)(PQR)该公式主析取范式包含3个极小项，因此可知有3种选派方案:丙去，甲和乙不去；乙去，甲和丙不去；甲和丙去，乙不去。,1.5联结词的完备集,定义1.16称F：0,1n0,1为n元真值函数（TruthValueFunction）。在这个定义中，F的自变量为n个命题变元，定义域0,1n=000,001,111，即0,1n中元素为由0,1组成的全体长为n的符号串，值域为0,1。n个命题变元共可构成22n个不同的真值函数。含命题变元P的1元真值函数共有4个。含两个命题变元P,Q的真值函数共有16个。,1.5联结词的完备集,定义1.17设S是一个联结词集合，如果任何n(n1)元真值函数都可以由仅含S中的联结词构成的公式表示，则称S是联结词完备集（AdequateSetofConnectives）。定理1.10S=，是联结词完备集。证因为任何n(n1)元真值函数都与惟一的一个主析取范式等值，而在主析取范式中仅含联结词，所以S=，是联结词完备集。,1.5联结词的完备集,推论1.1以下联结词集都是完备集：（1）S1=，（2）S2=，（3）S3=，（4）S4=，（5）S5=，,1.5联结词的完备集,证（1），（2）的成立是显然的。（3）由于S=，是联结词完备集，因而任何真值函数都可以由仅含S中的联结词的公式表示。同时对于任意公式A和B，AB(AB)(AB)，因而任意真值函数都可以由仅含S3=，中的联结词的公式表示，所以S3是联结词完备集。,1.5联结词的完备集,可以证明恒取0值的真值函数（即与矛盾式等值的真值函数）不能用仅含联结词集，中的联结词的公式表示，因而，不是联结词完备集。由此可知，等也都不是联结词完备集。所以，的任何子集都不是联结词完备集。,1.5联结词的完备集,定义1.18设P，Q为两个命题，复合命题“P与Q的否定式”（“P或Q的否定式”）称为P，Q的与非式（或非式），记作PQ（PQ）。符号（）称作为与非联结词（或非联结词）。PQ为真当且仅当P与Q不同时为真（PQ为真当且仅当P与Q同时为假）。由定义不难看出PQ(PQ)，PQ(PQ),1.5联结词的完备集,定理1.11，都是联结词完备集。证已知，为联结词完备集，因而只需证明其中的每个联结词都可以由定义即可。而P(PP）PP(a)PQ(PQ)(PQ)(PQ)(PQ)(b)PQ(PQ)(PQ)PQ(PP)(QQ)(c)由(a)(b)可知，是联结词完备集，类似可证是联结词完备集。,1.6命题逻辑的推理演算,推理：也称论证，由已知的命题得到新命题的思维过程前提：推理所根据的已知命题结论：从前提出发应用推理规则推出的新命题在数理逻辑中，集中注意的是研究和提供用来从前提导出结论的推理规则和论证原理，与这些规则有关的理论称为推理理论。,1.6命题逻辑的推理演算,1.6.1推理形式定义1.19设1,2,n,都是命题公式。若(12n)是重言式，则称由前提1,2,n推出的推理是有效的或正确的，并称是1,2,n的有效结论或逻辑结果，记为12n或1,2,n，记号12n也称为重言蕴含或推理形式。,1.6命题逻辑的推理演算,关于定义1.16还需做以下说明：（1）由前提1,2,n推结论的推理是否正确与各前提的排列次序无关，因而前提中的公式不一定是序列，而是一个有限公式集合。若推理是正确的，则记为12n，否则记为12n。,1.6命题逻辑的推理演算,（2）符号与是两个完全不同的符号，它们的区别与联系类似于和的关系。不是命题联结词而是公式间的关系符号，而是命题联结词。这两者之间有密切的联系，即的充要条件是公式为重言式。,1.6命题逻辑的推理演算,（3）必须把推理的有效性和结论的真实性区别开。有效的推理不一定产生真实的结论，产生真实结论的推理过程未必一定是有效的。再说，有效的推理中可能包含假的前提；而无效的推理却可能包含真的前提。,1.6命题逻辑的推理演算,可见，推理的有效性是一回事，前提与结论的真实与否是另一回事。所谓推理有效，指它的结论是它的前提的合乎逻辑的结果，也即，如果它的前提都为真，那么所得结论也必然为真，而并不是要求前提或结论一定为真或为假。如果推理是有效的话，那么不可能它的前提都为真时而它的结论为假。,1.6命题逻辑的推理演算,例1.18写出下述推理关系的推理形式。下午小王或去看电影或去游泳。他没去看电影。所以，他去游泳了。解设P：小王下午去看电影；Q：小王下午去游泳。前提：PQ，P结论：Q推理形式为:(PQ)PQ,1.6命题逻辑的推理演算,1.6.2推理规则1前提引入规则(P)在推理过程中，可以随时引入已知的前提。2结论引用规则(T)在推理过程中，前面已推出的有效结论都可作为后续推理的前提引用。,1.6命题逻辑的推理演算,3置换规则(R)在推理过程中，命题公式中的子公式都可以用与之等值的命题公式置换，得到证明的公式序列的另一公式。4代入规则(S)在推理过程中，重言式中的任一命题变元都可以用一命题公式代入，得到的仍是重言式。,1.6命题逻辑的推理演算,1.6.3推理定律定理1.12设，是两个命题公式，当且仅当且。定理1.13设，是命题公式，若且，则。定理1.14设，是命题公式，则的充要条件是是矛盾式。,1.6命题逻辑的推理演算,下面列出一些常用的推理定律（在后面的推理演算中以大写字母I加以引用）。（1）化简律，（2）附加律，（3）假言推理（又称分离规则）(),1.6命题逻辑的推理演算,（4）假言三段论()()()（5）等价三段论()()()（6）析取三段论()（7）拒取式()（8）二难推理()()(),1.6命题逻辑的推理演算,（9）,（10），（11）()，()（12）()()()（13）()()，()()（14），,1.6命题逻辑的推理演算,对于以上推理定律还有几点需要说明：（1）推理定律中出现的，均代表任意的命题公式；（2）若一个推理形式与某条推理定律对应一致，则不用证明就可判定这个推理是正确的，但需说明依据；（3）根据定理1.10，在1.3节中给出的16组等值式中的每一条公式都可以派生出两条推理定律。例如，双重否定律()产生两条推理定律()和()。,1.6命题逻辑的推理演算,1.6.4推理方法1真值表法设P1,P2,Pn是出现于前提1,2,m和结论中的全部命题变元，对P1,P2,Pn的所有情况作完全指派，这样能对应地确定1,2,m和的所有真值，列出这个真值表，即可判断如下推理形式是否成立：12m或1,2,m若从真值表上找出1,2,m均为1的行，对应的行也为1，则上式成立。或者，若为0的行，对应的行中1,2,m至少有一个0，则上式也成立。,1.6命题逻辑的推理演算,例1.20用真值表法证明(PQ)(PQ)P。解列出(PQ)(PQ)P的真值表,1.6命题逻辑的推理演算,从表中可以看出PQ与(PQ)均为1的行是第一、二行，此两行P也为1，所以该推理形式正确。当然也可以从另外一个方面来判断，表中P为0的行是第三、四行，此两行中PQ与(PQ)至少有一个为0，从而也可以判断出该推理形式正确。,1.6命题逻辑的推理演算,2直接证法直接证法就是由一组前提，利用前面的四条推理规则，根据已知的命题等值公式（1.3节中的16组公式）和推理定律，推演而得到有效的结论。,1.6命题逻辑的推理演算,例1.21证明(PQ)(PR)(QS)SR证明（1）PQP（2）PQR,E,(1)（3）QSP（4）PST,I,(2),(3)（5）SPR,E,(4)（6）PRP（7）SRT,I,(5),(6)（8）SRR,E,(7),1.6命题逻辑的推理演算,3.间接证法间接证法主要有两种，一种就是我们经常用的反证法，另外一种称之为CP规则。1）反证法要证明推理形式12m成立（记作），根据定理1.14可知，只须证明是矛盾式。因此，只须把作为附加前提加入推理过程中，推出矛盾即可。,1.6命题逻辑的推理演算,例1.22证明PQ，QR，RSP证明用反证法，把(P)作为附加前提加入到前提的集合中去，证明由此导致矛盾。(1)(P)P(附加)(2)PR,E,(1)(3)PQP(4)QT,I,(2),(3)(5)QRP(6)RT,I,(4),(5)(7)RSP(8)RT,I,(7)(9)RRT,I,(6),(8),矛盾因此，假设不成立，原推理形式正确。,1.6命题逻辑的推理演算,2）CP规则欲证()，即证()，亦即()永真。因为()()()()，所以若将作为附加前提，证明成立，即得证()成立。这一证明方法称为CP规则。,1.6命题逻辑的推理演算,例1.23验证下述推理是否正确。或者逻辑学难学，或者有许多学生喜欢它；如果数学容易学，那么逻辑学并不难学。因此如果许多学生不喜欢逻辑，那么数学并不容易学。解求解上述类型的推理问题，应先将命题符号化，然后写出前提、结论和推理形式，最后进行判断。令P：逻辑学难学；Q：有许多学生喜欢逻辑学；R：数学容易学。,1.6命题逻辑的推理演算,前提：PQ，RP结论：QR推理形式：PQ，RPQR(1)QP(附加)(2)PQP(3)PT,I,(1),(2)(4)RPP(5)RT,I,(3),(4)(6)QRCP因此整个推理正确。,1.7命题逻辑在计算机科学中的应用,逻辑难题可以用逻辑推理解决的难题称为逻辑难题。求解逻辑难题是实践逻辑规则的一种好方法。同样，涉及用于执行逻辑推理的计算机程序通常也使用著名的逻辑难题来演示它们的能力。许多人对求解逻辑难题感兴趣，有许多书和杂志也登载逻辑难题以供娱乐。,1.7命题逻辑在计算机科学中的应用,这是著名物理学家爱因斯坦出过的一道题。一个土耳其商人，想找一个十分聪明的助手协助他经商，有两个人前来应聘。这个商人为了试一试哪一个聪明些，就把两个人带进一间漆黑的屋子里，他打开电灯后说：“这张桌子上有五顶帽子，两顶是红色的，三顶是黑色的。现在，我把灯关掉，而且把帽子摆的位置弄乱，然后我们三个人每人摸一顶帽子戴在头上，在我开灯后，请你们尽快地说出自己头上戴的帽子是什么颜色的。”说完之后，商人将电灯关掉，然后三人都摸了一顶帽子戴在头上，同时商人将余下的两顶帽子藏了起来接着把电灯打开，这时那两个应试者看到商人头上戴的是一顶红帽子，过了一会儿，其中一个人便喊到：“我戴的是黑帽子。”请问这个人猜得对吗？是怎么推导出来的？,1.7命题逻辑在计算机科学中的应用,分析1：如果我戴的也是红帽子，那么，B就马上可以猜到自己是戴黑帽子(因为红帽子只有两顶)；而现在B并没有立刻猜到，可见，我戴的不是红帽子。可见，B的反应太慢了。,1.7命题逻辑