06CS/离散数学

第一章 基础:逻辑和证明

  • 命题(proposition):真或假的陈述句

  • 否定:¬(!、not、非、补)

  • 合取:∧(&&、and、且、交)

  • 析取:∨(||、or、或、并)

  • 异或:⊕(xor)
    只有一个为真时为真,其余为假(相同为假,不同为真)

  • 条件语句:→(蕴含)
    p→q,p 真 q 假为假,其余全为真(p 为自然语言中的 “条件”,q 为自然语言中的 “结果”)

  • 双条件语句:↔(双蕴含)
    只有一个为真时为假,其余为真(相同为真,不同为假)

  • 永真式(重言式):真值为永远真

  • 矛盾:真值为永远假

  • 可能式:真值可能真可能假

  • 逻辑等价:≡
    p↔q 为永真式

  • 命题函数:P(x1, x2, x3, …, xn)
    变量 + 谓词

  • 量词:全称量词,存在量词,约束论域量词

  • 推理规则:假言推理、取拒式、假言三段论、析取三段论、附加、简化、和取、消解

  • 证明方法:直接证明、反证法、归谬证明、穷举证明、分情形证明

第二章 基本结构:集合、函数、数列与求和

集合

  • 幂集合:包括全部子集的集合(2^n 个元素)
  • 笛卡尔积:按乘的顺序生成组合过的集合

函数

f 指派给 A 中元素 a 的惟一的 B 中元素是 b,就写成 f(a) = b。如果 f 是从 A 到 B 的函数,就写成 f:A->B(函数有时也被称作映射或变换)

  • 反函数:对应关系对调
  • 函数组合:(f▫g)(x) = f(g(x))