离散数学第2.4陈瑜.ppt

计算机科学与工程学院 主要内容 1.谓词公式的蕴涵 §2.4 谓词公式的蕴涵 一.谓词公式的蕴涵 定义2.16：设A和B是以为D论域的两个谓词公式,如果在任一解释下,当公式A取值真(1)时,公式B也取值真(1),则称A蕴涵B,记作A?B。 例4-1：设P(x)是以D为论域的谓词公式，证明: 证明：因为在某一解释下，当x=a，P(a)=1时，公式1右边在该解释下也取值1。同理，当在某解释下公式2的左边取值1时，则对任何x∈D，P(x)也在这个解释下取值1。 §2.4 谓词公式的蕴涵 一.谓词公式的蕴涵 定义2.16：设A和B是以为D论域的两个谓词公式,如果在任一解释下,当公式A取值真(1)时,公式B也取值真(1),则称A蕴涵B,记作A?B。 例4-1：设P(x)是以D为论域的谓词公式，证明: 证明：因为在某一解释下，当x=a，P(a)=1时，公式1右边在该解释下也取值1。同理，当在某解释下公式2的左边取值1时，则对任何x∈D，P(x)也在这个解释下取值1。 §2.4 谓词公式的蕴涵 定理2.8： A ? B iif A ? B是永真式。(略) 例4-2：证明P(x)→（?x）P(x)和（?x）P(x)→P(x)是永真式。 证明： 由前面例子可知P(x) ? （?x）P(x)，由定理2.8知P(x)→（?x）P(x)是永真式；实际上，当在某解释下P(x)取值1时，（?x）P(x)也取值 1；若P(x)取值0时，无论（?x）P(x)取什么值， P(x)→（?x）P(x)都取值1，所以是永真式。同理，（?x）P(x)→P(x)也是永真式。 §2.4 谓词公式的蕴涵 定理2.8： A ? B iif A ? B是永真式。 例4-2：证明P(x)→（?x）P(x)和（?x）P(x)→P(x)是永真式。 证明： 由前面例子可知P(x) ? （?x）P(x)，由定理2.8知P(x)→（?x）P(x)是永真式；实际上，当在某解释下P(x)取值1时，（?x）P(x)也取值 1；若P(x)取值0时，无论（?x）P(x)取什么值， P(x)→（?x）P(x)都取值1，所以是永真式。同理，（?x）P(x)→P(x)也是永真式。 §2.4 谓词公式的蕴涵 定理2.8： A ? B iif A ? B是永真式。 例4-2：证明P(x)→（?x）P(x)和（?x）P(x)→P(x)是永真式。 证明： 由前面例子可知P(x) ? （?x）P(x)，由定理2.8知P(x)→（?x）P(x)是永真式；实际上，当在某解释下P(x)取值1时，（?x）P(x)也取值 1；若P(x)取值0时，无论（?x）P(x)取什么值， P(x)→（?x）P(x)都取值1，所以是永真式。同理，（?x）P(x)→P(x)也是永真式。 §2.4 谓词公式的蕴涵 定理2.8： A ? B iif A ? B是永真式。 例4-2：证明P(x)→（?x）P(x)和（?x）P(x)→P(x)是永真式。 证明： 由前面例子可知P(x) ? （?x）P(x)，由定理2.8知P(x)→（?x）P(x)是永真式；实际上，当在某解释下P(x)取值1时，（?x）P(x)也取值 1；若P(x)取值0时，无论（?x）P(x)取什么值， P(x)→（?x）P(x)都取值1，所以是永真式。同理，（?x）P(x)→P(x)也是永真式。 §2.4 谓词公式的蕴涵 二.谓词演算中的蕴涵式(蕴涵定律) I11: （?x）P(x)∨（?x）Q(x)?（?x）(P(x)∨Q(x)) I12: （?x）(P(x)∧Q(x))?（?x）P(x)∧（?x）Q(x) I13: (?x)(P(x)→Q(x))?(?x)P(x)→(?x)Q(x) I14: （?x）P(x)→（?x）Q(x)?（?x）(P(x)→Q(x)) I15: (?x)(P(x)?Q(x))?(?x)P(x)?(?x)Q(x) §2.4 谓词公式的蕴涵 二.谓词演算中的蕴涵式(蕴涵定律) I11: （?x）P(x)∨（?x）Q(x)?（?x）(P(x)∨Q(x)) I12: （?x）(P(x)∧Q(x))?（?x）P(x)∧（?x）Q(x) I13: (?x)(P(x)→Q(x))?(?x)P(x)→(?x)Q(x) I14: （?x）P(x)→（?x）Q(x)?（?x）(P(x)→Q(x)) I15: (?x)(P(x)?Q(x))?(?x)P(x)?(?x)Q(x) §2.4 谓词公式的蕴涵 二.谓词演算中的蕴涵式(蕴涵定律) I11: （?x）P(x)∨（?x）Q(x)?（?x）(P(x)∨Q(x))