1、1 语法（语法（SyntaxSyntax）：语言符号及表达规则：语言符号及表达规则 。 语义（语义（SemanticsSemantics）：语言符号及表达规则的含义。：语言符号及表达规则的含义。 数理逻辑体系数理逻辑体系 形式系统（形式系统（Formal SystemFormal System）：利用逻辑语言的形式结：利用逻辑语言的形式结 构（即从语法的角度）来表达逻辑语句之间的关系。构（即从语法的角度）来表达逻辑语句之间的关系。 数理逻辑是采用数学的方法，研究思维形式及其规律的一数理逻辑是采用数学的方法，研究思维形式及其规律的一 门学科。门学科。 对思维的研究转变为对符号的演算。对思维的研究
2、转变为对符号的演算。 避免了自然语言的歧义性。避免了自然语言的歧义性。 奠定了自动推理的理论基础。奠定了自动推理的理论基础。 2 1.1. 命题公式命题公式 2.2. 公式的真值公式的真值 3.3. 范式范式 4.4. 联结词的完备集联结词的完备集 5.5. 推理理论推理理论 内容提要内容提要 1 1、命题公式、命题公式 概念概念： 命题，命题， 联结词联结词( ( ， ， ，) )，合式公式，子公式合式公式，子公式 命题的定义中包含二层含义：命题的定义中包含二层含义： ( (1 1) )在语法上在语法上命题必须是陈述句命题必须是陈述句。而疑问句而疑问句、祈使祈使 句和感叹句等无所谓真假句和感
3、叹句等无所谓真假，所以不是命题所以不是命题。 ( (2 2) )命题具有惟一的真值命题具有惟一的真值，这与我们是否知道它的真这与我们是否知道它的真 假是两回事假是两回事。 命题命题：具有确定真值的陈述句。：具有确定真值的陈述句。 真值真值：1(1(或或T)T)表示表示“真真”；0(0(或或 F)F)表示表示“假假” 5 下列句子中那些是命题？下列句子中那些是命题？ (1) 是有理数是有理数. (2) 2 + 5 = 7. (3) x + 5 3. (4) 你去教室吗？你去教室吗？ (5) 这个苹果真大呀！这个苹果真大呀！ (6) 请不要讲话！请不要讲话！ (7) 2050年元旦下大雪年元旦下大
4、雪. (8) 理发师理发师Richard专门为那些不专门为那些不 给自己理发的人理发。给自己理发的人理发。 2 假命题假命题 命题判断举例命题判断举例 真命题真命题 不是命题不是命题 不是命题不是命题 不是命题不是命题 不是命题不是命题 命题，但真值现在不知道命题，但真值现在不知道 不是命题，悖论不是命题，悖论 6 通常通常用小写英文字母用小写英文字母 p, q, r, , pi, qi, ri (i 1)表示命题。表示命题。 例如，令例如，令 p： 是有理数，则是有理数，则 p 的真值为的真值为0， q：2 + 5 = 7，则，则 q 的真值为的真值为1 命题符号分类：命题符号分类： 命题常
5、元（命题常项）： （bottom)， （top） 命题变元（命题变项）: p, q, r, 2 命题符号命题符号： 用来表示命题用来表示命题符号符号。 常见的常见的5个联结词个联结词 否定否定 (negation) 合取合取(conjunction) 析取析取(disjunction) 蕴含蕴含(implication) 等价等价(equailvalence) 命题分类命题分类 简单命题（也称原子命题）：再分解为更简单的简单命题（也称原子命题）：再分解为更简单的 命题。命题。 复合命题：若干简单命题通过复合命题：若干简单命题通过联结词联结词(connectives) (connectives)
6、 而构成的新命题。而构成的新命题。 这些联结词有明确的含义，注意与自然语言对应词的联系与区别这些联结词有明确的含义，注意与自然语言对应词的联系与区别! ! 设设p是一个命题，是一个命题， p称为称为p的否定式。的否定式。 p是真的当且仅当是真的当且仅当p是假的。是假的。 例、例、 p： 上海是一个大城市。上海是一个大城市。 否定词符号否定词符号 p：上海不是一个大城市。：上海不是一个大城市。 p p 1 0 0 1 合取词符号合取词符号 设设p，q是两个命题，命题是两个命题，命题 “p并且并且q”称为称为p，q的合取，的合取， 记以记以p q，读作，读作p且且q。 例、例、 p：2 2=5，
7、q：雪是黑的：雪是黑的 p q是真的当且仅当是真的当且仅当p和和q都是真的。都是真的。 p q：2 2=5并且雪是黑的并且雪是黑的 p q p q 1 1 1 0 0 1 0 0 1 0 0 0 析取词符号析取词符号 设设p，q是两个命题，命题是两个命题，命题 “p或者或者q”称为称为p，q的析取，的析取， 记以记以p q，读作，读作p或或q。 例如，例如，p：今天下雨，：今天下雨，q：今天刮风：今天刮风 p q是真的当且仅当是真的当且仅当p，q中至少有一个是真的。中至少有一个是真的。 p q：今天下雨或者刮风。：今天下雨或者刮风。 p q p q 1 1 1 0 0 1 0 0 1 1 1
8、0 自然语言中的“或者”一词有不可兼的意思。自然语言中的“或者”一词有不可兼的意思。 例、他是跳远冠军或是百米冠军。例、他是跳远冠军或是百米冠军。 “ ”所表示的“或”是“可兼或”所表示的“或”是“可兼或” 按照联结词“按照联结词“ ”的定义，当”的定义，当p，q都为真时，都为真时，p q也为真。也为真。 因此，对于“不可兼或”，我们不可以用因此，对于“不可兼或”，我们不可以用 来表示。来表示。 表示的是二者只能居其一，不会同时成立。表示的是二者只能居其一，不会同时成立。 我今天到北京出差或者到广州去度假我今天到北京出差或者到广州去度假 命题命题 p q 1 1 1 0 0 1 0 0 0 1
9、 1 0 p：我今天到北京出差，：我今天到北京出差， q：我到广州去度假：我到广州去度假 蕴含词符号蕴含词符号 设设p，q是两个命题，命题是两个命题，命题 “如果“如果p，则，则q”称为称为p蕴含蕴含q， 记以记以pq。 例、例、 p：f(x)是可微的，是可微的， q：f(x)是连续的是连续的 pq是假的当且仅当是假的当且仅当p是真的而是真的而q是假的。是假的。 pq： 若若f(x)是可微的，则是可微的，则f(x)是连续的。是连续的。 “善意的推定”：善意的推定”： 如果如果p是假命题，则不管是假命题，则不管q是什么命题，命题是什么命题，命题 “如果“如果 p，则，则q”(p q)在命题逻辑中
10、都被认为是真命题。在命题逻辑中都被认为是真命题。 例、例、p： 2 2=5，q： 雪是黑的，雪是黑的， 命题命题 “如果“如果2 2=5，则雪是黑的”是真命题。，则雪是黑的”是真命题。 p q p q 1 1 1 0 0 1 0 0 1 0 1 1 等价词符号等价词符号 设设p，q是两个命题，命题是两个命题，命题 “p当且仅当当且仅当q”称为称为p等价等价q， 记以记以pq。 例、例、 p ： a2+b2=a2， q： b=0 pq是真的当且仅当是真的当且仅当p，q或者都是真的，或者都是假或者都是真的，或者都是假 的。的。 pq： a2+b2=a2当且仅当当且仅当b=0 p q p q 1 1
11、 1 0 0 1 0 0 1 0 0 1 命题语言的语法命题语言的语法 命题语言的命题语言的 基本符号基本符号 命题变元符号：命题变元符号： p、q、r 命题常元符号：命题常元符号： ， 连接词符号：连接词符号： 辅助符号：辅助符号： ） ， （ 合式公式合式公式(Well-Formed Formulas): 递归定义如下：递归定义如下： (1) 命题常元和变元符号命题常元和变元符号是合式公式；是合式公式； (2) 若若A是合式公式，则是合式公式，则( A)是合式公式，称为是合式公式，称为A的否定式；的否定式； (3) 若若A，B是合式公式，则是合式公式，则 (A B)， (A B)， (AB
12、)， (AB)是合式公式；是合式公式； (4) 所有合式公式都是有限次使用所有合式公式都是有限次使用(1)，(2)，(3)、(4)得到的得到的 符号串。符号串。 子公式子公式 (subformulas): 如果是合式公式如果是合式公式A的一部分，且的一部分，且 本身也是一个合式公式，则称为公式本身也是一个合式公式，则称为公式A的子公式的子公式。 公式举例：公式举例： 例例、如下符号串不是公式：、如下符号串不是公式： 例例、 约定约定：（：（1 1）最外层的括号可以省略；）最外层的括号可以省略； （2 2）联结词运算的优先次序（由高到底）为：）联结词运算的优先次序（由高到底）为： ， 目的为减少
13、括号的数量。目的为减少括号的数量。 (AB)不是合式公式，是一个公式模式，代表不是合式公式，是一个公式模式，代表 一类具体的公式一类具体的公式 2 2、 公式的真值公式的真值 概念概念 赋值赋值，公式求值函数，真值表，等，公式求值函数，真值表，等值值式，重言式，式，重言式， 矛盾式，蕴含式矛盾式，蕴含式 赋值赋值（指派，解释）（指派，解释）： 设设 是命题变元集合，则称函数是命题变元集合，则称函数 v： 1，0是一个真值赋值。是一个真值赋值。 1、若、若A为命题变元符号为命题变元符号p，则，则v(A)= v(p); A A Av 若 0 若 1 )( 2、若、若A为命题常元，则为命题常元，则
14、A是一个公式，是一个公式，v是一个赋值，则是一个赋值，则A在赋值在赋值v下的值，记为下的值，记为 v(A),有：有： lse 0 1)(或1)(若 1 )( e CvBv Av 4、若、若A为析取式为析取式(B C) ，则，则 5、若、若A为析取式为析取式(B C) ，则，则 lse 0 1)(且1)(若 1 )( e CvBv Av 1)(若 0 0)(若 1 )( Bv Bv Av 3、若、若A为否定式为否定式( B) ，则，则 7、若、若A为等价式为等价式(B C) ，则，则 lse 0 )()(若 1 )( e CvBv Av 6、若、若A为蕴含式为蕴含式(BC) ，则，则 lse 1
15、 0)(且1)(若 0 )( e CvBv Av 成真赋值：当成真赋值：当v(A)=1时，称时，称v满足满足A，记为，记为v A 成假赋值：当成假赋值：当v(A)=0时，称时，称v不满足不满足A，记为，记为v A 若公式若公式A中有中有n个不同变元个不同变元p1,p2,.,pn，那么，那么A共有共有2n 种不同的赋值。种不同的赋值。 真值表：公式真值表：公式A在其所有可能的赋值下所取真值的表，称为在其所有可能的赋值下所取真值的表，称为 A的真值表。的真值表。 例、例、A=p q v(p)=1,v(q)=0, v(A)=1 v(p)=0,v(q)=0, v(A)=0 例例、 公式公式 (p q)
16、r (p q)r p q r 1 1 1 1 1 0 1 0 1 0 1 0 0 1 0 0 0 1 0 0 1 1 0 0 1 0 1 1 1 1 1 1 可满足的可满足的：公式公式A，若，若 赋值赋值v，使得，使得v A，则，则称称 A是可满足的。是可满足的。 不可满足的不可满足的：若若 赋值赋值v，使得，使得v A，则，则称称A是不可是不可 满足的。满足的。 例、例、 (p q)r 可满足的可满足的 (p p) 不可满足的不可满足的 v满足满足U：公式集：公式集U，若，若 赋值赋值v，使得对，使得对 公式公式A U， 有有 v A，则，则称称v为为U的成真赋值。的成真赋值。 否则，否则，
17、U是不可满足的。是不可满足的。 扩充到公式集扩充到公式集U 例、例、 重言式、矛盾式重言式、矛盾式 重言式（永真式）重言式（永真式） 任意赋值任意赋值v， 有有v A 矛盾式（永假式）矛盾式（永假式）任意赋值任意赋值v， 有有v A 例、例、(p p) (p p) A是永真的当且仅当是永真的当且仅当 A是永假的。是永假的。 若若A是永真的，则是永真的，则A是可满足的；反之不对。是可满足的；反之不对。 设设A是公式，则是公式，则A是矛盾式当且仅当是矛盾式当且仅当A是不可满足的。是不可满足的。 证明：证明： A是矛盾式是矛盾式 赋值赋值v， 有有v A 赋值赋值v， 有有v(A)=0 不存在赋值不
18、存在赋值v，使得，使得v(A)=1 A是不可满足的是不可满足的 等值式：等值式：若等价式若等价式AB是重言式，则称是重言式，则称A与与B等值，记作等值，记作 AB。 注意：注意： 与与是两个完全不同的是两个完全不同的 符号符号 用真值表可检查两个公式是否等值用真值表可检查两个公式是否等值 基本等值式（见课本基本等值式（见课本pp.17-18） 35 置换规则（置换定理）置换规则（置换定理） 设是公式设是公式A的子公式的子公式, Y。将。将A中的中的（可以是全部或（可以是全部或 部分部分X）用用Y来置换，所得到的公式来置换，所得到的公式B，则，则 AB。 判断下列各组公式是否等值判断下列各组公式
19、是否等值: (1) p(qr) 与与 (p q) r 36 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 (p q)r p(qr) qr p q r p q 0 0 0 0 0 0 1 1 结论结论: : p(qr) (p q) r 等值式例题等值式例题 (2) p(qr) 与与 (pq) r 37 0 1 0 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 0 0 0 0 0 1 0 1 0 0 1 1 1 0
20、0 1 0 1 1 1 0 1 1 1 (pq)r p(qr) qr p q r pq 1 1 1 1 0 0 1 1 结论结论: : p(qr) 与与 (pq) r 不等值不等值 基本等值式基本等值式 双重否定律双重否定律 AA 幂等律幂等律 A AA, A AA 交换律交换律 A BB A, A BB A 结合律结合律 (A B) CA (B C), (A B) CA (B C) 分配律分配律 A (B C)(A B) (A C), A (B C)(A B) (A C) 德摩根律德摩根律 (A B)AB (A B)AB 吸收律吸收律 A (A B)A, A (A B)A 38 基本等值式基
21、本等值式 零律零律 A , A 同一律同一律 A A. A A 排中律排中律 AA 矛盾律矛盾律 AA 蕴涵等值式蕴涵等值式 ABA B 等价等值式等价等值式 AB(AB) (BA) 假言易位假言易位 ABBA 等价否定等值式等价否定等值式 ABAB 归谬论归谬论 (AB) (AB) A 特别提示：必须牢记这特别提示：必须牢记这16组等值式，这是继续学习的基础组等值式，这是继续学习的基础 39 等值演算等值演算由已知的等值式推演出新的等值式的过程。由已知的等值式推演出新的等值式的过程。 证明两个公式等值证明两个公式等值 例例2 证明证明 p(qr) (p q)r 证证 p(qr) p ( q
22、r) （蕴涵等值式，置换规则）（蕴涵等值式，置换规则） ( pq) r （结合律，置换规则）（结合律，置换规则） (p q) r （德摩根律，置换规则）（德摩根律，置换规则） (p q)r （蕴涵等值式，置换规则）（蕴涵等值式，置换规则） 40 3 3、范式、范式 概念概念： 文字，析取范式，文字，析取范式，极极小项，主析取范式，合取范式，小项，主析取范式，合取范式， 极大项极大项，主合取范式，主合取范式 文字文字 设设A（命题变元集）（命题变元集）, 则则A和和 A都称为命题符号都称为命题符号A 的文字，其中前者称为的文字，其中前者称为正文字正文字，后者称为，后者称为负文字负文字。 析取范式
23、析取范式 形形如如 A1 A2 An (n 1) 的的公式称为析取范式公式称为析取范式，其中，其中Ai(i=1,n)是由文字组成的合是由文字组成的合 取范式。取范式。 例例：求：求 (P Q) (P Q)的析取范式的析取范式。 42 极极小项小项 文字文字的合取式的合取式称为称为极极小项小项，其中公式中每个命题符号，其中公式中每个命题符号的的 文字文字都在该合取式中出现一次。都在该合取式中出现一次。 注：注：(1) n个命题符号共有个命题符号共有2n个个极极小项小项。 (2)极极小项小项的编码与性质（的编码与性质（p.25）。）。 主主析取范式析取范式 给定给定的命题公式的主析取范式是一个与之
24、等价的的命题公式的主析取范式是一个与之等价的公式，后者公式，后者 由由极极小项的小项的析取组成。析取组成。 例例：求求公式公式(P Q) R的主的主析取范式析取范式 定理：公式的真值表中真值定理：公式的真值表中真值为为1的的指派所对应指派所对应的的极极小项小项的析取，的析取， 即为此公式的主析取范式。即为此公式的主析取范式。 例：求例：求P Q的主析取范式的主析取范式 43 合取范式合取范式 形为形为 A1 A2 An (n 1) 的公式称为合取范式，其中的公式称为合取范式，其中A1,An都是由文字组成的析取式。都是由文字组成的析取式。 例：求例：求(P (Q R) S的合取范式的合取范式 4
25、4 极大项极大项 文字的析取式称为文字的析取式称为极大项极大项，其中公式中每个命题符号的，其中公式中每个命题符号的 文字都在该合取式中出现一次。文字都在该合取式中出现一次。 注注：（：（1）n个命题符号共有个命题符号共有2n个个极大项极大项。 （2）极大项极大项的编码等性质（的编码等性质（p.25）。）。 主合取范式主合取范式 给定的命题公式的主合取范式是一个与之等价的公给定的命题公式的主合取范式是一个与之等价的公 式，后者由式，后者由极大项极大项的合取组成。的合取组成。 定理：公式的真值表中真值为定理：公式的真值表中真值为F的指派所对应的的指派所对应的极大项极大项的合取，的合取， 即为此公式
26、的主合取范式。即为此公式的主合取范式。 例：求例：求(P Q) ( P R)的主析取范式与主合取范式。的主析取范式与主合取范式。 45 4 4、联结词的完备集、联结词的完备集 概念概念： 真值函数，真值函数，异或，条件否定，与非，或非，联结词完备集异或，条件否定，与非，或非，联结词完备集 47 真值函数：真值函数： 称称F:0,1n 0,1 为为n元真值函数元真值函数. 0,1n=000, 001, , 111，包含，包含 个长为个长为n的的0,1符号串符号串. 共有共有 个个n元真值函数元真值函数. n 2 2 n 2 2 1元真值函数元真值函数 p 0 0 0 1 1 1 0 1 0 1
27、)1( 3 )1( 2 )1( 1 )1( 0 FFFF 48 p q 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 p q 0 0 0 1 1 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 )2( 7 )2( 6 )2( 5 )2( 4 )2( 3 )2( 2 )2( 1 )2( 0 FFFFFFFF )2( 15 )2( 14 )2( 13 )2( 12 )2( 11 )2( 10 )
28、2( 9 )2( 8 FFFFFFFF 2元真值函数元真值函数 异或异或 P Q (P Q) 条件否定条件否定 PQ (P Q) 与非与非 P Q (P Q) 或非或非 P Q (P Q) 注：能构造多少联结词呢？注：能构造多少联结词呢？ 11个个（二元以内）（二元以内） 49 c 联结词的完备集联结词的完备集(Adequate Set of Connectives) 设设C是联结词的集合，若对于任意一个合式公式均存在一是联结词的集合，若对于任意一个合式公式均存在一 个与之等价的公式，而后者只含有个与之等价的公式，而后者只含有C中的联结词，则称中的联结词，则称C是是 联结联结词词的完备的完备集
29、。集。 例如例如： （1） ， ， ， ， ， 是联结词是联结词 的的完备集完备集。 （2） ， ， ， ， ，是联结词是联结词 的完备集的完备集。 （3） 是是联结词的完备集联结词的完备集。 （4） ， ， ， , 不是联结词的完备集。不是联结词的完备集。 50 5 5、推理理论、推理理论 概念概念： 重言蕴含式，重言蕴含式，有效结论，有效结论，P P规则，规则，T T规则，规则，CPCP规则规则，推理，推理 重言重言蕴含蕴含式式 当且仅当当且仅当PQ是一个重言式时，称是一个重言式时，称P重言重言蕴含蕴含Q， 记为记为PQ。 注意注意: (1) 和和 含义的本质区别含义的本质区别。 (2)
30、重言重言蕴含蕴含式式也称为逻辑也称为逻辑蕴含式蕴含式。 证明证明P Q的方法：任的方法：任给给赋值赋值v (1) 假设假设v(P)=1, 推出推出v(Q)=1，或者，或者 (2) 假设假设v(Q)=0, 推出推出v(P)=0。 例：求证：例：求证： Q (P Q) P 常见的重言蕴含式常见的重言蕴含式(P.46) 52 推理定律推理定律重言蕴涵式重言蕴涵式 1. A (A B) 附加律附加律 2. (A B) A 化简律化简律 3. (AB) A B 假言推理假言推理 4. (AB)B A 拒取式拒取式 5. (A B)B A 析取三段论析取三段论 6. (AB) (BC) (AC) 假言三段
31、论假言三段论 7. (AB) (BC) (AC) 等价三段论等价三段论 8. (AB) (CD) (A C) (B D) 构造性二难构造性二难 (AB) ( AB) B 构造性二难构造性二难(特殊形式特殊形式) 9. (AB) (CD) ( BD) ( AC) 破坏性二难破坏性二难 每个等值式可产生两个推理定律每个等值式可产生两个推理定律 如如, 由由AA可产生可产生 AA 和和 AA 53 有效结论有效结论 设设A、C是两个命题公式，若是两个命题公式，若A C，称，称C是是A的有效结论。的有效结论。 推广推广:若若H1 Hn C, 称称C是一组前题是一组前题H1,Hn的有效结论。的有效结论。
32、 注：注：(1) 从理论上说，可利用真值表来判断某公式是否为一组公从理论上说，可利用真值表来判断某公式是否为一组公 式的有效结论，但有“组合爆炸”问题。式的有效结论，但有“组合爆炸”问题。 (2) 利用少量公理、若干推理规则推理出有效结论。利用少量公理、若干推理规则推理出有效结论。 54 形式系统形式系统: 一个一个形式系统形式系统 I 由下面四个部分组成：由下面四个部分组成： (1) 非空的字母表，记作非空的字母表，记作 A(I). (2) A(I) 中符号构造的合式公式集，记作中符号构造的合式公式集，记作 E(I). (3) E(I) 中一些特殊的公式组成的公理集，记作中一些特殊的公式组成
33、的公理集，记作 AX(I). (4) 推理规则集，记作推理规则集，记作 R(I). 记记 I=, 其中其中是是 I 的的 形式语言系统形式语言系统, 是是 I 的的形式演算系统形式演算系统. 自然推理系统自然推理系统: 无公理无公理, 即即AX(I)= 公理推理系统公理推理系统 (Hilbert): 推出的结论是系统中的重言式推出的结论是系统中的重言式, 称作称作 定理定理 55 P规则规则 在推导过程中在推导过程中,可以随时添加前提。可以随时添加前提。 T规则规则 在推导过程中在推导过程中,可以引入公式可以引入公式S，它是由其前题的一个或，它是由其前题的一个或 多个公式借助重言、蕴含而得到的
34、。多个公式借助重言、蕴含而得到的。 推理（证明）推理（证明） 从前提从前提A1, A2, Ak到结论到结论B的推理是一个公式序列的推理是一个公式序列C1, C2, Cl. 其中其中Ci(1 i l)是某个是某个Aj, 或者可由序列中前面的公式应用推理或者可由序列中前面的公式应用推理 规则得到规则得到, 并且并且Cl =B。 例：（例：（1）P Q，P R，Q S|- S R （2）(W R)V，V(C S),SU, CU|- W 56 归谬法归谬法（反证法）（反证法） 例：（例：（3）AB， (B C)|- A (4) P Q，P R，Q S|- S R CP规则规则(演绎定理演绎定理) 若若
35、 R|- S，则，则 |- RS, 其中其中 为命题公式的集合。为命题公式的集合。 例：（例：（5） A(BC), D A, B|- DC 57 命题逻辑总结命题逻辑总结 1.1. 命题公式：命题公式：命题，命题， 联结词联结词( ( ， ， ，) )， 合式公式，子公式合式公式，子公式 2.2. 公式的真值：公式的真值：赋值赋值，求值函数，真值表，等，求值函数，真值表，等值值式式， 重言式，矛盾式重言式，矛盾式 3.3. 范式：范式：析取范式，析取范式，极极小项，主析取范式，合取范式，小项，主析取范式，合取范式， 极大项极大项，主合取范式，主合取范式 4.4. 联结词的完备集：联结词的完备集：真值函数，真值函数，异或，条件否定，与非，异或，条件否定，与非， 或非，联结词完备集或非，联结词完备集 5.5. 推理理论：推理理论：重言蕴含式，重言蕴含式，有效结论，有效结论，P P规则，规则，T T规则，规则， CPCP规则规则，推理，推理 58
