@[TOC]
1.求主合取范式和主析取范式
合取，两个都对才对，所以是“与”号。
析取，一个对就对，所以是“或”号。
对于一个逻辑表达式，先列出真值表，主合取范式为所有令结果为假的最大项合取，主析取范式为所有令结果为真的最小项析取，举个例子：
求：$p\to q$的主合取范式和主析取范式。
解：列真值表：
| p | q | $p\to q$ |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 1 | 1 |
| 1 | 0 | 0 |
所以弄假表达式的最大项为：
弄真表达式的最小项为：
主合取范式、主析取范式可得。
2.逻辑等价/蕴含是否成立
反证法，若蕴含不成立，则必定存在一种指派$v$，弄真左侧，弄假右侧。
也可以列真值表求解。
对于任意指派，逻辑等价为两个逻辑表达式真值恒等，逻辑蕴含是指蕴含式恒真。
3.PC(Propositional Calculus)系统上的定理备忘（部分）
$$
If \ \ \vdash P,then\ \ \vdash A\to P
$$
$$
\neg A\to (A\to B)\
$$
$$
(\neg A\to B)\to ((\neg A\to\neg B)\to A)\
$$
$$
\neg A\to C,B\to C\Leftrightarrow (A\to B)\to C\
$$
$$
(A\to B)\to((A\to \neg B)\to\neg A)\
$$
$$
A\to B,C\to D \to (B\to C)\to(A \to D)
$$
4.ND(Natural Deduction)系统上的定理备忘（部分）
$$
\frac{\Gamma;A\vdash B\ \ \Gamma;\neg A\vdash B}{\Gamma\vdash B}\ \ (\neg -)\
$$
$$
\frac{\Gamma\vdash A}{\Gamma\vdash A\vee B}\ \ (\vee +)\
$$
$$
\frac{\Gamma;A\vdash C\ \ \Gamma;B\vdash C\ \ \Gamma\vdash A\vee B}{\Gamma\vdash C}\ \ (\vee -)\
$$
$$
\frac{\Gamma;A\vdash B\ \ \Gamma;A\vdash\neg B}{\Gamma\vdash \neg A}\ \ (\neg +)\
$$
$$
\frac{\Gamma\vdash A\ \ \Gamma\vdash\neg A}{\Gamma\vdash B}\ \ (\neg -)\
$$
事实上，PC、ND两个系统等价，定理可以通用。可惜考试的时候不能用。
5.连接词备忘
$\uparrow,\downarrow$分别为与非词，或非词。有如下规律：
$$
\neg p = p\uparrow p=p\downarrow p
$$
$$
p\vee q = (p\downarrow q)\downarrow(p\downarrow q)
$$
$$
p\wedge q = (p \uparrow q)\uparrow (p \uparrow q)
$$
对于蕴含词$\to$，可变换为：
$$
p\to q = \neg p \vee q
$$