离散数学部分概念和公式总结(考试专用) - CSDN文库

需积分: 35 187 浏览量更新于2023-03-16 评论收藏 111KB DOC 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

命题：称能判断真假的陈述句为命题。

命题公式：若在复合命题中，p、q、r 等不仅可以代表命题常项，还可以代表命题变项，这

样的复合命题形式称为命题公式。

命题的赋值：设 A 为一命题公式，p ,p ,…,p 为出现在 A 中的所有命题变项。给 p ,p ,…,p 指

定一组真值，称为对 A 的一个赋值或解释。若指定的一组值使 A 的值为真，则称成真赋值。

真值表：含 n（n≥1）个命题变项的命题公式，共有 2^n 组赋值。将命题公式 A 在所有赋值

下的取值情况列成表，称为 A 的真值表。

命题公式的类型：（ 1）若 A 在它的各种赋值下均取值为真，则称 A 为重言式或永真式。

（2）若 A 在它的赋值下取值均为假，则称 A 为矛盾式或永假式。

（3）若 A 至少存在一组赋值是成真赋值，则 A 是可满足式。

主析取范式：设命题公式 A 中含 n 个命题变项，如果 A 得析取范式中的简单合取式全是极

小项，则称该析取范式为 A 的主析取范式。

主合取范式：设命题公式 A 中含 n 个命题变项，如果 A 得析取范式中的简单合析式全是极

大项，则称该析取范式为 A 的主析取范式。

命题的等值式：设 A、B 为两命题公式，若等价式 A↔B 是重言式，则称 A 与 B 是等值的，

记作 A<=>B。

约束变元和自由变元：在合式公式x A 和 $x A 中，称 x 为指导变项，称 A 为相应量词的

辖域，x 称为约束变元，x 的出现称为约束出现，A 中其他出现称为自由出现（自由变元）。

一阶逻辑等值式：设 A，B 是一阶逻辑中任意的两公式，若 A↔B 为逻辑有效式，则称 A

与 B 是等值的，记作 A<=>B，称 A<=>B 为等值式。

前束范式：设 A 为一谓词公式，若 A 具有如下形式 Q1x1Q2x2Qk…xkB，称 A 为前束范式。

集合的基本运算：并、交、差、相对补和对称差运算。

笛卡尔积：设 A 和 B 为集合，用 A 中元素为第一元素，用 B 中元素为第二元素构成有序对

组成的集合称为 A 和 B 的笛卡尔积，记为 A×B。

二元关系：如果一个集合 R 为空集或者它的元素都是有序对，则称集合 R 是一个二元关系。

特殊关系：（ 1）、空关系：Φ （2）全域关系：EA={<x, y> | x∈A ∧ y∈A }= A×A

（3）恒等关系：IA={<x, x> | x∈A}

（4）小于等于关系：LA={<x, y>| x, y∈A∧x≤y∈A },A Í R

（5）整除关系： RÍ ={<x, y>| x，y∈ψ ∧ x Í y} ,ψ 是集合族

二元关系的运算：设 R 是二元关系，

（1）R 中所有有序对的第一元素构成的集合称为 R 的定义域 domR = { x | $y（<x ,

y>∈R）}

（2）R 中所有有序对的第二元素构成的集合称为 R 的值域 ranR = {y | $x（<x , y>∈R）}

（3）R 的定义域和值域的并集称为 R 的域 fldR= domR ∪ranR

二元关系的性质：自反性，反自反性，对称性，反对称性，传递性。

等价关系：如果集合 A 上的二元关系 R 是自反的，对称的和传递的，那么称 R 是等价关系。

设 R 是 A 上的等价关系，x , y 是 A 的任意元素，记作 x～y。

等价类：设 R 是 A 上的等价关系，对任意的x∈A，令[x]R={ y | y∈A ∧ x R y }，称[x]R 为 x

关于 R 的等价类。

偏序关系：设 R 是集合 A 上的二元关系，如果 R 是自反的，反对称的和传递的，那么称 R

为 A 上的偏序，记作≤；称序偶< A ,R >为偏序集合。

函数的性质：设 f: A®B，

（1）若 ranf = B，则称 f 是满射（到上）的。

（2）若 yÎ ranf 都存在唯一的 x ÎA 使得 f(x)=y,则称 f 是单射（— —）的。

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余4页未读，立即下载

评论0

smile_828

粉丝: 1
资源: 6

会员权益专享

图片转文字

全年可省5，000元立即开通

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