离散数学自学笔记命题公式及其真值表

　　我们把表示具体命题及表示常命题的p，q，r，s等与f，t统称为命题常元（proposition constant）。深入的讨论还需要引入命题变元（proposition variable）的概念，它们是以“真、假”或“1，0”为取值范围的变元，为简单计，命题变元仍用p，q，r，s等表示。相同符号的不同意义，容易从上下文来区别，在未指出符号所表示的具体命题时，它们常被看作变元。

　　命题常元、变元及联结词是形式描述命题及其推理的基本语言成分，用它们可以形式地描述更为复杂的命题。下面我们引入高一级的语言成分——命题公式。

　　定义1.1  以下三条款规定了命题公式（proposition formula）的意义：

　　（1）命题常元和命题变元是命题公式，也称为原子公式或原子。

　　（2）如果A，B是命题公式，那么（┐A），（A∧B），（A∨B），（A→B），（A？B）也是命题公式。

　　（3）只有有限步引用条款（1），（2）所组成的符号串是命题公式。

　　命题公式简称公式，常用大写拉丁字母A，B，C等表示。公式的上述定义方式称为归纳定义，第四章将对此定义方式进行讨论。

　　例1.8  （┐（p→（q∧r）））是命题公式，但（qp），p→r，p1∨p2∨…均非公式。

　　为使公式的表示更为简练，我们作如下约定：

　　（1）公式较外层括号一律可省略。

　　（2）联结词的结合能力强弱依次为  ┐，（∧，∨），→，？，（∧，∨）表示∧与∨平等。

　　（3）结合能力平等的联结词在没有括号表示其结合状况时，采用左结合约定。

　　例如， ┐p→q∨（r∧q∨s） 所表示的公式是 （（┐p）→（q∨（（r∧q）∨s）））

　　设A是命题公式，A1是A 的一部分，且A1也是公式，则A1称为公式A的子公式。

　　如对公式A：┐p→q∨（r∧q∨s），则p， ┐p ，q ，  （r∧q∨s） 及q∨（r∧q∨s）都是公式A的子公式，而┐q，  ┐p→q，  虽然是公式，但确不是A的一部分，因此不是A的子公式；q∨（r∧虽然是公式A的一部分，但不是公式，因而也不是A的子公式。

　　如果公式A含有命题变元p1，p2，…，pn，记为A（p1，…，pn），并把联结词看作真值运算符，那么公式A可以看作是p1，…，pn的真值函数。对任意给定的p1，…，pn的一种取值状况，称为指派（assignments），用希腊字母a，b等表示，A均有一个确定的真值。当A对取值状况 a 为真时，称指派a弄真A，或a是A的成真赋值，记为a （A） = 1；反之称指派a弄假A，或a是A的成假赋值，记为a （A） = 0.对一切可能的指派，公式A的取值可能可用表1.7来描述，这个表称为真值表（truth  table）。当A（p1，…，pn）中有k个联结词时，公式A的真值表应为2n行、k+n列（不计表头）。

　　例1.9  作出公式┐（p→（q∧r））的真值表。

　　表1.7