1.1 命题逻辑+1.2 等价.md

1.1 命题逻辑¶

命题概念¶

命题是一个陈述语句，即陈述真实的语句，或真或假，不能既真又假。

习惯上用字母 \(p,q,r,s,……\) 表示命题变量（或称为语句变量），即表示命题的变量。若一个命题是真命题，则它的真值为真，用\(T\)表示；如果是假命题，则它的真值为假，用\(F\)表示。

不能用简单的命题来表示的命题称为 原子命题 。
复合命题：由原子命题、命题联结词和圆括号组成

由已知命题用 逻辑运算符 组合而来的新命题也被称为 复合命题。

设计命题的逻辑领域称为 命题演算 或 命题逻辑。

逻辑运算符也称连结词，如否定运算符 \(\neg\)

联结词¶

定义 1——否定联结词

令 \(p\) 为一命题，则 \(p\) 的否定记作\(\neg p\)（也可记作 \(\overline{p}\)），指“不是 \(p\) 所指的情形”。命题 \(\neg p\) 读作“非 \(p\) ”。\(p\) 的否定（\(\neg p\)）的真值和 \(p\) 的真值相反。

定义 2——合取联结词

令 \(p\) 和 \(q\) 为命题。\(p\)、\(q\) 的合取即命题”\(p\)并且\(q\)“，记作\(p \land q\)。当 \(p\) 和 \(q\) 都是真时，\(p \land q\) 命题为真，否则为假。

或：

具有相容性：可兼或，兼或
具有排斥性：不可兼或，异或

定义 3——析取联结词

令 \(p\) 和 \(q\) 为命题。\(p\)、\(q\) 的析取即命题“\(p\) 或 \(q\)”，记作 \(p \lor q\)。当 \(p\) 和 \(q\) 均为假时，\(p \lor q\) 为假，否则为真。

定义 4——异或联结词

令 \(p\) 和 \(q\) 为命题。\(p\) 和 \(q\) 的异或（记作 \(p \oplus q\)）是这样一个命题：当 \(p\) 和 \(q\) 中恰好只有一个为真时命题为真，否则为假。

定义 5——条件（蕴含）联结词

令 \(p\) 和 \(q\) 为命题。条件语句 \(p \rightarrow q\) 是命题“如果 \(p\)，则 \(q\)”。当 \(p\) 为真而 \(q\) 为假时，条件语句 \(p \rightarrow q\) 为假，否则为真。在条件语句 \(p \rightarrow q\) 中，\(p\) 称为假设（前件、前提），\(q\) 称为结论（后件）。

条件语句也称为蕴含。

由条件语句 \(p \rightarrow q\) 可以构成一些新的条件语句。以下是三个常见的相关条件语句及其特殊名称：

逆命题：命题 \(q \rightarrow p\) 称为 \(p \rightarrow q\) 的逆命题。
逆否命题：命题 \(\neg q \rightarrow \neg p\) 称为 \(p \rightarrow q\) 的逆否命题。
反命题：命题 \(\neg p \rightarrow \neg q\) 称为 \(p \rightarrow q\) 的反命题。

在由 \(p \rightarrow q\) 衍生的三个条件语句中，只有逆否命题总是和 \(p \rightarrow q\) 具有相同的真值。

定义 6——双条件联结词

令 \(p\) 和 \(q\) 为命题。双条件语句 \(p \leftrightarrow q\) 是命题“\(p\) 当且仅当 \(q\)”。当 \(p\) 和 \(q\) 有同样的真值时，双条件语句为真，否则为假。双条件语句也称为双向蕴含。

Tip

1.联言判断的真假值特征：全真才真，一假则假

2.相容选言判断真假值特征：（一真即真，全假才假。）

3.不相容选言判断的真假值特征：（一真才真，全真全假皆为假）

4.假言判断的真假值特征

（1）充分条件假言判断：肯定前件与否定后件式（有前必有后，无后必无前，无前未必无后，有后未必有前）

（2）必要条件假言判断：否定前件与肯定后件式（无前必无后，有后必有前，有前未必有后，无后未必无前）

（3）充分必要条件假言判断：肯定前件式、肯定后件式、否定前件式、否定后件式（有前必有后，无前必无后，无后必无前，有后必有前

举例

P：2+2 = 4；Q：5是素数。

则：\(P \leftrightarrow Q\)，2+2=4当且仅当5是素数。

虽然P与Q并无内在关系，但因二者均为真，所以\(P \leftrightarrow Q\)的真值为T

补充——条件非联结词

当且仅当 \(P\) 为真且 \(Q\) 为假时，结果为真

由条件非联结词 \(\xi\) 和 \(P\)、\(Q\) 连接成 \(P \xi Q\)，称它为 \(P\) 和 \(Q\) 的条件非式复合命题，读作“\(P\) 条件非 \(Q\)”。\(P \xi Q\) 的真值由 \(P\) 和 \(Q\) 的真值确定：当且仅当 \(P\) 为 \(T\) 而 \(Q\) 为 \(F\) 时，\(P \xi Q\) 为 \(T\)；否则 \(P \xi Q\) 为 \(F\)。

补充——与非联结词

当且仅当 \(P\) 和 \(Q\) 同时为真时，结果为假，否则为真

由合取非联结词 \(\uparrow\) 和 \(P\)、\(Q\) 连接成 \(P \uparrow Q\)，称它为 \(P\) 和 \(Q\) 的合取非式复合命题，读作“\(P\) 合取非 \(Q\)”。\(P \uparrow Q\) 的真值由命题 \(P\) 和 \(Q\) 的真值确定：当且仅当 \(P\) 和 \(Q\) 均为 \(T\) 时，\(P \uparrow Q\) 为 \(F\)，否则 \(P \uparrow Q\) 为 \(T\)。“合取非”又常称为“与非”。

