1、Discrete Mathematics 西南科技大学 计算机科学与技术学院第一章 命题逻辑 1.2 命题公式与分类Discrete Mathematics 西南科技大学 计算机科学与技术学院1.命题常元与命题变元 命题常元： 表示一个具体的简单命题的符号。命题常元的真值是确定不变的，不是为 1，就是为 0。 命题变元： 没有赋予具体内容的原子命题。该命题变量无具体的真值，它的只域是集合 T， F(或0， 1)。 命题公式 是由命题常元、命题变元、联结词、括号等组成的符号串，但并不是由这些符号任意组成的符号串都是命题公式。Discrete Mathematics 西南科技大学 计算机科学与技术
2、学院2.命题公式的定义由以下形成规则生成的公式叫 命题公式 (简称 公式 )：(1) 命题变元和命题常元是命题公式。(2) 如果 A、 B是命题公式 , 则 (A) , (A B) , (A B) , (A B) , (A B)是合式公式。(3) 只有有限次地使用 (1)和 (2)所得到的符号串才是命题公式。 Discrete Mathematics 西南科技大学 计算机科学与技术学院例如：以下字符串就 不是命题公式 , 因为它们不符合形成规则： Q， (P Q， P Q， (PQ) R) u 为了减少圆括号的使用 , 以后书写命题公式时，可按 约定 省略公式中的部分圆括号。Discrete
3、Mathematics 西南科技大学 计算机科学与技术学院例 用定义说明 (P(P Q)是命题公式。解： (i) P是命题公式 根据 (1)(ii) Q是命题公式 根据 (1)(iii) (P Q)是命题公式 根据 (i)(ii)和 (2) (iv) (P(P Q)是命题公式 根据 (i)(iii)和 (2) Discrete Mathematics 西南科技大学 计算机科学与技术学院3.公式的赋值或解释（ 指派 ）如果 一个命题公式含有命题变元，则它的真值是不确定的。只有对它的每个命题变元用指定的真值后，命题公式才变成命题，其真值才能唯一确定。 定义 设 A为一个命题公式， P1,P2, P
4、n 为出现该公式中的所有的命题变元。分别给 P1,P2, Pn 指定一个真值，则称为对 A的一个 赋值 或 解释 。若指定的一组值使 A的值为真，则称这组值为 A的 成真赋值，若使 A的值为假，则称这组值为 A的 成假赋值 。Discrete Mathematics 西南科技大学 计算机科学与技术学院例 设命题 公式 A=p qr则110（ p=1,q=1,r=0）为 A的成假赋值。111(p=1,q=1,r=1) 是 A的成真赋值。 011是 A的成真赋值010是 A的成真赋值。Discrete Mathematics 西南科技大学 计算机科学与技术学院4.公式的真值表含 n个命题变元的命题
5、公式，共有 2n组赋值。将命题公式在所有赋值下取值的情况列成表，称为命题公式的 真值表 。 构造真值表的具体步骤如下：(1)找出命题公式中所含的所有命题变元 p1,p2, pn (若无下角标就按字典顺序给出 )，列出所有可能的赋值 (2n个 )； 按二进制加法进行 。(2)按从低到高的顺序对命题公式进行分解；(3)对应每个赋值，计算各列的值，直到最后计算出命题公式的值。Discrete Mathematics 西南科技大学 计算机科学与技术学院例 (a) 构造命题公式 (P Q) P)和 (P Q) P) 的真值表。 解：该公式的真值表如下：Discrete Mathematics 西南科技大学 计算机科学与技术学院(b) 构造公式 PQ 与 P Q P Q 的真值表 。 u两个命题公式， 如果有相同的真值，则称它们是逻辑等价命题 。u以上两个命题因后两列的真假值完全一致， 所以它们是 逻辑等价命题 。 解： PQ 的真值表如下：
