离散数学命题逻辑.

2019/12/201离散数学(DiscreteMathematics)2019/12/202第一部分数理逻辑(MathematicalLogic)逻辑：是研究推理的科学。公元前四世纪由希腊的哲学家亚里斯多德首创。作为一门独立科学，十七世纪，德国的莱布尼兹(Leibniz)给逻辑学引进了符号,又称为数理逻辑(或符号逻辑)。逻辑可分为：1.形式逻辑2.辩证逻辑辩证逻辑是研究反映客观世界辩证发展过程的人类思维的形态的。形式逻辑是研究思维的形式结构和规律的科学，它撇开具体的、个别的思维内容，从形式结构方面研究概念、判断和推理及其正确联系的规律。2019/12/203数理逻辑是用数学方法研究推理的形式结构和推理的规律的数学学科。它的创始人Leibniz，为了实现把推理变为演算的想法，把数学引入了形式逻辑。其后，又经多人努力，逐渐使得数理逻辑成为一门专门的学科。上个世纪30年代以后，数理逻辑进入一个崭新的发展阶段，逻辑学不仅与数学结合，还与计算机科学等密切关联。第一部分数理逻辑(MathematicalLogic)2019/12/2041931年Godel不完全性定理的提出，以及递归函数可计算性的引入，促使了1936年Turing机的产生，十年后，第一台电子计算机问世。从广义上讲，数理逻辑包括四论、两演算——即集合论、模型论、递归论、证明论和命题演算、谓词演算，但现在提到数理逻辑，一般是指命题演算和谓词演算。本书也只研究这两个演算。第一部分数理逻辑(MathematicalLogic)2019/12/205数理逻辑与计算机学、控制论、人工智能的相互渗透推动了其自身的发展，模糊逻辑、概率逻辑、归纳逻辑、时态逻辑等都是目前比较热门的研究领域。本篇我们只从语义出发，对数理逻辑中的命题演算与谓词演算等作一简单的、直接的、非形式化的介绍，将不涉及任何公理系统。第一部分数理逻辑(MathematicalLogic)2019/12/206第一章命题逻辑（PropositionalLogic）1.1命题及其表示方法1.2联结词1.3命题公式与翻译1.4真值表与等价公式1.5重言式与蕴含式1.6其他联结词1.7对偶与范式1.8推理理论2019/12/2071.1命题及其表示方法命题的定义命题的表示方法命题的分类小结2019/12/208一、命题(Statement,Proposition)的定义数理逻辑研究的中心问题是推理(inference)，而推理的前提和结论都是表达判断的陈述句，因而表达判断的陈述句构成了推理的基本单位。命题的真值(Truth,Value)：命题的判断结果。命题的真值只取两个值：真(用T(true)或1表示)、假(用F(false)或0表示)。定义1-1.1具有确定真假值的陈述句，称为命题。真命题：判断为正确的命题，即真值为真的命题。假命题：判断为错误的命题，即真值为假的命题。1-1命题及其表示方法2019/12/209判断命题的两个步骤：是否为陈述句；是否有确定的、唯一的真值。例判断下列句子是否为命题。(1)今天天气多好啊！(2)请你关上门.(3)Howdoyoudo?(4)3+3=8.(5)吸烟有害健康。T感叹句，不是命题祈使句，不是命题疑问句，不是命题F1-1命题及其表示方法2019/12/2010(6)太阳从西方升起。(7)x+39(8)1+101=110(9)国足能杀入2014世界杯当且仅当2+2=4。(10)如果太阳从西方升起，那么2是奇数。(11)今年五月一日是晴天。(12)明天我去看电影。(13)宇宙中有外星人。(14)我正在说谎。不是命题二进制中为真，十进制中为假FT是命题，其真值到五月一日方可知道是命题，客观上能判断真假悖论，不是命题F是命题，客观上能判断真假1-1命题及其表示方法2019/12/2011说明只有具有确定真值的陈述句才是命题。一切没有判断内容的句子，无所谓是非的句子，如感叹句、祁使句、疑问句等都不是命题。因为命题只有两种真值，所以“命题逻辑”又称“二值逻辑”。“具有确定真值”是指客观上的具有，与我们是否知道它的真值是两回事。如上例中的(11)(12)(13).1-1命题及其表示方法2019/12/2012二、命题的表示方法在本书中，用大写英文字母A,B,…,P,Q或带下标的字母P1,P2,P3,…,或数字(1),[2],…,等表示命题，称之为命题标识符(PropositionIdentifier)。例如P：梅西是球星。Q：5是负数。P3：明天天气晴。(2)：太阳从西方升起。皆为符号化的命题，其真值依次为1、0、1或0、0。1-1命题及其表示方法2019/12/2013命题常量(PropositionConstant)：表示确定命题的命题标识符。命题标识符又有命题常量、命题变元和原子变元之分。命题变元(PropositionValiable)：命题标识符如仅是表示任意命题的位置标志，就称为命题变元。原子变元(AtomicValiable)：当命题变元表示原子命题时，该变元称为原子变元。1-1命题及其表示方法2019/12/2014注意：一个符号(如P)，它表示的是命题常量还是命题变元，一般由上下文来确定。命题变元可以表示任意命题，它不能确定真值，故命题变元不是命题。这与“变数x不是数”是一样的道理。1-1命题及其表示方法2019/12/2015简单命题(SimpleProposition)/原子命题(AtomicProposition)/本原命题(PrimitiveProposition)：不能分解为更简单的陈述语句的命题(如上例中的命题)。三、命题的分类复合命题(CompoundProposition)：由简单命题通过联结词联结而成的命题。联结词就是复合命题中的运算符。1-1命题及其表示方法2019/12/2016四、小结本节主要介绍了命题、命题的真值、原子命题、复合命题、命题标识符、命题常量、命题变元和原子变元的概念。重点理解和掌握命题、命题变元两个概念。作业：P8(1)1-1命题及其表示方法2019/12/2017离散数学(DiscreteMathematics)2019/12/20181-2命题联结词(LogicalConnectives)否定联结词(Negation)合取联结词(Conjunction)析取联结词(Disjunction)条件联结词(蕴涵联结词Conditional)双条件联结(等值联结词Biconditional)小结2019/12/2019一、否定联结词(Negation)¬在命题逻辑中，主要研究的是复合命题，而复合命题是由原子命题与逻辑联结词组合而成，联结词是复合命题的重要组成部分。定义1-2.1设P为一命题，P的否定是一个新的复合命题，称为P的否定式，记作“¬P”，读作“非P”，符号“¬”称为否定联结词。¬P为真当且仅当P为假.1-2命题联结词(LogicalConnectives)2019/12/2020联结词“¬”的定义真值表P¬P0110“¬”属于一元运算符.1-2命题联结词(LogicalConnectives)2019/12/2021例1P：西安是一个城市.Q：3是偶数.则¬P：西安不是一个城市.¬Q：3不是偶数.例2P：西安处处清洁.Q：这些都是男同学.则¬P：西安不处处清洁(注意，不是处处不清洁).¬Q：这些不都是男同学.1-2命题联结词(LogicalConnectives)2019/12/2022二、合取联结词(Conjunction)PQP∧Q000010100111定义1-2.2设P,Q为命题，复合命题“P并且Q”(或“P与Q”)称为P与Q的合取式，记作P∧Q，符号“∧”称为合取联结词。当且仅当P和Q同时为真时P∧Q为真。联结词“∧”的定义真值表1-2命题联结词(LogicalConnectives)2019/12/2023“∧”属于二元(binary)运算符.合取运算特点：只有参与运算的二命题全为真时，运算结果才为真，否则为假。自然语言中的表示“并且”意思的联结词，如“既…又…”、“不但…而且…”、“虽然…但是…”、“一面…一面…”、“…和…”、“…与…”等都可以符号化为∧。1-2命题联结词(LogicalConnectives)2019/12/202424例3将下列命题符号化.(1)张三既聪明又用功.(2)张三虽然聪明，但不用功.(3)张三不但聪明，而且用功.(4)张三不是不聪明，而是不用功.不要见到“与”或“和”就使用联结词∧。例如:(1)我与你是兄弟。(2)张三和李四是朋友。解解设P：张三聪明。Q：张三用功。1-2命题联结词(LogicalConnectives)则(2)P∧¬Q(3)P∧Q(4)¬(¬P)∧¬Q(1)P∧Q2019/12/2025例4试生成下列命题的合取.(1)P：房间里有张桌子.Q：今天是星期三.(2)S：李平在吃饭.R：张明在吃饭..(((1)逻辑学中允许两个相互独立无关的，甚至互为否定的原子命题生成一个新的命题如上例的1)).“∧”与自然语言中“与”“和”的不同之处：解,(.)(2)自然语言中有时在各种不同意义上使用联结词与和，不能一概用去翻译如：我与你是兄弟(1)P∧Q：房间里有张桌子且今天是星期二.1-2命题联结词(LogicalConnectives)(2)S∧R：李平与张明在吃饭.2019/12/2026三、析取联结词(Disjunction)∨PQP∨Q000011101111定义1-2.3设P,Q为命题，复合命题“P或Q”称为P与Q的析取式，记作P∨Q，符号∨称为析取联结词.P∨Q为真当且仅当P与Q中至少有一个为真.联结词“∨”的定义真值表1-2命题联结词(LogicalConnectives)2019/12/2027“∨”属于二元(binary)运算符.析取运算特点：只有参与运算的二命题全为假时，运算结果才为假，否则为真。由析取联结词的定义可以看出，“∨”与汉语中的联结词“或”意义相近，但又不完全相同。在现代汉语中，联结词的“或”实际上有“可兼或”和“排斥或”之分。考察下面命题：(1)小王爱打球或爱跑步。设P：小王爱打球。Q：小王爱跑步。1-2命题联结词(LogicalConnectives)（可兼或）则上述命题可符号化为：P∨Q2019/12/2028(4)人固有一死，或重于泰山或轻于鸿毛.(2)张三学过英语或法语。设P：张三学过英语。Q：张三学过法语(3)派小王或小李中的一人去开会。设P：派小王去开会。Q：派小李去开会。(5)ab=0,即a=0或b=0.由此可见,“P∨Q”表示的是“可兼或”.则上述命题可符号化为：P∨Q则上述命题可符号化为：(P∧¬Q)∨(¬P∧Q)1-2命题联结词(LogicalConnectives)（可兼或）（排斥或）（排斥或）（可兼或）2019/12/2029注意：当P和Q客观上不能同时发生时，“P或Q”可以符号化为“P∨Q”。1.2（）逻辑学中允许联结两个毫无关系的命题（）自然语言中有时在各种不同意义上使用联结词或，不能一概用去翻译（如:张三或李四都可以做这件事）.“∨”与自然语言中“或”的不同之处：例如：小王现在在宿舍或在图书馆。设P：小王现在在宿舍。Q：小王现在在图书馆。则上述命题可符号化为：P∨Q。1-2命题联结词(LogicalConnectives)2019/12/2030四、条件联结词(蕴涵联结词Conditional)→PQP→Q001011100111定义1-2.4设P,Q为命题，复合命题“如果P那么Q(若P则Q)”称为P与Q的条件命题，记作PQ.PQ为假当且仅当P为真且Q为假。称符号“”为条件联结词。并称P为前件，Q为后件.联结词“”的定义真值表1-2命题联结词(LogicalConnectives)2019/12/2031PQ表示的基本逻辑关系是：Q是P的必要条件或P是Q的充分条件.因此复合命题“只要