天津理工大学：《离散数学》课程教学资源（PPT课件）第一章 命题逻辑 Propositional Logic 1.3 命题公式及分类

第一章命题逻辑（PropositionalLogic)1.2命题公式及分类1命题公式、命题合式公式是由命题常项、命题变项、联结词和圆括号按一定的逻辑关系联结起来的符号串。我们以如下递归的形式来定义合式公式命题常项：简单命题命题变项：真值不确定的陈述句2026/3/15计算机科学与工程系 1

2026/3/15 计算机科学与工程系 1 第一章 命题逻辑（Propositional Logic） 1.2命题公式及分类 1 命题公式 ✓ 命题合式公式是由命题常项、命题变项、联结 词和圆括号按一定的逻辑关系联结起来的符号 串。我们以如下递归的形式来定义合式公式： 命题常项：简单命题 命题变项：真值不确定的陈述句

第一章命题逻辑（PropositionalLogic）定义1.6：（1)单个命题常项或变项是合式公式(2）若A是合式公式，则IA)也是合式公式。(3）若A，B是合式公式，则(A^B)，(AVB),(A→B)，(AB)也是合式公式。（4）当且仅当有限次地应用(1)~(3)所得到的包含命题常项、命题变项、联结词和括号的符号串是合式公式。注：(1)合式公式也称为命题公式，并简称为公式(2)命题公式一般不是命题,仅当公式中的命题变元用确定的命题代入时,才得到一个命题.其真值依赖于代换变元的那些命题的真值2026/3/15计算机科学与工程系2

2026/3/15 计算机科学与工程系 2 第一章 命题逻辑（Propositional Logic） ✓ 定义1.6：(1)单个命题常项或变项是合式公式。 （2）若A是合式公式，则( A)也是合式公式。 （3）若A，B是合式公式，则(A∧B)，(A∨B)， (A→B)，(AB)也是合式公式。 （4）当且仅当有限次地应用(1)~(3)所得到的包含命 题常项、命题变项、联结词和括号的符号串是合式 公式。 注: (1)合式公式也称为命题公式，并简称为公式。 (2)命题公式一般不是命题,仅当公式中的命题变元 用确定的命题代入时,才得到一个命题.其真值依赖 于代换变元的那些命题的真值

第一章命题逻辑（PropositionalLogic）例l：指出（p→（pvq))是否是命题公式(wff)，如果是，则具体说明。由(1)解：① p是wff由(1)q是wff由(3)pvq是wff12（(p→(pvq))由(3) ①③4例2：(p→q),(r ^s)1q,p，(p)等均为合式公式，而pqva，(p→w)^q)等不是合式公式2026/3/15计算机科学与工程系3

2026/3/15 计算机科学与工程系 3 第一章 命题逻辑（Propositional Logic） 例1：指出(p→(pq))是否是命题公式(wff)， 如果是，则具体说明。 解： ① p是wff 由(1) ② q是wff 由(1) ③ pq是wff 由(3) ①② ④ (p→(pq)) 由(3) ①③ 例2: (p → q) , (r ∧ s) ∨  q , p，( p)等均为合式 公式，而pq ∨a , (p → w) ∧ q)等不是合式公式

合式公式的层次定义(1)若公式A是单个的命题（常项或变项），则称A为0层公式。(2)称A是n+1(n≥0)层公式是指下面情况之一:(a) A=一B,B是n层公式;(b)A=B^C,其中B,C分别为层和层公式，且n=max(i, j);(c) A=BvC,其中B,C的层次及n同(b);(d) A=B→C,其中B,C的层次及n同(b);(e) A=BC,其中B,C的层次及n同(b),2026/3/15计算机科学与工程系4

2026/3/15 计算机科学与工程系 4 合式公式的层次 定义 (1) 若公式A是单个的命题（常项或变项）,则称A为0 层公式. (2) 称A是n+1(n≥0)层公式是指下面情况之一： (a) A=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)

合式公式的层次（续）公式例如0层p1层-p2层p-3层-(p-→)r白4层((-pa) r)(-vs)2026/3/15计算机科学与工程系5

2026/3/15 计算机科学与工程系 5 合式公式的层次 (续) 例如 公式 p 0层 p 1层 p→q 2层 (p→q)r 3层 ((pq) →r)(rs) 4层