1.2命题公式及其赋值

1.2命题公式及其赋值命题常项(命题常元)：简单命题命题变项(命题变元)：真值不确定的陈述句定义

合式公式(命题公式,公式)递归定义如下：(1)单个命题常项或变项p,q,r是合式公式(2)若A是合式公式，则(

A)也是合式公式(3)若A,B是合式公式，则(A

B),(A

B),(A

B),(A

B)也是合式公式(4)只有有限次地应用(1)~(3)形成的符号串才是合式公式说明:外层括号可以省去

注1命题公式没有真值，仅当其中命题变项用确定的命题替换时才得到一个命题。注2定义中的A,B可以表示任意的命题公式，包括0和1。注3并不是由命题变项、联结词、括号组成的字符串都是命题公式。例如：¬(p∧q)、(p→q)→¬q是公式，p→q→(q)、pq↔r不是公式。本质上，命题公式的递归定义给我们阐述了什么形式的字符串是规范的。定义公式的层次(1)若公式A是单个的命题变项,则称A为0层公式.(2)称A是n+1(n≥0)层公式是指下面情况之一：

(a)A=

B,B是n层公式；

(b)A=B

C,其中B,C分别为i层和j层公式，且

n=max(i,j)；

(c)A=B

C,其中B,C的层次及n同(b)；

(d)A=B

C,其中B,C的层次及n同(b)；

(e)A=B

C,其中B,C的层次及n同(b).

例如公式

p0层

p1层

p

q2层

(p

q)

r3层

((

p

q)

r)

(

r

s)4层

定义

公式的赋值

给公式A中的命题变项p1,p2,…,pn指定一组真值称为对A的一个赋值或解释。使公式为真的赋值称为该公式的成真赋值，使公式为假的赋值称为该公式的成假赋值。注：

1赋值

=

1

2…

n之间不加标点符号，

i=0或1.2A中仅出现p1,p2,…,pn，给A赋值

1

2…

n是指p1=

1,p2=

2,…,pn=

n3A中仅出现p,

q,r,…,给A赋值

1

2

3…是指p=

1,q=

2,r=

3…4含n个变项的公式有2n个赋值.

真值表:公式A在所有赋值下的取值情况列成的表。一般按照二进制数的次序赋值。

例给出公式的真值表

A=(q

p)

q

p

的真值表pqq

p

(q

p)

q

(q

p)

q

p

00011011

1011

0001

1111例B=(

p

q)

q

的真值表pq

p

p

q

(

p

q)

(

p

q)

q00011011

1100110100100000例C=(p

q)

r

的真值表pqrp

q

r

(p

q)

r

000001010011100101110111

00111111

10101010

11101010pqp

q

p

q

q

p00011011

110111011101从真值表可以看出，无论对p，q做何种赋值，p

q、

p

q和

q

p的真值都相同。例p

q、

p

q和

q

p

的真值表定义设A为一个命题公式

(1)若A无成假赋值，则称A为重言式(也称永真式)(2)若A无成真赋值，则称A为矛盾式(也称永假式)(3)若A不是矛盾式，则称A为可满足式注：重言式是可满足式，但反之不真.下例中A为重言式，B为矛盾式，C为可满足式

A=(q

p)

q

p，B=(

p

q)

q，C=(p

q)

r问题：含n个命题变项的所有公式共产生多少个互不相同的真值表？定义

称定义域为{00…0,00…1,…,11…1}，值域为{0,1}的函数是n元真值函数，定义域中的元素是长为n的0,1串.常用F:{0,1}n

{0,1}表示F是n元真值函数.

n个命题变元共有

个n元真值函数.例如F:{0,1}2

{0,1}，且F(00)=F(01)=F(11)=0，F(01)=1，则F为一个确定的2元真值函数.2元真值函数对应的真值表pq0001011100000000000011110011001101010101

pq000101111111111100001