必胜高考网 > 自考 > 笔讲串讲 > 公共课 >

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

时间: 未知2 公共课
  我们把表示具体命题及表示常命题的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
p  q  r  q∧r   P→(q∧r)  ┐(p→(q∧r) 
0
0
0
0
1
1
1
1 
0
0
1
1
0
0
1
1 
0
1
0
1
0
1
0
1 
0
0
0
1
0
0
0
1 
1
1
1
1
0
0
0
1 
0
0
0
0
1
1
1
0 

  表1.7即为所求。可见指派(0,0,0),(0,0,1),(0,1,0),(0,1,1)及(1,1,1)均弄假该公式,而指派(1,0,0),(1,0,1),(1,1,0)都弄真这一公式。
32555