Chapter 1：Logic and Proofs

1.1命题逻辑(Propositional Logic)

命题(proposition)：一个陈述语句，或真或假
命题变量(Propositional variables)：$p,q,r,s…$
真值(truth value):如果一个命题为真，则其真值为真$(T)$，否则真值为假$(F)$
逻辑运算符(Logical operators) (Connectives): 从已知命题形成复合命题(compound propositions)

一些逻辑运算符：
Negation operator $\lnot$ (NOT)
Conjunction operator $\land$ (AND)
Disjunction operator $\lor$ (OR)
Exclusive or operator $\oplus$  (XOR)
Conditional operator  $\rightarrow$ (IF–THEN)
Biconditional operator  $\leftrightarrow$ (IF AND ONLY IF)

补充：NOR 与 OR 相反，记作 $p \downarrow q$，仅在$p$和$q$均为$F$时为$T$。

$p\land q $称为命题$p$和$q$的合取(并且),$p\lor q $称为命题$p$和$q$的析取(或)

异或：$p\oplus q$真值表

条件语句：$p\rightarrow q$真值表
注意，只要if后是$F$，则$p\rightarrow q$是$T$
$p$被称为前提 (hypothesis) , $q$被​称为结论 (conclusion)

Biconditional Operator:$p \leftrightarrow q$真值表

$p\rightarrow q$的逆命题(Converse)为$q\rightarrow p$
逆否命题(Contrapositive)为$\lnot q \rightarrow \lnot p$
反命题(Inverse)为$\lnot p \rightarrow \lnot q$

$p\rightarrow q$的几种常见表达方式
If p, then q
p implies q
If p, q
q if p
q when p
q follows from p
q whenever p
p is a sufficient condition for q
q is a necessary condition for p
p only if q
q unless ¬p

逻辑运算符优先级

1.2命题逻辑的应用

语句翻译：用命题变量表示语句中的每个成分，找出合适的逻辑联结词（运算符）。

1.3 命题等价式(Propositional Equivalences)

Classification of Compound Propositions

• Tautology : compound proposition that is always true
• Contradiction : compound proposition  that is always false.
• Contingency: compound proposition that is neither a tautology nor a contradiction

The compound propositions $p$ and $q$ are called logically equivalent if $p \leftrightarrow q$ is a tautology,notation:  $p \equiv q$ or $p \Leftrightarrow q$.

一些常见的逻辑等价式：

A compound proposition is satisfiable if there is an assignment of truth values to its variables that make it true. When no such assignments exist, the compound proposition is unsatisfiable.
A compound proposition is unsatisfiable if and only if its negation is a tautology.

1.5 嵌套量词(Nested Quantifiers)

Example $$\forall x\exist y F(x, y)$$

$$\forall \epsilon >0 \exist \ >0 \forall x ()$$

The Order of Quantifiers
$$\forall x \forall y P(x, y) \equiv \forall y \forall x P(x, y)$$