第2讲命题公式与赋值

2023/2/1命题逻辑1第1章命题逻辑命题演算或命题逻辑（Propositionalcalculusorpropositionallogic）符号化精确化——Aristotle(384B.C.-322B.C.)2023/2/1命题逻辑2命题(1)13不是偶数。(2)13是偶数也是奇数。(3)他一边走路一边唱歌。(4)她或许数学成绩好，或许英语成绩好。

(5)开往烟台的2547次火车三点或四点出发。(6)如果你努力学习，那么就可以得奖学金。(7)只要不下雨，我就骑自行车上班。(8)只有不下雨，我才骑自行车上班。(9)两圆的面积相等当且仅当它们的半径相等。2023/2/1命题逻辑3常用的联结词(connective)合取(conjunction)：与，并且，而且，也析取(disjunction)：或，要么…要么…否定(negation)：非，不蕴涵(conditional)：如果…就…，当，只有…才…

，除非…不，若…则…，等价(biconditional)：当且仅当2023/2/1命题逻辑4命题符号化原子命题：p,q,r,p1,q1,r1,…联结词：合取联结词：∧析取联结词：∨否定联结词：¬蕴涵联结词：→等价联结词：↔逻辑真值：0，1或F，T2023/2/1回顾5命题符号化（举例）(1)13不是偶数。┐p(2)13是偶数也是奇数。p∧q(3)他一边走路一边唱歌。p∧q

(4)她或许数学成绩好，或许英语成绩好。p∨q(5)开往烟台的2547次火车三点或四点出发。(p∧┐q)∨

(p∧┐q)(6)如果你努力学习，那么就可以得奖学金。p→q(7)只要不下雨，我就骑自行车上班。┐p→q(8)只有不下雨，我才骑自行车上班。q→┐p(9)两个圆的面积相等当且仅当它们的半径相等。p↔qp可表示任何命题p,q是简单命题，是命题常元2023/2/1命题逻辑6命题常元命题常元（命题常项）：p,q,r,p1,q1,r1,…

确定的简单命题。

2023/2/1命题逻辑7命题变元命题变元：p,q,r,p1,q1,r1,…

可以表示任何命题。在命题逻辑中，只研究形式推演的正确性，而不关心表示式所代表的实际含义。

2023/2/1命题逻辑8命题公式(well-formedformula)命题变元：p,q,r,p1,q1,r1,…联结词：∧，∨，¬，→，↔分隔符：（，）2023/2/1命题逻辑9命题的表示上节介绍了将命题表示为符号串。是否每个符号串都是命题的表示呢？

pq→

什么样的符号串才能表示命题呢？2023/2/1命题逻辑10命题公式递归定义单个命题变元是命题公式，称为原子（atomic）公式若A是命题公式，则(¬A)是命题公式若A,B是命题公式，则(A∧B),(A∨B),(A→B),(A↔B)也是命题公式只有有限次地应用上述规则形成的符号串才是命题公式（合式公式），简称为公式。A,B为元语言符号2023/2/1命题逻辑11子命题公式子命题公式：A，B是命题公式，若B是A中一部分则称B是A的子命题公式，特别A自己也是A的子命题公式。

2023/2/1命题逻辑12命题公式（举例）

p

(¬(¬p))，¬¬p((¬p)∧(¬p))，¬p∧¬p(¬(p∧q))，¬(p∧q)((¬p)∧q)，¬p∧q

约定：省略多余括号最外层优先级递减：¬；∧，∨；→，↔2023/2/1命题逻辑13命题公式的简单性质任一个命题公式必为下列形式之一：命题变元、(¬A)、(A∨B)、(A∧β)、(A→B)或(A↔B)命题公式的BNF(BacusNormalForm):A::=p|(¬A)|(A∨B)|(A∧B)|(A→B)|(A↔B)

每个命题公式都是有限符号串2023/2/1命题逻辑14分层命题公式若公式A是单个的命题变元，则称A是0层公式；称A是n+1(n0)层公式是指下面情况之一A=¬B，B是n层公式；A=B∧

C，其中B,C分别是i层和j层公式，且n=max（i,j）；A=B∨

C，其中B,C的层次与n同上；A=B→

C，其中B,C的层次与n同上；A=B↔

C，其中B,C的层次与n同上。若公式A的层次是k，

称A是k层公式。2023/2/1命题逻辑15命题公式（举例）

p

(¬(¬p))，¬¬p((¬p)∧(¬p))，¬p∧¬p(¬(p∧q))，¬(p∧q)(¬p∧q)→r¬(p∧q)↔((¬p∧s)∨

r)2023/2/1命题逻辑16注意！命题公式并不是命题，因此并无确定的真假值。当命题公式中的命题变元用确定的命题代入时，才得到一个命题。其真值由代换变元的命题真值决定2023/2/1命题逻辑17赋值(assignment,解释,指派)命题公式的真假由其中命题变元的值完全确定。定义1.8设A为一个命题公式，p1,

p2,…,

pn

是出现在公式A中的所有命题变元，给p1,

p2,…,

pn各指定一个真值，称为对A的一个赋值或解释。若赋值后公式A的真值为1，则称这组赋值为公式A的成真赋值，反之，则为成假赋值。

2023/2/1命题逻辑18赋值性质性质：n个变元，共有2n种不同的赋值赋值是从{p1,

p2,…,

pn}到{0，1}的一个函数。(p∧q)r

010为成真赋值

110为成假赋值2023/2/1命题逻辑19真值函数公式pqr可视为p,q,r的函数A(p,q,r)，称作真值函数——只有有限多种取值及函数值。自变量有2n组不同的取值，真值函数取值只有两种：1

T

0

F共有种不同的真值函数2023/2/1命题逻辑20例求A=(p∧q)→(¬(q∨r))的成真和成假赋值。解：要使A为假，必须p∧q为真且¬(q∨r)为假。从而p∧q必须为真，且q∨r也必须为真。故A的成假赋值为(1，1，1)和(1，1，0).A的成真赋值为(0，0，0)、(1，0，0)、(0，1，0)、(0，0，1)、(0，1，1)、(1，0，1)。2023/2/1命题逻辑21真值表(truth-table)定义1.9

命题公式在所有可能的赋值下所取值列成的表称为真值表.2023/2/1命题逻辑22真值表(truth-table)pq¬pp∧qp∨qp→qp↔q非合取析取蕴含等价不

和或如果…那么当且仅当00110101110000010111110110012023/2/1命题逻辑23哑元¬p也可以看作是含有命题变元p，q，的公式，q称为该公式的哑元。公式(p∧q)↔(¬p∨¬q)也可以看作是含有命题变元p，q，r的公式，r称为该公式的哑元。2023/2/1命题逻辑24α=(p∧q)→(¬(q∨r))的真值表2023/2/1命题逻辑25真值表(续)pqr(p∧q)→r¬p∨¬q∨r00001111001100110101010111111101111111012023/2/1命题逻辑26真值表(续)pqp∧q¬(p∧q)¬p∨¬qαβ0011010100011110111011110000α=¬(p∧q)↔(¬p∨¬q)β=(p∧q)↔(¬p∨¬q)2023/2/1命题逻辑27重言式(tautology)重言式:在各种赋值下取值均为真(永真式)矛盾式:在各种赋值下取值均为假(永假式)可满足式：有一个赋值下取值为真（非永假式）2023/2/1命题逻辑28重言式性质任何两个重言式的合取与析取仍然是一个重言式.