离散数学大作业.docx

离散数学大作业.docx离散数学大作业
班级：15计算机2班
学号：20150200224 姓名：王鹏
时间：
第一章命题逻辑
1. 1命题及其表不法
命题的概念：
数理逻辑将能够判断真假的陈述句称作命题。
1. 2命题联结词
否定联结词「P
与原命题相反
合取联结词/\
同时为真，才为真
析取联结词V
同时为假，才为假
蕴涵联结词一
当且仅当P为真，q为假
等价联结词㈠
同时为真，或同时为假才为真
命题公式、翻译与解释
命题公式
定义命题公式，简称公式，定义为：（1）单个命题变元是公式；（2）如果P 是公式，则「P是公式；（3）如果P、Q是公式，则PAQ> PVQ> PtQ、P — Q 都是公式；（4）当且仅当能够有限次的应用（1）、（2）、（3）所得到的包括命题变 元、联结词和括号的符号串是公式。
命题的翻译
可以把自然语言中的有些语句，转变成数理逻辑中的符号形式，称为命题的 翻译。
命题翻译时应注意下列事项：
（1） 确定所给句子是否为命题。
（2） 句子中联结词是否为命题联结词。
（3） 要正确的选择原子命题和合适的命题联结词。
真值表与等价公式
]. 真值表
定义'将公式G在其所有解释下所取得的真值列成一个表，称为G的真值表。 构造真值表的方法如下：
（1） 找出公式G中的全部命题变元，并按一定的顺序排列成Pl，P2，…，Pn。
（2） 列出G的2n个解释，赋值从00-0 （n个）开始，按二进制递加顺序依次写 出各赋值，直到11-1为止（或从11-1开始，按二进制递减顺序写出各赋值， 直到00-0为止），然后从低到高的顺序列出G的层次。
（3） 根据赋值依次计算各层次的真值并最终计算出G的真值
成真赋值+成假赋值=2n
命题公式的分类 定义设G为公式：
如果G在所有解释下取值均为真，则称G是永真式或重言式；
如果G在所有解释下取值均为假，则称G是永假式或矛盾式；
如果至少存在一种解释使公式G取值为真，则称G是可满足式。
等价公式
定义 设A和B是两个命题公式，如果A和B在任意赋值情况下都具有相同 的真值，则称A和B是等价公式。记为AoB。
性质定理
设A、B、C是公式，则
(1)
(2)
(3)
定理
(1)
(2)
(3)
(4)
AoA
若AoB则BoA 若AoB且BoC则AoC
设A、B、C是公式，则下述等价公式成立: 双重否定律 等幕律 交换律 结合律
(5)
(6)
-1 - A A
A/\AoA ； A/\BoB/\A ； (AAB) AC^AA
(AVB) VC^AV (BVC)
(AAB) \/Co (AVC) A (BVC) (AVB) /\Co (AAC) V (BAC)
「(AVB)
「(AAB)
AV (AAB) oA； AA (AVB) oA
AVlol ；
AVOoA ；
AV「Ao 1
A A - A 0
A—Bo「A\/B
A—Bo —iBf —iA
A㈠Bo (A—B)
等价否定等值式A㈠Bo「A㈠「Bo「B㈠「A 归缪式 (A-B) A (A-「B)
置换规则
AVAoA
AVB^BVA
(BAC)
分配律
德•摩根律
(7)
(8)
(9)
(10)
(11)
(12)
(13)
(14)
(15)
(16)
4.
吸收律
零一律 同一律
排中律 矛盾律 蕴涵等值式 假言易位 等价等值式
A/\0o0
A/\loA
A (B-A)
定理(置换规则)设。(A)是一个含有子公式A的命题公式，(p (B)是用公
式B置换了 (p (A)中的子公式A后得到的公式，如果AoB,那么° (A) o (p (B)。
5 对偶与范式
] 禺
定义 在仅含有联结词0、N、\/的命题公式A中，将联结词/\换成V,将
▽换成如果A中含有特殊变元0或1,就将0换成1, 1换成0,所得的命题 公式A*称为A的对偶式。
例：公式(「PVQ) A (PV^Q)的对偶式为：(「P/\Q) V (P/\「Q)
定理 设A和A*互为对偶式，Pi，P2,…，Pn是出现在A和A*中的所有原子 变元，若将A和A*写成n元函数形式，则
-.A (P], P2，…，Pn)oA* (->Pi， ->P2,…，->Pn)
A (->P1， ->P2，…，->Pn)o->A* (Pi，P2，…，Pn)
定理(对偶原理)设A、B是两个命题公式，若A0B,则A*oB*,其中A*、 B*分别为A、B的对偶式。
范式
定义仅由有限个命题变元及其否定构成的析取式称为简单析取式，仅由有 限个命题变元及其否定构成