离散数学屈婉玲PPT课件.pptx

离散数学是计算机科学的基础课程，它探讨了数学中离散而非连续的对象，如集合、图、逻辑和组合数学等领域。在屈婉玲教授的PPT课件中，重点介绍了两个核心概念：有序对和笛卡尔积，以及二元关系。 **有序对**是离散数学中的基本构造。有序对由两个元素组成，它们之间有特定的顺序，用尖括号`<x, y>`表示。这种顺序使得不同的元素顺序会产生不同的有序对，即`<x, y>`不等于`<y, x>`，除非`x`等于`y`。当两个有序对`<x, y>`和`<u, v>`相等时，其充分必要条件是`x`等于`u`且`y`等于`v`。 **笛卡尔积**是集合论中的一个重要概念，它定义为两个集合`A`和`B`的元素按顺序配对形成的集合，记作`A × B`。比如，如果`A = {1, 2, 3}`，`B = {a, b, c}`，那么`A × B`包含了所有`A`和`B`元素的组合，即`{<1, a>, <1, b>, ..., <3, c>}`。值得注意的是，笛卡尔积不满足交换律，即`A × B`通常不等于`B × A`，也不满足结合律`A × (B × C)`不等于`(A × B) × C`。此外，笛卡尔积对于集合的并和交操作满足分配律，并且如果其中任意一个集合为空集，结果也会是空集。笛卡尔积的大小取决于两个集合的基数，若`|A| = m`，`|B| = n`，则`|A × B| = mn`。 **二元关系**是离散数学中的另一个关键概念。一个二元关系是集合，它的元素可以是有序对，也可以是空集。如果`<x, y>`属于关系`R`，我们通常写作`xRy`，表示`x`和`y`之间存在关系；反之，如果`<x, y>`不在`R`中，写作`x y`。例如，`R={<1,2>,<a,b>}`是一个二元关系，而`S={<1,2>,a,b}`不是一个，因为它包含非有序对的元素。从集合`A`到`B`的二元关系是`A × B`的子集，而`A`上的二元关系是`A × A`的子集。 在实例中，例如`A={0,1}`，`B={1,2,3}`，`R1={<0,2>}`, `R2=A×B`, `R3=∅`, `R4={<0,1>}`都是从`A`到`B`的二元关系，其中`R3`和`R4`也是`A`上的二元关系。当`|A|=n`时，`A`上的不同二元关系数量为`2^n2`。 这些基础知识构成了离散数学的基石，对于理解计算机科学中的算法、数据结构、图论以及形式逻辑等高级主题至关重要。掌握这些概念有助于深入探究计算问题的本质，解决实际编程中的复杂问题。