离散数学第一章命题逻辑知识点总结.doc

数理逻辑部分第1章 :判断结果惟一的陈述句命题的真值:判断的结果真值的取值:真与假真命题:真值为真的命题假命题:真值为假的命题注意: 感叹句、祈使句、疑问句都不是命题,陈述句中的悖论以及判断结果不惟一确定的也不是命题。简单命题(原子命题):简单陈述句构成的命题复合命题:由简单命题与联结词按一定规则复合而成的命题简单命题符号化用小写英文字母p,q,r,…,pi,qi,ri(i≥1)表示简单命题用“1”表示真,用“0”表示假例如,令p: 是有理数,则p的真值为0q:2+5=7,“”定义设p为命题,复合命题“非p”(或“p的否定”)称为p的否定式,,“∧”定义设p,q为二命题,复合命题“p并且q”(或“p与q”)称为p与q的合取式,记作p∧q.∧称作合取联结词,并规定p∧q为真当且仅当p与q同时为真注意:描述合取式的灵活性与多样性分清简单命题与复合命题例将下列命题符号化. (1)王晓既用功又聪明.(2)王晓不仅聪明,而且用功.(3)王晓虽然聪明,但不用功.(4)张辉与王丽都是三好生.(5) p:王晓用功,q:王晓聪明,则(1) p∧q(2) p∧q(3) p∧:张辉是三好学生,s:王丽是三好学生(4) r∧s.(5) 令t:张辉与王丽是同学,:(1)~(4)说明描述合取式的灵活性与多样性.(5)中“与”联结的是两个名词,“∨”定义设p,q为二命题,复合命题“p或q”称作p与q的析取式,记作p∨q.∨称作析取联结词,并规定p∨ 将下列命题符号化(1) 2或4是素数.(2) 2或3是素数.(3) 4或6是素数.(4) 小元元只能拿一个苹果或一个梨.(5) :2是素数,q:3是素数,r:4是素数,s:6是素数,则(1),(2),(3): p∨r, p∨q, r∨s, 它们的真值分别为1,1,(4),(5):小元元拿一个苹果,u:小元元拿一个梨,则(4)符号化为 (t∧u)∨(t∧u).令v:王晓红生于1975年,w:王晓红生于1976年,则(5)既可符号化为(v∧w)∨(v∧w),又可符号化为v∨w,为什么?“”定义设p,q为二命题,复合命题“如果p,则q”称作p与q的蕴涵式,记作pq,并称p是蕴涵式的前件,,并规定,:q为p的必要条件“如果p,则q”的不同表述法很多:若p,就q只要p,就qp仅当q只有q才p除非q,才p 或 除非q,,pq为真常出现的错误:“”定义设p,q为二命题,复合命题“p当且仅当q”称作p与q的等价式,:(1)pq的逻辑关系:p与q互为充分必要条件(2)pq为真当且仅当p与q同真或同假联结词优先级:(),,,,,同级按从左到右的顺序进行以上给出了5个联结词:,,,,,组成一个联结词集合{,,,,},联结词的优先顺序为:,,,,;如果出现的联结词同级,又无括号时,则按从左到右的顺序运算;若遇有括号时,:本书中使用的括号全为园括号. ?命题常项??命题变项与合式公式?命题常项:简单命题?命题变项:真值不确定的陈述句?定义合式公式(命题公式,公式)递归定义如下:?(1)单个命题常项或变项p,q,r,…,pi,qi,ri,…,0,1? 是合式公式?(2)若A是合式公式,则(A)也是合式公式?(3)若A,B是合式公式,则(AB),(AB),(AB),(AB)也是合式公式?(4)只有有限次地应用(1)~(3)形成的符号串才是合式公式?说明:元语言与对象语言, 外层括号可以省去合式公式的层次定义(1)若公式A是单个的命题变项,则称A为0层公式.(2)称A是n+1(n≥0)层公式是指下面情况之一:(a)A=B,B是n层公式;(b)A=BC,其中B,C分别为i层和j层公式,且n=max(i,j);(c)A=BC,其中B,C的层次及n同(b);(d)A=BC,其中B,C的层次及n同(b);(e)A=BC,其中B,C的层次及n同(b).例如 公式p                      0层p                      1层pq