离散数学-4 一阶逻辑基本概念

时间:2024-03-28 12:21:47

   

离散数学-4 一阶逻辑基本概念

   

离散数学-4 一阶逻辑基本概念

   

个体常项:表示具体或特定的客体的个体词,用a, b, c表示

个体变项:表示抽象或者泛指的个体词,用x, y, z表示

个体域(论域)——个体变项的取值范围

有限个体域,如 {a, b, c}, {1, 2}

无限个体域,如 N, Z, R, …

全总个体域——由宇宙间一切事物组成

谓词——表示个体词性质或相互之间关系的词,常用F,G,H等表示。

谓词常项 表示具体性质或关系的谓词。 如, F(a)a是人

谓词变项 表示抽象的或者泛指的性质或关系。如, F(x)x具有性质F

nn1)元谓词

含有n(n1)个个体变项x1, x2 ,…, xn 的谓词P称作n元谓词,记为:P(x1, x2 ,…, xn )

一元谓词(n=1)——表示性质, P(x1)表示x1具有性质P

多元谓词(n2)——表示事物之间的关系,P(x1, x2 ,…, xn )表示x1, x2 ,…, xn 具有关系P

, L(x,y)xy 有关系 LL(x,y)xy,…

0元谓词——不含个体变项的谓词, 即命题常项或命题变项

量词——表示个体常项或变项之间数量关系的词

全称量词: 日常生活中常用的"一切的","所有的","每一个","任意的","凡","都"等词统称为全体量词,

x : 对个体域中所有的x

存在量词: 表示存在, 有一个,有的,至少有一个.

x : 个体域中有一个x

  • 一般,在全总个体域中,
    • 对全称量词,特性谓词常作蕴涵的前件(如:x(M(x)F(x)));
    • 对存在量词,特性谓词常作合取项(如:x(M(x)G(x)))。

    定义4.1 L是一个非逻辑符集合, L生成的一阶语言L 的字母表包括下述符号:

    非逻辑符号

    (1) 个体常项符号:a, b, c, …, ai, bi, ci, …, i 1

    (2) 函数符号:f, g, h, …, fi, gi, hi, …, i 1

    (3) 谓词符号:F, G, H, …, Fi, Gi, Hi, …, i 1

    逻辑符号

    (4) 个体变项符号:x, y, z, …, xi, yi, zi, …, i 1

    (5) 量词符号:,

    (6) 联结词符号:, , , , 

    (7) 括号与逗号:(, ),

    定义4.2 L 的项的定义如下:

    (1) 个体常项和个体变项是项.

    (2) (x1, x2, …, xn)是任意的n元函数,t1, t2, …, tn是任意的n个项,则(t1, t2, …, tn) 是项.

    (3) 所有的项都是有限次使用(1),(2)得到的. , a, x, x+y, f(x), g(x,y)等都是项

    定义4.3 R(x1, x2, …, xn)是L 的任意n元谓词,t1, t2, …, tn是L 的任意n个项,则称R(t1, t2, …, tn)是L 的原子公式. 如,F(x, y), F(f(x1, x2), g(x3, x4))等均为原子公式

    定义4.4 L 的合式公式定义如下:

    (1) 原子公式是合式公式.

    (2) A是合式公式,则 (A)也是合式公式

    (3) A, B是合式公式,则(AB), (AB), (AB), (AB)也是合式公式

    (4) A是合式公式,则xA, xA也是合式公式

    (5) 只有有限次地应用(1)(4)形成的符号串才是合式公式.

    合式公式简称公式

    , F(x), F(x)G(x,y), x(F(x)G(x))

    xy(F(x)G(y)L(x,y))等都是合式公式

    定义4.5 在公式 xA xA 中,称x指导变元A为相应量词的辖域. xx的辖域中,x的所有出现都称为约束出现A中不是约束出现的其他变项均称为是*出现.

    定义4.6 若公式A中不含*出现的个体变项,则称A封闭的公式,简称闭式.

  • 将谓词公式中的约束变元更改名称符号,这一过程称为约束变元换名
  • 约束变元的换名规则
    • 1)换名时,更改的变元名称的范围是量词中的指导变元,以及该量词辖域中所出现的所有该变元,公式的其余部分不变;
    • 2)换名时一定不能更改为该量词辖域中的其他变元名称。
  • 为了使一个变元在同一个公式中只以一种身份出现,除了进行约束变元换名外,也可以进行*变元代入
  • *变元的代入规则
    • 1)将给定公式中出现该*变元的每一处都用新的个体变元替换;
    • 2)新变元不允许在原公式中以任何约束形式出现。

    定义4.7 谓词逻辑中公式A的每一个解释(赋值)I由以下几部分构成:

    1)非空个体域D;

    2)D中的某些特定元素;

    3)D中的某些特定的函数;

    4)D中某些特定的谓词。

    用一个解释I解释一个谓词公式A包括:将I的个体域D作为A的个体域,A中的个体常元用I中的特定元素代替, A中的函数用I中的特定函数代替,谓词用I上的特定谓词代替。把这样得到的公式记作A'。称A'为A在I下的解释,或A在I下被解释成A'。

    定义4.8 若公式A在任何解释下均为真, 则称A永真式(逻辑有效式). A在任何解释下均为假, 则称A矛盾式(永假式,不可满足的). 若至少有一个解释使A为真, 则称A可满足式

    定义4.9 A0是含命题变项 p1, p2, …, pn的命题公式,A1, A2, …, Ann个谓词公式,用Ai (1in) 处处代替A0中的pi,所得公式A称为A0代换实例.

    定理4.2 重言式的代换实例都是永真式(逻辑有效的),矛盾式的代换实例都是矛盾式(不可满足的). 【可以用来判断公式的类型,可满足的进行解释就行】

题型

1、一阶逻辑命题符号化

注意是不是全总个体域,不是的话要用特性谓词将人从宇宙间的所有事物中分离出来

2、在一阶逻辑中将简单的数学命题符号化

3、给定解释和赋值,解释给定的公式

4、证明公式是可满足式

取一真一假的两个解释,注意说个体域

5、证明永真式或矛盾式

利用代换实例证明