§3命题形式和真值表.pdfVIP

§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 p ，…，p 中, 对序列p p ，…，p 1， 2 n 1， 2 n 指定的的任一真假值序列t ，t ，…，t 称为α的关 1 2 n 于p p ，…，p 的一个指派(asignment)，其中t 1， 2 n i = 0或1, i ∈N, 1 ≤ i ≤ n. N 即指派是从{p p ，…，p }到{0，1}的一个函数。 1， 2 n 成真指派 若p p ，…，p 的一个指派使α为真，则称此 1， 2 n 指派为α的一个成真指派 若p p ，…，p 的一个指派使α为假，则称此 1， 2 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))的成真和成假指派。 解：令(