本篇笔记介绍了命题逻辑的基本概念，包括命题、逻辑运算符、条件语句、真值表及其应用等内容。接着，讨论了逻辑等值式、逻辑定律、全功能集和标准式等重要主题。最后，笔记还涵盖了谓词逻辑、嵌套量词、推理准则和证明方法等内容，提供了对逻辑推理和证明的深入理解。（由 gpt-4o-mini 生成摘要）

1. 命题逻辑 Propositional Logic

1.1. 命题 Propositions

命题(proposition)：A proposition is a declarative sentence that is either true or false, but not both.

• 悖论(paradox) 不属于命题（e.g. This statement is false. or I'm lying.）

命题逻辑(propositional logic)：The area of logic that deals with propositions.

命题变量(propositional variable)：Small letters such as $p,q,r,s,\ldots$ used to present propositions.

真值(truth value)：T (true proposition), or F (false proposition)

We call a series of propositions consistent(一致的) if they can possibly be satisfied at the same time.

1.2. 逻辑运算符 Logical Operators

逻辑运算符(logical operator) or 逻辑连接词(logical connective): be used to form compound propositions from existing propositions

• 英语中的单词 or 既可以表示 inclusive or 也可以表示 exclusive or（e.g. George was born in 1956 or 1957.），取决于具体语境。

逻辑运算符的优先级(precedence) 如下：

1.3. 条件语句 Conditional Statements

推断(implication) or 条件语句(conditional statement)：$p\rightarrow q$, false when $p$ is true and $q$ is false. $p$ 为假时推出什么都是真的，$p$ 为真时必须推出真的才为真。

• 假设(hypothesis = antecedent = premise)：$p$
• 结论(conclusion = consequence): $q$

对于推断 $p\rightarrow q$ 我们可以定义以下条件语句：

• 逆命题(converse)：$q\rightarrow p$
• 否命题(inverse)：$\lnot p\rightarrow \lnot q$
• 逆否命题(contrapositive)：$\lnot q\rightarrow \lnot p$

双条件语句(biconditional statement)：The biconditional statement $p\leftrightarrow q$ is the propostion “$p$ if and only if $q$.” The biconditonal statemnt

1.4. 真值表 Truth Table

要学会画真值表(truth table)。

• $n$ 个不同的布尔变量所画的真值表应有 $2^n$ 行。

1.5. 命题逻辑的应用 Applications of Propositional Logic

1.5.1. 翻译句子 Translating Sentences

• 将英语句子翻译成逻辑表达式，来减少自然语言的不准确(inaccuracy) 和模糊(ambiguous)。

1.5.2. 系统描述 System Specification

可以用于精确地描述系统需求、解决一些逻辑谜题等。

1.5.3. 逻辑谜题 Logical Puzzles

2. 逻辑等值式 Propositional Equivalences

2.1. 导论 Introduction

先定义以下基本概念：

• 永真(tautology)：A proposition which is always true. (e.g. $p \lor \lnot p$)
• 永假(contradiction)：A proposition which is always false. (e.g. $p \land \lnot p$)
• 可能式(contingency)：A proposition which is neither a tautology nor a contradiction. (e.g. $p$)

命题 $p$ 和 $q$ 是逻辑等值(logically equivalent) 的，当且仅当命题 $p\leftrightarrow q$ 是永真的。可被表示为：$p\Leftrightarrow q$ 或 $p\equiv q$。

• 一个复合命题是可满足的(satisfiable)：if there is an assignment of truth values to its variables that makes it true. 称这组赋值为该复合命题的解。
• 一个复合命题是不可满足的(unsatisfiable)：when it is false for all assignments of truth values to its variables.

2.2. 逻辑定律 Logical Laws

• 可以用真值表来证明一些基本的逻辑定律：对于涉及到 $n$ 个变量的两个命题，画出 $2^n$ 种可能的变量取值下的真值表，若两个命题的值都相同则说明这两个命题是逻辑等值的。

2.3. 全功能集 Functionally Complete Collection of Logical Operators

只需要部分运算符就可以表示出所有可能的运算，称这样的一个运算符集合为全功能集(Functionally Complete Collection)。

极小全功能集：$\{\lnot, \lor\}$, $\{\lnot, \land\}$, $\{|\}$, $\{\downarrow\}$ 等。

2.4. 标准式 Propositional Normal Forms

2.4.1. DNF/CNF

先给出以下基本定义：

• A 字面量(literal) is a variable or its negation.
• Conjunctions with literals as conjuncts are called 合取子句(conjunctive clauses) (clauses). 通过 AND 连接起来的一组字面量。

标准式(Propositional Normal Forms) 有以下两种：

