离散数学(高教版)第4章概要.ppt

* 练习5 5. 证明下列公式为永真式: (1) (?xF(x)??yG(y))??xF(x)??yG(y) (2) ?x(F(x)?(F(x)?G(x))) (A?B)?A?B的代换实例 设I是任意的一个解释, 对每一个x?DI, F(x)?(F(x)?G(x))恒为真 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 主要内容 一阶逻辑命题符号化 个体词、谓词、量词 一阶逻辑命题符号化 一阶逻辑公式及其解释 一阶语言 合式公式 合式公式的解释 永真式、矛盾式、可满足式 第四章 一阶逻辑基本概念 * 4.1 一阶逻辑命题符号化 个体词——所研究对象中可以独立存在的具体或抽象的客体 如 ：1、小王是程序猿。 3、x是有理数。 2、 是无理数。 4、这辆汽车是那头画图汪的。 个体常项：表示具体或特定的客体的个体词，用a, b, c表示 个体变项：表示抽象或者泛指的个体词，用x, y, z表示 个体域(论域)——个体变项的取值范围 有限个体域，如 {a, b, c}, {1, 2} 无限个体域，如 N, Z, R, … 全总个体域——由宇宙间一切事物组成 * 谓词 谓词——表示个体词性质或相互之间关系的词，常用F,G，H等表示。 1） 是无理数。 “…是无理数“是谓词，记为F， 整个陈述句表示为F( ). 2)x是有理数。 “…是有理数”是谓词，记为G 整个陈述句表示为G(x) 3)小王与小李同岁。 “…与…有理数”是谓词，记为H。 整个陈述句表示为H(a,b).其中a表示小王,b表示小李 4）x与y具有关系L。 * 谓词常项 表示具体性质或关系的谓词。 如, F(a)：a是人 谓词变项 表示抽象的或者泛指的性质或关系。如, F(x)：x具有性质F n（n?1）元谓词 含有n(n?1)个个体变项x1, x2 ,…, xn 的谓词P称作n元谓词，记为：P(x1, x2 ,…, xn ) 一元谓词(n=1)——表示性质, P(x1)表示x1具有性质P 多元谓词(n?2)——表示事物之间的关系，P(x1, x2 ,…, xn )表示x1, x2 ,…, xn 具有关系P。 如, L(x,y)：x与 y 有关系 L，L(x,y)：x?y，… 0元谓词——不含个体变项的谓词, 即命题常项 或命题变项 * 实例1 例1 将下列命题在一阶逻辑中用0元谓词将命题符号化，并讨论他们的真值。 (1) 只有2是素数，4才是素数。 在命题逻辑中符号化： p：4是素数, q:2是素数,符号化为： p→q 解：在一阶逻辑中：设一元谓词F(x)：x是素数，命题可符号化为： F(4) →F(2) 命题为真。 * (2)如果5大于4，则4大于6. 在命题逻辑中符号化： p：5大于4, q:4大于6,命题符号化为： p→q 解：在一阶逻辑中：设二元谓词G(x,y)：xy，命题可符号化为： G(5,4) →G(4,6) 命题为假。 * 实例1 练习：用0元谓词将命题符号化 (1) 墨西哥位于南美洲 (2) 是无理数仅当 是有理数 (3) 如果23，则34 在一阶逻辑中： (1) F(a)，其中，a：墨西哥，F(x)：x位于南美洲. (2) F( )?G( ), 其中，F(x)：x是无理数，G(x)：x是有理数 (3) F(2, 3)?G(3, 4)，其中，F(x, y)：xy，G(x, y)：xy * 量词 量词——表示个体常项或变项之间数量关系的词 全称量词?: 日常生活中常用的”一切的”，“所有的”，“每一个”，“任意的”，“凡”，“都”等词统称为全体量词， ?x : 对个体域中所有的x 如, ?xF(x)表示个体域中所有的x具有性质F ?x?yG(x,y)表示个体域中