数理逻辑研究的中心问题是推理，而推理的前提和结论都是命题，因而命题是基本的推理单元。

定义：

具有确切真值的陈述句称为命题（proposition）。该命题只可以取一个“值”，称为真值。真值只有“真”和“假”两种，分别用**“T”（或“1”）和“F”（或“0“）**表示。

有时需要依靠环境、条件、时间、地点判断命题的真值，而一个句子本身是否能够分辨真假与我们是否知道他的真假是两回事，也就是说，对于一个句子，有时我们可能无法判断他的真假，但这个句子本身是有真假的。

原子命题(简单命题) :不能再分解为更为简单命题的命题。

复合命题:可以分解为更为简单命题的命题。这些简单命题之间是通过如"或者"、“并且”、"不”、"如果则…“， “当且仅当"等这样的关联词和标点符号复合而成。

通常使用大写的带或者不带下标的英文字母表示命题（包括原子命题和复合命题）

主要的命题连接词有5个：

定义：设P是任意一个命题，复合命题"非P"(或“P的否定”)称为P的否定式(negation) ，记作 ⌝ P \urcorner P ┐P ，“ ⌝ \urcorner ┐”为否定联结词。P为真当且仅当 ⌝ \urcorner ┐ P为假。

定义：设P、Q是任意两个命题,复合命题"P并且Q"(或"P和Q")称为P与Q的合取式(conjunction) ,记作 P ∧ Q P\land Q P∧Q,“A"为合取联结词。 P ∧ Q P\land Q P∧Q为真当且仅当P, Q同为真。

设P、Q是任意两个命题，复合命题“P或Q”称为P与Q的析取式(disjunction) ,记作 P ∨ Q P\vee Q P∨Q, “V"为析取联结词。 P ∨ Q P\vee Q P∨Q为真当且仅当P, Q至少有一个为真。

代表的是自然语言中的“可兼或”，“不可兼或”是异或。

设P、Q是任两个命题,复合命题“如果P，则Q”称为P与Q的蕴涵式(implication) ，记作P→Q,“→"为蕴涵联结词。P→Q为假当且仅当P为真且Q为假。一般把蕴涵式P→Q中的P称为该蕴涵式的前件, Q称为蕴涵式的后件。

前件为假，那么不管后件真假如何，命题为真。

在自然语言中，前件为假，不管结论真假，整个语句的意义,往往无法判断。但对于数理逻辑中的蕴涵联结词来说,当前件P为假时,不管Q的真假如何，则P→Q都为真。此时称为**“善意推定”**。

设P、Q是任两个命题,复合命题"P当且仅当Q"称为P与Q的等价式(equivalence) ,记作“ P ↔ Q P\leftrightarrow Q P↔Q“，"$\leftrightarrow " 为等价联结词 ( 也称作双条件联结词 ) 。 "为等价联结词(也称作双条件联结词)。 "为等价联结词(也称作双条件联结词)。P\leftrightarrow Q$为真当且仅当P、Q同为真假。

联结词是两个命题真值之间的联结，而不是命题内容之间的连接，因此复合命题的真值只取决于构成他们的各简单命题的真值，而与它们的内容无关，与二者之间是否有关系无关。

Example：

所有五个连接词的优先顺序为：

否定 > 合取 > 析取 > 蕴含 > 等价

同级的连接词，按其出现的顺序（从左往右）

若运算要求与优先次序不一样，可以使用括号；同级连接词相邻时也可以使用括号

括号中的优先级为最高优先级

