离散数学大作业.doc

离散数学大作业
班级:15计算机2班
学号:20150200224
姓名:王鹏
时间:
第一章命题逻辑

命题的概念:
数理逻辑将能够判断真假的陈述句称作命题。

1. 否定联结词﹁P
与原命题相反
2. 合取联结词∧
同时为真,才为真
3. 析取联结词∨
同时为假,才为假
4. 蕴涵联结词→
当且仅当p为真,q为假
5. 等价联结词
同时为真,或同时为假才为真
命题公式、翻译与解释
1. 命题公式
定义命题公式,简称公式,定义为:
(1)单个命题变元是公式;
(2)如果P是公式,则﹁P是公式;
(3)如果P、Q是公式,则P∧Q、P∨Q、PQ、 PQ都是公式;
(4)当且仅当能够有限次的应用(1) 、(2)、(3) 所得到的包括命题变元、联结词和括号的符号串是公式。
2. 命题的翻译
可以把自然语言中的有些语句,转变成数理逻辑中的符号形式,称为命题的翻译。
命题翻译时应注意下列事项:
(1)确定所给句子是否为命题。
(2)句子中联结词是否为命题联结词。
(3)要正确的选择原子命题和合适的命题联结词。
真值表与等价公式
1. 真值表
定义将公式G在其所有解释下所取得的真值列成一个表,称为G的真值表。
构造真值表的方法如下:
(1)找出公式G中的全部命题变元,并按一定的顺序排列成P1,P2,…,Pn。
(2)列出G的2n个解释,赋值从00…0(n个)开始,按二进制递加顺序依次写出各赋值,直到11…1为止(或从11…1开始,按二进制递减顺序写出各赋值,直到00…0为止),然后从低到高的顺序列出G的层次。
(3)根据赋值依次计算各层次的真值并最终计算出G的真值
成真赋值+成假赋值=2n
2. 命题公式的分类
定义设G为公式:
(1)如果G在所有解释下取值均为真,则称G是永真式或重言式;
(2)如果G在所有解释下取值均为假,则称G是永假式或矛盾式;
(3)如果至少存在一种解释使公式G取值为真,则称G是可满足式。
3. 等价公式
定义设A和B是两个命题公式,如果A和B在任意赋值情况下都具有相同的真值,则称A和B是等价公式。记为AB。
性质定理
设A、B、C是公式,则
(1)AA
(2)若AB则BA
(3)若AB且BC则AC
定理设A、B、C是公式,则下述等价公式成立:
(1)双重否定律 AA
(2)等幂律 A∧AA ; A∨AA
(3)交换律 A∧BB∧A ; A∨BB∨A
(4)结合律(A∧B)∧CA∧(B∧C)
(A∨B)∨CA∨(B∨C)
(5)分配律(A∧B)∨C(A∨C)∧(B∨C)
(A∨B)∧C(A∧C)∨(B∧C)
(6)德·摩根律(A∨B)A∧B
(A∧B)A∨B
(7)吸收律 A∨(A∧B)A;A∧(A∨B)A
(8)零一律 A∨11 ; A∧00
(9)同一律 A∨0A ; A∧1A
(10)排中律 A∨A1
(11)矛盾律 A∧A0
(12)蕴涵等值式 A→BA∨B
(13)假言易位 A→BB→A
(14)等价等值式 AB(A→B)∧(B→A)
(15)等价否定等值式 ABABBA
(16)归缪式(A→B)∧(A→B)A
4. 置换规则
定理(置换规则) 设(A)是一个含有子公式A的命题公式,(B)是用公式B置换了(A)中的子公式A后得到的公式,如果AB,那么(A)(B)。
对偶与范式
1. 对偶
定义在仅含有联结词Ø、∧、∨的命题公式A中,将联结词∧换成∨,将∨
换成∧,如果A中含有特殊变元0或1,就将0换成1,1换成0,所得的命题公式A*称为A的对偶式。
例:公式(P∨Q)∧(P∨Q) 的对偶式为:(P∧Q)∨(P∧Q)
定理设A和A*互为对偶式,P1,P2,…,Pn是出现在A和A*中的所有原子变元,若将A和A*写成n元函数形式,则
(1)A(P1,P2,…,Pn)A*(P1,P2,…,Pn)
(2)A(P1,P2,…,Pn)A*(P1,P2,…,Pn)
定理(对偶原理)设A、B是两个命题公式,若AÛB,则A*B*,其中A*、B*分别为A、B的对偶式。
2. 范式
定义仅由有限个命题变元及其否定构成的析取式称为简单析取式,仅由有限个命题变元及其否定构成的合取式称为简单合取式。
定义仅由有限个简单合取式构成的析取式称为析取范式。仅由有限个简单析取式构成的合取式称为合取范式。
定理(范式存在定理)任何命题公式都存在着与之等价的析取范式和合取范式。
3. 主范式
定义设G为公式,P1,P2,…,Pn为G中的所有命题变元,若G的析取