离散数学大作业

《离散数学大作业》由会员分享，可在线阅读，更多相关《离散数学大作业（20页珍藏版）》请在金锄头文库上搜索。

1、 0离散数学大作业班级：15 计算机 2 班学号：20150200224姓名：王鹏时间：2017.6.30第一章 命题逻辑1.1 命题及其表示法命题的概念:数理逻辑将能够判断真假的陈述句称作命题。1.2 命题联结词1. 否定联结词P与原命题相反与原命题相反 2. 合取联结词同时为真，才为真同时为真，才为真 3. 析取联结词同时为假，才为假同时为假，才为假 4. 蕴涵联结词当且仅当当且仅当 p p 为真，为真，q q 为假为假 5. 等价联结词同时为真，或同时为假才为真同时为真，或同时为假才为真1.3 命题公式、翻译与解释1. 命题公式 定义 命题公式，简称公式，定义为：（1）单个命题变元是公式

2、；（2）如 果 P 是公式，则P 是公式；（3）如果 P、Q 是公式，则 PQ、PQ、PQ、 PQ 都是公式；（4）当且仅当能够有限次的应用(1) 、(2)、(3) 所得到的包括命题变元、联结词和括号的符号串是公式。 2. 命题的翻译可以把自然语言中的有些语句，转变成数理逻辑中的符号形式，称为命题的 翻译。命题翻译时应注意下列事项： （1）确定所给句子是否为命题。 （2）句子中联结词是否为命题联结词。 （3）要正确的选择原子命题和合适的命题联结词。1.4 真值表与等价公式1. 真值表 定义 将公式 G 在其所有解释下所取得的真值列成一个表，称为 G 的真值表。构造真值表的方法如下： （1）找出

3、公式 G 中的全部命题变元，并按一定的顺序排列成 P1，P2，Pn。 （2）列出 G 的 2n个解释，赋值从 000（n 个）开始，按二进制递加顺序依次写出各赋值，直到 111 为止（或从 111 开始，按二进制递减顺序写出各赋值， 直到 000 为止） ，然后从低到高的顺序列出 G 的层次。1（3）根据赋值依次计算各层次的真值并最终计算出 G 的真值成真赋值成真赋值+ +成假赋值成假赋值=2=2n n2. 命题公式的分类定义 设 G 为公式： （1）如果 G 在所有解释下取值均为真，则称 G 是永真式或重言式永真式或重言式； （2）如果 G 在所有解释下取值均为假，则称 G 是永假式或矛盾式

4、；永假式或矛盾式； （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 1）双重否定律）双重否定律 A AA A （2 2）等幂律）等幂律 AAAAA A ； AAAAA A （3 3）交换律）交换律 ABABBABA ； ABABBABA （4 4

5、）结合律）结合律 （ABAB）CCAA（BCBC） （ABAB）CCAA（BCBC） （5 5）分配律）分配律 （ABAB）CC（ACAC）（BCBC） （ABAB）CC（ACAC）（BCBC） （6 6）德）德摩根律摩根律 （ABAB）AAB B （ABAB）AAB B （7 7）吸收律）吸收律 AA（ABAB）A A；AA（ABAB）A A （8 8）零一律）零一律 A1A11 1 ； A0A00 0 （9 9）同一律）同一律 A0A0A A ； A1A1A A （1010）排中律）排中律 AAA A1 1 （1111）矛盾律）矛盾律 AAA A0 0 （1212）蕴涵等值式）蕴涵等值式

6、ABABABAB （1313）假言易位）假言易位 ABABBBA A （1414）等价等值式）等价等值式 A AB B（ABAB）（BABA） （1515）等价否定等值式）等价否定等值式 A AB BA AB BB BA A （1616）归缪式）归缪式 （ABAB）（AAB B）A A 4. 置换规则定理（置换规则） 设（A）是一个含有子公式 A 的命题公式，（B）是用 公式 B 置换了（A）中的子公式 A 后得到的公式，如果 AB，那么（A） （B） 。1.5 对偶与范式1. 对偶 定义 在仅含有联结词 、的命题公式 A 中，将联结词换成，将2换成，如果 A 中含有特殊变元 0 或 1，就将

7、 0 换成 1，1 换成 0，所得的命题 公式 A*称为 A 的对偶式。 例：公式（PQ）（PQ） 的对偶式为：（PQ）（PQ） 定理 设 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 是两个命题公式，若 AB，则 A*B*，其中 A*、B*分别为 A、B 的对偶式。 2. 范式 定义 仅由有限个命题变元及其否定构成的析取式称为简单析取式简单析取式，仅由有 限个命题变元及其否定构成的

