[理学]大学 离散数学 第一章12.ppt

* * 定义1.9 将命题公式A在所有赋值下取值情况列成表，称为A的真值表。 构造真值表的步骤： （1）找出公式中所含的全体命题变项p1,p2, …pn（若无下标就按字典顺序排列），列出2n个赋值，本书规定，赋值从00 … 0开始，直到11 … 1为止。 （2）按从低到高的顺序写出公式的各个层次。 （3）对应各个赋值计算出各层次的真值，直到最后计算出公式的真值。 如果两个公式的真值表对所有赋值最后一列都相同，即最后结果都相同，则称这两个真值表相同，不考虑中间过程。 * 例 1.8 求下列公式的真值表。　　(1) (┐p∧q)→┐r; (2) (p∧┐p)?(q∧┐q); (3) ┐(p→q)∧q∧r　　 说明： 熟练之后，真值表的中间有些层次可不写 * 注意：　　给定n个命题变项，使用联结词和括号，可构成无穷多个命题公式。其中ｎ个命题变项共有2n个可能的赋值，而在每个赋值下公式只能取值０或1。因此含ｎ个命题变项的公式其真值表只有 种可能的情况。从而必有无穷多个公式具有相同的真值表。 * 例1.9 下列公式中哪些具有相同的真值表？　　(1)ｐ→ｑ； (2)ｐ?ｑ； (3) ┐(ｐ∧┐ｑ)； (4) (ｐ→ｑ)∧(ｑ→ｐ)；(5) ┐ｑ∨ｐ　　 5个公式的真值表 p q ｐ→ｑ ｐ?ｑ ┐（ｐ∧┐ｑ） （ｐ→ｑ）∧（ｑ→ｐ） ┐ｑ∨ｐ 0 0 1 1 1 1 1 0 1 1 0 1 0 0 1 0 0 0 0 0 1 1 1 1 1 1 1 1 * 设公式Ａ、Ｂ中总共含有命题变项p1，p2，…pn，但Ａ或Ｂ并不全含有这些变项。如果某个变项未在公式Ａ中出现，则称该变项为Ａ的哑元。同样可定义Ｂ的哑元。在讨论Ａ与Ｂ是否有相同的真值表时，应将哑元考虑在内，即将Ａ、Ｂ都看成含所有 p1，p2，…pn的命题公式。 * 例1.10　下列公式中，哪些具有相同的真值表？　　(1) p→q； (2) ┐q∨r； (3) (┐p∨q)∧((p∧r)→p)； (4) (q→r)∧(p→p)． 　解：四个命题共含p,q,r三个变项，r是(1)的哑元，p是(2)的哑元。 　 　４个公式的真值表 p q r ｐ→ｑ ┐ｑ∨ｒ （┐ｐ∨ｑ）∧（ｐ∧ｒ）→ｐ） （ｑ→ｒ）∧（ｐ→ｐ） 0 0 0 1 1 1 1 0 0 1 1 1 1 1 0 1 0 1 0 1 0 0 1 1 1 1 1 1 1 0 0 0 1 0 1 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 1 1 1 1 * 要点 一 命题与连结词命题与真值 命题，命题的真值，真命题，假命题，简单命题（或称原子命题），复合命题命题与真值的符号化 用p、q、r等表示命题，成为命题符号化；用1代表真，0代表假，成为真值得符号化。命题连结词及其符号化 记S={┐，∧，∨，→，?}，称S为常用联结词集。 * 二．命题公式及其赋值命题常项与命题变项 命题常项（简单命题），命题变项（取值为1或0的变量p，q，r，……）命题公式与赋值 合式公式，合式公式也称为命题公式或公式，公式的层次，公式的赋值，成真赋值，成假赋值，真值表。命题公式的类型 重言式（也称为永真式），矛盾式（也称为永假式），可满足式。判断公式类型的方法 在本章内主要用真值式判断公式的类型，求公式的成真赋值和成假赋值。 * 基本要求 分清简单命题和复合命题 深刻理解5种常用连接词，能对复合命题进行准确的符合化 深刻理解命题公式的赋值、成真赋值、成假赋值、重言式、矛盾式、可满足式等概念 熟练写出命题公式的真值表，准确判断公式类型，并求出公式的成真赋值和成假赋值 * * * * * * * * * * * * * * * * 例 A：李明既是三好学生又是足球队员。 　　 B：张平或者正在钓鱼或者正在睡觉。 　　 C：如果明天天气晴朗，那么我们举行运动会。 * 2. 命题的分类 （1）简单命题（也称原子命题） 不能被分解命题称为原子命题。 （2）复合命题 由简单命题通过联结词联结而成的命题称为复合命题。 * 例1.2 先将下面各陈述句中出现的原子命题符号化，并指出他们的真值，然后再写出这些陈述。 （1） 是有理数是不对的。 （2）2是偶素数 （3）2或4是素数 * P： 是有理数。（1）可以表示成非p q: 2是偶数。r： 2是素数。（2）可以表示成q