数理逻辑命题逻辑.ppt.ppt

数 理 逻 辑,南京师范大学泰州学院哲学系,绪论,数理逻辑 数理逻辑的产生与发展数理逻辑的研究内容预备知识（集合的基本知识、序偶与笛卡儿积、映射等）,数理逻辑是思维科学的一个分支，也是数学的一个分支。由于具有强有力的形式表达和形式分析的功能，数理逻辑在哲学、语言学、经济学、计算机科学、人工智能、决策学等多领域的现代发展中，得到了广泛的实质性的运用。熟悉和掌握数理逻辑基础，已成为当代人文、社会科学工作者应当具备的一种知识结构和素养。,它是应用数学方法引进一套符号系统来研究思维的形式结构和规律的学科，它起源于公元十七世纪。十九世纪英国的德摩根和乔治布尔发展了逻辑代数，二十世纪三十年代数理逻辑进入了成熟时期，基本内容（命题逻辑和谓词逻辑）有了明确的理论基础，成为数学的一个重要分支，同时也是电子元件设计和性质分析的工具。冯诺意曼，图灵，克林，等人研究了逻辑与计算的关系。基于理论研究和实践，随着1946年第一台通用电子数字计算机的诞生和近代科学的发展，计算技术中提出了大量的逻辑问题，逻辑程序设计语言的研制，更促进了数理逻辑的发展。除古典二值（真，假）逻辑外，还研究了多值逻辑、模态逻辑、概率逻辑、模糊逻辑、非单调逻辑等。不仅有演绎逻辑，也还有归纳逻辑。计算机科学中还专门研究计算逻辑、程序逻辑、时序逻辑等。现代数理逻辑分为四论：证明论，递归论，模型论，公理化集合论。,第一节、数理逻辑的定义、发展、研究内容1.数理逻辑的定义:数理逻辑又称符号逻辑。它是数学的一个分支，是用数学方法研究逻辑或形式逻辑的学科。其研究对象是对证明和计算这两个直观概念进行符号化以后的形式系统。数理逻辑是数学基础的一个不可缺少的组成部分。简言之，用数学的方法研究 关于推理、证明等问题的学科就叫做数理逻辑。广义理解：用数学方法研究演绎规律的学科。狭义理解：用数学方法研究数学中演绎规律和数学基础的学科、,2.数理逻辑的产生和发展：（1）利用计算的方法来代替人们思维中的逻辑推理过程，这种想法早在十七世纪就有人提出过。莱布尼茨就曾经设想过能不能创造一种“通用的科学语言”，可以把推理过程象数学一样利用公式来进行计算，从而得出正确的结论。由于当时的社会条件，他的想法并没有实现。但是它的思想却是现代数理逻辑部分内容的萌芽，从这个意义上讲，莱布尼茨可以说是数理逻辑的先驱。（2）1847年，英国数学家布尔发表了逻辑的数学分析，建立了“布尔代数，并创造一套符号系统，利用符号来表示逻辑中的各种概念。布尔建立了一系列的运算法则，利用代数的方法研究逻辑问题，初步奠定了数理逻辑的基础。,（3）十九世纪末二十世纪初，数理逻辑有了比较大的发展，1884年，德国数学家弗雷格出版了数论的基础一书，在书中引入量词的符号，使得数理逻辑的符号系统更加完备。对建立这门学科做出贡献的，还有美国人皮尔斯，他也在著作中引入了逻辑符号。从而使现代数理逻辑最基本的理论基础逐步形成，成为一门独立的学科。1910到1913年出版的罗素、怀特海合著的数学原理是这门学科兴起的标志。（4）随着数理逻辑的发展，到20世纪30年代，数理逻辑已完全成熟。数理逻辑的分支得到了迅速的发展，如“集合论”、“证明论”、“递归论”、“模型论”等。数理逻辑之所以发展这么迅速，主要原因是这门学科对于数学其它分支如集合论、数论、代数、拓扑学等的发展有重大的影响，特别是对新近形成的计算机科学的发展起了推动作用。反过来，其他学科的发展也推动了数理逻辑的发展。,3.数理逻辑研究的主要内容：数理逻辑最基本的也是最重要的组成部分，就是“命题演算”和“谓词演算”（1）命题演算是研究关于命题如何通过一些逻辑连接词构成更复杂的命题以及逻辑推理的方法。（2）谓词演算也叫做命题涵项演算。在谓词演算里，把命题的内部结构分析成具有主词和谓词的逻辑形式，由命题涵项、逻辑连接词和量词构成命题，然后研究这样的命题之间的逻辑推理关系。,4.数理逻辑与传统逻辑的区别：第一，传统逻辑与现代逻辑的研究对象不完全相同。有些内容如类比与假说，是传统逻辑的研究内容，但现代逻辑尚未展开这些方面的全面研究。现代逻辑研究的许多内容则是传统逻辑没有研究甚至也没有能力去研究的，比如，一个公理系统的完全性与无矛盾性。第二，传统逻辑与现代逻辑在人们的实践中所起的认识作用有些区别。传统逻辑是一般思维中的便利工具，它对实际思维中常见的思维形式类型（主要是推理）加以分析、研究。这种研究的理论成果，在规范、导引人们进行符合逻辑的思维方面发挥着重要作用。而现代逻辑是数学研究中的有用工具，它运用一些数学方法对思维形式类型进行研究，这种研究的成果对数学、计算机科学、人工智能等科学的发展有重要意义。,第三，传统逻辑和现代逻辑所使用的工具语言不同。传统逻辑的研究主要运用自然语言，因为自然语言本身具有模糊、歧义性等特点，使得传统逻辑在理论上有某些缺陷，比如不能准确地处理关系命题、必须预设命题的主项和谓项所指称的对象存在等等。但自然语言同我们的日常经验比较接近，因此，传统逻辑在日常生活的应用上较之现代逻辑更为广泛。现代逻辑则主要运用人工语言，通过建立形式系统以实现对思维形式的研究。人工语言和数学方法的运用使得现代逻辑较之传统逻辑更为精确，研究的内容也更为深刻。当然，这也使得现代逻辑更为抽象而远离人们的日常经验。,5.数理逻辑的主要特点：（1）使用一整套符号语言，从而简化了推理形式。数理逻辑使用一套专门的符号来处理各种思维形式，完全消除了自然语言的含混性，摆脱了自然语言的局限。（2）数理逻辑借助人工符号语言，使整个推理形式化。（3）数理逻辑同逻辑学其他分支相比较，它的主要特点是系统性。它通过符号把把思维的各种逻辑形式联系起来，组成一个完整的系统。它研究各种系统的逻辑发展过程，也研究系统之间的相互关联。,第二节、预备知识,一、集合概念及其表示1.集合的基本概念 所谓集合，就是把人们直观的或想象中的某些确定的能够区分的对象汇合在一起组成的一个整体。组成集合的各个对象，称为这个集合的元素或成员。,例1 指出以下叙述中哪些是集合，哪些不是集合？（1）中国人的集合；（2）百货商店里好看的花布的集合；（3）1000以内的素数的集合；（4）26个英文字母组成的集合；（5）这个班里高个子学生的集合；（6）直线y2x-5上的点的集合。,解（1）（3）（4）（6）是集合；（2）不是集合，因为对每一种布，没有确定的标准说它是“好看”还是“不好看”；（5）也不是集合，因为在“高个子”与“不是高个子”之间没有明确的界限，但是，如果我们给出一个完全确定的标准（如身高大于1.80米），合乎这个标准的算是“高个子”，否则不算，那么对于这个班里的每一个学生，总可以明确地断定是否合乎这个标准，这时“这个班里高个子学生”就构成一个集合。,集合及其表示,通常，用大写字母A，B，C，表示集合，用小写字母a，b，c，表示元素。用如下的字母表示常用的集合：N 自然数的集合（包含0）；Nm 小于m的自然数集合,即0,1,m-1；I 整数的集合；I+正整数的集合；I_ 负整数的集合；R 实数的集合；R+正实数的集合；R_ 负实数的集合；Q 有理数的集合；C 复数的集合。,设a为任一个对象，A为任意一个集合，则在a和A之间有且仅有以下两种情况中的一个出现：a为A的元素，记作“aA”，并称为“a属于A”或“A含有a”；a不为A的元素，记作“aA”，并称“a不属于A”。当a1A，a2A，.，anA时，常简写为a1，a2，.，anA。,2.集合的表示方法 1.列举法 这种方法是将集合中的元素一一列举出来，或者列出足够多的元素以反映集合中成员的特征，并用花括号将元素括起来，其表示形如 Aa1，a2，an 或 A=a1，a2，a3,例如，A=a,b,c,d,x,y,z，B=0,1,2,3,4,5,6,7,8,9就是用列举法表示的集合。,2.描述法 这种方法是用一个条件来描述集合中元素具有的共同性质。这个条件可以是一句话或一个或多个表达方式。其表示形式如 A=x P(x)或 A=x：P(x)其中P(x)表示“x满足性质P”或“x具有性质P”。例如，前面列出的常用集合N和Nm，可以用列举法分别表示为 N=n|n是自然数 Nm=n|nN且0nm,例2 设全集合是整数集I，试用列举法表示集合 A=x|x-10 x-240且-5x6 解 A=-1,0,1,2,3,4,5,6,二、特殊的集合1、空集定义3-1.3：不含任何元素的集合称为空集，记作。=x|p(x)p(x)例如：X=x|x2+1=0，xR是空集。注意：，空集是任意集合的子集。2、全集定义3-1.4：在一定范围内，如果所有集合均是某一集合的子集，则称该集合为全集。记作E。E=x|p(x)p(x),3.幂集 定义：给定集合A，由A的所有子集为元素组成的集合称为A的幂集，记作(A)或2A 从定义中可看出，集合A的幂集实际上是以A的所有子集为元素组成的集合。,例4.5 求下列集合的幂集。（1）A=；（2）B=；（3）C=,；（4）D=a,b,c。解（1）P(A)=；（2）P(B)=,；（3）P(C)=,；（4）P(D)=,a,b,c,a,b,a,c,b,c,a,b,c。,三、集合的关系相等(外延性公理)：两个集合是相等的，当且仅当它们有相同的成员。两个集合A和B相等，记作A=B，两个集合不相等，记作AB。0，1=x|x(x2-2x+1)=0，x I0，11，2,两个集合 A和 B相等当且仅当它们具有相同的元素。即对任意集合A、B,A=B x(xAxB),外延公理,子集的定义：设A、B是任意两个集合，如果A的每一个元素都是B的元素，则称集合A是集合B的子集合（或子集，subsets），或称A包含在B内，记为AB；或称B包含A，记为BA。即 AB x(xAxB),设A，B，C为任意集合，根据定义，显然有：包含关系具有自反性：A A 包含关系具有传递性：若A B且B C，则A C。,注：可能AB或BA，也可能两者均不成立，不是两者必居其一。,定理 设A，B和C为任意三个集合，则有（1）A；（2）AA；（3）若AB且BC，则AC；（4）若AB且BC，则AC。,例如 设A=a,b,c,B=a,b,c,d,C=a,b,则 AB,CA,CB,A,C,B,a,b,c,d,e,f,g,h,i,j,练习 设A=a,b,c,a,a,b，试指出下列论断是否正确？(1)aA()(8)bA()(2)aA()(9)a,bA()(3)aA()(10)a,bA()(4)A()(11)cA()(5)A()(12)cA()(6)bA()(13)cA()(7)bA()(14)a,b,cA(),例4.3 列出集合A=1,2的全部子集。解 因为是任何集合的子集，所以是A的子集。由A中任意一个元素所组成的集合是A的子集，所以1和2是A的子集。由A中任意两个元素所组成的集合是A的子集，所以1,2是A的子集。因为A中只有两个元素，故A再没有其他的子集。由上可知，A有四个子集：，1，2，1,2。,例4.4 设有集合A,B,C和D,下述论断是否正确？说明理由。（1）若AB,BC,则AC 解 正确。因为BC，所以集合B的每一个元素也是集合C的元素，由AB知A是B的一个元素，因此A也是C的一个元素，故AC。（2）若AB,BC,则AC 解 错误。举反例如下：设A=a，B=a,b，C=a,b,c，显然AB，BC，但A不是C的子集。因为aA，但aC。,四、集合的运算及其性质,要求：1、掌握如下概念：交集、并集、补集等概念。2、熟练掌握集合运算定律，会使用运算定律证明两个集合相等。,一、集合的运算1、交集：定义：设任意两个集合A和B，由A和B的所有共同元素组成的集合，称为A和B的交集，记为AB。AB=x|xAxB文氏图,例1：A=0，2，4，6，8，10，12，B=1，2，3，4，5，6，AB=2，4，6例2：设A是平面上所有矩形的集合，B是平面上所有菱形的集合，AB是所有正方形的集合。例3：设A是所有能被K整除的整数的集合，B是所有能被L整除的整数的集合，AB是所有能被K与L最小公倍数整除的整数的集合。,性质：a)AA=Ab)A=c)AE=Ad)AB=BAe)(AB)C=A(BC)f)ABA，ABB,例题4：设AB，求证ACBC。证明：对任一x AC，则x A且x C，因为有若x A，则x B，所以x B且x C，故x BC。因此ACBC。,2、并集定义3-2.2：设任意两个集合A和B，所有属于A或属于B的元素组成的集合，称为A和B的并集，记作AB。AB=x|x Ax B文氏图,例1：A=1，2，3，4，B=2，4，5，AB=1，2，3，4，5例2：设A是奇数集合，B是偶数集合，AB是整数集合，AB=。,性质：a)AA=Ab)AE=Ec)A=Ad)AB=BAe)(AB)C=A(BC)f)AAB，BAB,例题3：设AB，CD，求证ACBD。证明：对任一x AC，则x A或x C，若x A，则x B，故x BD；若x C，则x D，故x BD。因此ACBD。,定理3-2.1 设A，B，C为三个集合，则下列分配律成立。a)A(BC)=(AB)(AC)b)A(BC)=(AB)(AC),证明：a)设S=A(BC)，T=(AB)(AC)，若x S，则x A且x BC，即x A且 x B或 x A且 x C，x AB或x AC即x T，所以S T。反之，若x T，则x AB或x AC，x A且 x B或 x A且 x C，即x A且x BC，于是x S，所以TS。因此，S=T。b)证明完全与a)类似。,定理3-2.2 设A，B为任意两个集合，则下列吸收律成立。a)A(AB)=Ab)A(AB)=A,证明：a)A(AB)=(AE)(AB)=A(EB)=AE=Ab)A(AB)=(AA)(AB)=A(AB)=A,定理3-2.3 AB，当且仅当AB=B或AB=A。,证明：若AB，对任意x A必有x B，对任意x AB，则x A或x B，即x B，所以AB B。又B AB，因此得到AB=B。反之，若AB=B，因为A AB，所以A B。同理可证得AB=A,3、差集、补集定义3-2.3：设A、B是任意两个集合，所有属于A而不属于B的元素组成的集合称为B对A的补集，或相对补，(或A和B差集)记作A-B。A-B=x|xAxB文氏图,定义3-2.4：设E为全集，任一集合A关于E的补，称为A的绝对补，记作A。A=E-A=x|xExA文氏图,性质：a)(A)=Ab)E=c)=Ed)AA=Ee)AA=,定理3-2.4 设A，B为任意两个集合，则下列关系式成立。a)(AB)=ABb)(AB)=AB定理3-2.5 设A，B为任意两个集合，则下列关系式成立。a)A-B=ABb)A-B=A-(AB)定理3-2.6 设A，B，C为三个集合，则A(B-C)=(AB)-(AC)定理3-2.7 设A，B为任意两个集合，若AB，则a)BAb)(B-A)A=B,五、序偶与笛卡尔积,要求：了解有序n元组、笛卡尔积。,一、有序n元组1、序偶(有序2元组)：两个具有固定次序的客体组成一个序偶(有序2元组)，记作，其中x是它的第一元素，y是它的第二元素。例：平面直角坐标系中的一个点的坐标就构成为一个有序序偶，我们可用表示。注：序偶是讲究次序的，例和是表示平面上两个不同的点，这与集合不同，1，3和3，1是两个相等的集合。2、定义3-4.1：两个序偶相等，=，当且仅当x=u且y=v。,3、有序元组：是一个序偶，其第一元素本身也是一个序偶，表示为，z或。4、有序n元组：有序n元组也是一个序偶，其第一元素是一个n-1元组。，xn，通常简记为：，其中xi称作它的第i坐标，i=1，2，n。=的充要条件是xi=yi，i=1，2，n。序偶其元素可以分别属于不同的集合，因此任给两个集合A和B，我们可以定义一种序偶的集合。,二、笛卡尔积1、定义3-4.2：设A和B是任意两个集合，由A中元素作第一元素，B中元素作第二元素构成序偶，所有这样序偶的集合称集合A和B的笛卡尔积或直积。记作AB。即AB=|xAyB,例题 若A=，B=1，2，3，求AB，BA，AA，BB以及(AB)(BA)。解：AB=，BA=，AA=，BB=，(AB)(BA)=若A、B均是有限集，|A|=m，|B|=n，则|AB|=mn。,2、n个集合的笛卡尔积：集合A1，A2，An，则特别地，,约定：若A=或B=，则A B=，B A=,（4）映射：在数学及相关的领域经常等同于函数。设A和B是两个集合，如果按照某种对应关系f，对于集合A中的任何一个元素，在集合B中都存在唯一的一个元素与之对应，那么，这样的对应（包括集合A，B，以及集合A到集合B的对应关系f）叫做集合A到集合B的映射(Mapping)，记作f：AB。单射：指将不同的变量映像到不同的值的函数。也就是说，对于任意x1,x2A，并且x1x2,则f(x1)f(x2).满射：指集合B等于值域的函数。即：对集合B中任意元素，都存在至少一个定义域中的元素与之对应。也就是说，Ran(f)=B 双射（也称一一对应）：既是单射又是满射的函数。直观地说，一个双射函数形成一个对应，并且每一个输入值都有正好一个输出值以及每一个输出值都有正好一个输入值。雙射（單射與滿射）單射但非滿射 滿射但非單射 非滿射非單射,（5）等势：如果存在A到B的双射，则A和B是等势的。基数：所有等势的集合所确定的数，称为基数。记为A。有穷集和无穷集：如果存在自然数n，使得A=n，就称为有穷集；否则就称为无穷集。自然数集是我们遇到的第一个无穷集，它的基数我们用w0表示。如果A为有穷集或A=w0，则称A为可数集；否则A为不可数集。二、能行方法：这一方法是由有穷多条有穷长的指令组成；每一步做什么取决于这些指令或者再加上一步操作所得的结果；并且按此方法能在有穷步内结束求解过程，并给出确定的答案。能行可判定：如果一个问题存在上述这样一种能行方法去求解，则称该问题是能行可判定的。,参考书目：1.莫绍揆:数理逻辑初步上海：上海人民出版社,1980年版 2.王宪钧：数理逻辑引论北京：北京大学出版社1982年版 3.胡世华等：数理逻辑基础北京：科学出版社1982年版4.A.G.汉密尔顿：数理逻辑（汉译本）朱水林译，上海：华东师范大学出版社1986年版5.（美）I.M.科庇：符号逻辑宋文坚等译，北京：北京大学出版社1988年版6.张家龙：数理逻辑发展史从莱布尼茨到哥德尔 北京：社会科学文献出版社1993年版7.陈慕泽：数理逻辑教程上海：上海人民出版社2001年版 8.毕富生：数理逻辑北京：高等教育出版社2004年版 9.李小五：现代逻辑讲义广州：中山大学出版社2005年版10.邢滔滔：数理逻辑北京：北京大学出版社2008年版 11.徐明：符号逻辑讲义武汉：武汉大学出版社2008年版12刘壮虎：素朴集合论北京：北京大学出版社2001年版,第一章、命题逻辑,第一节、原子命题与复合命题一、命题及其真值：1.命题逻辑（proposition logic):它是以命题为基本逻辑形式的逻辑学的基础组成部分。与“词项逻辑”相对。也就是说，在考查和研究命题时，只把一个命题分析到其中所含命题成分为止，即把简单命题作为整体来考察，不把一个简单命题再分析为非命题成分的结合，不把个体词、谓词和量词等非命题成分分析出来。可以更进一步地说，由简单命题（原子命题）出发，通过使用命题联结词构成复合命题，然后研究复合命题的逻辑形式以及符合命题之间的推理关系。比如：pq p q,2.命题逻辑的发展历史：（1）古希腊：亚里士多德：在他的逻辑研究体系中，已涉及到一些命题逻辑的基本内容，如命题的概念、命题的真假、命题联结词、命题之间的关系等。斯多亚学派：他们对命题逻辑作了深入的研究，比较系统地建立起了命题逻辑理论，对构成命题的算子（联结词）作了非常准确的分析，也有了正确的真值表观念，特别对蕴涵的意义进行了极其复杂的讨论。他们的命题逻辑的某些方面是公理化的，并且还对规律和元定理作出了区分。（2）中世纪：中世纪的逻辑学家对命题逻辑作出了杰出的贡献，如西班牙的彼得（逻辑大全）、威廉奥康等都对逻辑的发展作出了重要贡献。他们构造两套命题逻辑系统：简单蕴涵系统和当下蕴涵系统，把斯多亚学派的命题逻辑推进了一步。（3）十九世纪中叶：1879年，弗雷格才第一个建立了初步自足的命题逻辑公理系统，即命题演算。在这个系统中，他用了否定和蕴涵两个初始联结词，并且它有六条公理。如果我们用p,q,r来表示命题变元，就可以写成：p(qp);(p(qr)(pq)(p r);(p(qr)(q(pr)(p q)(q p)pp pp 其中第三个公理可以从第一、第二个公理推导出。最后三个公理可以用“（pq)（pq)代替。因此，简化后的公理系统只有三条公理，这个公理系统为许多现代逻辑学家所采用。,3.（1）命题的涵义：简单来说，就是有真假的语句。即通过肯定或否定对事物作出某种陈述的语句。如“水银是液体”和“水银不是液体”这两个语句就是真假的。它们分别直接表达了两个相应的判断，因而都是命题。凡不表达判断的语句，都不是命题。（2）命题的真值：就是指命题的真或假。4.原子命题和复合命题：（1）原子命题：是数理逻辑中的基本概念。是在指在结构上不能分解出其他命题的命题。如：所有的牛都是动物；有的罪犯不是杀人犯；注意：原子命题是由词项结合而成，它包括个体词和谓词两个部分，即由指称个体的词和表示一个个体的性质或表示两个及两个以上个体之间关系的词所构成。（2）复合命题：就是指在自身中包含了其他命题的命题。亦即以其他命题作为其构成要素的命题。它是由逻辑联结词和支命题所组成。逻辑联结词：就是在复合命题中联结各支命题、表明支命题之间逻辑关系的词项。它决定了复合命题的逻辑性质。复合命题的真假，决定于它的支命题之间的联系是否符合逻辑联结词的涵义所规定的联系。支命题：就是复合命题中所包含的命题。一般说来，支命题是简单命题，但是并不都是简单命题，也可以是复合命题。如“革命或迟或早总将发生，并将必然取得胜利。”,第二节、真值联结词与真值形式,一、真值联结词：1.真值联结词：在复合命题中联结各支命题、表明支命题之间逻辑关系的词项，它刻画的是原子命题和由其构成的复合命题之间的真假关系。如“合取”、“选取”等。2.常用真值联结词的逻辑特征：(1)否定词：（否定运算、非运算）符号,读作“非”，“否定”设命题为，则在的前面加否定词，变成，读做“的否定”或“非”,定义：严格由真值表定义 举例：北京是一座城市。：北京不是一座城市。：每一种生物均是动物。F：有一些生物不是动物。T这里不能讲成“每一种生物都不是动物”为假命题了。对量化命题的否定，除对动词进行否定外，同时对量化词也要加以否定。,(2)合取词（“合取”、“积”、“与”运算）符号“”设，为两个命题，则称与的合取，读作：“与”、“与的合取”、“并且”等。定义（由真值表给出）：真值表如下：当且仅当和的真值均为“”，则（）的真值为“”。否则，其真值为“”。注意：和是互为独立的；地位是平等的，和的位置可以交换而不会影响的结果。,举例：(a)P：王华的成绩很好 Q：王华的品德很好。则：王华的成绩很好并且品德很好。(b)P：我们去种树 Q：房间里有一台电视机 则：我们去种树与房间里有一台电视机(c)P：今天下大雨 Q：3+3=6 则：今天下大雨和3+3=6由例(b)(c)可见，在日常生活中，合取词应用在二个有关系的命题之间。而在逻辑学中，合取词可以用在二个毫不相干的命题之间。(d)下列语句不是合取联结词组成的命题。P:王大和王二是亲兄弟。Q:他打开箱子然后（而后）拿出一件衣服来,(3)析取词（或运算）符号“”设、为二个命题，则（）称作与的“析取”，读作：“或”。定义（由真值表给出）：当且仅当、均为“”时，（）为“”。否则，其真值为“”如右图：,区分“可兼或”与“不可兼或（异或，排斥或）”析取词为可兼或即:P和Q均为“T”时（PQ）为“T”例如：灯泡有故障或开关有故障。今晚写字或看书。今天下雨或打雷。以上例句均为可兼或。“不可兼或”中当P和Q均为“T”时，则P异或Q为“F”。（异或用“”（不相容）表示）,例：他通过电视看杂技或到剧场看杂技。他乘火车去北京或乘飞机去北京。以上两句均为不“可兼或”。（4）蕴涵：符号“”，读作：“如果则”、“蕴含”、为二个命题，（）为新的命题，读作：“如果则”，“蕴含”，“仅当”，“当且”，“是的充分条件”。定义：（由真值表定义）：,当为“”，为“”时，则（）为“”，否则（）均为“”。：称为前件、条件、前提、假设：称为后件、结论。举例：（a）P：我拿起一本书 Q：我一口气读完了这本书 PQ：如果我拿起一本书，则我一口气读完了这本书。(b)P：月亮出来了 Q：33=9 PQ：如果月亮出来了，则 33=9。通常称：(a)为形式条件命题。前提和结果有某种形式和内容上的联系。(b)为实质条件命题。前提和结果可以有联系，也可以没有联系，只要满足单条件命题的定义。所以,是形式条件命题一定是实质条件命题,反之不一定。“”是实质条件命题。例：我买到了鱼；:我吃鱼。：如果我买到了鱼，则我吃鱼。但“如果我没买到鱼，则我吃鱼”，这在日常生活中是不可能的，但在单条件命题的定义中是允许的。,可以证明：Q P 原命题 逆反命题 逆命题 反命题列出真值表,由真值表得：原命题逆反命题；逆命题反命题。,（5）等值：符号“”设、为二个命题，则读作：“当且仅当”，“等价”,“是的充分必要条件”。定义（见真值表）：每当和的真值相同时，则（）的真值为“”，否则（）的真值为“”。,举例：（a）设：ABC是等腰三角形：ABC有两只角相等：ABC是等腰三角形当且仅当ABC中有两只角相等。（b）下面均为等价联结词：春天来了当且仅当燕子飞回来了。平面上二直线平行，当且仅当这二直线不相交。当且仅当雪是白色的。,中，、的地位是平等的，、交换位置不会改变真值表中的值。当且仅当仅当当且,3.命题联结词在使用中的优先级（）先括号内，后括号外（）运算时联结词的优先次序为：（由高到低）（）联结词按从左到右的次序进行运算例（）可省去括号因为“”运算是可结合的。（）可省去括号因为符合上述规定而（）中的括号不能省去，因为“”不满足结（）最外层的括号一律均可省去（）可写成,4.命题联结词小结：（）五个联结词的含义与日常生活中的联结词的含义大致相同。（）“或”可分为可兼或（）和异或（）（不可兼或）(3)除“”为一元运算外，其余四个均为二元运算。(4)“”分为形式条件和实质条件命题，当前件为“”时，不论后件怎样，则单条件命题的真值均为“”。(5)命题联结词是命题或命题之间的联结词，而不是名词之间、数字之间和动词之间的联结词。,二、真值形式：约定：（）我们只注意命题的真假值，而不再去注意命题的汉语意义。（）对命题联结词，我们只注意真值表的定义，而不注意它日常生活中的含义。1.真值形式（又称之为“命题公式”）命题常元：表示确定的命题T，F。命题变元：以真假为其变域之变元，或没有指定真值的命题。常用大写英文字母表示。真值形式：由命题变元、常元、联结词、括号，以规定的格式联结起来的字符串。定义：命题公式可按下述法则来生成：）孤立的命题变元是一个命题公式。）若是命题公式，也为命题公式。）若、是命题公式，则（）、（）、（）、（）均为命题公式。,2.复合命题的真值形式：数理逻辑的特点是把逻辑推理变成类似数学演算的完全形式化了的逻辑演算，为此，首先要把推理所涉及到的各命题符号化。把用自然语言表达的复合命题翻译成相应真值形式的步骤：第一，确定复合命题所包含的所有不同的原子命题。第二，用同一命题变项表示所有相同的原子命题，用不同的命题变项分别表示所有不同的原子命题。一般用小写字母p.q.r.s.s来表示。第三，确定复合命题所断定支命题之间的逻辑关系，并用相应的真值联结词加以表达。第四，依据确定的层次，写出整个复合命题真值形式。如：如果天气晴朗，那么我们去逛动物园。首先，我们用p来表示天气晴朗，用q来表示我们去逛动物园这个原子命题；然后，用假言这个真值联结词把这两个原子命题联结起来。因此，这个假言命题的真值形式是：pq,例.写出下列复合命题的真值形式：（1）李明是计算机系的学生，他住在312室或313室。（2）虽然交通堵塞，但是老王还是准时到达了车站。（3）只有一个角是直角的三角形才是直角三角形。（4）老王或小李中有一个去上海出差。解：（1）首先用字母表示简单命题。P：李明是计算机系的学生。Q：李明住在312室。R：李明住在313室。该命题符号化为：P（QR）（2）首先用字母表示简单命题。P：交通堵塞。Q：老王准时到达了车站。该命题符号化为：PQ（3）首先用字母表示简单命题。P：三角形的一个角是直角。Q：三角形是直角三角形。该命题符号化为：P Q（4）首先用字母表示简单命题。P：老王去上海出差。Q：小李去上海出差。该命题符号化为：P Q也可符号化为：（PQ）（PQ）或者（P Q）（PQ）,2.命题推理及其真值形式：1.命题推理：简单地说就是根据某些规则从一个命题或几个命题得出一个或几个命题的思维过程和思维活动。比如：如果某人是杀人犯，那么他一定去过犯罪现场。这个人没去过犯罪现场 那么这个人不是杀人犯2.写出命题推理的真值形式的步骤：第一，分别写出各个前提和结论的真值形式；第二，用合取号把各个前提的真值形式联结起来，所得的合取式，就是前提的真值形式；第三，用蕴涵号把前提和结论的真值形式联结起来，所得的蕴涵式，就是整个命题推理的真值形式。,举例：如果上帝不能创造出一块他自己都不能搬动的石头，则他不是万能的；如果上帝能创造出一块他自己都搬不动的石头，则他同样不是万能的。上帝或者能创造出一块自己都不能搬动的石头，或者不能，二者必居其一。因此，上帝不是万能的。我们用p表示上帝能创造出一块他自己都不能搬动的石头，用q表示上帝是万能的。则推理的形式表示如下：p q p q p p q因此这个命题推理的真值形式就可表示为：（p q）（p q）（p p）q,3.真值函数（Truth function）:也叫做“真值函项”。所谓真值函数就是指定义域和值域都为真值的函数。也就是说，如果对于一个变元的任意一个允许值，另一变元总有一个确定的值与之对应，那么后者（“因变元”）就是前者（“自变元”）的函数。注意：（1）任何真值形式都表示一个真值函数，真值形式是真值函数的表现形式。（2）真值函数的个数是真值函数中所含的不同命题变元的个数确定。N个命题变元可以有的真假情况是2n个，对于每一个真假情况，又都可以有两种断定：肯定和否定。因此，对于2n中情况，肯定和否定的组合22n个。其中每一个组合是一个真值函数的内容。,注意：关于计算当命题变项的数目为n（自然数）时，真值函项种类有多少种？第一，当命题的变项的数目为1时，设命题变项为p，这时p的真值共有两种：真和假。在p的每一种取值下，真值函项的取值各有两种。因此产生不同真值函项的数目有且只有2*2=4（种）第二，当命题变项的数目为2时，设命题变项为p和q，那么p与q组成的所有不同的真值组合共有2*2=22=4（种）即真真、真假、假真、假假四种组合。对于两个变项的每一种真值组合，真值函项的取值又各有两种。因此，当命题变项的数目为2时，所构成不同的真值函项有且只有2*2*2*2=24=222=16（种）第三，当命题变项的数目为3时，设命题变项为p、q、r，那么p、q、r所有不同的真值组合共有2*2*2=23=8（种）对于三个变项的每一种真值组合，真值函项的取值又各有两种可能，即：真或假。因此，当命题变项的数目为时，能构成不同的真值函项有且只有2*2*2*2*2*2*2*2=28=223=256（种）第四，依次类推，当命题变项的数目为n时，其中每一个命题变项的取值有且只有两种可能，即真或者假。因此，n个命题变项的不同取值的真值组合为：2*2*2*.*2=2n（种）。对于其中每一种命题变项的真值组合，真值函项的取值又各有两种，由此可推，含有n个命题变项的不同的真值组合函项共有：2*2*2*.*2=22n。从上述就可以看出，当命题变项的数目确定之后，不同真值函项的个数是完全确定的、有限的，它的真值形式的个数是无限的。一个真值函项可以由不同的真值形式来表示。,4.真值联结词的完全性与独立性,真值联结词的完全性：又称真值联结词的完备集，设是一些命题联结词构成的集合。称是联结词的完备集，如果对于任意的n元（n1）真值函数f都可使用只含中联结词的公式A表达，即A至多含n个命题变元p1p2pn,且A在任意真值函数t：var0,1下真值t（A）等于f（t(p1),t(p2),t(pn).简单地来说，一组真值联结词是完全的，当且仅当由它能定义任一n元真值联结词。真值联结词的独立性：在一组真值联结词中，某个联结词如果不能由该组中其他联结词定义，则称为是独立的；一组真值联结词满足独立性，当且仅当其中每个联结词都是独立的。如，就是满足独立性的一组联结词。,5.真值形式的类型：1）一个真值形式是重言式，当且仅当它在其命题变项的任意一组赋值下都真。如pp就是重言式，无论p取任何值，它的值都是真的。另外如pp等都是重言式。在命题逻辑中，重言式是数理专家最感兴趣的，因为它们中的一部分是命题逻辑中的逻辑规律。因此，从思维和形式结构上来讲，我们又可以把重言式分为以下三类：第一类：有些重言式表示了命题逻辑的逻辑规律。例如，pp是命题逻辑中的排中律，（pp)表示的是命题逻辑中的不矛盾律。第二类：有一些重言式还可以表示命题逻辑中正确的推理形式，如像这样一种推理形式：(pq)q p.第三类：还有一些重言式是以等值式出现的，它们又叫做重言等值式。这些等值式也表现了命题逻辑的规律，其中一些对逻辑演算是很重要的。借助这些规律可以形成一些重要的逻辑方法，例如求否定、及范式等。除了以上三类以外，还有一些重言式是和我们的实际思维关系不大的，或者说在我们的思维中一般不会出现以这类重言式为形式的命题和推理，但这些重言式在逻辑中有具有非常重要的作用。如，一些命题演算的公理、定理及在求证定理过程中得到的公式等。,2）一真值形式是矛盾式（永假式），当且仅当它在其命题变项的任意一组赋值下都就是假的。比如pp、(pp)等这些真值形式就是一个矛盾式。从形式上看，如果否定整个重言式，得到的公式就是一个矛盾式。矛盾式是逻辑矛盾的表现形式。3）一个真值形式是满足式（又称之为可真式），当且仅当它在其命题变项的至少一组赋值下为真。如pq,pq,pq等是可满足式。因此，从上述就可以看出，真值形式可以分为矛盾式和满足式，而满足式又可以分为重言式和非重言式。根据上述的分类，我们可以得出以下结论：第一，一个真值形式A是重言式，当且仅当它的否定A是矛盾式。第二，一个真值形式A是满足式，当且仅当它的否定A不是重言式。第三，一个真值形式是不是重言式当且仅当至少在它所含命题变项的一种取值下，其值为假。第四，一个真值形式是不可满足的，当且仅当它的否定是重言式。第五，重言式一定是可满足的，反之不然。第六，不可满足式一定不是重言式，反之不然。,第三节、真值形式的判定方法 根据上面情况可以得知，重言式是真值形式中最重要的一种，它是逻辑真理的表现形式，各种逻辑规律以及正确的逻辑推理形式等逻辑真理均可表现为重言式。因此，命题逻辑理论的主要内容就是研究重言式的判定和证明方法。数理逻辑的特点在于从有限的公理出发，根据少许的规则，可以推出许多重言式，即正确的推理形式。因此，如何推出重言式、如何判定重言式等问题就成了数理逻辑的重要问题。为此下面就简单介绍一些判定真值形式（也可以说重言式）的方法，这里主要介绍真值表方法、归谬赋值法、范式方法、真值树方法等几种方法。一、重言式的定义：第一种：用真值表验证的真值形式，如果最后一列的每一 表值都是真的，那么该真值形式就是重言式。第二种：一个真值形式是重言式，当且仅当用别的命题去替换构成命题的任一原子命题，其结构总是真的。第三种：一个真值形式是重言式，当且仅当对该真值形式中的原子命题赋以任何真值，其结果总是真的。总之，不论所含的命题变项取什么真值，函项的值总是真的真值函项就是重言式。,二、真值表方法：1.真值表法：真值表是能显示任何复合判断在它的肢判断的各种真值组合下