Untitled

命题 proposition / statement

陈述语句，要么逻辑真要么逻辑假，具有明确的真假属性

• $x + 1 = 2$ 不是命题

布伦变量 Boolean variable

定义逻辑类集合为 $\mathbb B = \{\top, \bot\}$

二元衔接运算符

• $\neg$ 表示反逻辑
• $\wedge$ 表示 与 conjunction
• $\vee$ 表示 或 disjunction
• $\to$ 表示蕴含 imply 注意这个不是推导关系, 更适合理解为受骗的情况，只有被骗是 0， 其他都没有被骗都可以是 1；表述为 p 仅当 q 逻辑, 通俗说法是 若 q 不为真则 p 也 不能为 真
• $\leftrightarrow$ 表示if and only if (实际上是同或，相同为 1，00 -> 1 是虚真)
• XOR (exclusive or) 异或，不同 为 1， 相同为 0
  ![[source/_posts/wesley_knowledge_repo/math/discrete math/补充知识/Pasted image 20240522104903.png]]

特殊逻辑

• 恒真 tautology
• 恒假 contradiction
• 不确定 contingency
• 等价 equivalent, 即 iff + tautology

逻辑运算公式

commutative 交换律

$p\land q \Leftrightarrow q \land p$
$p\lor q \Leftrightarrow q \lor p$

associativity 结合律

仅限相同符号之间可以换括号
$(p\land q) \land r \Leftrightarrow p\land (q\land r)$

distributivity 分配律

$p\lor(q\land r) \Leftrightarrow)(p\lor q)\land(p\lor r)$ 注意这里和乘法并不是那么相似
$p\land(q\lor r) \Leftrightarrow (p\land q)\lor(p\land r)$

negation 反逻辑公式

反向 imply $p\to q \Leftrightarrow \neg q \to \neg p$

De Morgan’s Law 德摩根定律

$\neg(p\land q) \equiv \neg p \lor \neg q$
$\neg(p\lor q) \equiv \neg p \land \neg q$

identity 自身恒等量

$p\lor 0 \equiv p$ , $p\land 1 \equiv p$

null 无关量

$p\land 0\equiv$ , $p\lor 1 \equiv 1$ 表示与 $p$ 自身无关

absorption 吸收律

$p\lor (p\land q) \equiv p$
$p\land(p\lor q) \equiv p$

imply 蕴含的逻辑

$p\to q \equiv \neg p\lor q$

如何证明两个逻辑表达式等价？

1. 使用真值表：适用于 case 较少的时候
2. 使用等价公式：通用，但是要对常见的比较熟悉

谓词与量词

谓词

对于非命题 “x 大于 3” 我们称呼 " 大于 3 " 为 谓词，同时用 “P(x)” 表示语句 $x > 3$
那么我们有 $P(2)$ 假 和 $P(4)$ 真
这里称呼 $P$ 为 命题函数 或者 n元谓词

前置条件和后置条件

前置条件：描述合法输入的语句叫做前置条件
后置条件：程序运行的输出应该满足的条件称为后置条件

量词

命题函数中的变量被赋值的时候得到的语句就变成了某个具有真值的命题

全称量词 和 存在量词

论域 domain of discourse 或 全体域 universe of discourse 简称为 域 domain
$\forall$全称量化：谓词在所考虑范畴内每一个个体都为真
$\exists$ 存在量化： 谓词对所考虑范畴内一个或多个个体为真, 必须指定论域，否则无效

有限域量词

当一个量词的域是有限的时候，所有元素可以一一列出

量化表达式的否定

$\neg\forall xP(x) \equiv \exists x\neg P(x)$

$\neg\exists xP(x) \equiv \forall x\neg P(x)$

通俗的说，对 “任意都符合” 取非逻辑，得到 “存在不符合”, vice versa

嵌套量词

如果存在一个量词出现在另一个量词的作用域内的情况，如: $\forall x \exists y(x+y=0)$
所谓 “嵌套”，就是我们常说的递推或者递归的思想，通过对 x 的遍历，然后对每个x 对 y 进行遍历，直到获得有一个真值 (这取决于y前是存在还是任意)

嵌套量词的否定

可以通过连续的应用单个量词语句的否定规则得到，例如:

$\neg\forall x\exists y(xy=1)\equiv\exists x\neg\exists y(xy=1)\equiv\exists x\forall y\neg(xy=1)$

推理规则

基本概念

论证 argument, 有效性 valid, 前提 premise, 谬误 fallacy

论证形式

命题逻辑中的一个论证是一连串的命题，除了论证的最后一个命题之外，都是前提 最后的命题叫做 结论
例: “如果今天正在下雪，那么我们就去滑雪”(前提) + “今天下雪” $\to$ “去滑雪”

真值树 Truth Tree

方法论

1. 找到反例：前提为 true 但是结论是 false
2. 先展开结论句并且取反逻辑到基本逻辑类型(下面这个表格里面有的)
3. 逐步展开剩下的所有前提到树结构中
4. 从枝到根找到矛盾的逻辑点
5. 最终看有几个开的逻辑，只有全部闭合才会是 valid，反之为 invalid
   ![[source/_posts/wesley_knowledge_repo/math/discrete math/补充知识/Pasted image 20240522132919.png]]