使用说明
本文内容仅做概念梳理总结，用于校验所学知识、考前复习等场景，如果你对其中的内容感到生疏，建议查阅教材：
屈婉玲， 耿素云， 张立昂. 离散数学[M]. 第2版. 北京: 高等教育出版社， 2015.
概念树
- 命题：能判断真假的陈述句称为命题（悖论、感叹句、祈使句不属于命题）。
- 真值：命题的真值只取“真”或“假”，对应的命题称为“真命题”和“假命题”。
- 简单命题（原子命题）：不能分解为更简单的命题称为简单命题。
- 复合命题：简单命题通过联结词联结而成的命题称为复合命题。
- 联结词：
- 否定联结词（$\neg$）：对原命题取反，称之为$p$的否定式。
- 合取联结词（$\land$）：设$p$，$q$为两个命题，复合命题$p$并且$q$，称之为$p$与$q$的合取式，记作$p \land q$。同时为真才为真，上箭头当作And来记忆。
- 析取联结词（$\lor$）：设$p$，$q$为两个命题，复合命题$p$或者$q$，称之为$p$与$q$的析取式，记作$p \lor q$。 析取表示“至少一个为真即为真”。
- 相容或、排斥或：自然语言中的或分为相容和排斥，如：“配餐可选汤或沙拉”此时两个命题二选一是排斥或，“招聘要求会开车或会英语”中两个命题可以共存是相容或。析取联结词表示的是相容或。
- 蕴含联结词：设$p$、 $q$是两个命题，复合命题“如果 $p$，则 $q$”，则成为$p$与$q$的蕴含式，$p \to q$。
- 等价联结词：设$p$、 $q$是两个命题，复合命题“ $p$等且仅当$q$”，则成为$p$与$q$的等价式，$p \leftrightarrow q$。
- 命题变元（命题变项）：一个真值确定的简单命题称之为命题常项，相对应，用一个字母表示一个命题，命题的值不确定，可取真或假，称之为命题变元。
- 合式公式：命题变元、联结词、括号组成合式公式，一般简称为公式、或者命题公式、命题形式。
- 原子命题变元：单个命题变元也算合式公式，称之为原子命题变元。
- 合式公式的层数：
- 若 A 为原子命题变元，则层数为 0
- 若 A = ¬B，则层数为 B 的层数 + 1
- 若 A = B ◦ C，则层数为 max(层数(B), 层数(C)) + 1
- 合式公式赋值：设$p_1, p_2, ..., p_n$是合式公式A的全部命题变元，给$p_1, p_2, ..., p_n$各指定一个真值，称之为对A的一个赋值。
- 成真赋值、成假赋值：合式公式为真的赋值称之为成真赋值，反之为成假赋值。
- 真值表：把所用的合式公式赋值列举一遍，形成一个表格，就是真值表。
- 重言式（永真式）：合式公式A在它所有的赋值下都是真，叫它重言式。
- 矛盾式（永假式）：合式公式A在它所有的赋值下都是假，叫它矛盾式。
- 可满足式：合式公式A至少在一个赋值下为真，叫它可满足式。
- 元语言符号与对象语言符号
- 对象语言符号：构成命题公式的符号（如 $p,q,r$，$\neg,\land,\lor,\to,\leftrightarrow$）
- 元语言符号：用于描述命题公式之间关系的符号（如 $A,B$，$\Leftrightarrow$）
- 等值式：两个命题公式$A、B$，若$A \leftrightarrow B$为重言式，则称$A$与$B$是等值的，记作$A \Leftrightarrow B$。（注意：$\leftrightarrow$ 是联结词，$\Leftrightarrow$ 表示公式等值关系）
- 等值式模式
- 双重否定律：$A \Leftrightarrow \neg \neg A$，很好理解。
- 幂等律：$A \Leftrightarrow A \lor A$，$A \Leftrightarrow A \land A$
- 交换律：$A \land B \Leftrightarrow B \land A$ ，$A \lor B \Leftrightarrow B \lor A$
- 结合律：$(A \land B) \land C \Leftrightarrow A \land (B \land C)$ ，$(A \lor B) \lor C \Leftrightarrow A \lor (B \lor C)$
- 分配律：$A \land (B \lor C) \Leftrightarrow (A \land B) \lor (A \land C)$ ，$A \lor (B \land C) \Leftrightarrow (A \lor B) \land (A \lor C)$
- 德摩根律：$\neg (A \lor B) \Leftrightarrow \neg A \land \neg B$ ，$\neg (A \land B) \Leftrightarrow \neg A \lor \neg B$
- 吸收率：$A \lor (A \land B) \Leftrightarrow A$ ，$A \land (A \lor B) \Leftrightarrow A$
- 零律：$A \land 0 \Leftrightarrow 0$，$A \lor 1 \Leftrightarrow 1$
- 同一律：$A \lor 0 \Leftrightarrow A$，$A \land 1 \Leftrightarrow A$
- 排中律：$A \lor \neg A \Leftrightarrow 1$
- 矛盾律：$A \land \neg A \Leftrightarrow 0$
- 蕴含等值式：$A \to B \Leftrightarrow \neg A \lor B$
- 等价等值式：$(A \leftrightarrow B) \Leftrightarrow ((A \to B) \land (B \to A))$
- 假言易位：$A \to B \Leftrightarrow \neg B \to \neg A$
- 等价否定等值律：$(A \leftrightarrow B) \Leftrightarrow (\neg A \leftrightarrow \neg B)$
- 归谬律：$(A \to B) \land (A \to \neg B) \Leftrightarrow \neg A$
- 等值式模式
- 合式公式：命题变元、联结词、括号组成合式公式，一般简称为公式、或者命题公式、命题形式。