自考离散数学基础串讲资料六

发布时间： 2018-04-02

3.命题逻辑公式

【定义1.1】命题逻辑公式(propositional logic formula)由以下子句归纳定义：

[1]. 归纳基：命题常量或命题变量是命题逻辑公式，称为命题逻辑公式的原子项。

[2]. 归纳步：如果A, B是逻辑公式，则(ØA)、(AÙB)、(AÚB)、(A®B)和(A«B)也是命题逻辑公式。

[3]. 最小化：所有的命题逻辑公式都通过1和2得到。

在这里我们隐含地使用的字母表是大小写的英文字母、命题联结符和园括号。英文字母还可带下标。其它的符号都不属于我们的符号表，即在命题逻辑公式中不能出现这些符号。后面我们将命题逻辑公式简称为命题公式，或在没有二义的情况下进一步简称为公式。

【例子1.1】((p Ú q) ® ((Øp) « (q Ù r)))是命题公式，它通过以下步骤生成：

1.p是公式； // 根据定义1.1的[1]

2.q是公式； // 根据定义1.1的[1]

3.(p Ú q)是公式；// 根据定义1.1的[2]

4.(Øp)是公式； // 根据定义1.1的[2]

5.r是公式； // 根据定义1.1的[1]

6.(q Ù r)是公式；// 根据定义1.1的[2]

7.((Øp) « (q Ù r))是公式；// 根据定义1.1的[2]，以及4, 6

8.((p Ú q) ® ((Øp) « (q Ù r)))是公式。 // 根据定义1.1的[2]，以及3, 7