1.2 命题公式及其分类

上一节介绍了几个常用的联结词及其组成的基本复合命题表达式、p→q、p↔q等，其中p、q可以代表特定的命题，也可以代表任意的命题。当p、q代表特定的命题时，真值是确定的，称为命题常量（常项）。当p、q代表任意的命题时，称为命题变元（变项）。由代表命题常量或命题变元的字母、联结词、括号等组成的符号串称为命题公式，但不是由这些符号任意组成的符号串都是命题公式。下面给出命题公式的定义。

定义1.2.1

1）每一个命题常量或命题变元都是命题公式。

2）如果A是命题公式，则是命题公式。

3）如果A和B都是命题公式，则（A∧B）、（A∨B）、（A→B）、（A↔B）都是命题公式。

4）一个由命题常量或命题变元、联结词和括号所组成的符号串是命题公式，当且仅当这个符号串是有限次应用上面的步骤得到的。

命题公式可以简称为公式。根据定义，、p→（q→r）、（p∧q）↔r等都是命题公式。为了书写方便，一般的括号及整个公式最外层的括号可以省略，例如，可写成。

一个含有命题变元的命题公式的真值是不确定的。只有当公式中的所有命题变元代表特定的命题时，命题公式才成为命题，其真值才唯一确定。例如，命题公式p∧q中，若指定p为“2是素数”，q为“3是奇数”，也就是p的真值为真，q的真值为真，则p∧q为真命题；若指定p为“2是素数”，q为“3是偶数”，则p∧q为假命题，因为p的真值为真，而q的真值为假。对命题公式的各个命题变元指定一个特定的命题，实际上就是对命题公式的解释或赋值，定义如下。

定义1.2.2 若命题公式A含有的全部命题变元为p₁,p₂,…,p_n，给p₁,p₂,…,p_n指定一组真值，称为对A的一个解释或赋值。使A的真值为真的赋值称为成真赋值，使A的真值为假的赋值称为成假赋值。通常赋值与命题变元之间按下标或字母顺序对应，即当A的全部命题变元为p₁,p₂,…,p_n时，给A赋值α₁,α₂,…,α_n，是指p₁=α₁,p₂=α₂,…,p_n=α_n；当A的全部命题变元为p,q,r,…时，给A赋值α₁,α₂,α₃,…是指p=α₁,q=α₂,r=α₃,…。

例如，公式A为，p=0、q=1、r=0是对A的一个赋值，这时A的真值为1；p=1、q=1、r=0是对A的又一个赋值，这时A的真值为0。也就是010是公式A的一个成真赋值，而110是公式A的一个成假赋值。

含n（n≥1）个命题变元的命题公式，共有2n个不同的赋值。将命题公式在所有赋值下的真值列成一个表，称为该命题公式的真值表。命题公式有n个命题变元，它的真值表有2n行。n个命题变元的不同的真值表有个。

例1.2.1 写出下列公式的真值表。

1）

2）

3）

解 1）有3个变元，真值表有8行，见表1.2.1。

在写出命题公式的真值表时，按联结词的优先级次序，首先计算在各种赋值下的真值，然后计算的赋值，最后算出的真值。

2）同理可以写出的真值表，见表1.2.2。

3）的真值表见表1.2.3。

在表1.2.1中有些赋值使命题公式为真，有些赋值使命题公式为假。而在表1.2.2中，所有赋值均使命题公式的真值为1，在表1.2.3中，所有赋值均使命题公式的真值为0。

◀

按照命题公式在各种赋值下的取值情况，可将命题公式分类如下。

定义1.2.3 设A为一个命题公式。

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

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

3）若至少存在一种赋值使A的真值为1，则称A为可满足式。

这三类公式之间有下面的关系。

1）公式A永真，则永假，反之亦然。

2）公式A是可满足的，当且仅当不是永真式。

3）公式A不是可满足的，则一定是永假式。

4）公式A不是永假式，则一定是可满足的。

判断一个命题公式的类型（即永真式、永假式、可满足式）可通过构造命题公式的真值表来实现，如例1.2.1中的公式1）存在为真的赋值，也存在为假的赋值，是可满足式，公式2）的所有赋值都使公式的真值为1，是永真式，公式3）的所有赋值都使公式的真值为0，是永假式。