1.5 对偶与范式
1.5.1 对偶
定义 在仅含有联结词Ø、∧、∨的命题公式A中，将联结词∧换成∨，将∨换成∧，如果A中含有特殊变元0或1，就将0换成1，1换成0，所得的命题公式A*称为A的对偶式。
例：公式（
P∨Q）∧（P∨Q） 的对偶式为：（P∧Q）∨（P∧Q）
定理 设A和A*互为对偶式，P1，P2，…，Pn是出现在A和A*中的所有原子变元，若将A和A*写成n元函数形式，则
（1）A（P1，P2，…，Pn）A*（P1，P2，…，Pn）
（2）A（P1，P2，…，Pn）A*（P1，P2，…，Pn）
定理（对偶原理）设A、B是两个命题公式，若AÛB，则A*B*，其中A*、B*分别为A、B的对偶式。
1.5.2 范式
定义 仅由有限个命题变元及其否定构成的析取式称为简单析取式，仅由有限个命题变元及其否定构成的合取式称为简单合取式。
定义 仅由有限个简单合取式构成的析取式称为析取范式。仅由有限个简单析取式构成的合取式称为合取范式。
定理（范式存在定理）任何命题公式都存在着与之等价的析取范式和合取范式。
1.5.3 主范式
定义 在含有n个命题变元P1，P2，…，Pn的简单合取范式中，若每个命题变元或其否定不同时存在，但二者之一必出现且仅出现一次，且第i个命题变元或其否定出现在从左起的第i个位置上（若命题变元无脚标，则按字典顺序排列），这样的简单合取式称为极小项。相应的，满足上述条件的简单析取式称为极大项。n个命题变元P1，P2，…，Pn的极小项用公式可表示为 Pi* ，极大项可表示为Pi*，其中，Pi*为Pi或Pi（i=1，2，…，n）。
定义 设G为公式，P1，P2，…，Pn为G中的所有命题变元，若G的析取范式中每一个合取项都是P1，P2，…，Pn的一个极小项，则称该析取范式为G的主析取范式。矛盾式的主析取范式为0。
定理 任意的命题公式都存在一个唯一的与之等价的主析取范式。
用等值演算求主析取范式步骤如下：
（1） 求G的析取范式G'；
（2）若G中某个简单合取式m中没有出现某个命题变元Pi或其否定Pi，则将m作如下等价变换：
mm∧（Pi∨Pi）（ m∧Pi）∨（m∧Pi）
（3）将重复出现的命题变元、矛盾式和重复出现的极小项都消去；
（4）重复步骤（2）、（3），直到每一个简单合取式都为极小项；
（5）将极小项按脚标由小到大的顺序排列，并用∑表示。如m0∨m1∨m7可表示为∑（0，1，7）。
定义 设G为公式，P1，P2，…，Pn为G中的所有命题变元，若G的合取范式中每一个析取项都是P1，P2，…，Pn的一个极大项，则称该合取范式为G的主合取范式。通常，主合取范式用∏表示。重言式的主合取范式中不含任何极大项，用1表示。
定理 任意的命题公式都存在一个唯一的与之等价的主合取范式。
1.6 公式的蕴涵
1.6.1 蕴涵的概念
定义
设G、H是两个公式，若G→H是永真式，则称G蕴涵H，记作GH。
蕴涵关系有如下性质：
（1） 对于任意公式G，有GG；
（2）对任意公式G、H，若GH且HG，则GH；
（3） 若GH且HL，则GL。
广义的蕴涵概念
定义 设G1，G2，…，Gn，H是公式，如果（G1∧G2∧…∧Gn）→H是永真式，则称G1，G2，…，Gn蕴涵H，又称H是G1，G2，…，Gn的逻辑结果，记作（G1∧G2∧…∧Gn）H或（G1，G2，…，Gn）H。
1.6.2 基本蕴涵式
（1）P∧QP； （2）P∧QQ；
（3）PP∨Q； (4) QP∨Q；
（5）P（P→Q）； （6）Q（P→Q）；
（7）（P→Q）P； （8）（P→Q）Q；
（9）P，P→QQ； （10）Q，P→QP；
（11）P，P∨QQ； （12）P→Q，Q→RP→R；
（13）P∨Q，P→R，Q→RR； （14）P→Q，R→S（P∧R）→（Q∧S）；
（15）P，QP∧Q。
1.7 其它联结词与最小联结词组
1.7.1 其它联结词
定义 设P、Q为命题公式，则复合命题P Q称为P和Q的不可兼析取，当且仅当P与Q的真值不相同时，PQ的真值为1，否则PQ的真值为假。
定义 设P、Q是两个命题公式，复合命题P Q称为命题P、Q的条件否定，当且仅当P的真值为1，Q的真值为0时，P Q的真值为1，否则 PQ的真值为0。
1.7.2 最小联结词组
定义 设S是一些联结词组成的非空集合，如果任何的命题公式都可以用仅包含S中的联结词的公式表示，则称S是联结词的全功能集。特别的，若S是联结词的全功能集且S的任何真子集都不是全功能集，则称S是最小全功能集，又称最小联结词组。
定理 {，∧，∨，→，}是联结词的全功能集。
定理 {，∧，∨}是联结词的全功能集。
定理 {，∧}，{、∨}，{，→}是最小联结词组。
定理 {↑}，{↓}是最小联结词组。
1.8 命题逻辑推理理论
1.8.1 命题逻辑推理理论
定义 如果G1，G2，…，Gn蕴涵H，则称H能够由G1，G2，…，Gn有效推出，G1，G2，…，Gn称为H的前提，H称为G1，G2，…，Gn的有效结论。称（G1∧G2∧…∧Gn）→H是由前提G1，G2，…，Gn推结论H的推理的形式结构。
1.8.2 推理规则
下面给出推理中常用的推理规则。
1． 前提引入规则：可以在证明的任何时候引入前提；
2． 结论引入规则：在证明的任何时候，已证明的结论都可以作为后续证明的前提；
3． 置换规则：在证明的任何时候，命题公式中的任何子命题公式都可以用与之等价的命题公式置换。
4． 言推理规则：P，P→QQ
5． 附加规则：PP∨Q；
6． 化简规则：P，QP；
7． 拒取式规则：Q，P→QP；
8． 假言三段论规则：P→Q，Q→RP→R；
9． 析取三段论规则：P，P∨QQ；
10.构造性二难规则：P∨Q，P→R，Q→RR；
11.合取引入规则：P，QP∧Q
1.8.3 推理常用方法
1.直接证法
直接证法就是根据一组前提，利用前面提供的一些推理规则，根据已知的等价公式和蕴涵式，推演得到有效的结论的方法，即有前提直接推导出结论。
例 构造下列推理的证明。
前提：P∨Q，P→R，Q→S 结论：S∨R
证明
（1）P∨Q 前提引入规则
（2）P→R 前提引入规则
（3）Q→S 前提引入规则
（4）S∨R （1）（2）（3）构造性二难规则
2．间接证法
间接证法主要有如下两种情况。
（1）附加前提证明法
有时要证明的结论以蕴涵式的形式出现，即推理的形式结构为：
（G1∧G2∧…∧Gn）（R→C）
设（G1∧G2∧…∧Gn）为S，则上述推理可表示为证明S（R→C），即证明S→（R→C）为永真式。
用附加前提证明法证明下面推理。
前提：P→（Q→R），S∨P，Q 结论：S→R
证明：
（1）S∨P 前提引入规则
（2）S 附加前提引入规则
（3）P （1）（2）析取三段论规则
（4）P→（Q→R） 前提引入规则
（5）Q→R （3）（4）假言推理规则
（6）Q 前提引入规则
（7）R （5）（6）假言推理规则
2）归缪法
定义 设G1，G2，…，Gn是n个命题公式，如果G1∧G2∧…∧Gn是可满足式，则称G1，G2，…，Gn是相容的。否则（即G1∧G2∧…∧Gn是矛盾式）称G1，G2，…，Gn是不相容的。
例 用归缪法证明。
前提：P∨Q，P→R，Q→S 结论：S∨R
证明
（1）（S∨R） 附加前提引入规则
（2）S∧R （1）置换规则
（3）S （2）化简规则
（4）R （2）化简规则
（5）Q→S 前提引入规则
（6）Q∨S （5）置换规则
（7）Q （3）（6）析取三段论
（8）P∨Q 前提引入规则
（9）P （7）（8）析取三段论规则
（10）P→R 前提引入规则
（11）P∨R （10）置换规则
（12）R （9）（11）析取三段论规则
（13）R∧R （4）（12）合取引入规则
