离散数学1.2.ppt

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

1、简单命题具有确定的真值命题常项或命题常元复合命题x>y、x+y>5真假可以变化命题变项或命题变元命题公式1.2命题公式及其赋值命题常元：表示具体确定内容的命题。命题变元：表示不确定具体内容的命题。定义：命题常项和命题变项简单命题的具有唯一确定的真值，因此简单命题称为命题常项或命题常元。对于x+y>5这样的真假可以变化的简单陈述句称为命题变项或命题变元。说明：（1）命题变项不是命题。（2）也用p，q，r，…表示命题变项：命题变项的符号化。（3）一个命题标识符表示的是命题还是命题变项由上下文决定。定义（命题公式）：将命题变项用联结词和圆括号按照一定的逻辑关

2、系联结起来的符号串称为命题公式或合式公式。以下给出命题公式的严格定义定义：命题公式（合式公式）（1）单个命题变项是命题公式，并称为原子命题公式。（2）如果A是命题公式，则┐A是命题公式。（3）如果A、B是命题公式，则A∨B、A∧B、A→B、AB也是命题公式。（4）只有有限次运用（1）（2）（3）所得到的符号串是命题公式。例如：┐(┐p∧q)（r∨s）命题公式的定义有关命题公式的几点说明：（1）今后将命题公式简称为公式。（2）定义中的A、B符号代表任意的公式，而不是某个具体的公式。（3）在不引起疑义和运算顺序的前提下，可以省略公式中的括号。例：p→（

3、q∧r）和（p→q）∧rp→（q∧r）的括号可以省略，写成p→q∧r（p→q）∧r的括号则不能省略定义（公式的层次）（1）若A是单个的命题变项，则称A为0层公式。（2）若A是n（n≥0）层公式，则┐A为n+1层公式。（3）若A、B分别是n层和m层公式，则A∧B、A∨B、A→B及AB是max（n，m）+1层公式。例：讨论公式（1）┐p∨q（2）p∨q∧r（3）(┐p∧q)→r（4）┐(┐p∧q)（r∨s）的层次。3层公式2层公式2层公式4层公式命题公式的复杂度命题公式与命题的关系（1）含有命题变项的命题公式的真值通常是不确定的。例如：假设p：a大于2

4、；q：a大于1，易见p、q、p→q都是命题公式。但p→q却是真命题。（2）对命题公式中的命题变项用指定的命题常项代替后，命题公式就有了唯一确定的真值，从而命题公式就变成了命题。例如：对于命题变项p、q、r，公式A=(p∨q)→r的真值不确定。如果指定p为“2是素数”，q为“3是偶数”，r为“4能被2整除”，则A就变成了一个真命题。如果指定p为“2是素数”，q为“3是偶数”，r为“3能被2整除”，则A就变成了一个假命题。这种为了决定公式的真值而对命题变项指定真值的行为称为对该公式的赋值或解释。命题公式与命题的关系定义（赋值）：设p1，p2，…，pn是出现

5、在公式A中的全部命题变项(按下标顺序或字典顺序排列)，对这n个命题变项p1，p2，…，pn各指定一个真值的过程称为对公式A的一个赋值或解释。若指定的一组值使A的真值为1，则称这组值为A的成真赋值。若使A的真值为0，则称这组值为A的成假赋值。说明：（1）若公式A中出现的命题变项为p1，p2，…，pn，给定A的赋值a1a2…an(其中ai为0或1)是指p1=a1，p2=a2，…，pn=an。（2）含n个命题变项的公式共有2n个不同的赋值。例：对于公式A=(p∨q)→r，110是A的一组赋值，即p=1，q=1，r=0易见这使得A的真值为0，因此是A的一个成假

6、赋值。此外，111，101，011，000，001是A的成真赋值，100，010是A的成假赋值。定义（真值表）：将命题公式A在所有赋值下的取值情况列成表，称作A的真值表。构造真值表的具体步骤：（1）找出公式中所有的命题变项p1，p2，…，pn（若无下标就按字典顺序排列），列出2n个赋值。（2）按从低到高的顺序从1层公式依次写出公式的各个层次。（3）对应各个赋值计算出各层次的真值，直到最后计算出公式的真值。例：求(┐p∧q)→┐r的真值表，并求所有的成真赋值和成假赋值。（1）找出公式(┐p∧q)→┐r中所有的命题变项p，q，r，并列出8个赋值。注意：所有

7、赋值按二进制从低到高的顺序排列。（2）按从低到高的顺序写出公式(┐p∧q)→┐r的各个层次。┐p┐r┐p∧q(┐p∧q)→┐r（3）对应各个赋值计算出各层次的真值，直到最后计算出公式的真值。由真值表可见，(┐p∧q)→┐r的成假赋值为011，其余7个赋值都是成真赋值。例：求公式┐(p→q)∧q∧r的真值表p→q┐(p→q)┐(p→q)∧q┐(p→q)∧q∧r例：求公式┐(p→q)∧q∧r的真值表由真值表可见，┐(p→q)∧q∧r的赋值都是成假赋值。例：求公式（p∧┐p）（q∧┐q）的真值表由真值表可见，（p∧┐p）（q∧┐q）的赋值都是成假赋值。定

8、义（公式的分类）：设A为任一命题公式（1）若A在所有赋值下的真值均为真，则称A是重言式或永真式