• 析取范式(Disjunctive Normal Form, DNF)：A formula is said to be in disjunctive normal form if it is written as a disjunction, in which all the terms are conjunctions of literals. (e.g. $(p\land q)\lor(p\land \lnot q)$.)
  • 最外面一层的运算符都是析取 $\lor$；
  • 括号内的运算符都是合取 $\land$；
  • 括号不能嵌套；
  • $\lnot$ 只能出现在变量前。
• 合取范式(Conjunctive Normal Form, CNF)：和 DNF 的定义相反；把 $\land$ 和 $\lor$ 互换。

2.4.2. Full DNF/CNF

• A 极小项(minterm) is a conjunctive of literals in which each variable is represented exactly once.
• A 极大项(maxterm) is a disjunctive of literals in which each variable is represented exactly once.

可以从真值表中得到主析取范式(Full Disjunctive Normal Form)：

• 每个最小项对应真值表中 $f=\text{T}$ 的恰好一行。

利用 De Morgan's Laws，也可以从真值表中得到主合取范式(Full Conjuctive Normal Form)：

• 取出所有真值表为中为 $\text{F}$ 的位置，写出 $\lnot f$。
• 对 $\lnot f$ 应用 De Morgan's Laws，可以将式子中的合取析取互换，从而求得 FCNF。

3. 谓词逻辑 Predicate Logic

3.1. 谓词 Predicates

考虑 $x>0$，可以被表示为命题函数(propositional function) $P(x)$，这里 $P$ 表示 $\text{is greater than } 0$ 且 $x$ 是一个变量。

• Propositional functions become propositions (and have truth values) when their variables are each replaced by a value from the domain or bound by a quantifier.
• A statement of the form $P(x_1,x_2,\ldots, x_n)$ is the value of the propositional function P at the $n$-tuple $(x_1,x_2,\ldots, x_n)$ and $P$ is called a $n$-ary predicate.

我们可以用命题函数来描述前提条件(preconditions) 和后置条件(postconditions) ，这可以用于约束一段程序的输入和输出。

3.2. 量词 Quantifiers

• 全称量词(universal quantifier) $\forall$：都是真才为真，存在一个为假就为假。可以转化为合取。
• 存在量词(existential quantifier) $\exists$：都是假才为假，存在一个为真就为真。可以转化为析取。
• 唯一量词(uniqueless quantifier) $\exists !$：有且仅有一个为真时才为真。

我们在使用量词时，可能只要求对于某一范围内的 $x$ 成立，我们把此时 $x$ 的取值范围称为 讨论域(domain of discourse = universe of discourse)，一般简写为 domain。

3.3. 谓词逻辑的等值 Equivalences in Predicate Logic

Statements involving predicates and quantifiers are logically equivalent if and only if they have the same truth value no matter

• 代入了什么谓词选择 which predicates are substituted into these statements and
• 使用了什么讨论域 which domain of discourse is used for the variables in these propositional functions

同样使用 $\equiv$ 符号来表示谓词逻辑中的等值。

德摩根定律(De Morgan’s laws) 在谓词逻辑中也适用：

只有在 $A(x)$ 和 $B(x)$ 都输出真时，$A(x) \land B(x)$ 才为真，此时第一个等式的两侧都为真，否则两侧都为假。类似的可以证明第二个等式。

但是如果把上面的等式的 $\land$ 和 $\lor$ 互换则不成立。容易举出反例。

但这两个命题在其中一个方向上是正确的。

此外，还有：

4. 嵌套量词 Nested Quantifiers

嵌套量词(nested quantifier)：出现在另一个量词的辖域下的量词。Nest quantifiers are quantfiers that occur within the scope of other quantifiers.

4.1. 量词的顺序 Order of Quantifiers

除非所有量词都是 $\forall$ 或所有量词都是 $\exists$，否则量词的顺序是有意义的。The order of nested quantifiers matters if quantifiers are of different types

E.g.:

• $\forall x\ \exists y\ L(x,y)$：Everybody loves somebody.
• $\exists y\ \forall x\ L(x,y)$：There is someone who is loved by everyone.

可以用循环来理解量词的顺序。

4.2. 前缀范式 Prenex Normal Form

任意表达式都可以被转化为前缀范式(prenex normal form)。

如何得到 PNF？可以遵循一下步骤：

1. 消除所有的 $\rightarrow$ 和 $\leftrightarrow$。Eliminate all occurrences of $\rightarrow$ and $\leftrightarrow$ from the formula in question.
2. 向内移动否定符号，注意应用德摩根定律。Move all negations inward such that, in the end, negation only appear as part of literals.
3. 对变量进行重命名，确定不同部分的变量不会冲突。Standardize the variables a part (when necessary).
4. 最后，将所有量词移动到最前面。The prenex normal form can now be obtained by moving all quantifiers to the front of the formula.

5. 推理准则 Rules of Inference

