屈婉玲离散数学第四章课件.ppt

1、1主要内容主要内容l 一阶逻辑命题符号化一阶逻辑命题符号化 个体词、谓词、量词个体词、谓词、量词 一阶逻辑命题符号化一阶逻辑命题符号化l 一阶逻辑公式及其解释一阶逻辑公式及其解释 一阶语言一阶语言 合式公式合式公式 合式公式的解释合式公式的解释 永真式、矛盾式、可满足式永真式、矛盾式、可满足式第四章第四章 一阶逻辑基本概念一阶逻辑基本概念24.1 一阶逻辑命题符号化一阶逻辑命题符号化 个体词个体词所研究对象中可以独立存在的具体或抽象的客体所研究对象中可以独立存在的具体或抽象的客体 个体常项个体常项：具体的事务，用：具体的事务，用a,b,c表示表示 个体变项个体变项：抽象的事物，用：抽象的事物，

2、用x,y,z表示表示 个体域个体域(论域论域)个体变项的取值范围个体变项的取值范围 有限个体域，如有限个体域，如 a,b,c,1,2 无限个体域，如无限个体域，如 N,Z,R,全总个体域全总个体域由宇宙间一切事物组成由宇宙间一切事物组成3谓词谓词谓词谓词表示个体词性质或相互之间关系的词表示个体词性质或相互之间关系的词 谓词常项谓词常项 如如,F(a)：a是人是人 谓词变项谓词变项 如如,F(x)：x具有性质具有性质F n（n 1）元谓词）元谓词 一元谓词一元谓词(n=1)表示性质表示性质 多元谓词多元谓词(n 2)表示事物之间的关系表示事物之间的关系 如如,L(x,y)：x与与 y 有关系有关

3、系 L，L(x,y)：x y，0元谓词元谓词不含个体变项的谓词不含个体变项的谓词,即命题常项即命题常项 或命题变项或命题变项4量词量词量词量词表示数量的词表示数量的词 全称量词全称量词:表示所有的表示所有的.x:对个体域中所有的对个体域中所有的x 如如,xF(x)表示个体域中所有的表示个体域中所有的x具有性质具有性质F x yG(x,y)表示个体域中所有的表示个体域中所有的x和和y有关系有关系G 存在量词存在量词:表示存在表示存在,有一个有一个.x:个体域中有一个个体域中有一个x 如如,xF(x)表示个体域中有一个表示个体域中有一个x具有性质具有性质F x yG(x,y)表示个体域中存在表示个

4、体域中存在x和和y有关系有关系G x yG(x,y)表示对个体域中每一个表示对个体域中每一个x都存在一个都存在一个y使得使得 x和和y有关系有关系G x yG(x,y)表示个体域中存在一个表示个体域中存在一个x使得对每一个使得对每一个y,x和和y有关系有关系G5实例实例1例例1 用用0元谓词将命题符号化元谓词将命题符号化 (1)墨西哥位于南美洲墨西哥位于南美洲 (2)是无理数仅当是无理数仅当 是有理数是有理数 (3)如果如果23，则，则33，q：3y，G(x,y)：xy x(F(x)y(G(y)L(x,y)或者或者 x y(F(x)G(y)L(x,y)(2)令令F(x)：x是无理数，是无理数，

5、G(y)：y是有理数，是有理数，L(x,y)：xy x(F(x)y(G(y)L(x,y)或者或者 x y(F(x)G(y)L(x,y)9实例实例4例例4 在一阶逻辑中将下面命题符号化在一阶逻辑中将下面命题符号化 (1)没有不呼吸的人没有不呼吸的人 (2)不是所有的人都喜欢吃糖不是所有的人都喜欢吃糖解解(1)F(x):x是人是人,G(x):x呼吸呼吸x(F(x)G(x)x(F(x)G(x)(2)F(x):x是人是人,G(x):x喜欢吃糖喜欢吃糖 x(F(x)G(x)x(F(x)G(x)10实例实例5例例5 设个体域为实数域设个体域为实数域,将下面命题符号化将下面命题符号化 (1)对每一个数对每一

6、个数x都存在一个数都存在一个数y使得使得xy (2)存在一个数存在一个数x使得对每一个数使得对每一个数y都有都有xy解解 L(x,y):x5,G(x):x4,公式为真公式为真 解释解释I2:个体域个体域N,F(x):x5,G(x):xy 真真解释解释2:D2=Z,F(x):x是偶数是偶数,G(x):x是奇数是奇数,H(x,y):xy 假假30练习练习55.证明下列公式为永真式证明下列公式为永真式:(1)(xF(x)yG(y)xF(x)yG(y)(2)x(F(x)(F(x)G(x)(AB)AB的代换实例的代换实例设设I是任意的一个解释是任意的一个解释,对每一个对每一个x DI,F(x)(F(x)G(x)恒为真恒为真