命题逻辑

前置

• naive-set-theory-2

命题逻辑

• simple statement(简单命题): a declarative sentence(a subject with a predicate) that is either true or false
• connective(联结词): a symbol that connects two statements to form a new statement
• compound statement(复合命题): a statement that is formed by connecting two or more simple statements using connectives
• statement(命题): simple statement or compound statement
• truth values(真值): T(true) or F(false)

connective	symbol
Negation(否定)	$\neg$
Conjunction(合取)	$\wedge$
Disjunction(析取)	$\vee$
Implication(蕴含)	$\to$
Equivalence(等价)	$⟺$

$p$	$\neg p$
F	T
T	F

$p$	$q$	$p\wedge q$
F	F	F
F	T	F
T	F	F
T	T	T

$p$	$q$	$p\vee q$
F	F	F
F	T	T
T	F	T
T	T	T

$p$	$q$	$p\to q$
F	F	T
F	T	T
T	F	F
T	T	T

$p$	$q$	$p⟺q$
F	F	T
F	T	F
T	F	F
T	T	T

• A statement form(命题形式，命题公式) is an expression involving statement variables and connectives, which can be formed using the rules:
  • (i) Any statement variable is a statement form.
  • (ii) if $\mathcal{A}$ and $\mathcal{B}$ are statements forms, then $\neg \mathcal{A}$, $\mathcal{A}\wedge \mathcal{B}$, $\mathcal{A}\vee \mathcal{B}$, $\mathcal{A}\to \mathcal{B}$, and $\mathcal{A}⟺\mathcal{B}$ are also statement forms.
• tautology(重言式): a statement form that is true for all possible values of its statement variables
• contradiction(矛盾式): a statement form that is false for all possible values of its statement variables
• logically implies(逻辑蕴含): $\mathcal{A}$ logically implies $\mathcal{B}$ if $\mathcal{A}\to \mathcal{B}$ is a tautology, denoted as $\mathcal{A}⟹\mathcal{B}$
• logically equivalent(逻辑等价): $\mathcal{A}$ and $\mathcal{B}$ are logically equivalent if $\mathcal{A}⟺\mathcal{B}$ is a tautology, denoted as $\mathcal{A}⟺\mathcal{B}$
• restricted statement forms：在 statement form的基础上限制联结词$\neg$，$\wedge$，$\vee$
• adequate connectives(完备联结词)：An adequate set of connectives is a set such that every truth function canbe represented by a statement form containing only connectives from that set.
• Argument(论证)：An argument is a sequence of statements，${\mathcal{A}}_1,\cdots ,{\mathcal{A}}_n,\mathcal{A}$，${\mathcal{A}}_1,\cdots ,{\mathcal{A}}_n$ are premises(前提)，$\mathcal{A}$ is conclusion(结论)
• invalid argument(无效论证)：A argument is invalid if it is possible to assign truth values to the statement variables occurring in such a way as to make each of ${\mathcal{A}}_1,\cdots ,{\mathcal{A}}_n$ take value T and to make $\mathcal{A}$ take value F; Otherwise the argument form is valid.

性质

1. 若$\mathcal{A}$和$\mathcal{A}\to \mathcal{B}$都是重言式,则$\mathcal{B}$也是重言式
2. 用任意statement form替换重言式$\mathcal{A}$中的命题变量所得到的statement form仍是重言式。
3. 若$\mathcal{C}$是$\mathcal{A}$中的命题公式，$\mathcal{B}$是与$\mathcal{C}$等价的命题公式，则用$\mathcal{B}$替换$\mathcal{A}$中的$\mathcal{C}$后得到的命题公式${\mathcal{A}}^{\prime }$与$\mathcal{A}$逻辑等价。
4. 常见完备联结词：$\{\neg ,\wedge \},\{\neg ,\vee \},\{\neg ,\to \}$
5. 一个论证是有效的当且仅当$(({\mathcal{A}}_1\wedge \cdots \wedge {\mathcal{A}}_n)\to \mathcal{A})$是重言式。

常用的logically equivalent

• 双重否定：$\neg \neg p⟺p$
• 合取交换律：$p\wedge q⟺q\wedge p$
• 合取结合律：$(p\wedge q)\wedge r⟺p\wedge (q\wedge r)$
• 合取德摩根律：$\neg (p\wedge q)⟺\neg p\vee \neg q$
• 合取吸收律：$p\wedge (p\vee q)⟺p$
• 析取交换律：$p\vee q⟺q\vee p$
• 析取结合律：$(p\vee q)\vee r⟺p\vee (q\vee r)$
• 析取德摩根律：$\neg (p\vee q)⟺\neg p\wedge \neg q$
• 析取吸收律：$p\vee (p\wedge q)⟺p$
• 析取对合取的分配律：$p\vee (q\wedge r)⟺(p\vee q)\wedge (p\vee r)$
• 合取对析取的分配律：$p\wedge (q\vee r)⟺(p\wedge q)\vee (p\wedge r)$
• 蕴含：$p\to q⟺\neg p\vee q$
• 等价：$(p⟺q)⟺(p\to q)\wedge (q\to p)$
• 逆否：$(p\to q)⟺(\neg q\to \neg p)$