离散数学讲义(第1章)VIP免费

1天津财经大学信息科学与技术系王宁ninglw@163.comDiscreteMathematics离散数学讲义（电子版）2趣味逻辑数学题－巧猜围棋子�甲手里有一个围棋子，要乙来猜棋子的颜色是白的还是黑的。条件是：只允许乙问一个只能回答“是”或“否”的问题，但甲可以说真话，也可以说假话。问：乙可以向甲提出一个什么问题，然后从甲回答“是”或“否”中就能判断出甲手中围棋子的颜色？3趣味逻辑数学题－巧猜围棋子�答案�乙问：“棋子是白的且你说了真话，或者棋子是黑的且你说了假话，对吗？”�分析：棋子白：甲说真话：是甲说假话：是棋子黑：甲说真话：否甲说假话：否4趣味逻辑数学题－巧猜围棋子�用数理逻辑学方法解题P表示：“棋子为白色”Q表示：“甲说的是真话”数理逻辑运算符：¬（非），∧（与），∨（或）问题答案：S=(P∧Q)∨(¬P∧¬Q)5第一篇数理逻辑6数理逻辑�数理逻辑是用数学方法来研究推理过程的科学。主要是指引进一套符号体系的方法，因此数理逻辑一般又叫符号逻辑。�基本内容是：命题逻辑（演算）和谓词逻辑（演算）。27第一章命题逻辑8第一章命题逻辑�命题演算是数理逻辑的基本组成部分，是谓词演算的基础。�本章包括以下内容：1-1命题及其表示法1-2联结词1-3命题公式与翻译1-4真值表与等价公式9第一章命题逻辑�本章包括以下内容：1-5重言式与蕴含式1-6其他联结词1-7对偶与范式1-8推理理论10�命题：能够表达判断（分辩其真假）的陈述语句。�例：‘中国是一个国家’。�‘9为素数’。�原子命题（简单命题）：不能分解成更简单的陈述语句的命题。�复合命题：由连结词、标点符号和原子命题复合构成的命题。一个命题总是具有一个“值”，称为真值一般用字母“T”(True)表示“真”，“F”(False)表示“假”。只有具有确定真值的陈述句才是命题1-1命题及其表示法11判断下列句子哪些是命题？•中国人民是伟大的。•雪是黑的。•1+101=110•别的星球上有生物。•全体立正！是命题，真值为T是命题，真值为F是命题，真值需根据上下文确定是命题，它的真值是唯一确定的，只是目前人们不知道不是命题，祈使句不是命题1-1命题及其表示法（续）12•明天是否开大会？•天气多好啊！•我正在说谎。•我学英语，或者我学日语。•如果天气好，那么我去散步。不是命题，疑问句不是命题不是命题，感叹句不是命题是悖论复合命题复合命题1-1命题及其表示法（续）再次注意：命题是具有唯一真值的陈述句。313�习惯上，命题用大写字母A，B，…，P，Q，…或用带下标的大写字母Ai或数字[12]等表示。称为命题标识符。例如：P：今天下雨。或[12]：今天下雨。�命题常量：命题标识符表示确定的命题。�命题变元：命题标识符只表示任意命题的位置标志。（命题变元不是命题）1-1命题及其表示法（续）14（1）否定设P为一命题，则新命题“P是不对的”称为P的否定。记作：¬P如：P：2是常数。¬P：2不是常数。Q：今天是星期四。¬Q：今天不是星期四。1-2联结词15例：P：上海是一个大城市。¬P：上海并不是一个大城市。或¬P：上海是一个不大的城市。这两个命题具有相同的含义，因此用同一个符号表示。1-2联结词（续）16P与¬P的真值关系：TF¬PFTP否定是一个一元运算。1-2联结词（续）17设P，Q是两个命题，新命题“P并且Q”是一个复合命题，称为命题P，Q的合取。记作：P∧Q如：P：北京是中国的首都。Q：北京是一个故都。P∧Q：北京是中国的首都并且是一个故都。（2）合取1-2联结词（续）规定：P∧Q的真值为T当且仅当P，Q同时为T。18P∧Q：今天下雨且明天下雨。例：P：今天下雨。Q：明天下雨。P∧Q：今天与明天都下雨。则P∧Q：这两天都下雨。1-2联结词（续）合取是一个二元运算。419FFFFFTFTP∧QTFTTPQP∧Q的真值关系：1-2联结词（续）20设P，Q为两个命题，则复合命题“P或者Q”称为命题P，Q的析取。记作：P∨Q如：P：北京是中国的首都。Q：北京是一个故都。P∨Q：北京是中国的首都或者是一个故都。规定：P∨Q的真值为T当且仅当P，Q中至少有一个真值为T。1-2联结词（续）（3）析取或：P∨Q的真值为F当且仅当P，Q同时为F。21P∨Q的真值关系：FFFTFTTTP∨QTFTTPQ1-2联结词（续）析取是一个二元运算...