8、合取式称为简单合取式简单合取式。 定义 仅由有限个简单合取式构成的析取式称为析取范式析取范式。仅由有限个简单 析取式构成的合取式称为合取范式合取范式。 定理（范式存在定理）任何命题公式都存在着与之等价的析取范式和合取范式。 3. 主范式 定义 设 G 为公式，P1，P2，Pn为 G 中的所有命题变元，若 G 的析取范 式中每一个合取项都是 P1，P2，Pn的一个极小项，则称该析取范式为 G 的 主析取范式。矛盾式的主析取范式为 0。 定理 任意的命题公式都存在一个唯一的与之等价的主析取范式。定义 设 G 为公式，P1，P2，Pn为 G 中的所有命题变元，若 G 的合取 范式中每一个析取项都是

9、P1，P2，Pn的一个极大项，则称该合取范式为 G 的主合取范式。通常，主合取范式用表示。重言式的主合取范式中不含任何极 大项，用 1 表示。定理 任意的命题公式都存在一个唯一的与之等价的主合取范式。1.6 公式的蕴涵1. 蕴涵的概念定义 设 G、H 是两个公式，若 GH 是永真式，则称 G 蕴涵 H，记作 GH。 蕴涵关系有如下性质： （1） 对于任意公式 G，有 GG； （2）对任意公式 G、H，若 GH 且 HG，则 GH； （3） 若 GH 且 HL，则 GL。 2. 基本蕴涵式 （1 1）PQPQP P； （2 2）PQPQQ Q； （3 3）P PPQPQ； (4)(4) Q QP

10、QPQ； （5 5）P P（PQPQ） ； （6 6）Q Q（PQPQ） ； （7 7）（PQPQ）P P； （8 8）（PQPQ）Q Q； （9 9）P P，PQPQQ Q； （1010）Q Q，PQPQP P； （1111）P P，PQPQQ Q； （1212）PQPQ，QRQRPRPR； （1313）PQPQ，PRPR，QRQRR R； （1414）PQPQ，RSRS（PRPR）（QSQS） ； （1515）P P，Q QPQPQ。1.7 其它联结词与最小联结词组31. 其它联结词 定义 设 P、Q 为命题公式，则复合命题 P Q 称为 P 和 Q 的不可兼析取， 当且仅当 P 与 Q

11、的真值不相同时，PQ 的真值为 1，否则 PQ 的真值为假。定义 设 P、Q 是两个命题公式，复合命题 P Q 称为命题 P、Q 的条件否c定，当且仅当 P 的真值为 1，Q 的真值为 0 时，P Q 的真值为 1，否则 cPQ 的真值为 0。c2. 最小联结词组 定义 设 S 是一些联结词组成的非空集合，如果任何的命题公式都可以用仅 包含 S 中的联结词的公式表示，则称 S 是联结词的全功能集。特别的，若 S 是联 结词的全功能集且 S 的任何真子集都不是全功能集，则称 S 是最小全功能集，又 称最小联结词组。定理 ，是联结词的全功能集。定理 ，是联结词的全功能集。 定理 ，、，是最小联结词

12、组。定理 ，是最小联结词组。1.8 命题逻辑推理理论1.8.1 命题逻辑推理理论 定义 如果 G1，G2，Gn蕴涵 H，则称 H 能够由 G1，G2，Gn有效推 出，G1，G2，Gn称为 H 的前提，H 称为 G1，G2，Gn的有效结论。称 （G1G2Gn）H 是由前提 G1，G2，Gn推结论 H 的推理的形式结构。 2. 推理规则下面给出推理中常用的推理规则。 1 前提引入规则：前提引入规则：可以在证明的任何时候引入前提； 2 结论引入规则：结论引入规则：在证明的任何时候，已证明的结论都可以作为后续证明的前 提； 3 置换规则：置换规则：在证明的任何时候，命题公式中的任何子命题公式都可以用与

13、之 等价的命题公式置换。 4 假言推理规则：假言推理规则：P，PQQ 5 附加规则：附加规则：PPQ； 6 化简规则：化简规则：P，QP； 7 拒取式规则：拒取式规则：Q，PQP； 8 假言三段论规则：假言三段论规则：PQ，QRPR； 9 析取三段论规则：析取三段论规则：P，PQQ； 10.构造性二难规则：构造性二难规则：PQ，PR，QRR； 11.合取引入规则：合取引入规则：P，QPQ 3. 推理常用方法 1.直接证法直接证法就是根据一组前提，利用前面提供的一些推理规则，根据已知的等 价公式和蕴涵式，推演得到有效的结论的方法，即有前提直接推导出结论。 2间接证法间接证法主要有如下两种情况。4（1）附加前提证明法 有时要证明的结论以蕴涵式的形式出现，即推理的形 式结构为：（G1G2Gn）（RC）设（G1G2Gn）为 S，则上述 推理可表示为证明 S（RC） ，即证明 S（RC）为永真式。用附加前提证明法证明下面推理。 前提：P（QR） ，SP，Q 结论