离散数学第1章学案.ppt

1.1 命 题1.1.1 基本概念　　断言是一陈述语句。 一个命题是一个或真或假而不能两者都是的断言。如果命题是真，我们说它的真值为真; 如果命题是假，我们说它的真值是假。 　　例 1.1 - 1 下述都是命题:　　(1) 今天下雪;　　(2) 3+3=6;　　(3) 2 是偶数而 3 是奇数;　　(4) 陈涉起义那天，杭州下雨;　　(5) 较大的偶数都可表为两个质数之和。 　　以上命题中，(1)的真值取决于今天的天气; (2)和(3)是真; (4)已无法查明它的真值，但它是或真或假的， 故将它归属于命题; (5)目前尚未确定其真假，但它是有真值的，应归属于命题。 　　例 1.1 - 2 下述都不是命题:　　(1) x+y＞4。 　　(2) x=3。　　(3) 真好啊!　　(4) 你去哪里?　　(1)和(2)是断言，但不是命题，因为它的真值取决于x和y的值。 (3)和(4)都不是断言，所以不是命题。 下边我们再看一个例子。 　　例 1.1 - 3 一个人说:“我正在说谎”。　　他是在说谎还是在说真话呢? 如果他讲真话，那么他所说的是真，也就是他在说谎。 我们得出结论如果他讲真话，那么他是在说谎。 另一方面，如果他是说谎，那么他说的是假; 因为他承认他是说谎，所以他实际上是在说真话，我们得出结论如果他是说谎，那么他是讲真话。 　　从以上分析，我们得出他必须既非说谎也不是讲真话。 这样，断言“我正在说谎”事实上不能指定它的真假，所以不是命题。 这种断言叫悖论。　　若一个命题已不能分解成更简单的命题，则这个命题叫原子命题或本原命题。 例1.1 - 1中(1)、(2)、(4)、(5)都是本原命题，但(3)不是，因为它可写成“2 是偶数”和“3 是奇数”两个命题。　　命题和本原命题常用大写字母P、Q、R…表示。 如用P表示“4 是质数”，则记为 　　　P: 4 是质数 1.1.2 命题联结词　　原子命题常可通过一些命题联结词构成新命题，这种命题称为复合命题。例如　　 P: 明天下雪　　 Q: 明天下雨是两个命题，利用联结词“不”、“并且”、“或(者)”等可分别构成新命题:　　 “明天不下雪”;　　 “明天下雪并且明天下雨”;　　 “明天下雪或者明天下雨”等。 即　　 “非P”;　　 “P并且Q”;　　 “P或Q”等。　　在代数式x+3 中，x、3 叫运算对象，+叫运算符，x+3 表示运算结果。 在命题演算中，也用同样的术语。 命题联结词就是命题演算中的运算符，叫逻辑运算符或叫逻辑联结词。 常用的联结词有以下 5 个。 1 否定词 ? 设P表示命题，则‘P不真’ 是另一命题，记为 ? P，读为 ‘非P’ 否定词可用右表定义，此表称为 ? P的真值表 　　这张表叫真值表。定义运算符的真值表， 可指明如何用运算对象的真值来决定一个应用运算符的命题的真值。 真值表的左边列出运算对象的真值的所有可能组合，结果命题的真值列在最右边的一列。 为了便于阅读，我们通常用符号T(true)或 1 代表真，符号F(false)或 0 代表假。 一般在公式中采用T和F，在真值表中采用 1 和 0。 这样，以上真值表可写成表1.1-2所示的形式。 表1.1-2 　　例 1.1-4　　(1) P: 4 是质数。　 　　　P: 4 不是质数。或 4 是质数，不是这样。　　(2) Q: 这些都是男同学。　 　　　Q: 这些不都是男同学。(翻译成“这些都不是男同学”是错的。) 2 合取词 ∧ 若 P,Q 表示命题，则 ‘P并且Q’ 也是命题，记为 P∧Q ,读为 ‘P合取Q’. P∧Q 的真值表如右表所示。由真值表可知 P∧Q 真,当且仅当 P,Q 俱真. 3 析取词 ∨ 若 P,Q 表示命题，则 ‘P或者Q’ 也是命题，记为 P∨Q,读为 ‘P析取Q’. P∨Q 的真值表如右表所示。由真值表可知 P∨Q 真,当且仅当P,Q 至少有一个真 表1.1-4 　　例 1.1-6　　(1) P: 今晚我写字，Q: 今晚我看书。　　　P∨Q: 今晚我写字或看书。　　“或”字常见的含义有两种: 一种是“可兼或”，如例1.1-6中的或，它不排除今晚既看书又写字这种情况; 一种是“排斥或”，例如“人固有一死，或重于泰山，或轻于鸿毛”中的“或”，它表示非此即彼，不可兼得。 运算符∨表示可兼或，排斥或以后用另一符号表达。 　　(2) P: 今年是闰年; Q: 今年她生孩子。　　P∨Q: 今年是闰年或者今年她生孩子。　　逻辑运算符