离散数学-第三章(上).ppt

* 计算机应用技术研究所 * * * 执行X的条件可化简为： (Ａ∧Ｂ)∨(?Ａ∧Ｂ) ?Ｂ∧(Ａ∨ ?Ａ) ?Ｂ 执行Y的条件可化简为： (Ａ∧?Ｂ)∨(?Ａ∧?Ｂ) ? ?Ｂ∧(Ａ∨?Ａ) ? ?Ｂ T X Y End Start B F 程序可简化为：If B then X else Y 命题公式的应用 * 计算机应用技术研究所 * * * 4 一家航空公司，为了保证安全，用计算机复核飞 行计划。每台计算机能给出飞行计划正确或有误 的回答。由于计算机也有可能发生故障，因此采 用三台计算机同时复核。由所给答案，再根据 “少数服从多数”的原则作出判断，试将结果用 命题公式表示，并加以简化，画出电路图。 命题公式的应用 * 计算机应用技术研究所 * * * 设C1，C2，C3分别表示三台计算机的答案。 S表示判断结果。 真值表和联结词的定义，S可用C1，C2，C3所对应的命题公式表示出来，可画出该命题公式所对应的电路图。 C1 C2 C3 S 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 命题公式的应用 * 计算机应用技术研究所 * * * S ? (?C1∧C2∧C3)∨(C1∧?C2∧C3) ∨(C1∧C2∧?C3)∨(C1∧C2∧C3) ?((C1∨?C1)∧C2∧C3)∨(C1∧(C2∨?C2) ∧C3)∨(C1∧C2∧(C3∨?C3)) ?(C2∧C3)∨(C1∧C3)∨(C1∧C2) C1 C2 C3 S ≥1 ≥1 命题公式的应用 * 计算机应用技术研究所 * 命题公式的应用 * 计算机应用技术研究所 * 命题公式的应用 分析：如果被问的是诚实战士且回答“对”，那么另外一名(说谎战士) 应回答“是”，说明手指门不是死亡门； 如果被问的是诚实战士且回答“不对”，那么另外一名(说谎战士)应回答“不是”，说明手指门是死亡门。 * 计算机应用技术研究所 * 本节内容到此结束 * * * * * * * * * * * * * * * * * * * * * * * * * * * 计算机应用技术研究所 * 命题公式与真值表 命题公式的基本概念 命题公式的基本类型 命题公式的等值演算 命题公式的应用 * 计算机应用技术研究所 * 观察下列真值表 P Q ?P ∨Q P ?Q （P ∧ Q）∨（ ?P ∧ ? Q ） P ?Q F F T T T T F T T T F F T F F F F F T T T T T T 是否发现什么问题？ ?P ∨Q ＝P ? Q ？ （P ∧ Q）∨（ ?P ∧ ? Q ） ＝P ?Q ？ 公式的等值关系 * 计算机应用技术研究所 * 公式的等值关系 【定义】A、B是含有命题变元P1,P2,…, Pn的命题公式，如不论对P1, P2 , …, Pn作任何指派，都使得A和B的真值相同，则称之为命题公式A与B等价或等值，记作A?B。 显然有： ?P∨Q?P?Q (P∧Q)∨(?P∧?Q)?P?Q * 计算机应用技术研究所 * 公式的等值关系 可以证明，命题公式的等值关系有如下性质： (1) 自反性，即对任意命题公式A， A?A (2) 对称性，即对任意命题公式A和B，若A?B，则B?A (3) 传递性，即对任意命题公式A，B和C，若A?B，B?C，则A?C (4) 如果A(P1,P2,…,Pn)?B(P1,P2,…,Pn)，则 A(?P1,?P2,…,?Pn)?B(?P1,?P2,…,?Pn) * 计算机应用技术研究所 * 公式的等值关系 【例】 A(P,Q)?P→Q ; B(P,Q)??P∨Q 则有： A(P,Q)?B(P,Q) A(?P,?Q)??P→?Q B(?P, ?Q)?P∨?Q 可见：A(?P,?Q)?B(?P, ?Q) * 计算机应用技术研究所 * 公式的等值关系 【例】根据等值关系的定义，用真值表证明 p→(q→p)??p→(p→?q) p q ?p ?q q→p p→(q→p) p→?q