离散数学讲义(第1章)

《离散数学讲义(第1章)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、趣味逻辑数学题－巧猜围棋子离散数学讲义（电子版）∑甲手里有一个围棋子，要乙来猜棋DiscreteMathematics子的颜色是白的还是黑的。条件是：只允许乙问一个只能回答“是”或“否”的问题，但甲可以说真话，也可以说假话。问：乙可以向甲提出一个什么问题，然后从甲回答“是”或“否”天津财经大学信息科学与技术系王宁中就能判断出甲手中围棋子的颜ninglw@163.com色？2趣味逻辑数学题－巧猜围棋子趣味逻辑数学题－巧猜围棋子∑答案∑用数理逻辑学方法解题∑乙问：“棋子是白的且你说了真话，或者棋子是黑的且你说了假话，对P表示

2、：“棋子为白色”吗？”Q表示：“甲说的是真话”数理逻辑运算符：∑分析：棋子白：甲说真话：是¬（非），∧（与），∨（或）甲说假话：是棋子黑：甲说真话：否问题答案：S=(P∧Q)∨(¬P∧¬Q)甲说假话：否34数理逻辑∑数理逻辑是用数学方法来研究推理第一篇过程的科学。主要是指引进一套符号体系的方法，因此数理逻辑一般又叫符号逻辑。数理逻辑ł基本内容是：命题逻辑（演算）和谓词逻辑（演算）。561第一章命题逻辑ö命题演算是数理逻辑的基本组成部分，是谓词演算的基础。第一章ö本章包括以下内容：1-1命题及其表示法命题逻辑1-2联结词1

3、-3命题公式与翻译1-4真值表与等价公式78第一章命题逻辑1-1命题及其表示法ö本章包括以下内容：ö命题：能够表达判断（分辩其真假）的陈述语句。8例：‘中国是一个国家’。1-5重言式与蕴含式8‘9为素数’。1-6其他联结词ö原子命题（简单命题）：不能分解成更简单的陈述语句的命题。1-7对偶与范式ö复合命题：由连结词、标点符号和原子命题复合构成的命题。1-8推理理论一个命题总是具有一个“值”，称为真值一般用字母“T”(True)表示“真”，“F”(False)表示“假”。只有具有确定真值的陈述句才是命题9101-1命题及其

4、表示法（续）1-1命题及其表示法（续）判断下列句子哪些是命题？•明天是否开大会？不是命题，疑问句不是命题•中国人民是伟大的。是命题，真值为T•天气多好啊！不是命题，感叹句不是命题•雪是黑的。是命题，真值为F•我正在说谎。是悖论•1+101=110是命题，真值需根据上下文确定•我学英语，或者我学日语。复合命题•别的星球上有生物。是命题，它的真值是唯一确定•如果天气好，那么我去散步。复合命题的，只是目前人们不知道•全体立正！不是命题，祈使句不是命题再次注意：命题是具有唯一真值的陈述句。111221-1命题及其表示法（续）1-

5、2联结词（1）否定8习惯上，命题用大写字母A，B，…，P，Q，…或用带下标的大写字母Ai或数字[12]等表示。称为设P为一命题，则新命题“P是不对的”称为命题标识符。P的否定。记作：¬P例如：P：今天下雨。如：P：2是常数。或[12]：今天下雨。¬P：2不是常数。¾命题常量：命题标识符表示确定的命题。Q：今天是星期四。¾命题变元：命题标识符只表示任意命题的位置标志。¬Q：今天不是星期四。（命题变元不是命题）13141-2联结词（续）1-2联结词（续）P与¬P的真值关系：例：P：上海是一个大城市。¬P：上海并不是一个大城市

6、。P¬P或¬P：上海是一个不大的城市。TFFT这两个命题具有相同的含义，因此用同一个符号表示。否定是一个一元运算。15161-2联结词（续）1-2联结词（续）（2）合取例：P：今天下雨。设P，Q是两个命题，新命题“P并且Q”是一个复合命题，称为命题P，Q的合取。记作：Q：明天下雨。P∧Q则如：P：北京是中国的首都。P∧Q：今天下雨且明天下雨。Q：北京是一个故都。P∧Q：今天与明天都下雨。P∧Q：北京是中国的首都并且是一个P∧Q：这两天都下雨。故都。规定：P∧Q的真值为T当且仅当P，Q同时为T。合取是一个二元运算。1718

7、31-2联结词（续）1-2联结词（续）（3）析取P∧Q的真值关系：设P，Q为两个命题，则复合命题“P或者Q”称为命题P，Q的析取。记作：P∨QPQP∧Q如：P：北京是中国的首都。TTTQ：北京是一个故都。TFFP∨Q：北京是中国的首都或者是一个故都。FTF规定：P∨Q的真值为T当且仅当P，Q中至少有FFF一个真值为T。或：P∨Q的真值为F当且仅当P，Q同时为F。19201-2联结词（续）1-2联结词（续）注意：析取联结词∨与汉语中的“或”的意义不P∨Q的真值关系：完全相同。汉语中的“或”既可以表示“排斥或”，也可以表示“

8、可兼或”。PQP∨Q例如：“排斥或”TTTP：今天晚上我在家看电视或去剧场看戏。TFTFTTQ：他可能是100米或400米赛跑的冠军。“可兼或”FFF（析取）R：他昨天做了二十或三十道习题。这里“或”不析取是一个二元运算。是命题联结词命题R是一个原子命题。21221-2联结词（续）1-2联结词（续）（4）条件（蕴含）