《数学离散数学》PPT课件

《《数学离散数学》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学主讲：路永刚Email:ylu@lzu.edu.cn兰州大学信息科学与工程学院上节课的内容谓词一元谓词n元谓词量词全称量词存在量词量词的辖域自由变元与约束变元约束变元的改名规则谓词演算的永真公式谓词等价的定义定义1:两个任意谓词公式A和B,E是它们公有的论述域,若(1)对公式A和B中的谓词变元,指派以任一在E上有定义的确定的谓词。(2)对谓词命名式中的个体变元,指派以E中的任一确定的个体。所得的命题都具有同样的真值,则称公式A和B遍及E等价,记为：在E上AB。定义2:如果两谓词公式A和B,在任意论述域上都等价,则称A和B

2、等价,记为AB。定义3:给定任一谓词公式A,如果在论述域E上,对公式A中的谓词和个体变元进行定义1中的两种指派,所得命题(1)都真，则称A在E上有效或在E上永真。(2)至少有一个是真,则称A在E上可满足。(3)都假,则称A在E上永假或在E上不可满足。谓词公式的分类定义4：给定任一谓词公式A,如果在任意论述域上,对上述两种指派,(1)A永真,则称A永真或有效。(2)A至少在一个域上可满足,则称A可满足。(3)A永假,则称A永假或不可满足。若谓词公式A的个体域是有限的,谓词的解释也有限,则可用真值表判定谓词公式A是否永真。谓词公式的分类

3、例：设P(x)仅可解释为:A(x):x是质数,B(x):x是合数。论述域是{3,4},判定谓词公式P(x)∧xP(x)是否永真。解:(见右表)所以,P(x)∧xP(x)非永真式。但是，当谓词的解释和个体变元的数量稍大,用真值表判定是否永真就难以实现。这时，一般利用推导方法,因此,如同命题演算一样,首先要求出基本的永真公式,以作为推导的根据。谓词演算的基本永真公式1、首先，命题演算的永真公式也是谓词演算的永真公式,基本的就是前面介绍的表1.2-1(2)的逻辑恒等式和永真蕴含式。2.含有量词的谓词演算的基本永真公式。(i)xAA

4、xAA这里A是不含自由变元x的谓词公式,因为A的真值与x无关,所以上述等价式成立。(ii)xP(x)P(y)，或xP(x)P(x)P(y)xP(x)，或P(x)xP(x)前一公式的意义是:如果断言“对一切x,P(x)是真”成立,那么对任一确定的x,P(x)是真。后一公式的意义是:如果对某一确定的x,P(x)是真,那么断言“存在一x,使P(x)是真”成立。根据前提三段论,从这两个公式可推得xP(x)xP(x)(iii)量词的否定：(xP(x))xP(x)(xP(x))xP(x)由于“并非对一切

5、x,P(x)是真”等价于“存在一些x,P(x)是真”,所以前一式成立。由于“并不存在一x,使P(x)是真”等价于“对一切x,P(x)是真”,所以后一式成立。对比这两个式子,容易看出,如果把P(x)看作整体,那么将x和x两者互换,可从一个式得出另一个式。这说明x和x具有对偶性。另外,由于两个量词可以互相表达,所以有一个量词就够了。(xP(x))xP(x)(xP(x))xP(x)例：xyz(x+z=y)xyz(x+z=y)xyz(x+z=y)xyz(x+z=y)x

6、yz(x+z≠y)(iv)量词辖域的扩张和收缩xA(x)∨Px(A(x)∨P)xA(x)∧Px(A(x)∧P)xA(x)∨Px(A(x)∨P)xA(x)∧Px(A(x)∧P)其中P是不含自由变元x的谓词。这里也可以看出x和x具有对偶性。(v)量词的分配:①x(A(x)∧B(x))xA(x)∧xB(x)②x(A(x)∨B(x))xA(x)∨xB(x)第①个等价式的成立是由于对一切x,A(x)∧B(x)是真,等价于对一切x,A(x)是真并且对一切x,B(x)是真。第②个公式可由第①个公式推出。

7、因为①中的A(x),B(x)是任意的,所以可用A(x),B(x)分别取代A(x)和B(x),得否定等价式两边得x(A(x)∧B(x))xA(x)∧xB(x)x(A(x)∨B(x))(xA(x))∧(xB(x))x(A(x)∨B(x))xA(x)∨xB(x)第③个公式是成立的,因为存在一x使A(x)∧B(x)是真,所以存在一x使A(x)是真,同时存在一x使B(x)是真。但第③个公式不是等价式。例：设A(x)和B(x)分别解释为“x是奇数”和“x是偶数”,论述域是自然数N,则xA(x)是真,x

8、B(x)是真,所以xA(x)∧xB(x)是真,但x(A(x)∧B(x))是假,所以第③个公式不等价。(v)量词的分配:③x(A(x)∧B(x))xA(x)∧xB(x)④xA(x)∨xB(x)x(A(