命题与联结词

命题是真假性唯一的陈述句，不能可真可假。若陈述句中存在悖论，或者分情况确定真假，也不构成命题

最简单的命题是原子命题，它是由简单陈述句构成的命题，将其抽象为符号，如p,q,r。它的作用和地位可以类比于单词，具有最基本的语义，也称为原子语句

由原子命题通过联结词联结而成的陈述句称为复合命题。逻辑联结词可以如下列出

规定联结词具有优先级

()\to \neg\to\wedge,\vee\to\Rightarrow,\Leftrightarrow

同级联结词从左到右结合。联结词的真假如下表

$p,q$	$\neg p$	$p\wedge q$	$p\vee q$	$p\Rightarrow q$	$p\Leftrightarrow q$
啥啊	$p$ 假时真	$pq$ 都真时真	$pq$ 都假时假	$p$ 真 $q$ 假时假	$pq$ 真假相同时真
0 0	1	0	0	1	1
0 1	1	0	1	1	0
1 0	0	0	1	0	0
1 1	0	1	1	1	1

比较难以理解的是蕴含联结词。可以这样理解： $p\Rightarrow q$ 为真意味着p蕴含q，即当p为真时q一定为真，而不要求p为假时q的真假性。也就是说p蕴含q不成立仅有一种可能，即p为真时q为假

逻辑等价

在所有的模型中两个语句真假相同称为逻辑等价。基本的逻辑等价可以列出如下表

定律	表达式1	表达式2
双重否定律	$\neg \neg A \equiv A$
恒等律	$A \lor A \equiv A$	$A \land A \equiv A$
交换律	$A \lor B \equiv B \lor A$	$A \land B \equiv B \land A$
结合律	$(A \lor B) \lor C \equiv A \lor (B \lor C)$	$(A \land B) \land C \equiv A \land (B \land C)$
分配律	$A \lor (B \land C) \equiv (A \lor B) \land (A \lor C)$	$A \land (B \lor C) \equiv (A \land B) \lor (A \land C)$
德·摩根律	$\neg (A \lor B) \equiv \neg A \land \neg B$	$\neg (A \land B) \equiv \neg A \lor \neg B$

存在一些为常数的情况

此外还有一些常用的逻辑恒等式

定律	表达式
蕴涵等值式	$A \Rightarrow B \equiv \neg A \lor B$
等价等值式	$A \Leftrightarrow B \equiv (A \Rightarrow B) \land (B \Rightarrow A)$
假言易位	$A \Rightarrow B \equiv \neg B \Rightarrow \neg A$
等价否定等值式	$A \Leftrightarrow B \equiv \neg A \Leftrightarrow \neg B$
归谬论	$(A \Rightarrow B) \land (A \Rightarrow \neg B) \equiv \neg A$

首先需要定义简单析取式和简单合取式

简单析取式

有限个文字用“或”连接形成的析取式

简单析取式的例子可以列出如下

简单合取式

有限个文字用“与”连接形成的合取式

简单合取式的例子可以列出如下

进一步定义析取范式与合取范式

析取范式DNF（与或式，先与再或）

有限个简单合取式用“或”连接形成的析取式

A_1\lor A_2\lor\cdots\lor A_n

其中 $A_i$ 是简单合取式

合取范式CNF（或与式，先或再与）

有限个简单析取式用“与”连接形成的合取式

A_1\land A_2\land\cdots\land A_n

其中 $A_i$ 是简单析取式

可以利用逻辑等价将命题改为析取范式或是合取范式

重言式：在所有模型都为真的语句，又称为有效的语句，如

A\lor \neg A

矛盾式：在所有模型都为假的语句，如

A\land \neg A

可满足式：非矛盾式的语句。重言式是可满足式，但是可满足式不是重言式

重言式的反是矛盾式，可以利用这个关系证明命题，即反证法

A\Rightarrow B 等价于 A\land \neg B 矛盾