定义：一个特定的命题是一个常值命题 ，它不是具有值“T"(“1”) ，就是具有值“F"(“0")。

定义：一个任意的没有赋予具体内容的原子命题是一个变量命题，常称它为命题变量(或命题变元)(propositional variable)，该命题变量无具体的真值,它的变域是集合{T, F}(或{0, 1})。

复合命题是由原子命题与联结词构成的命题。所以，当其中的原子命题是命题变元时，此复合命题也即为命题变元的函数，且该函数的值仍为“真”或"假”值，这样的函数可形象地称为“真值函数”或“命题公式”，此命题公式没有确切的真值。 G = P ∨ Q → ⌝ P G=P\vee Q\rightarrow \urcorner P G=P∨Q→┐P

命题演算的合式公式又称为命题公式（简称公式），按如下规则生成：

仅由有限步使用规则（1）（2）（3）得到的包含命题变元、连接词和括号的符号串才是命题公式。

note：

原子命题变元是最简单的合式公式，称为原子合式公式，简称原子公式

命题公式没有真值，只有对其命题变元进行真值指派后,方可确定命题公式的真值;

整个公式的最外层括号可以省略；公式中不影响运算次序的括号也可以省略。

在实际应用中，为了便于存储和运算，命题公式常用二元树的方式来表达。

定义：设 P 1 、 P 2 、 P 3 、 . . . P n P_1、P_2、P_3、 ... P_n P1​、P2​、P3​、...Pn​是出现在公式G中的所有命题变元，指定 P 1 、 P 2 、 P 3 、 . . . . P n P_1、 P_2、P_3、 .... P_n P1​、P2​、P3​、....Pn​一组真值，则这组真值称为G的一个解释，常记为 I I I。

如果公式在I下的解释是真的，则称I满足G，此时I是G的成真赋值；如果G在解释I下是假的，则称I弄假G，此时I是G的弄假赋值。

由公式G在其所有的解释下所取的真值构成的表，称为G的真值表。

定义：

三种公式直接的关系：

定义：设G, H是两个命题公式 P 1 , P 2 , P 3 , . . . , P n P_1, P_2, P_3, ... , P_n P1​,P2​,P3​,...,Pn​.是出现在G, H中所有的命题变元，如果对于 P 1 , P 2 , P 3 , . . . , P n P_1,P_2,P_3,...,P_n P1​,P2​,P3​,...,Pn​的 2 n 2^n 2n个解释，G与H的真值结果都相同，则称公式G与H是等价的，记作G = H。( 或G ⇔ \Leftrightarrow ⇔H)

定理：对于任意两个公式G和H，G = H的充分必要条件是公式 G ↔ H G\leftrightarrow H G↔H是永真公式。

可判定性：能否给出一个可行方法，完成对任意公式的判定类问题。（类型或等价判定）

命题公式是可判定的。——使用真值表/公式推理的方法判定公示

设 G , H , S G, H, S G,H,S 为任意的命题公式。 (1) E 1 : G ∨ G = G E_{1}: G \vee G=G E1​:G∨G=G; E 2 : G ∧ G = G E_{2}: G \wedge G=G E2​:G∧G=G. 幂等律 (2) E 3 : G ∨ H = H ∨ G E_{3}: G \vee H=H \vee G E3​:G∨H=H∨G; E 4 : G ∧ H = H ∧ G E_{4}: G \wedge H=H \wedge G E4​:G∧H=H∧G. 交换律 (3) E 5 : G ∨ ( H ∨ S ) = ( G ∨ H ) ∨ S E_{5}: G \vee(H \vee S)=(G \vee H) \vee S E5​:G∨(H∨S)=(G∨H)∨S; E 6 : G ∧ ( H ∧ S ) = ( G ∧ H ) ∧ S E_{6}: G \wedge(H \wedge S)=(G \wedge H) \wedge S E6​:G∧(H∧S)=(G∧H)∧S. 结合律 (4) E 7 : G ∨ 0 = G E_{7}: G \vee 0=G E7​:G∨0=G; E 8 : G ∧ 1 = G E_{8}: G \wedge 1=G E8​:G∧1=G. 同一律 (5) E 9 : G ∨ 1 = 1 E_{9}: G \vee 1=1 E9​:G∨1=1; E 10 : G ∧ 0 = 0 E_{10}: G \wedge 0=0 E10​:G∧0=0. 零律 (0) E 11 : G ∨ ( H ∧ S ) = ( G ∨ H ) ∧ ( G ∨ S ) E_{11}: G \vee(H \wedge S)=(G \vee H) \wedge(G \vee S) E11​:G∨(H∧S)=(G∨H)∧(G∨S); E 12 : G ∧ ( H ∨ S ) = ( G ∧ H ) ∨ ( G ∧ S ) E_{12}: G \wedge(H \vee S)=(G \wedge H) \vee(G \wedge S) E12​:G∧(H∨S)=(G∧H)∨(G∧S). 分配律 (1) E 13 : G ∨ ( G ∧ H ) = G E_{13}: G \vee(G \wedge H)=G E13​:G∨(G∧H)=G E 14 : G ∧ ( G ∨ H ) = G E_{14}: G \wedge(G \vee H)=G E14​:G∧(G∨H)=G. 吸收律 (8) E 15 : ¬ G ∧ G = 0 E_{15}: \neg G \wedge G=0 E15​:¬G∧G=0. 矛盾律 (9) E 16 : ¬ G ∨ G = 1 E_{16}: \neg G \vee G=1 E16​:¬G∨G=1. 排中律 (10) E 17 : ¬ ( − G ) = G E_{17}: \neg(-G)=G E17​:¬(−G)=G. 双重否定律

Example：

真值表能够方便地给出命题公式的真值情况，但是真值表的规模随着命题变元的数量呈指数型增长，因而我们考虑一种真值表的替代方法，这种方法是基于命题公式的一种标准形式。

定义：

note：有限个包括一个，文字既是子句也是短语

定义：

有限个简单合取式（短语）的析取式称为析取范式 如 ( P ∧ Q ) ∨ ( ⌝ P ∧ Q ) ，又如 P ∨ ⌝ Q , P , ⌝ Q 如(P\land Q)\vee (\urcorner P\land Q)，又如P\vee \urcorner Q, P,\urcorner Q 如(P∧Q)∨(┐P∧Q)，又如P∨┐Q,P,┐Q 有限个简单析取式（子句）的合取式称为合取范式 如 ( P ∨ Q ) ∧ ( ⌝ P ∨ Q ) ，又如 P ∧ ⌝ Q , P , ⌝ Q 如(P\vee Q)\land (\urcorner P\vee Q)，又如P\land \urcorner Q, P,\urcorner Q 如(P∨Q)∧(┐P∨Q)，又如P∧┐Q,P,┐Q

总结

范式存在定理：

对于任意命题公式，都存在与其等价的合取范式和析取范式。

Proof：

可以由逻辑等价公式求出等价它的析取范式和合取范式，具体步骤如下：

总结：

命题公式的析取范式可以指出公式何时为真，而合取范式可以指出公式何时为假，从而能够代替真值表。

命题公式的范式表达并不唯一，比如对公式 ( P ∨ Q ) ∧ ( P ∨ R ) (P\vee Q)\land (P\vee R) (P∨Q)∧(P∨R)而言，对应的析取范式有很多

最后：

一般求解范式的时候，最后要进行化简的过程。

引入主范式：

由于范式的不唯一性，我们考虑对构成范式的子句或短语进一步规范化 ,从而形成**唯一的主析取范式和主合取范式**。

在含有n个命题变元 P 1 , P 2 , . . . , P n P_1,P_2,...,P_n P1​,P2​,...,Pn​的短语或者子句中，若每个命题变元与其否定不同时存在，但二者之一恰好出现一次且仅一次，并且出现次序与 P 1 , P 2 , . . . , P n P_1,P_2,...,P_n P1​,P2​,...,Pn​一致，则称此短语为关于 P 1 , P 2 , . . . , P n P_1,P_2,...,P_n P1​,P2​,...,Pn​的一个极小项或者极大项。

一般来说，若有n个命题变元，则应有 2 n 2^n 2n个不同的极小项和 2 n 2^n 2n个不同的极大项

定义：

公理：

任何一个公式都有与其等价的主析取范式和主合取范式。

Proof：

求出公式的析取范式和合取范式

消去重复出现的变元，矛盾式与重言式

若析取（合取）式的某一个短语（子句） B i B_i Bi​中缺少命题变元P，则可用下面的方法将命题变元P补进去

利用幂等律将重复的极小项和极大项合并，并利用交换律进行顺序调整，由此可转换成标准的主析取范式和主合取范式。

利用真值表技术求主析取范式和主合取范式的简要方法:

从真值表按所给的算法求出主范式的方法,称为真值表技术(technique of truth table)。

由真值表技术可知，对于任一个命题公式而言，主析取范式所使用的极小项的编码和主合取范式所使用的极大项的编码是“互补”的关系。从而我们在求主析取范式和主合取范式时，可根据公式特点，先求出二者之一，然后可直接写出另一 个。

主范式可以用于了解公式的真值情况，进行公式类型的判定和等价关系的判定。

定义：称 F : { 0 , 1 } n → { 0 , 1 } F:\{0,1\}^n\rightarrow \{0,1\} F:{0,1}n→{0,1}为n元真值函数

F的定义域： { 0 , 1 } n = { 00...0 , 00...1 , . . . , 11...1 } \{0,1\}^n=\{00...0,00...1,...,11...1\} {0,1}n={00...0,00...1,...,11...1}，即由0，1组成的长为n的符号串的全体，值域为 { 0 , 1 } \{0,1\} {0,1}。n个命题变项可以构成 2 2 n 2^{2^n} 22n个不同的真值函数。

每个真值函数与唯一的主析取范式（主合取范式）等值。例如 F 0 ( 2 ) ⇔ 0 F_0^{(2)}\Leftrightarrow 0 F0(2)​⇔0(矛盾式)， F 1 ( 2 ) ⇔ ( p ∧ q ) ⇔ m 3 … … F_1^{(2)}\Leftrightarrow (p \land q) \Leftrightarrow m_3…… F1(2)​⇔(p∧q)⇔m3​……，等。每个主析取范式对应无穷多个等值的命题公式，每一个命题公式又有唯一等值的主析取范式，所以每个真值函数对应无穷多个等值的命题公式，每个命题公式又对应唯一的等值的真值函数。

定义： 设S是一个联结词集合，如果任何 n ( ≥ 1 ) n(\geq 1) n(≥1)元真值函数都可以由仅含S中的联结词构成的公示表示，那么则称S是联结词的完备集。

定理： S = { ⌝ , ∨ , ∧ } S=\{\urcorner, \vee, \land\} S={┐,∨,∧}是连接词完备集

推论：以下的联结词都是联结词完备集

(1) S 1 = { ¬ , ∧ , ∨ , → } S_{1}=\{\neg, \wedge, \vee, \rightarrow\} S1​={¬,∧,∨,→} (2) S 2 = { ¬ , ∧ , ∨ , → , ↔ } S_{2}=\{\neg, \wedge, \vee, \rightarrow, \leftrightarrow\} S2​={¬,∧,∨,→,↔} (3) S 3 = { ¬ , ∧ } S_{3}=\{\neg, \wedge\} S3​={¬,∧} (4) S 4 = { ¬ , ∧ } S_{4}=\{\neg, \land\} S4​={¬,∧} (5) S 5 = { ¬ , → } S_{5}=\{\neg, \rightarrow\} S5​={¬,→}

设p, q是两个命题，复合命题“p与q的否定”称为p, q的与非式，记做 p ↑ q p\uparrow q p↑q，即 p ↑ q ⇔ ¬ ( p ∧ q ) p\uparrow q \Leftrightarrow \neg(p \land q) p↑q⇔¬(p∧q)，符号$\uparrow $称为与非连接词。

设p, q是两个命题，复合命题“p或q的否定”称为p, q的或非式，记做 p ↓ q p\downarrow q p↓q，即 p ↓ q ⇔ ¬ ( p ∨ q ) p\downarrow q \Leftrightarrow \neg(p \vee q) p↓q⇔¬(p∨q)，符号$\uparrow $称为与非连接词。

定理： { ↑ } 和 { ↓ } \{\uparrow \}和\{\downarrow\} {↑}和{↓}都是联结词完备集