离散数学(第四章)解析.ppt

第二章 谓词逻辑 说明： 第四章 小结 二、例 1．在一阶逻辑中将下面命题符号化，并讨论真值： （1）存在x，使得 x+7=5 (a) D1为全总个体域 (b) D2=N (c) D3=R （1） (a) ?xH(x)，H(x)：x+7=5，为真 (b) ?x(F(x)?H(x))，H(x)同(a)中，F(x)：x为自然数，为假. (c) ?x(F(x)?H(x))，H(x)同(b)中，F(x) ： x为实数，为真 本例说明：不同个体域内，命题符号化形式可能不同（也可能相同），真值可能不同（也可能相同）. 2．在一阶逻辑中将下列命题符号化 （1）大熊猫都可爱 （2）有人爱发脾气 （3）说所有人都爱吃面包是不对的 （4）没有不爱吃糖的人 （5）一切人都不一样高 （6）并不是所有的汽车都比火车快 由于没指出个体域，故用全总个体域 （1）?x(F(x)?G(x)) 其中，F(x): x为大熊猫，G(x): x可爱 （2）?x(F(x)?G(x)) 其中，F(x): x是人，G(x): x爱发脾气 （3）??x(F(x)?G(x)) 或 ?x(F(x)??G(x)) 其中，F(x): x是人，G(x):x爱吃面包 （4）??x(F(x)??G(x)) 或 ?x(F(x)?G(x)) 其中，F(x): x是人，G(x): x爱吃糖 （5）?x(F(x)??y(F(y)??H(x,y)??L(x,y))),或 ?x?y(F(x)?F(y)??H(x,y)??L(x,y)) 其中，F(x):x是人, H(x,y), x与y相同, L(x,y): x与y一样高 （6）??x?y(F(x)?G(y)?H(x,y)) 或 ?x?y(F(x)?G(y)??H(x,y)) 其中, F(x):x是汽车, G(y):y是火车, H(x,y):x比y快 说明： 使用的是全总个体域 (1)与(2)是两个基本公式的使用 (3)与(4)是否定式 (5)与(6)使用了二元谓词 (3)-(6)的不同符号化形式是等值的 3. 给定解释I如下: (a) 个体域D=N (b) =2 (c) (x,y)=x+y, (x,y)=x?y (d) 谓词 (x,y):x=y 说明下列公式在I下的涵义,并讨论真值 (1) ?xF(g(x,a),x) (2) ?x?y(F(f(x,a),y)?F(f(y,a),x)) (3) ?x?y?zF(f(x,y),z) (4) ?xF(f(x,x),g(x,x)) (5) ?x?y?zF(f(y,z),x) 作业: 1.预习§5.1 2 . 习题9、11(1)(3)(5) §2.2 一阶逻辑公式及其解释 一阶语言——用于一阶逻辑公式的形式语言 一、一阶语言F与合式公式 定义4.1 一阶语言F的字母表定义如下： （1）个体常项：a, b, c, …, ai, bi, ci, …, i ?1 （2）个体变项：x, y, z, …, xi, yi, zi, …, i ?1 （3）函数符号：f, g, h, …, fi, gi, hi, …, i ?1 （4）谓词符号：F, G, H, …, Fi, Gi, Hi, …, i ?1 （5）量词符号：?, ? （6）联结词符号：?, ?, ?, ?, ? （7）括号与逗号：(, ), ， §2.2 一阶逻辑公式及其解释 定义4.2 F的项的定义如下： （1）个体常项和个体变项是项. （2）若?(x1, x2, …, xn)是任意的n元函数，t1, t2, …, tn是任意的n个项，则?(t1, t2, …, tn) 是项. （3）所有的项都是有限次使用（1），（2）得到的. 其实，个体常项、变项是项，由它们构成的n元函数和复合函数还是项. §2.2 一阶逻辑公式及其解释 例1：D是个体名称的集合， x,y（∈D）为个体变项，a：张三，b：李四 所以x，y，a，b是项 假设f(x):x的父亲，F(x,y):x是y的父亲 f(a), f(f(a)), F(a,b), F(f(f(a)),b) 则f(a):张三的父亲，是项 f(f(a)):张三的祖父，是项 在谓词逻辑中，项起的是名词的作用，不是句子 §2.2 一阶逻辑公式及其解释 定义4.3 设R(x1, x2, …, xn)是F的任意n元谓词，t1, t2, …, tn是F的任意的n个项，则称R(t1, t2, …, tn)是F的原子公式. 其实