离散数学第一章知识点总结.doc

离散数学第一章知识点总结(仅供参考) 1. 判断给定的句子是否为命题的基本步骤:首先应是陈述句;其次要有唯一的真值。例:(1 )我正在说谎。不是命题。因为无法判定其真假值,若假设它为假即我正在说谎,则意味着它的反为真,即我正在说实话,二者相矛盾;若假定它为真即我正在说实话,则意味着它的反为假, 我正在说谎,二者也相矛盾。这其实是一个语义上的悖论。悖论不是命题(2) x-y >2。不是命题。因为 x,y 的值不确定, 某些 x,y使x?y>2 为真, 某些 x,y使x?y>2 为假, 即x?y>2 的真假随 x,y 的值的变化而变化。因此 x?y>2 的真假无法确定, 所以 x?y>2不是命题。 2. 命题可以分为两种类型:原子命题(不能再分解为更简单命题,又可称为简单命题); 复合命题( 通过联结词、标点符号将原子命题联结而成的命题) 3. 命题常元:一个命题标识符如果表示确定的简单命题,就称为命题常元命题变元:如果一个命题标识符只表示任意简单命题的位置标志,就称它为命题变元注:当命题变元 P 用一个特定的简单命题取代时, P 才能确定真值,这时也称对 P 进行指派 4. 联接词:(1 )否定联接词: ﹁假为真,真为假;还可以用“非”、“不”、“没有”、“无”、“并不”等多种方式表示否定(2 )合取联接词: ∧一个为假就为假还可用“并且”、“同时”、“以及”、“既……又……”、“不但……而且……”、“虽然……但是……”等多种方式表达合取(3 )析取联接词: ∨一个为真就为真;一般用或表示注:联结词∨是可兼或,因为当命题 P和Q 的真值都为真时, 其值也为真。但自然语言中的“或”既可以是“排斥或”也可以是“可兼或”。例 晚上我们去教室学习或去电影院看电影。(排斥或) 例 他可能数学考了 100 分或英语考了 100 分。(可兼或) 例 刘静今天跑了 200 米或 300 米远。(既不表示“可兼或”也不表示“排斥或”,它只是表示刘静所跑的大概路程, 因此它不是命题联结词,故例 是原子命题。) (4 )蕴涵联结词: 前真后假才为假;还可以用当……则……、因为……所以……、仅当、只有……才……、除非……才……、除非……、否则非……表示(5) 等价联接词: 同真同假才为真;还可以用当且仅当、充分必要表示 5. 命题公式: 1 )单个命题变元是合式公式,并简称为原子命题公式; 2 )如果 A 是合式公式,那么(﹁ A) 也是合式公式; 3) 如果 A,B 都是合式公式, 那么(A ∧B ), (A ∨B ), (AB ), (AB) 都是合式公式; 4) 当且仅当有限次地应用 1), 2), 3) 所得到的包含命题变元、联结词和括号的字符串是合式公式。根据定义 可知, P,(﹁P ), (P (P∨Q )), ((﹁P∧Q)∧P ), ((P Q)R) 都是命题公式。而(∨P ), (P Q, (P∨Q)R) 都不是命题公式。 元命题公式:一个命题公式中总共包含有 n 个不同的命题变元 )若公式 A 是单个的命题变元,则称 A为0 层公式。 2 )称 A是 n+1 (n≥0 )层公式是指下面情况之一: (1) A= ﹁ B,B是n 层公式; (2) A=B ∧ C, 其中 B,C 分别为 i 层和 j 层公