东南大学计算机科学与工程学院周德宇dzhou@seueducn

东南大学计算机科学与工程学院周德宇dzhou@seueducn内容摘要：

p q p pq pq pq pq F F T F F T T F T T F T T F T F F F T F F T T F T T T T 27 命题与 联接词 联接词的优先级 、 、 、 、  括号最优先 同一优先级：从左到右 例子：求于命题 pqr含义相同的命题 ((p)q)r ((pq))r p(qr) (pqr) 28 命题与 联接词 例： p：北京比天津人口多 q： 2＋ 2＝ 4 r：乌鸦是白色的 求下列命题真值 ((172。 p ∧ q) ∨ (p ∧ 172。 q) ) →r (q∨ r) →(p→172。 r) (172。 p∨ r)  (p∧ 172。 r) T T F 29 命题与 联接词 例子：符号化下面命题 小强虽然不聪明，但很用功 小李学过英语或者法语 小李正在教室看书或在图书馆上网 金无足赤，人无完人 得道多助，失道寡助 pq pq (pq) (pq) pq (pq)(pq) 30 命题与 联接词 问题 1：区别 x+y4 明天下雨 31 命题与 联接词 问题 2： 得道多助，失道寡助 (pq)(pq) 32 命题与 联接词 课堂练习： p： 2+3=5 q：大熊猫产在中国 r：太阳从西部升起 求下列命题真值 (r(pq))(pr) F F F T T T F F 33 命题公式 及其赋值 命题常项：简单命题 命题变项：表示命题的变量 真值可以变化的陈述句 命题变项不是命题 命题变项用确定命题代入才能确定真值 命题所用符号：常用小写２６个英文字母 命题变量不同于代数式的变量 x+y4的 x， y不是命题变量 34 蕴含的几种表述 如果 p, 则 q P仅当 q 只有 q才 p 除非 q才 p 除非 q否则非 p qp 35 命题公式 及其赋值  合式公式（命题公式）的递归定义： 1. 单个命题常项或命题变项是合式公式（原子命题公式） 2. A为合式公式，则 A是合式公式 3. A， B为合式公式 ,则（ AB），（ AB）， AB）， （ AB）为合式公式 4. 有限次应用 13形成的字符串为合式公式  思考一下递归定义的好处  子公式 B：给定合式公式 A  B是 A的一部分  B是合式公式 36 命题公式 及其赋值  符号说明  大写字母 A， B表示合式公式  公式简写法则：  公式最外层括号可以省略  （  A）的括号可以省略  根据运算符优先级省略括号 省略括号不能影响公式解释 37 命题公式 及其赋值  合式公式的树状展开 (AB)((C)(DC)) AB A B (C)(DC) (C) DC C D C 38 命题公式 及其赋值  例子  (AB)C  (pq)(qr)  (B)  pqr 39 命题公式 及其赋值  公式层次  若公式 A是单个的命题变元，则称 A为 0层合式  称公式 Ａ 是 n+1(n≥0)层公式是指下面情况之一 a) A＝ 172。 B， B是 n层公式 b) A＝ BΛC，其中 B， C分别为 i层和 j层公式，且 n＝max(i,j) c) A＝ B ∨ C ，其中 B， C的层次及 n同 (b) d) A＝ B  C ，其中 B， C的层次及 n同 (b) e) A＝ B ↔ C ，其中 B， C的层次及 n同 (b)  若公式 Ａ 的层次为 k，则称 A是 k层公式  层次 ≠联接词数 40 命题公式 及其赋值  例子： p,q,r,s为命题变元  ((pq)r)s  (pq)(qr)  (pqr)s (pqr) 4 3 5 41 命题公式及其 赋值  命题公式的真值  命题变项的常量化：常项替换（解释）  例子：公式 pqr  真值为 T的解释 • p:3是奇数； q:7是奇。