离散数学1.1-1.4

（14） 若2+2≠4，则太阳从西方升起

（15） 燕子飞回南方，春天来了。（分析真值） （16） 2+2=4当且仅当3不是奇数（分析真值） （17） 小王是游泳冠军或百米赛跑冠军 （18） 小王现在在宿舍或图书馆里 （19） 选小王或小李中的一人当班长

（20） 如果我上街，我就去书店看看，除非我很累

（21） 王一乐是计算机系的学生，他生于1968或1969年，他

是三好学生

（22） 一个人起初说“占据空间的，有质量的而且不断变化的

叫做物质”；后来他改说“占据空间的有质量的叫做物质，而物质是不断变化的”。

解：p：它占据空间 r：它不断变化

q：它有质量 s：它是物质

提示：根据命题的实际含义，不拘泥于原句形式地确定原子命题和选用联结词

1.2 命题公式及分类

命题公式：由命题常项或命题变项组成的复合命题形式。

合式公式：

（1） 单个命题常项或变项p,q,r,…,pi,qi,ri,…，0，1是合式公式； （2） 如果A是合式公式，则（?A）也是合式公式； （3） 如果A，B是合式公式，则（A∧B），（A∨B），（A→B），

（A?B）也是合式公式

（4） 只有有限次地应用（1）—（3）组成的符号串才是合式

公式

合式公式也称命题公式或公式。

例3：

（1）?（p∨q）; p→（p→q）; （p∧q）?r

（2）pq→r ; ?p∨q）→r ; （（?p→q）→（q→p））)

命题公式的层次的定义：

（1） 若A是单个命题（常项或变项），p,q,r,…,pi,qi,ri,…，0，1，则称A是0层公式。

（2） 称A是n+1(n≥0)层公式是指A符合下列情况之一：

① A=?B,B是n层公式；

② A= B∧C，其中B，C分别为i层和j层公式，且 n=max(i,j); ③ A= B∨C，其中B，C的层次同② ④ A= B→C，其中B，C的层次同② ⑤ A= B?C，其中B，C的层次同② （3） 若A的最高层次为k，则称A是k层公式

例4：?(?p∧q) →(r∨s)

对一个公式的解释和赋值定义如下：’

设A为一个命题公式，p1, p2,…，pn为出现在A中的所有的命题变项。给p1, p2,…，pn指定一组真值，称为对A的一个赋值或解释。若指定的一组值使A的值为真，则称这组值为A的成真赋值，若使A的值为假，则称这组值为A的成假赋值。

例：公式A=p∧q→r，110是A的一个赋值，即另p=1,q=1,r=0,110是一个成假赋值；那么111，011，010是A的成真赋值。

含n个命题变项的命题公式，共有2n组赋值。将命题公式A在所有赋值之下取值的情况列成表，称为A的真值表。

构造真值表的步骤：

（1） 找出命题公式中所含的所有命题变项，列出所有可能赋

值

（2） 从低到高写出各层次 （3） 计算命题公式的值 例5：

（1）基本真值表

（2）例2中的（15）

设A为一个命题公式

（1） 若A在它的各种赋值下取值为真，则称A为重言式或永

真式

（2） 若A在它的各种赋值下取值为假，则称A为矛盾式或永

假式

（3） 若A至少存在一组赋值是成真赋值，则称A为可满足式

重言式是可满足式，但可满足式不一定是重言式

提示：判断命题公式类型的方法之一是真值表。

1.3 等值演算

n个命题变项只能生成2个真值不同的命题公式

设A,B为两个命题公式，若等价式A?B是重言式，则称A与B是等值的，记作A?B

A?B不是命题公式

2n