离散数学--1.1-1.2数学语言与证明方法

《离散数学--1.1-1.2数学语言与证明方法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章数学语言与证明方法1第1章数学语言与证明方法1.1逻辑符号1.2集合及其运算1.3证明方法概述21.1逻辑符号命题与真值联结词(¬,,,,,)命题公式(重言式,矛盾式,可满足式)重要等值式重要推理规则个体,个体域与谓词全称量词与存在量词3联结词真值:真,假或1,0命题:具有确定真值的陈述句,通常用p,q,r等表示真命题:真值为真的命题假命题:真值为假的命题例如,p:2+2=4,q:3是偶数它们都是命题,p是真命题,q是假命题.否定联结词否定式p:非p(p的否定)p为真当且仅当p为假4联结词(续)合取联结词合取式p

2、q:p并且q(p与q)pq为真当且仅当p与q同时为真析取联结词析取式pq:p或qpq为假当且仅当p与q同时为假排斥或联结词排斥或pq:p并且非q,或者q并且非ppq为真当且仅当p与q中一个为真,另一个为假5联结词(续)蕴涵联结词蕴涵式pq:如果p,则qpq为假当且仅当p为真q为假等价联结词等价式pq:p当且仅当qpq为真当且仅当p与q同时为真或同时为假6实例设p:2是偶数,q:1+1=3,则p的真值为1q的真值为¬p的真值为¬q的真值为pq的真值为p¬q的真值为pq的真值为¬pq的真值为p¬q的真值为¬p

3、¬q的真值为pq的真值为¬pq的真值为p¬q的真值为¬p¬q的真值为0010110111001pq的真值为p¬q的真值为007实例(续)pq的真值为p¬q的真值为¬pq的真值为¬p¬q的真值为0111又设r:今天是星期一,s:明天是星期二,t:明天是星期三rs的真值为rt的真值为1不定8命题公式命题变项:取值为0或1的变元,也用p,q,r等表示.命题公式:用联结词和圆括号把命题和命题变项按照一定规则连接起来的符号串,常用A,B,C等表示.例如,A=(pq)(rp)公式的赋值:对公式中每一个命题变项给定一个值(

4、0或1).公式的成真赋值:使公式为真的赋值.公式的成假赋值:使公式为假的赋值.例如,p=1,q=1,r=1是A的成真赋值,p=0,q=1,r=0是A的成假赋值.9重言式,矛盾式与可满足式重言式(永真式):无成假赋值的命题公式矛盾式(永假式):无成真赋值的命题公式可满足式:不是矛盾式的命题公式例如,A=(pq)(rp)是可满足式,但不是重言式,B=(pq)(pq)(pq)(pq)是重言式,C=p(pq)(pq)是矛盾式.AB:蕴涵式AB是重言式的简记.AB:等价式AB是重言式的简记，称A与

5、B等值，AB是等值式.10基本等值式双重否定律AA幂等律AAA,AAA交换律ABBA,ABBA结合律(AB)CA(BC)(AB)CA(BC)分配律A(BC)(AB)(AC)A(BC)(AB)(AC)德·摩根律(AB)AB(AB)AB11基本等值式(续)吸收律A(AB)A,A(AB)A零律A11,A00同一律A0A,A1A排中律AA1矛盾律AA0蕴涵等值式ABAB等价等值式AB(AB)(B

6、A)假言易位等值式ABBA等价否定等值式ABAB归谬论(AB)(AB)A12重要推理规则(推理定律)附加律A(AB)化简律(AB)A假言推理(AB)AB拒取式(AB)BA析取三段论(AB)BA假言三段论(AB)(BC)(AC)等价三段论(AB)(BC)(AC)构造性二难(AB)(CD)(AC)(BD)破坏性二难(AB)(CD)(BD)(AC)13谓词与量词个体域:被研究对象的全体,如自然数集,人类等.个体词:个体域中

7、的一个元素.全称量词:表示任意的,所有的,一切的等.存在量词:表示存在,有的,至少有一个等.谓词:表示个体词性质或相互之间关系的词例如,谓词P(x)表示x具有性质PxP(x)表示个体域中所有的x具有性质PxP(x)表示个体域中存在x具有性质P141.2集合及其运算集合及其表示法包含(子集)与相等空集与全集集合运算(,,-,~,)基本集合恒等式包含与相等的证明方法15集合的概念朴素集合论(康托,G.Cantor),罗素(Russell)悖论集合是数学中最基本的概念,没有严格的定义理解成某些个体组成的整体,常用A,B,C等表示

8、元素:集合中的个体xA(x属于A):x是A的元素xA(x不属于A):x不是A的元素无穷集:元素个数无限的集合有穷集(有限集):元素个数有限的集合.

9、A

10、:A中元素个数k元集:k个元素的集合,k016集