• An 论据(argument) is a sequence of statements that end with a conclusion
• By 有效的(valid), we mean the conclusion must follow from the truth of the preceding statements (premises)
• We use 推理准则(rules of inference) to construct valid arguments

6. 证明 Proof

6.1. 一些术语 Some Terminology

• A 证明(proof) is a valid argument that establishes the truth of a mathematical statement.
• A 定理(theorem) (or 命题(proposition)/fact/result) is a statement that can be shown to be true.
  • 公理(axioms) (or 假设(postulates)) are statements we assume to be true
• A 引理(lemma) is a less important theorem that is helpful in the proof of other results
• A 推论(corollary) is a theorem that can be established directly from a theorem that has been proved.
• A 猜想(conjecture) is a statement that is being proposed to be a true statement
  • A conjecture becomes a theorem once it has been proved to be true.

6.2. 形式化证明 Formal Proofs

形式化证明(formal proof) v.s. 非形式化证明(informal proof)：

• Formal Proofs：
  • Can be extremely long;
  • May be hard to follow.
• Informal Proofs:
  • Each step may involve multiple rules of inference;
  • Steps may be skipped;
  • The axioms being assumed and the rules of inference used are not explicitly stated.

6.3. 证明方法 Proof Methods

6.3.1. 直接证明法 Direct Proof

通过直接证明法(direct proof) 证明 $p\rightarrow q$ 的方法是：

• 通过推理规则(rules of inference)、公理、逻辑恒等式(logical equivalences) 等推出 $q$ 也为真。

其余的证明方法都是间接证明法(indirect proof)。

6.3.2. 空证明和平凡证明 Vacuous and Trivial Proof

• 空证明(vacuous proof)：当 $p$ 为假时 $p\rightarrow q$ 为真，所以我们可以通过证明 $p$ 为假来证明 $p\rightarrow q$ 为真。
• 平凡证明(trivial proof)：当 $q$ 为真时 $p\rightarrow q$ 为真，所以我们也可以通过证明 $q$ 为真来证明 $p\rightarrow q$ 为真。

6.3.3. 反证法 Proof by Contraposition

反证法(proof by contraposition) 可以看做对原命题的逆否命题的直接证明，根据逻辑恒等式：

• 假设 $\lnot q$ 为真；
• 推出 $\lnot p$ 也为真（or 推出 $p$ 为假），从而证明原命题。

6.3.4. 归谬证明法 Proof by Contradiciton

Proof $p$ by contradiction:

• assumes $p$ is false.
• deduces that $\lnot p \rightarrow (q \land \lnot q)$, which $q \land \lnot q$ is a contradiction.
• $p$ follows from the above

Proof $p\rightarrow q$ by contradiction:

• assumes that both $\lnot q$ and $p$ are true.
• show that $(p \land \lnot q) \rightarrow \text{F}$.

6.4. 证明策略 Proof Strategies

6.4.1. 分类讨论 Proof by Cases

• Convince the reader that the cases are inclusive (i.e. they exhaust all possibilities)
• Establish all implications

6.4.2. 穷举法 Exhausitve Proof

An 穷举法(exhaustive proof) is a special type of proof by cases where each case involves checking a single example.

6.4.3. 不失一般性地 Without Loss of Generality

不失一般性地(without loss of generality)，常用于证明过程中，可以缩写为 WLOG。比如：我们想要证明 $|xy|=|x|\cdot |y|$，若已经证明了 $x\ge 0,\ y<0$ 的情况下成立，则可以不是一般性的得到 $x<0,\ y\ge 0$ 时也成立，因为这就是把 $x'=y,\ y'=x$ 代入后运用一次乘法交换律的情况。

合理运用 WLOG 可以帮助我们在分类讨论的过程中省略一些重复的证明，从而使证明过程更为简洁。

6.4.4. 存在性证明 Existence Proof

• 构造存在性证明(constructive existence proof)：
  • 证明 $P(c)$ 对于定义域中的某一个 $c$ 成立。
  • 然后 $\exists x P(x)$ 就成立，根据存在性推广规则(existential generalization = EG)。
• 非构造存在性证明(inconstructive existence proof)：
  • 假设不存在 $c$ 使得 $P(c)$ 成立。
  • 然后推出一个矛盾，这可以说明原命题成立。

6.4.5. 唯一性证明 Uniqueness Proof

唯一性证明(uniqueness proof) To show that a theorem assert the existence of a unique element with a particular property.

唯一性证明可以分为证明其存在性和唯一性两部分。

• 存在性(existence)：We show that an element $x$ with the desired property exists.
• 唯一性(uniqueness)：We show that if $y\neq x$, then $y$ does not have the desired property. Equivalently, we can also show that if $x$ and $y$ both have the desired property, then $x=y$.