命题逻辑 | 夜雨阁

命题

$p$	$q$	$\neg p$	$p\wedge q$	$p\vee q$	$p\rightarrow q$	$p\leftrightarrow q$
0	1	1	0	1	1	0
0	0	1	0	0	1	1
1	1	0	1	1	1	1
1	0	0	0	1	0	0

命题公式：命题符号化的结果，符号串（也称合式公式）表示了命题的组成结构
类比代数公式：将联结词看作运算符
命题变量：表示某个不确定的命题的符号，值只能取0或1
命题常量：表示一个具体命题的符号， 0、1、其他符号
规定联结词的优先次序(从高到低)： $\neg$ 、∧、∨、→、 $\leftrightarrow$ ，前置单目联结符 $\neg$ 右结合，其它是双目联结符，左结合
含n个命题变量的命题公式 $A(p_1,p_2,...,p_n)$ 为n元命题公式
赋值：给公式中的每个变量赋予特定真值(0/1)
成真赋值：使得命题公式的真值为1的赋值
成假赋值：使得命题公式的真值为0的赋值
命题公式相等：两个公式任意赋值都取相同的真值
是永真式

$A\wedge A =A$ ， $A\vee A = A$
$A \wedge 0 = 0$ ， $A\vee 1 = 1$
$A \wedge 1 = A$ ， $A\vee 0 = A$
$A \wedge \neg A = 0$ ， $A \vee \neg A = 1$
$\neg \neg A = A$
$A\vee B = B\vee A$ ， $A\wedge B = B\wedge A$
$A\vee B\vee C = A\vee (B\vee C)$ ， $A\wedge B \wedge C = A\wedge (B\wedge C)$
$A\vee (B \wedge C) = (A\vee B) \wedge (A\vee C)$
$A\wedge (B\vee C) = (A\wedge B)\vee(A\wedge C)$
$A\vee (A\wedge B) = A$ ， $A\wedge (A \vee B) = A$
$\neg (A \vee B) = \neg A \wedge \neg B$ ， $\neg(A\wedge B) = \neg A \vee \neg B$
$A\rightarrow B = \neg A \vee B$
$A\leftrightarrow B = (A\rightarrow B)\wedge (B\rightarrow A)$
$A\rightarrow B = \neg B \rightarrow \neg A$
ps：可利用真值表证明

联结词集合 $S$ ，对任意真值函数 $F(x_1,x_2,…,x_n)$ ，存在仅含 $S$ 中的联结词的命题公式 $A$ ， $A$ 所对应的真值函数恰为 $F(x_1,x_2,…,x_n)$ ，即使用 $S$ 里的连接词就可以表示所有命题公式。
冗余联结词：联结词，删除它后的联结词集仍功能完备
独立联结词：非冗余联结词
极小完备集：不含冗余联结词
$\{\neg,\wedge,\vee \}$ 是完备集
$\{ \neg,\wedge \}$ ， $\{\neg,\vee\}$ 是极小完备集
定义： $p\uparrow q \Leftrightarrow \neg(p \wedge q)$ ， $p\downarrow q \Leftrightarrow \neg(p \vee q)$
$\{\uparrow\}$ ， $\{\downarrow\}$ 是完备集，证明：只需将 $\neg,\wedge,\vee$ 用 $\uparrow$ ( $\downarrow$ )表示出来即可

推理的数学模型
$H_1,H_2,...,H_n,C$ 命题公式， $H_i(i=1,2,...,n)$ 为前提， $C$ 为结论
$H_1,H_2,...,H_n$ 推出结论 $C$ 的推理正确： $H_1,H_2,...,H_n\Rightarrow C$ ，即 $(H_1\wedge H_2\wedge ...\wedge H_n)\rightarrow C$ 永真

推理规则：
- P规则(前提引入规则)：前提可在推理的任何一步引入
- T规则(重言蕴涵规则)：如果推理中前面已有的某些公式可合乎逻辑地推出公式C，则在推理中可以引入C

置换规则： $if\space A=B$ ，则 $A$ 推出 $B$
假言推理规则： $p,p\rightarrow q$ ，推出 $q$
附加规则： $p$ 推出 $p \vee q$
化简规则： $p \wedge q$ 推出 $p$
拒取式规则： $\neg q,p\rightarrow q$ 推出 $\neg p$
假言三段论规则： $p\rightarrow q,q\rightarrow r$ 推出 $p\rightarrow r$
析取三段论规则： $\neg q,p\vee q$ 推出 $p$
构造性二难推理规则： $p\vee s,p\rightarrow q,s\rightarrow t$ 推出 $q\vee t$
破坏性二难推理规则： $\neg q \vee \neg t,p\rightarrow q,s\rightarrow t$ 推出 $\neg p \vee \neg s$
合取引入规则： $p,q$ 推出 $p\wedge q$
消解法： $p\vee q,\neg p\vee r$ 推出 $q\vee r$

证明 $H_1,H_2,…,H_n\Rightarrow H\rightarrow C$ 的问题转化为证明 $H_1,H_2,…,H_n,H\Rightarrow C$ 的问题， $H$ 称为附加前提

欲证明 $H\Rightarrow C$ ，只需找到公式 $B$ 并证明 $H\wedge \neg C\Leftrightarrow B\wedge \neg B$
引入否定结论，证明 $p\wedge \neg p$ 的形式
从永假式可以推出(蕴含)任意命题
- 证明：对于任意命题公式 $C$ 和 $A$ ， $A\wedge \neg A\rightarrow C$ 是永真公式，所以 $A\wedge \neg A\Rightarrow C$
从任意命题可以推出(蕴含)永真式
逻辑蕴含关系并不必然表示因果关系，逻辑推理不等于因果推理