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

离散数学第一章知识点总结(仅供参考):首先应是陈述句;其次要有唯一的真值。例:(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不是命题。:原子命题(不能再分解为更简单命题,又可称为简单命题);复合命题(通过联结词、标点符号将原子命题联结而成的命题)命题常元:一个命题标识符如果表示确定的简单命题,就称为命题常元命题变元:如果一个命题标识符只表示任意简单命题的位置标志,就称它为命题变元注:当命题变元P用一个特定的简单命题取代时,P才能确定真值,:(1)否定联接词:﹁假为真,真为假;还可以用“非”、“不”、“没有”、“无”、“并不”等多种方式表示否定(2)合取联接词:∧一个为假就为假还可用“并且”、“同时”、“以及”、“既……又……”、“不但……而且……”、“虽然……但是……”等多种方式表达合取(3)析取联接词:∨一个为真就为真;一般用或表示注:联结词∨是可兼或,因为当命题P和Q的真值都为真时,其值也为真。但自然语言中的“或”既可以是“排斥或 ”也可以是“可兼或 ”。。(排斥或) 。(可兼或) 。(既不表示“可兼或”也不表示“排斥或”,它只是表示刘静所跑的大概路程,因此它不是命题联结词,。)(4)蕴涵联结词:®前真后假才为假;还可以用当……则……、因为……所以……、仅当、只有……才……、除非……才……、除非……、否则非……表示(5)等价联接词:«同真同假才为真;还可以用当且仅当、:1)单个命题变元是合式公式,并简称为原子命题公式;2)如果A是合式公式,那么(﹁A)也是合式公式;3)如果A,B都是合式公式,那么(A∧B),(A∨B),(A®B),(AB)都是合式公式;4)当且仅当有限次地应用1),2),3)所得到的包含命题变元、联结词和括号的字符串是合式公式。,P,(﹁P),(P®(P∨Q)),((﹁P∧Q)∧P),((P«Q)®R)都是命题公式。而(∨P),(P«Q,(P∨Q)®R)都不是命题公式。n元命题公式:一个命题公式中总共包含有n个不同的命题变元1)若公式A是单个的命题变元,则称A为0层公式。2)称A是n+1(n≥0)层公式是指下面情况之一:(1)A=﹁B,B是n层公式;(2)A=B∧C,其中B,C分别为i层和j层公式,且n=max(i,j);(3)A=B∨C,其中B,C的层次同(2);(4)A=B®C,其中B,C的层次同(2);(5)A=B«C,其中B,C的层次同(2);3)若公式A的层次为k,则称A是k层公式。(﹁P∧Q)®R为3层公式。(﹁(P®﹁Q))∧((R∨S)«﹁P)为