《数理逻辑.ppt》由会员分享，可在线阅读，更多相关《数理逻辑.ppt（140页珍藏版）》请在三一办公上搜索。
1、命题逻辑谓词逻辑非经典逻辑,数理逻辑,数理逻辑概述,数理逻辑是用数学的方法研究思维规律的一门学科。由于它使用了一套符号，简洁的表达出各种推理的逻辑关系，因此数理逻辑一般又称为符号逻辑。数理逻辑和计算机的发展有着密切的联系，它为机器证明、自动程序设计、计算机辅助设计等计算机应用和理论研究提供必要的理论基础。,数理逻辑的发展前期,前史时期古典形式逻辑时期：亚里斯多德的直言三段论理论初创时期逻辑代数时期（17世纪末）(1)资本主义生产力大发展，自然科学取得了长足的进步，数学在认识自然、发展技术方面起到了相当重要的作用。(2)人们希望使用数学的方法来研究思维，把思维过程转换为数学的计算。,数理逻辑的发
2、展前期,(3)莱布尼兹(Leibniz,16461716)完善三段论，提出了建立数理逻辑或者说理性演算的思想：提出将推理的正确性化归于计算，这种演算能使人们的推理不依赖于对推理过程中的命题的含义内容的思考，将推理的规则变为演算的规则。使用一种符号语言来代替自然语言对演算进行描述，将符号的形式和其含义分开。使得演算从很大程度上取决与符号 的组合规律，而与其含义无关。,数理逻辑的发展前期,(4)布尔(G.Boole,18151864)代数：将有关数学运算的研究的代数系统推广到逻辑领域，布尔代数既是一种代数系统，也是一种逻辑演算。,数理逻辑的奠基时期,弗雷格(G.Frege,18481925)：概念
3、语言一种按算术的公式语言构成的纯思维公式语言(1879)的出版标志着数理逻辑的基础部分命题演算和谓词演算的正式建立。皮亚诺(Giuseppe Peano,18581932)：用一种新的方法陈述的算术原理(1889)提出了自然数算术的一个公理系统。,数理逻辑的奠基时期,罗素(Bertrand Russell,18721970)：数学原理(与怀特黑合著，1910,1912,1913)从命题演算和谓词演算开始，然后通过一元和二元命题函项定义类和关系的概念，建立了抽象的类演算和关系演算。由此出发，在类型论的基础上用连续定义和证明的方式引出了数学（主要是算术）中的主要概念和定理。,数理逻辑的奠基时期,逻
4、辑演算的发展：甘岑(G.Gentzen)的自然推理系统(Natural Deduction System)，逻辑演算的元理论：公理的独立性、一致性、完全性等。各种各样的非经典逻辑的发展：路易斯(Lewis,18831964)的模态逻辑，实质蕴含怪论和严格蕴含、相干逻辑等，卢卡西维茨的多值逻辑等。,第1章 命题逻辑,命题逻辑研究的是以原子命题为基本单位的推理演算，其特征在于，研究和考查逻辑形式时，我们把一个命题只分析到其中所含的原子命题成分为止。通过这样的分析可以显示出一些重要的逻辑形式，这种形式和有关的逻辑规律就属于命题逻辑。,第1章 命题逻辑,内容提要：1.命题逻辑的基本概念、命题联结词 2
5、.命题公式、自然语言的形式化 3.命题公式的等值和蕴含 4.范式 5.联结词的完备集 6.推理理论 7.命题逻辑在计算机科学中的应用,1.1 命题与联结词,1.1.1 命题与命题变元定义1.1 能够分辨真假的陈述句叫做命题（Proposition）。该定义有两层含义：(1)命题是陈述句。其他的语句，如疑问句、祈使句、感叹句均不是命题；(2)这个陈述句表示的内容可以分辨真假，而且不是真就是假，不能不真也不假，也不能既真又假,1.1 命题与联结词,作为命题的陈述句所表示的判断结果称为命题的真值，真值只取两个值：真或假。凡是与事实相符的陈述句是真命题，而与事实不符合的陈述句是假命题。通常用1（或字母
6、T）表示真，用0（或字母F）表示假。,1.1 命题与联结词,例1.1 判断下列语句是否为命题，并指出其真值。,4是素数。x大于y。充分大的偶数等于两个素数之和。今天是星期二吗？请不要吸烟！这朵花真美丽啊！我正在说假话。,是，假命题不是，无确定的真值是，真值客观存在不是，是疑问句不是，祈使句不是，感叹句不是，悖论,1.1 命题与联结词,注意：一个语句本身是否能分辨真假与我们是否知道它的真假是两回事。也就是说，对于一个句子，有时我们可能无法判定它的真假，但它本身却是有真假的，那么这个语句是命题，否则就不是命题。感叹句、疑问句、祈使句都不能称为命题。判断结果不唯一确定的陈述句不是命题。陈述句中的悖论
7、不是命题。,1.1 命题与联结词,命题的分类原子命题（Automic Proposition）：是指不能再分解为更简单命题的命题；复合命题（Compound Proposition）：是指由若干命题用联结词组成的新命题。例如“雪是白的”是原子命题；“昨天下雨，而且打雷”，“如果明天天晴我就去打球或者游泳”都是复合命题。,1.1 命题与联结词,定义1.2 真值确定的原子命题称为命题常元（Propositional Constant），真值不确定的原子命题称为命题变元（Propositional Variable）。如果命题符号P代表命题常元则意味它是某个具体命题的符号化，如果P代表命题变元则意味
8、着它可指代任何具体命题。如果没有特别指明，通常来说命题符号P等是命题变元，即可指代任何命题。,1.1 命题与联结词,1.1.2 命题联结词及真值表否定词“”（或“”）否定词（Negation）是一元联结词。相当于自然语言中的“非”、“不”等，真值表如右图。,1.1 命题与联结词,合取词“”合取词（Conjunction）是二元联结词。相当于自然语言中的“与”、“并且”、“而且”、“也”等，真值表如右图。,1.1 命题与联结词,析取词“”析取词（Disjunction）是二元联结词。相当于自然语言中的“或”、“要么要么”等，真值表如右图。,1.1 命题与联结词,蕴含词“”蕴含词（Implicat
9、ion）是二元联结词。相当于自然语言中的“若则”、“如果就”、“只有才”，真值表如右图。,1.1 命题与联结词,等价词“”等价词（Equivalence）是二元联结词。相当于自然语言中的“等价”、“当且仅当”、“充要条件”等，真值表如右图。我们给联结词规定优先级顺序：的优先级最高，接着依次是，和。,1.2 命题公式,1.2.1 命题公式与命题符号化 定义1.3 命题公式（Propositional Formula）归纳定义如下：（1）命题变元是命题公式；（2）如果是命题公式，则也是命题公式；（3）如果和是命题公式，则，均是命题公式；（4）只有有限次地利用（1）（3）形成的符号串才是命题公式。,
10、1.2 命题公式,例如，(PQ)，P(PQ)等都是命题公式，而CPQ，RP等不是命题公式。命题逻辑里讨论的对象是命题公式，而日常生活中的推理问题是用自然语言描述的，因此要进行推理演算必须先把自然语言符号化（或形式化）成逻辑语言，即命题公式。然后再根据逻辑演算规律进行推理演算。,1.2 命题公式,例1.2 将下列用自然语言描述的命题符号化。（1）我和他既是弟兄又是同学。（2）我和你之间至少有一个要去海南岛。（3）如果他没来见你，那么他或者是生病了，或者是不在本地。（4）n是偶数当且仅当它能被2整除。,1.2 命题公式,从以上例子中可以看出，所谓命题符号化是指把一个用自然语言叙述的命题相应地写成由
11、命题变元、联结词和圆括号表示的命题公式。符号化应该注意下列事项：确定给定句子是否为命题。句子中连词是否为命题联结词。要正确地表示原子命题和适当选择命题联 结词。,1.2 命题公式,1.2.2 命题公式的分类变元组：设n元公式中所含有的不同命题元为P1,P2,Pn，我们把这些命题变元组成的变元组(P1,P2,Pn)称为的变元组。完全指派：的变元组(P1,P2,Pn)的任意一组确定的值都称为该公式关于该变元组(P1,P2,Pn)的完全指派。,1.2 命题公式,部分指派：如果仅对变元组中部分变元赋以确定的值，其余变元没有赋以确定的值，则这样的一组值称为该公式关于该变元组(P1,P2,Pn)的部分指派
12、。例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)和部分指派(P,Q,R,S)=(0,1,0,S)都是的成真指派，而指派(P,Q,R,S)=(1,0,1,0)为的成假指派。,1.2 命题公式,子公式（Sub Formula）
13、：设为命题公式，为中的一个连续的符号串，且为命题公式，则称为的子公式。例如，设公式=(PQ)(P(QR)，则(PQ)，(QR)，(P(QR)等都是的子公式，而(PQ)，(P(Q，(QR)等都不是的子公式，因为它们本身不是公式。,1.2 命题公式,用归纳法不难证明，对于含有n个命题变元的公式，有2n个完全指派，即在该公式的真值表中有2n行。为方便构造真值表，特约定如下：命题变元按字典序排列。对每个指派，以二进制数从小到大或从大到小顺序列出。若公式较复杂，可先列出各子公式的真值(若有括号，则应从里层向外层展开)，最后列出所求公式的真值。,1.2 命题公式,例1.5 利用真值表求命题公式(P(QR)
14、的成真指派和成假指派。,1.2 命题公式,重言式/永真式（Tautology）：若公式的所有完全指派均是成真指派，则公式称为重言式或永真式。矛盾式/永假式（Absurdity）：若公式的所有完全指派均是成假指派，则公式称为矛盾式或永假式。可满足式（Contingency）：若公式中有成真指派，则公式称为可满足式。,1.2 命题公式,对定义的几点说明 1）是可满足式的等价定义是：至少存在一个成真指派。2）重言式一定是可满足式，但反之不真。因而，若公式是可满足式，且它至少存在一个成假指派，则称为非重言式的可满足式。,1.2 命题公式,3）真值表可用来判断公式的类型：若真值表最后一列全为1，则公式为
15、重言式；若真值表最后一列全为0，则公式为矛盾式；若真值表最后一列中至少有一个1，则公式为可满足式。,1.2 命题公式,例1.6 判断下列公式的类型。(1)(PQ)Q解 令=(PQ)Q,1.2 命题公式,(2)(QP)(PQ)解 令=(QP)(PQ),1.2 命题公式,(3)(PQ)(PQR)解 令=(PQ)(PQR),1.3 等值演算,1.3.1 等值式 定义1.8 设，是两个命题公式，若，构成的等价式为重言式，则称公式与是等值（Equivalent）的，记作。,1.3 等值演算,注意：定义中给出的符号与是两个完全不同的符号。不是命题联结词而是公式间的关系符号，不表示一个公式，即不代表命题，它
16、表示公式与公式有等值关系，而是命题联结词，是一个公式，表示某个命题。然而这两者之间有密切的联系，即的充要条件是公式为重言式。,1.3 等值演算,判断两个公式与是否等值，其中最直接的方法是用真值表法判断是否为重言式。例1.7 判断(PQ)与PQ这两个命题公式是否等值。,1.3 等值演算,下面给出16组重要的等值式（在后面的推理演算中以大写字母E加以引用），这些等值式也称作命题定律，其正确性可以用真值表加以证明。（1）双重否定律()（2）等幂律，,1.3 等值演算,（3）交换律，（4）结合律()()，()()（5）分配律()()()（对的分配律）()()()（对的分配律）,1.3 等值演算,（6）
17、德摩根律()，()（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。那
18、么，由此而得到的新公式叫做公式的一个代换实例。,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)。
19、证明(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)P1P 1 因此该公式是重言式。,1.3 等值演算,（2）(P(PQ)R 解(P(PQ)R(PPQ)R(PPQ)R 0R 0因此该公式是矛盾式。,1.3 等值演算,（3）P(PQ)P)Q)解 P(PQ)P)Q
20、)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）名，由于甲，乙，丙每人报告的情况都各对一半，故有下面三个
21、等值式：(R1Q2)(R1Q2)1(R2S3)(R2S3)1(P2S4)(P2S4)1因为重言式的合取仍为重言式，所以1。即 1(R1Q2)(R1Q2)(R2S3)(R2S3)(R1Q2R2S3)(R1Q2R2S3)(R1Q2R2S3)(R1Q2R2S3),1.3 等值演算,由于C不能既第一又第二，B和C不能并列第二，所以 R1Q2R2S30 R1Q2R2S30于是得(R1Q2R2S3)(R1Q2R2S3)1再将与合取得1，即 1(P2S4)(P2S4)(R1Q2R2S3)(R1Q2R2S3)(P2S4R1Q2R2S3)(P2S4R1Q2 R2S3)(P2S4R1Q2R2S3)(P2 S4R1
22、Q2R2S3),1.3 等值演算,由于A，B不能同时第二，D不能第三又第四，所以 P2S4R1Q2R2S30 P2S4R1Q2R2S30 P2S4R1Q2R2S30于是可得 P2S4R1Q2R2S31因此C第一，A第二，D第三，B第四。,1.3 等值演算,定义1.10 如果命题公式中只出现命题变元、命题常元、命题联结词、和，则称为限制性命题公式。定义1.11 在限制性公式中，将联结词换成，将换成，将0换成1，将1换成0，所得到的公式称为的对偶式，记为*。,1.3 等值演算,显然，和*互为对偶式。例如，公式(PQ)(R)与公式(PQ)(R)互为对偶式。定理1.3 设和*是互为对偶的两个公式，P1
23、,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 若干个质合取
24、式的析取式称为析取范式。亦即该公式具有形式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）利用分配律将公式
25、化为所需要的范式。,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)，此公式也是原公式的析取范式，由此可见，
26、与命题公式等值的析取范式也不是惟一的。,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个命题变元的质合取式（质析取式）中，若
27、每个命题变元与其否定不同时存在，而二者之一必出现且仅出现一次，且第i个命题变元或其否定出现在从左算起的第i位上(若命题变元无下标,则按字典顺序排序)，这样的质合取式（质析取式）称为极小项（极大项）。,1.4 范式,n个命题变元共可产生2n个不同的极小项，其中每个极小项都有且仅有一个成真指派。若在极小项中，将命题变元看成1，命题变元的否定看成0，则每个极小项惟一地对应一个二进制数，若把该二进制数转化成十进制数为i，并将所对应极小项记作mi，类似地，n个命题变元共可产生2n个不同的极大项，每个极大项只有一个成假指派，将其对应的十进制数i做极大项的下标，记作Mi。,1.4 范式,例如，两个命题变元P
28、,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 即(P
29、QR)(PQR)(PQR)。公式所在的列有五个0，它们分别对应于编码000，010，011，100，101，因此所求的主合取范式为：M0M2M3M4M5 即(PQR)(PQR)(PQR)(PQR)(PQR)。,1.4 范式,定理1.9 任何一个不为矛盾式（重言式）的命题公式都存在着与之等值的主析取范式（主合取范式），并且是惟一的。从定理中可看出，矛盾式的主析取范式是空公式，定义它为0，其主合取范式必由所有极大项的合取构成，同理重言式的主合取范式也是空公式，定义它为1，其主析取范式必由所有极小项的析取构成。因此，利用一个公式的主范式可以判别这个公式是否为重言式或矛盾式。,1.4 范式,求一个给定
30、公式的主析取范式和主合取范式除了可以用真值表法，还可以用类似于求范式的方法，下面给出求解步骤：（1）利用蕴含等值式和等价等值式消去公式中的联结词“”和“”；（2）利用德摩根律和双重否定律将联结词“”向内深入，使之只作用于命题变元；（3）利用分配律将公式化为析取范式或合取范式；,1.4 范式,（4）利用同一律消去矛盾的质合取式(重言的质析取式)；（5）利用等幂律消去相同的质合取式(质析取式)以及质合取式(质析取式)中相同的合取项(析取项)；（6）利用同一律、分配律将不包含某一命题变元的质合取式(质析取式)置换为包含这一命题变元的质合取式(质析取式)，直到每一质合取式(质析取式)成为极小项(极大项
31、)为止。例如 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)11 1 由于公式的主合取范式是一个空公式，因此原公式为重言式。,1.4 范式,例1.16 求公式(P
32、R)(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 某单
33、位要在甲，乙，丙三人中选派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元真值函数（Truth Value Function）。在这个定义中，F的自变量
34、为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是联结词完备集（Adequate Set of Connectives）。定理1.10 S=，是联结词完备集。证 因为任何n(n1)元真值函数都与惟一的一个主析取范式等值，而在主析取范式中仅含联结词，所以S=，是联结词完
35、备集。,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值的真值函数（即与矛盾式等值的真值函数）不能用仅含联结词集，中的联结词的公式表示，因而，不是联结词完备集。由此可知，等也都不是联结词完备集。所以，的任何
36、子集都不是联结词完备集。,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)可知，是联结词
37、完备集，类似可证是联结词完备集。,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
38、还需做以下说明：（1）由前提1,2,n推结论的推理是否正确与各前提的排列次序无关，因而前提中的公式不一定是序列，而是一个有限公式集合。若推理是正确的，则记为12n，否则记为12n。,1.6 命题逻辑的推理演算,（2）符号与是两个完全不同的符号，它们的区别与联系类似于和的关系。不是命题联结词而是公式间的关系符号，而是命题联结词。这两者之间有密切的联系，即的充要条件是公式为重言式。,1.6 命题逻辑的推理演算,（3）必须把推理的有效性和结论的真实性区别开。有效的推理不一定产生真实的结论，产生真实结论的推理过程未必一定是有效的。再说，有效的推理中可能包含假的前提；而无效的推理却可能包含真的前提。,1
39、.6 命题逻辑的推理演算,可见，推理的有效性是一回事，前提与结论的真实与否是另一回事。所谓推理有效，指它的结论是它的前提的合乎逻辑的结果，也即，如果它的前提都为真，那么所得结论也必然为真，而并不是要求前提或结论一定为真或为假。如果推理是有效的话，那么不可能它的前提都为真时而它的结论为假。,1.6 命题逻辑的推理演算,例1.18 写出下述推理关系的推理形式。下午小王或去看电影或去游泳。他没去看电影。所以，他去游泳了。解 设P：小王下午去看电影；Q：小王下 午去游泳。前提：PQ，P 结论：Q 推理形式为:(PQ)PQ,1.6 命题逻辑的推理演算,1.6.2 推理规则 1前提引入规则(P)在推理过程
40、中，可以随时引入已知的前提。2结论引用规则(T)在推理过程中，前面已推出的有效结论都可作为后续推理的前提引用。,1.6 命题逻辑的推理演算,3置换规则(R)在推理过程中，命题公式中的子公式都可以用与之等值的命题公式置换，得到证明的公式序列的另一公式。4代入规则(S)在推理过程中，重言式中的任一命题变元都可以用一命题公式代入，得到的仍是重言式。,1.6 命题逻辑的推理演算,1.6.3 推理定律 定理1.12 设，是两个命题公式，当且仅当且。定理1.13 设，是命题公式，若且，则。定理1.14 设，是命题公式，则的充要条件是是矛盾式。,1.6 命题逻辑的推理演算,下面列出一些常用的推理定律（在后面
41、的推理演算中以大写字母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
42、.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。解
43、列出(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）PQ P（2）PQ R,E,(1)（3）QS P（4）PS T,
44、I,(2),(3)（5）SP R,E,(4)（6）PR P（7）SR T,I,(5),(6)（8）SR R,E,(7),1.6 命题逻辑的推理演算,3.间接证法 间接证法主要有两种，一种就是我们经常用的反证法，另外一种称之为CP规则。1）反证法 要证明推理形式12m成立（记作），根据定理1.14可知，只须证明是矛盾式。因此，只须把作为附加前提加入推理过程中，推出矛盾即可。,1.6 命题逻辑的推理演算,例1.22 证明PQ，QR，RSP 证明 用反证法，把(P)作为附加前提加入到前提的集合中去，证明由此导致矛盾。(1)(P)P(附加)(2)P R,E,(1)(3)PQ P(4)Q T,I,(2)
45、,(3)(5)QR P(6)R T,I,(4),(5)(7)RS P(8)R T,I,(7)(9)RR T,I,(6),(8),矛盾 因此，假设不成立，原推理形式正确。,1.6 命题逻辑的推理演算,2）CP规则 欲证()，即证()，亦即()永真。因为()()()()，所以若将作为附加前提，证明成立，即得证()成立。这一证明方法称为CP规则。,1.6 命题逻辑的推理演算,例1.23 验证下述推理是否正确。或者逻辑学难学，或者有许多学生喜欢它；如果数学容易学，那么逻辑学并不难学。因此如果许多学生不喜欢逻辑，那么数学并不容易学。解 求解上述类型的推理问题，应先将命题符号化，然后写出前提、结论和推理形
46、式，最后进行判断。令P：逻辑学难学；Q：有许多学生喜欢逻辑学；R：数学容易学。,1.6 命题逻辑的推理演算,前提：PQ，RP结论：QR推理形式：PQ，RPQR(1)QP(附加)(2)PQP(3)P T,I,(1),(2)(4)RP P(5)RT,I,(3),(4)(6)QR CP 因此整个推理正确。,1.7 命题逻辑在计算机科学中的应用,逻辑难题 可以用逻辑推理解决的难题称为逻辑难题。求解逻辑难题是实践逻辑规则的一种好方法。同样，涉及用于执行逻辑推理的计算机程序通常也使用著名的逻辑难题来演示它们的能力。许多人对求解逻辑难题感兴趣，有许多书和杂志也登载逻辑难题以供娱乐。,1.7 命题逻辑在计算机
47、科学中的应用,这是著名物理学家爱因斯坦出过的一道题。一个土耳其商人，想找一个十分聪明的助手协助他经商，有两个人前来应聘。这个商人为了试一试哪一个聪明些，就把两个人带进一间漆黑的屋子里，他打开电灯后说：“这张桌子上有五顶帽子，两顶是红色的，三顶是黑色的。现在，我把灯关掉，而且把帽子摆的位置弄乱，然后我们三个人每人摸一顶帽子戴在头上，在我开灯后，请你们尽快地说出自己头上戴的帽子是什么颜色的。”说完之后，商人将电灯关掉，然后三人都摸了一顶帽子戴在头上，同时商人将余下的两顶帽子藏了起来接着把电灯打开，这时那两个应试者看到商人头上戴的是一顶红帽子，过了一会儿，其中一个人便喊到：“我戴的是黑帽子。”请问这
48、个人猜得对吗？是怎么推导出来的？,1.7 命题逻辑在计算机科学中的应用,分析1：如果我戴的也是红帽子，那么，B就马上可以猜到自己是戴黑帽子(因为红帽子只有两顶)；而现在B并没有立刻猜到，可见，我戴的不是红帽子。可见，B的反应太慢了。,1.7 命题逻辑在计算机科学中的应用,分析2：设P1表示“猜对的人戴红帽子”；P2表示“猜对的人戴黑帽子”；Q1表示“另一个人戴红帽子”；Q2表示“另一个人戴黑帽子”；R1表示“商人戴红帽子”。现在知道，商人头上戴的是红帽子，即R1为真，又知道另一个人没有作出断定，即既不能断定Q1为真，也不能断定Q2为真。,1.7 命题逻辑在计算机科学中的应用,根据题设条件，可得
49、如下公式：R1P1Q2：如果商人和猜对的人戴的都是红帽子，那么另一个戴的就是黑帽子，因为红帽子只有两顶。R1Q1P2：如果商人和另一个戴的都是红帽子，那么猜对的人戴的就是黑帽子。P1P2：如果猜对的人戴的不是红帽子，那么他戴的就是黑帽子。Q1Q2：如果另一个人戴的不是红帽子，那么他戴的就是黑帽子。,1.7 命题逻辑在计算机科学中的应用,推演步骤如下：（1）P1（根据假设）；（2）R1（根据题设）（3）R1P1（合取构成）；（4）R1P1Q2（根据题设）（5）Q2（3）（4）分离）。这就是说，“另一个人戴黑帽子”这个判定是必然可以作出的，但是这与题设条件（即“另一个没有作出判定”）相矛盾，因此，
50、P1为假，即P1为真，故可得：（6）P1；（7）P1P2（根据题设）；（8）P2（6）（7）分离）。这就是说，“猜对的人戴着黑帽子”是真的，所以猜对的人肯定的说：“我戴的是黑帽子”。,习题课,知识回顾：1.基本概念 命题、命题常元、命题变元、原子命题、复合命题、命题联结词、命题公式、指派（完全、部分、成真、成假）、重言式（永真式）、矛盾式（永假式）、可满足式、析取范式、合取范式、主析取范式、主合取范式、对偶式、推理形式。,习题课,2.命题公式间的关系 等值、蕴含、命题定律、推理定律3.推理理论（规则、方法）,习题课,课堂练习题：1.将下列命题符号化。（1）刘晓月跑得快，跳得高。（2）老王是山东
