离散数学复习题
复习1数理逻辑部分
一、主要内容
一命题逻辑基本概念主要内容
1命题与联结词命题与真值
命题判断结果惟一的陈述句命题的真值判断的结果真值的取值真与假真命题与假命题
例1下列句子中那些是命题1是有理数2
257
3xx年元旦下大雪命题分类简单命题与复合命题简单命题符号化
用小写英文字母pqr…piqirii≥1表示简单命题用“1”表示真用“0”表示假例如令
p是有理数则p的真值为0q257则q的真值为1
定义设p为命题复合命题“非p”或“p的否定”称为p的否定式记作p符号称作否定联结词规定p为真当且仅当p为假
定义设pq为两个命题复合命题“p并且q”或“p与q”称为p与q的合取式记作p∧q∧称作合取联结词规定p∧q为真当且仅当p与q同时为真
f定义设pq为两个命题复合命题“p或q”称作p
与q的析取式记作p∨q∨称作析取联结词规定p∨q
为假当且仅当p与q同时为假例2将下列命题符号化
1吴颖既用功又聪明2吴颖不仅用功而且聪明
3吴颖虽然聪明但不用功4张辉与王丽都是三好生5张辉与王丽是同学解令p吴颖用功q吴颖
聪明1pq2pq3pq
4设p张辉是三好生q王丽是三好生
pq
5p张辉与王丽是同学
13说明描述合取式的灵活性与多样性45要求分清“与”所联结的成分例3将下列命题符号化12或4是素数22或3是素数34或6是
素数
4小元元只能拿一个苹果或一个梨5王小红生于1975年或1976年
解1令p2是素数q4是素数pq2令p2是素数q3是素数pq3令p4是素数q6
是素数pq
4令p小元元拿一个苹果q小元元拿一个梨pqpq
f5p王小红生于1975年q王小红生于1976年pqpq或pq13为相容或
45为排斥或符号化时5可有两种形式而4则不能
定义设pq为两个命题复合命题“如果p则q”称作p与q的蕴涵式记作pq并称p是蕴涵式的前件q为蕴涵式的后件称作蕴涵联结词规定pq为假当且仅当p为真q为假
1pq的逻辑关系q为p的必要条件2“如果p则q”有很多不同的表述方法若p就q只要p就qp仅当q只有q才p
除非q才p或除非q否则非p…3当p为假时pq恒为真称为空证明4常出现的错误不分充分与必要条件
例4设p天冷q小王穿羽绒服将下列命题符号化1只要天冷小王就穿羽绒服2因为天冷所以小王穿羽绒服3若小王不穿羽绒服则天不冷4只有天冷小王才穿羽绒服5除非天冷小王才穿羽绒服
6除非小王穿羽绒服否则天不冷7如果天不冷则小r