离散数学课件-第1章-2.ppt

《离散数学课件-第1章-2.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、12021/7/23离散数学DiscreteMathematics汪荣贵教授合肥工业大学软件学院专用课件2010.3第一章逻辑与证明学习内容1.1逻辑1.2命题等价1.3谓词和量词1.4对偶与范式1.5推理规则1.6证明导论1.7证明的方法和策略1.8数理逻辑的应用命题等价命题公式真值表等价公式重言式和蕴含式命题变元如果命题标识符表示一个具体、确定的命题，称为命题常元。如果命题标识符表示任意一个命题，称为命题变元。命题变元无确定的真值。命题是能判断真假的陈述句。而命题变元代表任意的命题，其真值是不确定的。因而不是命题。复合命题如果一个命题不能再分解

2、成更简单的命题，则称该命题为原子命题。如果一个命题不是原子命题，称该命题为复合命题。如果用命题变元表示原子命题时，该命题变元称为原子变元。命题逻辑中，可以通过命题联结词将原子变元联结起来表示复合命题。命题公式把命题常元，命题变元按照一定的逻辑顺序和规则，用命题联结词连接起来就构成了命题演算的合式公式，也叫命题公式。命题公式合式公式(wff)(wellformedformulas)：按下列规则构成的符号串称为命题演算的合式公式，也称为命题公式，简称公式。⑴单个命题变元和常元是合式公式。⑵如果A是合式公式，那么¬A是合式公式。⑶如果A和B是合式公式，那

3、么(A∧B)、(A∨B)、(A→B)和(A↔B)是合式公式。⑷当且仅当有限次地应用了⑴、⑵、⑶所得到的符号串是合式公式。命题公式上面的定义给出合式公式定义的方法称为归纳定义，它包括三部分：基础、归纳、界限其中⑴是基础，⑵和⑶是归纳，⑷是界限。以后将多次出现这种形式的定义。命题公式下列符号串是合式公式：¬(p∨q)，¬(p∨q)，(p→(p∨¬q))，(((p→q)∧(q→r))↔(s↔t))下列符号串不是合式公式：(p→q)→(∧q)，(p→q，(p∧q)→q)命题公式约定：为方便，最外层括号可以不写，合式公式可以写成：P∧Q，PR，(P∨Q)

4、∧R如果规定逻辑联接词的优先级：¬、∧、∨、→、则：P∧QR也是合式公式命题等价命题公式真值表等价公式重言式和蕴含式命题公式的赋值设pl，p2，…，pn是出现在公式A中的全部命题变元，给pl，p2，…，pn各指定一个真值，称为对公式A的一个赋值或解释。若指定的赋值使A的真值为T，则称这个赋值为A的成真赋值，若使A的真值为F，则称这个赋值为A的成假赋值。例如，给公式(p∨q→r)赋值011是指p=0，q=1，r=1，它是该公式的成真赋值；赋值110是指p=1，q=1，r=0，它是该公式的成假赋值。真值表的概念在命题公式A中，对A的每一个赋值，就确

5、定了A的一个真值，把它们汇列成表，称该表为命题公式A的真值表。真值表的概念在命题公式A中，对A的每一个赋值，就确定了A的一个真值，把它们汇列成表，称该表为命题公式A的真值表。例如：PQPPQ(PQ)∨QTTFTTTFFTTFTTTTFFTFF真值表的概念说明:设P1，P2,…,Pn为命题公式P中的命题变量，对于命题变元每一种真值指派的可能组合，都能唯一确定P的真值（即有2的n次幂种分布）。为了有序地列出公式的真值表，在对命题变元做指派时，可以按照二进制数的次序列表。【例】构造命题公式¬p∨q的真值表，并求成真赋值和成假赋值。解：命题公式¬

6、p∨q的真值表如表1.6所示。00，01，11是成真赋值，10是成假赋值。¬ppq¬p∨q0011011110001101pqp∧q¬p¬q¬p∧¬q(p∧q)∨(¬p∧¬q)0001111010100010001001110001【例】构造命题公式(p∧q)∨(¬p∧¬q)的真值表，并求成真赋值和成假赋值。解：命题公式(p∧q)∨(¬p∧¬q)的真值表如下表所示。00，11是成真赋值，01，10是成假赋值。为了有序地列出A(P1,P2,…,Pn)的真值表，可以将F看成0，将T看成1，按照二进制数00…0,00…01,00…010,…,11…10,

7、11…1(即十进制的0,1,2,….,2n-1)的次序进行指派列真值表。如A(P,Q)的真值表可按照如下次序指派：00(F,F)，01(F,T)，10(T,F)，11(T,T)如A(P,Q,R)的真值表可按照如下次序指派：000(F,F,F),001(F,F,T),010(F,T,F),011(F,T,T)100(T,F,F),101(T,F,T),110(T,T,F),111(T,T,T)真值表构造总结例如列出P(QR)的真值表PQRQRP(QR)000FFFTT001FFTTT010FTFFT011FTTTT100TFFTT101TF

8、TTT110TTFFF111TTTTT观察下面的真值表PQ¬P∨QPQ（P∧Q）∨（¬P∧¬Q）PQFFTTTTFTT