离散数学(第)陈瑜讲解.ppt

计算机科学与工程学院 陈瑜 Email：chenyu.inbox@ * 主要内容 1.命题公式的蕴涵 1)九类蕴涵关系 2)蕴涵关系的基本性质 2.推理的基本概念和推理形式 3.推理规则 1)P规则 2)T规则 3)CP规则 §1．6 命题公式的蕴涵 定义1.18 设A和B是两个合适公式，如果在任何解释下，A取值1时B也取值1，则称公式A蕴涵公式B，并记A ?B。（A取0时的情况不考虑） 定理1.11: A?B 当且仅当 A→B为永真式。 注意：蕴含和条件联结词→是完全不同的。 1)→是命题联结词，A→B是一个命题公式； 2)?是公式间关系符，A?B不是一个命题公 式，仅表示A，B间的蕴含关系。 §1．6 命题公式的蕴涵 定义1.18 设A和B是两个合适公式，如果在任何解释下，A取值1时B也取值1，则称公式A蕴涵公式B，并记A ?B。（A取0时的情况不考虑） 定理1.11: A?B 当且仅当 A→B为永真式。 注意：蕴含和条件联结词→是完全不同的。 1)→是命题联结词，A→B是一个命题公式； 2)?是公式间关系符，A?B不是一个命题公 式，仅表示A，B间的蕴含关系。 §1．6 命题公式的蕴涵 定义1.18 设A和B是两个合适公式，如果在任何解释下，A取值1时B也取值1，则称公式A蕴涵公式B，并记A ?B。 定理1.11: A?B 当且仅当 A→B为永真式。 注意：蕴含和条件联结词→是完全不同的。 1)→是命题联结词，A→B是一个命题公式； 2)?是公式间关系符，A?B不是一个命题公 式，仅表示A，B间的蕴含关系。 §1．6 命题公式的蕴涵 定义1.18 设A和B是两个合适公式，如果在任何解释下，A取值1时B也取值1，则称公式A蕴涵公式B，并记A ?B。 定理1.11: A?B 当且仅当 A→B为永真式。 注意：蕴含和条件联结词→是完全不同的。 1)→是命题联结词，A→B是一个命题公式； 2)?是公式间关系符，A?B不是一个命题公 式，仅表示A，B间的蕴含关系。 §1．6 命题公式的蕴涵 定义1.18 设A和B是两个合适公式，如果在任何解释下，A取值1时B也取值1，则称公式A蕴涵公式B，并记A ?B。 定理1.11: A?B 当且仅当 A→B为永真式。 注意：蕴含和条件联结词→是完全不同的。 1)→是命题联结词，A→B是一个命题公式； 2)?是公式间关系符，A?B不是一个命题公 式，仅表示A，B间的蕴含关系。 证明 定理1.11: A?B 当且仅当 A→B为永真式。证： 1)因A?B，由蕴涵定义知：A取1，B也取1。此时，由→运算规则知A→B取1。此外，A若为0， A→B也必取1。因此， A→B为永真式。 2)如果A→B为永真式，那么A取1时必有B也取1，从而A?B。（注：此处由假设“A→B为永真式”也可得出A取0时，B取0或1，A→B也为1的结果，但根据蕴涵定义，我们不需要判断此情况。） 蕴含关系的性质 ① 自反性 A ? A ② 反对称性，如果A ? B，且B ? A，则必有： A ? B ③ A ? B 且A为永真式，则B必为永真式 ④ 传递性，如果A ? B，B ? C，则A ? C ⑤ 如A ? B，A ? C，则A ? B∧C ⑥ 如A ? C，B ? C，则A∨B ? C 蕴含关系的性质 ① 自反性 A ? A ② 反对称性，如果A ? B，且B ? A，则必有： A ? B ③ A ? B 且A为永真式，则B必为永真式 ④ 传递性，如果A ? B，B ? C，则A ? C ⑤ 如A ? B，A ? C，则A ? B∧C ⑥ 如A ? C，B ? C，则A∨B ? C 蕴含关系的性质 ① 自反性 A ? A ② 反对称性，如果A ? B，且B ? A，则必有： A ? B ③ A ? B 且A为永真式，则B必为永真式 ④ 传递性，如果A ? B，B ? C，则A ? C ⑤ 如A ? B，A ? C，则A ? B∧C ⑥ 如A ? C，B ? C，则A∨B ? C 蕴含关系的性质 ① 自反性 A ? A ② 反对称性，如果A ? B，且B ? A，则必有： A ? B ③ A ? B 且A为永真式，则B必为永真式 ④ 传递性，如果A ? B，B ? C，则A ? C ⑤ 如A ?