离散数学：命题逻辑
命题逻辑
命题
数理逻辑研究的中心问题是推理，而推理的前提和结论都是命题，因而命题是推理的基本单位
Definition
具有确切真值的陈述句成为命题(proposition)。该命题可以取一个值，称为真值。真值只有“真”和“假”两种，分别用“T”（1）或者“F”（0）表示。
一切没有判断的句子，图命令句（祈使句）、感叹句、疑问句、二义性的陈述句等都不能作为命题
复合命题
Definition
- 原子命题（简单命题）：不能再分解为更为简单命题的命题。
- 符合命题：可以分解为更为简单命题的命题。这些命题之间通过如“或者”、“并且”、“不”、“如果……则……”、“当且仅当”等这样的关联词和标点符号复合而成。
\[ 预定：通常用大写的带或不带小标的英文字母表示命题(包括原子命题和符合命题)\\ A,B,C,\cdots,P,Q,R,\cdots,P_i,Q_i,R_i,\cdots\\ \]
命题连接词
否定联结词
Definition
设P是任意一个命题，复合命题“非P”（或“P的否定”）成为P的否定式(negation),记作\(\neg P\)
\(\neg\)是否定连接词。P当且仅当$ P$为假。
P \(\neg P\) 0 1 1 0 \(\neg\)是自然语言中“非”、“不”、“没有”等的逻辑抽象
合取联结词
Definition
设P、Q是任意两个命题，复合命题“P并且Q”（或“P和Q”）成为P与Q的合取式(conjunction),记作\(P \wedge Q\),\("\wedge"\)为合取联结词。\(P\wedge Q\)为真当且仅当P、Q同为真。
P Q \(P\wedge Q\) 0 0 0 0 1 0 1 0 0 1 1 1
析取联结词
Definition
设P、Q是任意两个命题，复合命题“P或Q”称为P与Q的析取式(disjunction),记作\(P \vee Q\),\(\vee\)为析取联结词.\(P \vee Q\)为真当且仅当P，Q至少有一个为真。
P Q \(P \vee Q\) 0 0 0 0 1 1 1 0 1 1 1 1
蕴含联结词
Definition
设P、Q是任意两个命题，复合命题“如果P，则Q”成为P与Q的蕴含式(implication),记作\(P\rightarrow Q\),\(\rightarrow\)为蕴含联结词。\(P \rightarrow Q\)为假当且仅当P为真且Q为假。一般把蕴含式\(P \rightarrow Q\)中的P称为该蕴含是的前件，Q称为蕴含式的后件。
P Q \(P\rightarrow Q\) 0 0 1 0 1 1 1 0 0 1 1 1
等价联结词
Definition
设P、Q是任意两个命题，复合命题“P当且仅当Q”称为P与Q等价式(quivalence),记作\(P\leftrightarrow Q\),\(\leftrightarrow\)为等价联结词(也称作双条件联结词)。\(P\leftrightarrow Q\)为真当且仅当P、Q同为真假。
P Q \(P\leftrightarrow Q\) 0 0 1 0 1 0 1 0 0 1 1 1
联结词总结
| P | Q | \(\neg P\) | \(P \wedge Q\) | \(P \vee Q\) | \(P \rightarrow Q\) | \(P \leftrightarrow Q\) |
|---|---|---|---|---|---|---|
| 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 |
联结词是两个命题真值之间的联结，而不是命题内容之间的联结，因此复合命题的真值只取决于构成他们的各简单命题的真值，而与它们的内容无关，与两者之间是否有联系无关。
联结词的优先级
- 优先顺序:否定，合取，析取，蕴含，等价
- 同济联结词，按其先后顺序
- 若运算要求和优先次序不一致时，可使用括号；同级联结词相邻时，也可使用括号。括号中运算为最高优先级。
命题公式和真值表
命题变元
Definition
一个特定的命题是一个常值命题，它不是具有值“T”（“1”），就是具有值“F”（“0”）。
Definition
一个任意没有赋予具体内容的原子命题是一个变量命题，常称它为命题变量（或命题变元）(propositional variable)，该命题变量无具体的真值，它的变域是集合｛T，F｝。
复合命题是由原子命题与联结词构成的命题。所以，当其中的原子命题是命题变元时，此复合命题也即为命题变元的函数，且该函数的值仍为“真”或“假”值，这样的函数可形象地成为“真值函数”或者“命题公式”，此命题公式没有确切的真值。
例如：\(G=P \wedge Q \rightarrow \neg R\)
命题公式
Definition
命题验算的合式公式(well formed formula,wff),又称为命题公式(简称公式)，按以下规则生成：
- 命题变元本身是一个公式；（如：P，Q，R，……）
- 如G是公式，则\((\neg G)\)也是公式；（如：\(\neg P ,\neg Q,\neg R,\cdots\)）
- 如果G、H是公式，则\((G\wedge H)、(G \vee H)、(G \rightarrow H)、(G\leftrightarrow H)\)也是公式；(如：\(P\wedge Q,(\neg Q)\rightarrow R,\cdots\))
- 仅由有限步使用规则（1）、（2）、（3）后所得到的包含命题变元、联结词和括号的符号串才是命题公式.(如：\(\neg(P\wedge Q) \leftrightarrow R,(\neg Q \vee(P\wedge\neg R))\rightarrow R,\cdots\))
如果G是含有n个命题变元\(P_1、P_2、\cdots 、P_n\)的公式，可记为：\(G(P_1,P_2,\cdots,P_n)\)或简写为G。
- 原子命题变元时最简单的合式公式，成为原子合式公式，简称原子公式；
- 命题公式没有真值，只有对其命题变元进行真值指派后，方可确定命题公式的真值；
- 整个公式的最外层括号可以省略；公式内不影响运算顺序的括号也可以省略。
- 在实际应用中，为了便于储存和运算，命题公式常用二元树的方式来表达。
公式的解释
Definition
设\(P_1、P_2、P_3、\cdots、P_n\)是出现在公式G中的所有命题变元，指定\(P_1、P_2、P_3、\cdots、P_n\)一组真值，则这组真值称为G的一个解释，常记为I。
如果公式G在解释I下是真的，则称I满足G，此时I是G的成真赋值；
如果公式G在解释I下是假的，则称I弄假于G，此时I是G的成假赋值。
真值表
Definition
由公式G在其所有可能的即使下所取真值构成的表，成为G的真值表(truth table).
命题公式的分类和等价
命题公式的分类
公式G称为永真公式(重言式，tautology),如果在它的所有解释之下其真值都为真。
公式G称为永假公式(矛盾式，contradiction)，如果在它的所有解释下其真值都为“假”。有时也称为不可满足公式。
公式G称为可满足公式(satisfiable),如果它不是永假的。
关系
- G是永真的当且仅当\(\neg G\)是永假的；
- G是可满足的当且仅当至少有一个解释I，使G在I下为真。
- 若G是永真式，则G一定是可满足式，但反之可满足时不一定是永真式；
公式的逻辑等价
Definition
设 G，H 是两个命题公式,\(P_1,P_2,P_3,\cdots,P_n\)是出现在 G,H 中所有的命题变元,如果对于\(P_1,P_2,P_3,\cdots,P_n\)的 2n 个解释,G 与 H 的真值结果都相同，则称公式 G 与 H 是等价的,记作G=H。(或\(G\Leftrightarrow H\))
充分必要条件，定理
对于任意两个公式G和H，G=H的充分必要条件是公式\(G\leftrightarrow H\)是永真公式。
命题公式的可判定性
能否给出一个可行方法，完成对任意公式的判定类问题。(类型或等价判定)
命题公式是可判定的。
基本等价关系及其应用
基本等价关系
定理：
设G，H，S为任意的命题公式。
定理 名称 \(E_1:G\vee G=G\)
\(E_2:G\wedge G=G\)幂等率 \(E_3:G \vee H=H \vee G\);
\(E_4:G \wedge H=H \wedge G\)交换律 \(E_5:G\vee(H\vee S)=(G\vee H)\vee S\);
\(E_6:G\wedge(H\wedge S)=(G\wedge H)\wedge S\)结合律 \(E_7:G\vee 0=G\);
\(E_8:G\wedge 1=G\)同一律 \(E_9:G\vee 1=1\);
\(E_{10} :G\wedge 0=0\)零率 \(E_{11}:G\vee(H\wedge S)=(G\vee H)\wedge(G\vee S)\);
\(E_{12}:G\wedge(H\vee S)=(G\wedge H)\vee(G\wedge S)\)分配率 \(E_{13}:G\vee(G \wedge H)=G\):
\(E_{14}:G\wedge(G\vee H)=G\)吸收率 \(E_{15}:\neg G\wedge G=0\) 矛盾律 \(E_{16}:\neg G \vee G=1\) 排中律 \(E_{17}:\neg(\neg G)=G\) 双重否定率 \(E_{18}:\neg (G\vee H)=\neg G \wedge \neg H\);
\(E_{19}:\neg(G \wedge H)=\neg G \vee \neg H\)德摩根律 \(E_{20}:G\rightarrow H=\neg G \vee H\) 蕴含式 \(E_{21}:G\rightarrow H= \neg H \rightarrow \neg G\) 假言易位 \(E_{22}:G\leftrightarrow H=(G\rightarrow H)\wedge(H\rightarrow G)=(\neg G \vee H)\wedge (\neg H \vee G)\) 等价式 \(E_{23}:G\leftrightarrow H=\neg G\leftrightarrow \neg H\) 等价否定等式 \(E_{24}:(G\rightarrow H)\wedge(G \rightarrow \neg H)=\neg G\) 归谬论
范式
Definition
- 命题变元或命题变元的否定称为文字。\(P,\neg P,Q,\neg Q,\cdots\)
- 有限个文字的析取成为简单析取式（或子句）。\(P\vee Q \vee R,\cdots\)
- 有限个文字的合取成为简单合取式（或短语）。\(\neg P\wedge Q \wedge R\)
- P与\(\neg P\)称为互补对。
Definition
有限个简单合取式（短语）的析取式成为析取范式(disjunctive normal form);
如\((P\wedge Q)\vee(\neg P \wedge Q)\)
有限个简单析取式（子句）的合取式成为合取范式(conjunctive normal form)。
如：\((P \vee Q)\wedge(\neg P \vee Q)\)
范式存在定理
对于任何命题公式，都存在与其等价的析取范式和合取范式。
主范式
极小项和极大项
Definition
在含有n个命题变元\(P_1,P_2,P_3,\cdots,P_n\)的短语或子句中，若每个命题变元与其否定不同时存在，但二者之一恰好出现一次且仅一次，并且出现次序与\(P_1,P_2,P_3,\cdots,P_n\)一致，则称此短语或子句为关于\(P_1,P_2,P_3,\cdots,P_n\)的一个极小项或极大项。
一般来说，若有n个命题变元，则有\(2^n\)个不同的极小项和\(2^n\)个不同的极大项。
极小项
- 没有两个不同的极小项是等价的。
- 每个极小项只有一组成真赋值，因此可用于给极小项编码。编码规律：命题变元与1对应，命题变元的否定与0对应。
极大项
- 没有两个不同的极大项是等价的。
- 每个极大项只有一组成假赋值，因此可用于给极大项编码。编码规律为：命题变元与0对应，命题变元的否定与1对应
性质(小写字母极小项，大写字母极大项)
\(m_i\wedge m_j=0\)
\(M_i\vee M_j=1\)(\(i\neq j\))
\(m_i =\neg M_i\)
\(M_i=\neg m_i\)
\[ \bigvee_{i=0}^{2^n-1} m_i=1\\ \bigwedge_{i=0}^{2^n-1}M_i=0 \]
主析取范式和主合取范式
Definition
- 在给定的析取范式中，若每个短语都是极小项，且按照编码从小到大的排序排列，则称该范式为主析取范式(priincipal disjunctive normal form)。
- 在给定的合取范式中，若每一个最大子句都是极大项，且按照编码从小到大的顺序排列，则称该范式为主合取范式(principal conjunctive normal form)。
Theorem
任何一个公式都有与之等价的主析取范式和主合取范式。
主范式求解定理
Proof
求出该公式所对应的的析取范式和合取范式
消去重复的命题变元，矛盾式和重言式；
幂等率、矛盾律、同一律、排中律、零率
主范式可用于了解公式的真值情况，进行公式类型的判定以及等价关系的判定。
- 如果主析取范式包含所有的极小项，该公式为永真公式
- 如果主合取范式包含所有的极大项，该公式为永假公式
- 若两个公式具有相同的主析取范式或主合取范式，则两公式等价
基本推理形式和蕴含关系
推理的基本形式
所谓推理，是指从一组前提合乎逻辑的退出结论的思维过程。在这里，我们使用命题公式来表达前提和结论。
Definition \[ 设G_1,G_2,\cdots,G_n,H是公式，称H是G_1,G_2,\cdots,G_n的逻辑结果当且仅当对任意解释I\\ 如果I使得G_1\wedge G_2 \wedge G_3 \wedge \cdots\wedge G_n为真，则I也会使H为真。记为G_1,G_2,\cdots,G_n\Rightarrow H."\Rightarrow"成为蕴含关系。\\ 此时称G_1,G_2,\cdots,G_n\Rightarrow H为有效的，否则成为无效的。G_1,G_2,\cdots,G_n\\ 成为一组前提，有时用集合\Gamma来表示，记作\Gamma= \{G_1,G_2,\cdots,G_n \},H成为结论。\\ 此时也成H是前提集合\Gamma的逻辑结果。记为\Gamma\Rightarrow H。 \] Theorem
公式H是前提集合\(\Gamma= \{G_1,G_2,\cdots,G_n \}\)的逻辑结果当且仅当（\(G_1\wedge G_2 \wedge\cdots\wedge G_n\rightarrow H\)）为永真公式。
推理定律-基本蕴含关系
Theorem
设G，H，I为任意的命题公式。
规则 表示 1.简化规则 \(I_1:G\wedge H\Rightarrow G\)
\(I_2:G\wedge H\Rightarrow H\)2.添加规则 \(I_3:G\Rightarrow G\vee H\)
\(I_4:H\Rightarrow G\vee H\)3.合取引入规则 \(I_5:G,H\Rightarrow G\wedge H\) 4.选言三段论 \(I_6;G\vee H,\neg G\Rightarrow H\)
\(I_7:G\vee H,\neg H\Rightarrow G\)5.假言推定原则 \(I_8:G\rightarrow H,G\Rightarrow H\) 6.否定后件式 \(I_9:G\rightarrow H,\neg H\Rightarrow \neg G\) 7.假言三段论 \(I_{10}:G\rightarrow H,H\rightarrow I\Rightarrow G\rightarrow I\) 8.二难推论 \(I_{11}:G\vee H,G\rightarrow I,H\rightarrow I\Rightarrow I\)
自然演绎法推理
推理规则
Theorem
- 规则P（称为前提引用规则）：在推导过程中，可随时引入前提集合中的任意前提；
- 规则T（称为逻辑结果引用规则）：在推导过程中，可以随时引入公式S，该公式S是由其前的一个或多个公式推导出来的逻辑结果。
- 规则CP（称为附加前提规则）：如果能从给定的前提集合\(\Gamma\)与公式P推导出S，则能从此前提集合\(\Gamma\)推导出\(P\rightarrow S\)
自然演绎法
Definition
从前提集合\(\Gamma\)推出结论H的一个演绎是构造命题公式的一个有线序列： \[ H_1,H_2,H_3,\cdots,H_{n-1},H_{n} \] 其中，\(H_i\)或者是\(\Gamma\)中的某个前提，或者前面某些\(H_j(j<i)\)的有效结论，并且\(H_n\)就是H，则称该公式H是该演绎的有效结论，或者称从前提\(\Gamma\)能够演绎出来结论H来。