L2命题逻辑2 离散数学ppt课件

We denote the Inverse relation of B to A by S R-1.
R1 {(b, a) | (a, b) R, a A, b B}
2024/11/24
§5.1 Relations and their properties (7)
Exam:集合A={a, b, c}，B={1, 2, 3, 4, 5}，R是A 上的关系，S是A到B的关系。 R={<a, a>, <a, c>, <b, b>, <c, b>, <c, c>}， S={<a, 1>, <a, 4>, <b, 2>, <c, 4>, <c, 5>} 求：S·R，(S·R)-1，R–1，S–1，R–1·S–1
2024/11/24
§5.1 Relations and their properties (7) 5.1.4 Properties of relations
特殊关系 空关系 全域关系EA 恒等关系IA P(A)上的包含关系 三角形的相似关系
自反性 ⅹ
√ √ √ √
反自反性
√
ⅹ ⅹ ⅹ ⅹ
对称性
√ √ √
ab(a A b A (a,b) R (b,a) R a b)
ab(a A b A aRb a b bR a)
2024/11/24
§5.1 Relations and their properties (6)
5.1.4 Properties of relations
We denote the composite of R and S by SR.
S R {(a, c) | a A, c C, b B such that (a, b) R, (b, c) S}

14
2.3 范式
• 2.3.1 析取范式与合取范式
– 简单析取式与简单合取式 – 析取范式与合取范式
• 2.3.2 主析取范式与主合取范式
– 极小项与极大项 – 主析取范式与主合取范式 – 主范式的用途
15
简单析取式与简单合取式
文字:命题变项及其否定的统称 简单析取式:有限个文字构成的析取式 如 p, q, pq, pqr, … 简单合取式:有限个文字构成的合取式 如 p, q, pq, pqr, …
29
主析取范式的用途
(1) 求公式的成真赋值和成假赋值 设公式A含n个命题变项, A的主析取范式有s个极小项, 则A 有s个成真赋值, 它们是极小项下标的二进制表示, 其余2n-s 个赋值都是成假赋值
例如 (pq)r m0 m2 m4 m5 m6 成真赋值: 000,010,100,101,110; 成假赋值: 001,011,111
范式:析取范式与合取范式的统称
定理2.4 (1) 一个析取范式是矛盾式当且仅当它的每一个 简单合取式都是矛盾式 (2) 一个合取范式是重言式当且仅当它的每一个简单析取 式都是重言式
17
范式存在定理
定理2.5 任何命题公式都存在着与之等值的析取范式与合 取范式. 证 求公式A的范式的步骤： (1) 消去A中的,
30
主析取范式的用途(续)
(2) 判断公式的类型 设A含n个命题变项，则 A为重言式当且仅当A的主析取范式含2n个极小项 A为矛盾式当且仅当 A的主析取范式不含任何极小项,记作0 A为可满足式当且仅当A的主析取范式中至少含一个极小项
31
实例
例3 用主析取范式判断公式的类型:
(1) A (pq)q (2) B p(pq) (3) C (pq)r

02
集合论基础
集合的基本概念
总结词
集合是离散数学中的基本概念， 是研究离散对象的重要工具。
详细描述
集合是由一组确定的、互不相同 的、可区分的对象组成的整体。 这些对象称为集合的元素。例如 ，自然数集、平面上的点集等。
集合的运算和性质
总结词
集合的运算和性质是离散数学中的重要内容，包括集合的交、并、差、补等基本运算，以及集合的确定性、互异 性、无序性等性质。
生，1表示事件一定会发生。
离散概率论的运算和性质
概率的加法性质
如果两个事件A和B是互斥的，那么P(A或B)等于P(A)加上 P(B)。
概率的乘法性质
如果事件A和B是独立的，那么P(A和B)等于P(A)乘以P(B) 。
全概率公式
对于任意的事件A，存在一个完备事件组{E1, E2, ..., En}， 使得P(Ai)>0 (i=1,2,...,n)，且E1∪E2∪...∪En=S，那么 P(A)=∑[i=1 to n] P(Ai)P(A|Ei)。
工程学科
离散数学在工程学科中也有着重要的 应用，如计算机通信网络、控制系统 、电子工程等领域。
离散数学的重要性
基础性
离散数学是数学的一个重要分支 ，是学习其他数学课程的基础。
应用性
离散数学在各个领域都有着广泛的 应用，掌握离散数学的知识和方法 对于解决实际问题具有重要的意义 。
培养逻辑思维
学习离散数学可以培养人的逻辑思 维能力和问题解决能力，对于个人 的思维发展和职业发展都有很大的 帮助。
详细描述
邻接矩阵是一种常用的表示图的方法，它是 一个二维矩阵，其中行和列对应于图中的节 点，如果两个节点之间存在一条边，则矩阵 中相应的元素为1，否则为0。邻接表是一 种更有效的表示图的方法，它使用链表来存 储与每个节点相邻的节点。

(3)至于p为0即“我期终考了年级不是前 10”时,无论q为1或为0，即无论"我老妈 奖励1000元"或不奖励，都不能说老妈的 话是假的，故善意的认为pq为1均为1
1.1 命题及联结词
定义1.5双条件:当p与q值相同时,pq为1,不同 为0。 称p当且仅当q
“普通老师赚了100万当且仅当他 中了100万的彩票”， 普通老师赚了100万 普通老师买彩票中了100万大奖
故pq为0
1.1 命题及联结词
定义1.4条件式当p是1 ,q是0时,pq为0,即 10为0,其他情况为1。 p称为前件,q称为后件
(1)当p为1即“我期终考了年级前10”
q为0即“我老妈没有奖励1000元” 这时老妈的话为假，即pq为0 (2)当p为1即“我期终考了年级前10” q为1即“我老妈奖励1000元” 这时妈妈的话就对了，即pq为1
由于所有内容(整数，实数，字符，汉字，图片，声 音，视频，网页，……)进入电脑后，全是01组成的字 符串，从而都可以用布尔运算即逻辑运算实现，命题逻 辑成为计算机的基础。
命题逻辑将数学由连续变到离散，由高数进入离散。
Google采用逻辑运算进行搜索：数字之美 吴军 杨圣洪 000100010001110000 两者对应位置与运算。 离散数学 100100000000100001
陈述句(6)的正确性，到2018年12月时能确定的，若届 时建成了则它是对的、为真命题，否为假命题。
1.1 命题及联结词
对错确定的陈述语句称为命题。如：
(7) x与y之和为100，其中x为整数，y为整数 (8)1加1等于10 (7)的对错不确定。当x为50、y为50时是对的，当x为 51、y为52时是错的。 (8)的对错是不确定的，为二进制时正确，当为八进制、 十进制时是错的，因此这两个陈述句不是命题。 (9)青枫峡的红叶真美呀！ (10)动作快点！ (11)你是杨老师吗？ 这三个语句不是陈述语句，因此不是命题。