补充——或非

当且仅当 \(P\) 和 \(Q\) 同时为假时，结果为真

由析取非联结词 \(\downarrow\) 和 \(P\)、\(Q\) 连接成 \(P \downarrow Q\)，称它为 \(P\) 和 \(Q\) 的析取非式复合命题，读作“\(P\) 析取非 \(Q\)”。\(P \downarrow Q\) 的真值由 \(P\) 和 \(Q\) 的真值确定：当且仅当 \(P\) 和 \(Q\) 均为 \(F\) 时，\(P \downarrow Q\) 为 \(T\)，否则 \(P \downarrow Q\) 为 \(F\)。“析取非”又常称为“或非”。

优先级¶

定义——合式公式

合式公式是由以下规则生成的公式：

单个原子公式是合式公式。
若 \(A\) 是一个合式公式，则 \(\neg A\) 也是一个合式公式。
若 \(A\)、\(B\) 是合式公式，则 \(A \land B\)、\(A \lor B\)、\(A \rightarrow B\) 和 \(A \leftrightarrow B\) 都是合式公式。
只有有限次使用上述规则生成的公式才是合式公式。

当合式公式较为复杂时，为减少圆括号的使用量，可作以下约定：

规定联结词的优先级由高到低的次序为：\(\neg\)、\(\land\)、\(\lor\)、\(\rightarrow\)、\(\leftrightarrow\)。
相同的联结词按从左至右的次序计算时，圆括号可省略。
最外层的圆括号可以省略。

真值表¶

定义：如果给定命题公式A的一组真值指派使得A的真值为真，则称该组真值为公式A的成真指派，反之，称为A的成假指派。

命题逻辑的应用¶

对于命题“如果天不下雨，我们去打篮球，除非班上有会”，我们可以通过以下步骤进行符号化：

确定原子命题： - 设 \(P\): 今天天天下雨 - 设 \(Q\): 我们去打篮球 - 设 \(R\): 今天班上有会

构建逻辑表达式： - \(\neg R \rightarrow (\neg P \rightarrow Q)\) - \((\neg P \land \neg R) \rightarrow Q\)

1.2 命题等价式¶

定义——等价

给定两个命题公式 \(A\) 和 \(B\)，如果对于其任何一组指派而言，\(A\) 和 \(B\) 的真值都相同，则称 \(A\) 和 \(B\) 是等价的，记为 \(A \Leftrightarrow B\)。

基本等价关系¶

双重否定律：\(A \Leftrightarrow \neg \neg A\)
等幂律：\(A \Leftrightarrow A \lor A\)、\(A \Leftrightarrow A \land A\)
交换律：\(A \lor B \Leftrightarrow B \lor A\)、\(A \land B \Leftrightarrow B \land A\)
结合律：\((A \lor B) \lor C \Leftrightarrow A \lor (B \lor C)\)、\((A \land B) \land C \Leftrightarrow A \land (B \land C)\)
分配律：\(A \lor (B \land C) \Leftrightarrow (A \lor B) \land (A \lor C)\)、\(A \land (B \lor C) \Leftrightarrow (A \land B) \lor (A \land 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 \lor \text{True} \Leftrightarrow \text{True}\)、\(A \land \text{False} \Leftrightarrow \text{False}\)
同一律：\(A \lor \text{False} \Leftrightarrow A\)、\(A \land \text{True} \Leftrightarrow A\)
否定律：\(A \lor \neg A \Leftrightarrow \text{True}\)、\(A \land \neg A \Leftrightarrow \text{False}\)
条件转化律：\(P \rightarrow Q \Leftrightarrow \neg P \lor Q\)
双条件转化律：\(P \leftrightarrow Q \Leftrightarrow (P \rightarrow Q) \land (Q \rightarrow P)\)
假言易位：\(P \rightarrow Q \Leftrightarrow \neg Q \rightarrow \neg P\)
等价否定等值式：\(P \leftrightarrow Q \Leftrightarrow \neg P \leftrightarrow \neg Q\)

等价置换定理¶

定义：如果 \(X\) 是合式公式 \(A\) 的一部分，且 \(X\) 本身也是一个合式公式，则称 \(X\) 为合式公式 \(A\) 的子公式。

设 \(X\) 是合式公式 \(A\) 的子公式，若 \(X \Leftrightarrow Y\)，如果将 \(A\) 中的 \(X\) 用 \(Y\) 来置换，所得到的公式 \(B\) 与公式 \(A\) 等价，即 \(A \Leftrightarrow B\)。

可满足性¶

定义

对于某个命题公式，如果其在分量的任何指派下，其对应的真值均为T，则称该命题公式为重言式或永真式。

对于某个命题公式，如果其在分量的任何指派下，其对应的真值均为F，则称该命题公式为矛盾式或永假式。

定义——可满足式

如果某个命题不是矛盾式，则该命题称为可满足式。

定义——蕴含式

在逻辑学中，当且仅当 \(P \rightarrow Q\) 是重言式时，我们称“ \(P\) 蕴含 \(Q\) ”，并记作 \(P \Rightarrow Q\)。

逆换式：将 \(P \rightarrow Q\) 的前提和结论互换，得到 \(Q \rightarrow P\)。
反换式：将 \(P \rightarrow Q\) 的前提和结论都取反，得到 \(\neg P \rightarrow \neg Q\)。
逆反式：将 \(P \rightarrow Q\) 的前提和结论互换后再取反，得到 \(\neg Q \rightarrow \neg P\)。