§3命题形式和真值表 ?上节介绍了将命题表示为符号串。 ?是否每个符号串都是命题呢？ p q → ?什么样的符号串才能表示命题呢？ 如下命题形式定义的符号串表示的 才是命题。 命题形式的定义 定义6命题形式是由命题变元和联结词按以下规 则组成的符号串: (1) 任何命题变元都是命题形式---此时称为原子 命题形式; (2) 如果α是命题形式, 则(?α)也是命题形式; (3) 如果α、β是命题形式, 则(α∨β)、(α∧β)、 (α→β)和(α?β)都是命题形式; (4) 只有有限次地应用(1)—(3)构成的符号串才是 命题形式. 下列符号串都是命题形式： (?p) (p∧(?q)) (p ∨(?p)) (p ?(?p)) (p ∧(?p)) ((p ∧ p) →(?(p ∨r))) 下列符号串是否为命题形式？ （1）pq → （2）(p?q) （3）(p∧(?q)) （4）p∧(?q) （5）((?q)) （6）?p 一些注记 1.定义6是归纳定义，而不是循环定义。 (1)是奠基，(2)、(3)是归纳步骤。 2.如果在(2)和(3)中将括号去掉，结果如何？ p→q→r 与P→q→r、P→q→r 3.如仅去掉(2)和(3)中某类公式的括号呢？例如， 仅去掉(2)中括号。 (p∧?q) —— ?的优先级高于其它的。 4.如果规定省略命题形式最外层括号，与2的差别。 约定 ? ?的优先级高于其它的 ?省略命题形式最外层括号 命题形式的简单性质 ?任一个命题形式必为下列形式之一： 命题变元、(?α)、(α∨β)、(α∧β)、 (α→β)或(α?β) ?命题形式的BNF (Bacus Normal Form): α ::= p | (?α) | (α∨β) | (α∧β) | (α→β)| (α?β) ?每个命题形式都是有限符号串。 指派 ?命题形式的真假由它中命题变元的值完全确定。 ? 定义7设α为一个命题形式, α中出现的所有命题 变元都在p 1， p 2 ，…，p n 中, 对序列p 1， p 2 ，…，p n 指定的的任一真假值序列t 1 ，t 2 ，…，t n 称为α的关 于p 1， p 2 ，…，p n 的一个指派(asignment)，其中t i = 0或1, i ∈ N N, 1 ≤ i ≤ n. 即指派是从{p 1， p 2 ，…，p n }到{0，1}的一个函数。 成真指派 ?若p 1， p 2 ，…，p n 的一个指派使α为真，则称此 指派为α的一个成真指派 ?若p 1， p 2 ，…，p n 的一个指派使α为假，则称此 指派为α的一个成假指派。 ?由定义可知： ? ?p关于p的成真指派为0, 成假指派为1. ? p ∧ q关于p、q的成真派为<1, 1>, 成假指派为 <1,0>, <0,1>, <0, 0>. ? p ∨ q关于p、q的成真指派为<1,1>, <0,1>, <1,0>, 成假指派为<0,0>. ?不难给出p→ q、p ? q的成真和成假指派. (§2.1). 例5 求(p∧q) → (?(q∨r))的成真和成假指派。 解：令(p∧q) → (?(q∨r))为α。 要使α为假，必须p∧q为真且?(q∨r)为假。 从而p∧q必须为真，且q∨r也必须为真。 故α的成假指派为(1，1，1)和(1，1，0). α的成真指派为(0，0，0)、(1，0，0)、(0，1，0)、 (0，0，1)、(0，1，1)、(1，0，1)。 定义8命题形式在所有可能的指派下所取值列成的 表称为真值表. (p∧q) → (?(q∨r))的真值表 1 1 1 0 1 0 0 0 r 1 1 0 1 0 1 0 0 q 0011 1000 1001 0011 1000 1000 1101 1100 α?(q∨r)(p∧q)P p ∧ (? p)、p ∨ (? p)的真值表 解： 101 100 p ∨ (? p)p ∧ (? p)P (? p) ∨q、p→q的真值表 解： 1111 0001 1110 1100 p→q(? p) ∨qqp p→(q→r)、(p→q)→r的真值表 1 1 1 0 1 1 1 1 p→(q→r) 1111 1101 1100 1001 1110 0011 0010 0000 (p→q)→rrqp 命题形式的类型 定义9 ?命题形式α称为重言式(或永真式)，如果α关于 其中出现的命题变元的所有指派均为成真指派. ?命题形式α称为矛盾式(永假式)，如果α对于其 中出现的命题变元的所有指派均为成假指派. ?一个命题形式α称为可满足式, 如果α对于其中 出现的命题变元的某个指派为成真指派. 例如：p ∧ (? p)为矛盾式，p ∨ (? p)为重言式。 (? p) ∨q为可满足式。 例7 证明下列各式都是重言式 (1) p→(q→(p ∧ q)) 证明： 11111 10010 11001 11000 p→(q→(p ∧ q))q→(p ∧ q) p ∧ qqp 例7(续） (2) ((p?p 1 )∧(q?q 1 ))→((p∧q)?(p 1 ∧q 1 )) 11111 10011 11100 10000 101** 110** 1**01 1**10 αq 1 qp 1 p 与哑元的无关性 定理1设命题形式α中出现的命题变元都在 p 1 , p 2 , … ,p n 中, p n+1 , … , p n+m 是另外m个不在α中 出现的命题变元. 对于p 1 , p 2 , … , p n , p n+1 , … ,p n+m 的任意两个指派: <u 1 , u 2 , … , u n , u n+1 , … , u n+m >和 <v 1 , v 2 , … , v n , v n+1 , … , v n+m >， 其中：u i , v i = 0或1 (1 ≤ i, j ≤ n+m). 若u 1 = v 1 , … , u n =v n , 则α在这两个指派下的值相同. 作业 ? p508 (P100) 2（1）、（4） 3（2）、（3）、（6）、（8）、（9） That’s All of Today Thanks for Listening