离散数学-数理逻辑

离散数学讲义之数理逻辑主讲:邱晓红2数理逻辑简介•数理逻辑是用数学方法研究形式逻辑的科学。数学方法即符号方法，故数理逻辑又称符号逻辑。包含命题逻辑、谓词逻辑、证明论、模型论、递归函数、公理化集合论、归纳逻辑、模态逻辑、多值逻辑和时态逻辑等内容，与计算机有密切关系。3各知识点关联图扩展命题符号化简单命题命题复合命题联结词真值表谓词逻辑完备集范式量词谓词公式主合取范式个体词谓词对偶式公式命题逻辑解释扩展0元谓词命题公式前束范式合取范式析取范式主析取范式等价式蕴含式Skolem范式归结原理推理规则合一前提引入P规则置换等T规则置换推理系统量词引入规则量词消去规则量词辖域约束变元自由变元换名规则代入规则自动推理4第一部分：数理逻辑•第一章命题逻辑•1.1命题及其表示•1.2逻辑联结词•1.3命题公式与解释•1.4真值表与等价公式•1.5命题公式的分类与蕴含式•1.6其它逻辑联结词和最小功能•完备联结词组•1.7对偶与范式•1.8推理理论•习题一•实验一真值表的程序计算•第2章谓词逻辑•2.1谓词的基本概念•2.2谓词公式与解释•2.3变元的约束2.4谓词演算的等价式与蕴含式2.5谓词公式范式2.6谓词演算的推理理论习题二实验二命题逻辑简单推理系统第3章基于归结原理的推理证明**3.1谓词公式与子句集3.2海伯伦（HERBRAND）理论3.3归结原理(RESOLUTIONMETHOD)3.4归结过程的控制策略习题三实验三归结原理的程序实现5第一章：命题逻辑主要内容：命题及表示、联结词、命题公式与翻译、真值表与等价公式、重言式与蕴涵式、其他联结词、对偶与范式、推理理论。教学要求：深刻理解和掌握命题逻辑中的基本概念和基本方法。重点：命题逻辑中的基本概念和基本推理方法难点：推理理论。实践活动：真值表的程序计算61.1命题及其表示•定义1.1.1能够判断真假的陈述句称为命题（Proposition）。命题的判断结果称为命题的真值，常用T(True)（或1）表示真，F(False)（或0）表示假。真值为真的命题称为真命题，真值为假的命题称为假命题。•判定一个句子是否为命题要分为两步：一是判定是否为陈述句，二是能否判定真假，二者缺一不可。7例1.1.1判断下列句子是否为命题（1）北京是中国的首都。（2）请勿吸烟！（3）雪是黑的。（4）明天开会吗？（5）x+y=8。（6）我正在说谎。（7）19+15≤12。（8）1+101=110。（9）今天天气多好啊！（10）别的星球上有生物。8•解在上述的十个句子中，（2）、（9）为祈使句，（4）为疑问句，（5）、（6）虽然是陈述句，但（5）没有确定的真值，其真假随x、y取值的不同而有改变，（6）是悖论(Paradox)（即由真能推出假，由假也能推出真），因而（2）、（4）、（5）、（6）、（9）均不是命题。（1）、（3）、（7）、（8）、（10）都是命题，其中（10）虽然现在无法判断真假，但随着科技的进步是可以判定真假的。需要进一步指出的是，命题的真假只要求它有就可以，而不要求立即给出。如例1.1.1的（8）1+101=110，它的真假意义通常和上下文有关，当作为二进制的加法时，它是真命题，否则为假命题9命题分类命题标识符•根据命题的结构形式，命题分为原子命题和复合命题。•定义1.1.2不能被分解为更简单的陈述语句的命题称为原子命题(SimpleProposition)。由两个或两个以上原子命题组合而成的命题称为复合命题(CompoundProposition)。•定义1.1.3表示原子命题的符号称为命题标识符(Identifier)。•命题标识符依据表示命题的情况，分为命题常元和命题变元。101.2逻辑联结词•一个复合命题，不论其构成多么复杂，一般都可以分析出构成该命题的原子命题。下面介绍5种常用的逻辑联结词(LogicalConnectives)，分别是“非”（否定联结词）、“与”（合取联结词）、“或”（析取联结词）、“若…则…”（条件联结词）、“…当且仅当…”（双条件联结词），通过这些联结词可以把多个原子命题复合成一个复合命题。111.2.1否定联结词定义1.2.1设P为一命题，P的否定(Negation)是一个新的命题，记为P（读作非P）。规定若P为T，则P为F；若P为F，则P为T。P的取值情况依赖于P的取值情况，真值情况见表1.2.1。在自然语言中，常用“非”、“不”、“没有”、“无”、“并非”等来表示否定。例1.2.1P：北京是中国的首都。P：北京不是中国的首都。P是真命题，P是假命题。Q：所有的海洋动物都是哺乳动物。Q：不是所有的海洋动物都是哺乳动物。Q为假命题，Q为真命题。121.2.2合取联结词定义1.2.2设P、Q为两个命题，P和Q的合取(Conjunction)是一个复合命题，记为PQ（读作P与Q），称为P与Q的合取式。规定P与Q同时为T时，PQ为T，其余情况下，PQ均为F。联结词“”的定义见表1.2.2。显然PP的真值永远是假，称为矛盾式。在自然语言中，常用“既…又…”、“不但…而且…”、“虽然…但是…”、“一边…一边…”等表示合取。例1.2.2（1）今天下雨又刮风。设P：今天下雨。Q：今天刮风。则（1）可表示为PQ（2）1+1=2且太阳从西方升起。设P：1+1=2。Q：太阳从西方升起。则（2）可表示为PQ131.2.3析取联结词定义1.2.3设P、Q为两个命题，P和Q的析取(Disjunction)是一个复合命题，记为PQ（读作P或Q），称为P与Q的析取式。规定当且仅当P与Q同时为F时，PQ为F，否则PQ均为T。析取联结词“”的定义见表1.2.3。析取联结词“”与汉语中的“或”二者表达的意义不完全相同，汉语中的“或”可表达“排斥或”，也可以表达“可兼或”，而从析取联结词的定义可看出，“”允许P、Q同时为真，因而析取联结词“”是可兼或。对于“排斥或”将在1.6中论述。141.2.4条件联结词定义1.2.4设P、Q为两个命题，P和Q的条件(Conditional)命题是一个复合命题，记为PQ（读作若P则Q），其中P称为条件的前件，Q称为条件的后件。规定当且仅当前件P为T，后件Q为F时，PQ为F，否则PQ均为T。条件联结词“”的定义见表1.2.4在自然语言中，常会出现的语句如“只要P就Q”、“因为P所以Q”、“P仅当Q”、“只有Q才P”、“除非Q才P”等都可以表示为“PQ”的形式。151.2.5双条件联结词定义1.2.5设P、Q为两个命题，其复合命题QP称为双条件(Biconditional)命题，PQ读作P当且仅当Q。规定当且仅当P与Q真值相同时，QP为T，否则QP均为F。双条件联结词“”的定义如表1.2.5所示。例1.2.5（1）雪是黑色的当且仅当2+24。（2）燕子北回，春天来了。（1）设P：雪是黑色的。Q：2+24。则（1）可表示为QP，其真值为T。（2）设R：燕子北回。S：春天来了。则（2）可表示为SR，其真值为T。161.2.6字位运算与布尔检索计算机用位串表示信息，而位串是0个或多个字位的序列。每个字位有两个可能的值，即0或1，字位的这种取值来自二进制数字，因为0和1是用在数的二进制表示中的数字。1946年著名的统计学家图凯（JohnTukey）引入了这一术语。因为真值只有两个取值，即真（T）和假（F），所以可以用字位表示真值，即用1表示真（T），0表示假（F）。计算机的字位运算对应于逻辑运算，只要在运算符、和的真值表中用1代替T，用0代替F，就能得到表1.2.6所示的对应的字位运算表。这里，NOT、OR和AND表示、和相对应的字位运算，许多程序设计语言正是这样表示的。17例1.2.6求位串0110110110的按位NOT以及与位串1100011101的按位AND和OR按位（这里以及本书其它地方均把位串按3个字位分块以便于阅读）。解位串0110110110的按位NOT由对应字位的NOT运算得到；两个位串的按位AND和按位OR分别由对应字位的AND和OR运算得到，其结果是■逻辑运算还广泛用于信息检索，例如，检索网页索引。由于这些检索使用命题逻辑技术，所以又称为布尔检索。NOT按位00100100111101101100ORAND按位按位1111111101100010100010101110011101101100181.3命题公式与解释•上一节介绍了5种常用的逻辑联结词，利用这些逻辑联结词可将具体的命题表示成符号化的形式。对于较为复杂的命题，需要由这5种逻辑联结词经过各种相互组合以得到其符号化的形式，那么怎样的组合形式才是正确的、符合逻辑的表示形式呢？191.3.1命题公式定义1.3.1（1）单个的命题变元是命题公式。（2）如果A是命题公式，那么A也是命题公式。（3）如果A、B是命题公式，那么(A∧B),（A∨B),(A→B)和(AB)也是命题公式。（4）当且仅当能够有限次地应用（1）、（2）、（3）所得到的包含命题变元、联结词和括号的符号串是命题公式（又称为合式公式，或简称为公式）。201.3.2命题的符号化有了命题公式的概念之后，就可以把自然语言中的一些命题解释成命题逻辑中的符号化形式。把一个文字描述的命题相应地写成由命题标识符、逻辑联结词和圆括号表示的命题形式称为命题的符号化或解释。命题符号化的一般步骤：（1）明确给定命题的含义；（2）找出命题中的各原子命题，分别符号化。（3）使用合适的逻辑联结词，将原子命题分别连接起来，组成复合命题的符号化形式。21命题的符号化范例例1.3.3张三或李四都可以做这件事。设P：张三可以做这件事。Q：李四可以做这件事。则命题符号化为：QP，而不是QP。例1.3.4（1）只有你走，我才留下。这个命题的意义也可以理解为：如果我留下了，那么你一定走了。设P：你走。Q：我留下。则命题符号化为：PQ。221.4真值表与等价公式定义1.4.1设1P，2P，…，nP是出现在命题公式A中的全部命题变元，给1P，2P，…，nP各指定一个真值，称为对公式A的一个赋值（或解释或真值指派）。若指定的一组值使公式A的真值为1，则这组值称为公式A的成真赋值。若指定的一组值使公式A的真值为0，则这组值称为公式A的成假赋值。例如，对公式RQP)(，赋值011（即令)1,1,0RQP，则可得到公式的真值为1；若赋值000，则公式真值为0。因此，011为公式的一个成真赋值；000为公式的一个成假赋值。除了上述的两种赋值外，公式的赋值还有000，001，…等。一般的结论是在含有n个命题变元的命题公式中，共有n2种赋值。23真值表定义1.4.2将命题公式A在所有赋值下的取值情况列成表，称为公式A的真值表(TruthTable)。构造真值表的基本步骤：（1）找出公式中所有的命题变元1P，2P，…，nP，按二进制从小到大的顺序列出n2种赋值。（2）当公式较为复杂时，按照运算的顺序列出各个子公式的真值。（3）计算整个命题公式的真值。24真值表范例例1.4.1写出下列公式的真值表，并求其成真赋值和成假赋值。（1）QP解（1）的真值表见表1.4.1。表1.4.1QP的真值表PQPQP0011011110001101成真赋值为00，01，11，成假赋值为10。25（2）QQP)(解（2）的真值表见表1.4.2。表1.4.2QQP)(的真值表PQQP)(QPQQP)(00100011001001011100无成真赋值，成假赋值为00，01，10，11。261.4.2等价公式定义1.4.3给定两个命题公式BA,，设1P，2P，…，nP是出现在命题公式BA,中的全部命题变元，若给1P，2P，…，nP任一组赋值，公式A和B的真值都对应相同，则称公式A与B等价或逻辑相等(Equivalence)，记作AB。需要注意的是，“”不是逻辑联结词，因而“AB”不是命题公式，只是表示两个命题公式之间的一种等价关系，即若AB，A和B没有本质上的区