当前位置：文档之家 › 一阶逻辑等值演算与推理课件(离散数学)分解

一阶逻辑等值演算与推理课件(离散数学)分解

  • 格式：ppt
  • 大小：713.51 KB
  • 文档页数：62

下载文档原格式

  / 62

合集下载

离散数学 第五章的课件

离散数学 第五章的课件


xF(x,y,z)yG(x,y,z)
tF(t,y,z)yG(x,y,z) tF(t,y,z)wG(x,w,z)
个体变项符号，其余部分不 变
（换名规则） （换名规则）
或者
xF(x,y,z)yG(x,y,z) xF(x,t,z)yG(x,y,z) xF(x,t,z)yG(w,y,z) （代替规则） （代替规则）
10
实例
例5.4 给定解释I如下： （a）个体域 D＝{2,3}. （b）D中特定元素 a =2 （c）D上的特定函数 f (x) ： f (2) =3, f (3)=2 . （d）D上的特定谓词 F (x) ： F (2)=0, F (3)=1; G (x,y)： G (2,2)= G(2,3)= G(3,2)=1，G(3,3)=0； L (x,y)： L (2,2)= L (3,3)=1， L (2,3)= L(3,2)=0； 求下列各式在I下的真值。 (2) x(F(f(x))∧G(x,f(x))) (F(f(2))∧G(2,f(2)))∨(F(f(3))∧G(3,f(3))) (F(3)∧G(2,3))∨(F(2)∧G(3,2)) (1∧1)∨(0∧1) 1
注意:(3)(4)说明量词的顺序不能随便颠倒
13
实例
例5.5 证明下列等值式。 (1) x(M(x)∧F(x)) x(M(x)→F(x)) (2) x(F(x)→G(x)) x(F(x)∧G(x)) (3) xy(F(x)∧G(y)→H(x,y)) xy(F(x)∧G(y)∧H(x,y)) (4) xy(F(x)∧G(y)∧L(x,y)) xy(F(x)∧G(y)→L(x,y))
或
x(F(x,y) yG(x,y,z)) x(F(x,y) tG(x,t,z))
离散数学课件第二章 一阶逻辑

离散数学课件第二章 一阶逻辑


§2.1
一阶逻辑的基本概念
原因：命题逻辑不考虑命题之间的内在联系
和数量关系。
要反映这种内在联系，就要对命题逻 辑进行分析 , 分析出其中的个体词、谓词和 量词，再研究它们之间的逻辑关系，总结出 正确的推理形式和规则，这就是一阶(谓词) 逻辑的研究内容。 办法：将命题再次细分。
解决这个问题的方法： 在表示命题时，既表示出主语，也表示 出谓语，就可以解决上述问题。这就提出了 谓词的概念(谓词是用来刻划个体词的性质 或事物之间的关系的词,谓词S(x)相当于一 个函数).
§2.1 一阶逻辑的基本概念
2.1.1 个体、谓词和命题函数 在谓词逻辑中，将原子命题分解为谓词和个体两部分。
主语 谓语 宾语
讨论对象 对象的性质或关系
讨论对象
个体词（组）
谓词
个体词（组）
1、定义：在原子命题中，所描述的对象称为个体；用 以描述个体的性质或个体间关系的部分，称为谓词。
例2.1：分析下列个命题中的个体和谓词
如何表示？
2.1.3 命题函数 谓词本身并不是命题，只有谓词的括号内填入足够 的个体，才变成命题。 设 H(x) 是谓词 表示 x “能够到达山顶” ， l 表示个体李四， t 表示老虎， c 表示汽车， 那么H（l）， H（t）， H（c），等分别表示各 个不同的命题：但它们有一个共同的形式， 即 H（x） 当 x 分别取 l、 t、 c 时 就表示“李四能够到达山顶”，“老虎能够到达山 顶”，“汽车能够到达山顶”。
Discrete Mathematics
刘师少
Tel： 86613747（h） E-mail： lss@
授课:
51学时
教学目标:
知识、能力、素质
第二章 一阶逻辑
离散数学一阶逻辑等值演算与推理32页PPT

离散数学一阶逻辑等值演算与推理32页PPT

离散数学一阶逻辑等值演算与推理
•
46、寓形宇内复几时，曷不委心任去 留。
•
47、采菊东篱下，悠然见南山。
•
48、啸傲东轩下日 有所长 。
•
50、环堵萧然，不蔽风日；短褐穿结 ，箪瓢 屡空， 晏如也 。
谢谢你的阅读
❖ 知识就是财富 ❖ 丰富你的人生
71、既然我已经踏上这条道路，那么，任何东西都不应妨碍我沿着这条路走下去。——康德 72、家庭成为快乐的种子在外也不致成为障碍物但在旅行之际却是夜间的伴侣。——西塞罗 73、坚持意志伟大的事业需要始终不渝的精神。——伏尔泰 74、路漫漫其修道远，吾将上下而求索。——屈原 75、内外相应，言行相称。——韩非
离散数学 第二章一阶逻辑PPT课件

离散数学 第二章一阶逻辑PPT课件


注: 个体变项取值范围:个体域(论域) 有限的事物
无特殊说明
无限的事物
（宇宙间的一切事物称为全总个体域）
谓词常项:具体性质或关系的谓词
谓词 谓词变项:抽象或泛指的谓词
F,G,H,…
个体变项x具有性质F,记作F(x) 谓词符号化
个体变项x,y具有性质F,记作F(x,y)
注:下文中称这种个体变项和谓词的联合体F(x),F(x,y)为谓词.
谓词 用来刻画个体词的性质或个体词之间关系
的词。
例如: ① 2 是无理数.
②王宏是程序员.
③小李比小赵高2厘米.
个体词: 2 , 王宏,小李,小赵
谓词: …是无理数,
个体词性质
…是程序员, …比…高2厘米.
个体词之间关系
4
个体常项:具体和特定的个体词 a,b,c,… 个体词
个体变项:抽象或泛指的个体词 x,y,z,…
要求: 1)个体域为有理数集合. 2)个体域为实数集合. 3)个体域为全总个体域.
6
谓词中的其它概念:
1).元数:谓词中所包含的个体词数. 一元谓词:个体词性质的.
2).n元谓词 n元谓词:个体词之间关系的.
表示方法定义域:个体词变项的个体域.
P(x1,x2,…xn) 值域:{0,1}
注: n元谓词不是命题,真值无法确定.要使之成为命题,必须:
指定某一谓词常项代替P
用n个个体常项代替n个体变项
注: (1)0元谓词也不是命题.要使之成为命题,必须:指定某一
谓词常项代替L.
(2)命题逻辑中的简单命题,也可以用0元谓词表示.因而 命题可看成是谓词的特殊情况.
例1: 将下列命题用0元谓词符号化.
(1)2是素数且是偶数.
一阶逻辑等值演算与ppt课件

一阶逻辑等值演算与ppt课件

取解释I：个体域为自然数集合N；
〔1〕取F〔x〕：x是奇数，替代A〔x〕； 取G〔x〕：x是偶数，替代B〔x〕。
那么x〔F〔x〕∨G〔x〕〕为真命题，
而xF〔x〕∨ xG〔x〕为假命题。
两边不等值。
;
例5.2
证 明
〔2〕x〔A〔x〕∧B〔x〕〕 <≠> xA〔x〕∧xB〔
x〕
x〔F〔x〕∧G〔x〕〕：有些x既是奇数又是偶数为 假命题；
〔x〕〕 〔2〕┐x〔F〔x〕→G〔x〕〕 x〔F〔x〕∧┐G
〔x〕〕 〔3〕┐xy〔F〔x〕∧G〔y〕→H〔x，y〕〕
xy〔F〔x〕∧G〔y〕∧┐H〔x,y〕〕 〔4〕┐xy〔F〔x〕∧G〔y〕∧L〔x，y〕〕
xy〔F〔x〕∧G〔y〕→┐L〔x,y〕〕
;
例5.5的证明
〔1〕 ┐x〔M〔x〕∧F〔x〕〕 x〔M〔x〕→┐F 〔x〕〕 ┐x〔M〔x〕∧F〔x〕〕 x┐〔M〔x〕∧F〔x〕〕 x〔┐M〔x〕∨┐F〔x〕〕 x〔M〔x〕→┐F〔x〕〕
而xF〔x〕∧xG〔x〕：有些x是奇数并且有些x是 偶数为真命题。
两边不等值。
阐明 全称量词“〞对“∨〞无分配律。 存在量词“〞对“∧〞无分配律。
当B〔x〕换成没有x呈现的B时，那么有
x〔A〔x〕∨B〕 xA〔x〕∨B
x〔A〔x〕∧B〕 xA〔x〕∧B
;
例5.3—消去量词
例5.3 设个体域为D＝{a,b,c}，将下面各公式的量词消去：
〔双
〔2〕F〔x〕→G〔y〕 ┐F〔x〕∨G〔y〕 〔蕴 涵等值式〕
〔3〕x〔F〔x〕→G〔y〕〕→ zH〔z〕
┐〔x〔F〔x〕→G〔y〕〕∨zH〔z〕
〔蕴涵等值式〕
;
消去量词等值式
离散数学课件-5-一阶逻辑等值演算与推理

离散数学课件-5-一阶逻辑等值演算与推理

离散数学课件-5-一阶逻辑等值演算与推理第五章一阶逻辑等值演算与推理§1 一阶逻辑等值式与置换规则定义：A，B两个谓词公式，若A?B是永真式，则称A与B是等值的，记为A?B。

常用等值式：第一组：命题逻辑中常用等值式的代换实例第二组：一阶逻辑中的特有等值式1．消去量词当D={a1, a2,…, a n}时，有①?xA(x)?A(a1)∧A(a2)∧…∧A(a n)②?xA(x)?A(a1)∨A(a2)∨…∨A(a n)2．量词否定①??xA(x)??x?A(x)②﹁?xA(x)??x?A(x)3．辖域收缩与扩张①?x(A(x)∨B)??xA(x)∨B②?x(A(x)∧B)??xA(x)∧B③?x(A(x)∨B)??xA(x)∨B④?x(A(x)∧B)??xA(x)∧B4．量词分配①?x(A(x)∧B(x))??xA(x)∧?xB(x)②?x(A(x)∨B(x))??xA(x)∨?xB(x)演算规则：1．置换规则：φ(A)：含A的谓词公式φ(B)：用公式B替换φ(A)中所有A之后的公式若A?B，则φ(A)?φ(B)。

2．换名规则：设A是谓词公式，把A中某指导变元对应的全部约束出现替换为A中未出现过的符号，而A中其余部分不变，设所得谓词公式为A′，则A?A′。

3．代替规则设A是谓词公式，把A中某个体变项的全部自由出现替换为A中未出现过的符号，而A中其余部分不变，设所得公式为A′，则A?A′。

例①?xF(x,y,z)→?yG(x,y,z)sF(s,y,z)→?tG(x,t,z) 换名②?x(F(x,y)→?yG(x,y,z))x(F(x,t)→?yG(s,y,z)) 代替例给定解释I：D I ={2,3}，a：2，b：3G(x,y)：G(a, a)=G(a, b)=G(b, a)=1，G(b, b)=0F(x)：F(a)=0，F(b)=1① ?x(F(x)∧G(x,a))(F(a)∧G(a,a))∧(F(b)∧G(b,a))?(0∧1)∧(1∧1)? 0② ?x?yG(x,y)x(G(x,a)∧G(x,b))(G(a,a)∧G(a,b))∨(G(b,a)∧G(b,b))(1∧1)∨(1∧0)1例证明：﹁?x(F(x)→G(x))??x(F(x)∧﹁G(x)) 解：﹁?x(F(x)→G(x))﹁?x(﹁F(x)∨G(x))x﹁(﹁F(x)∨(G(x)x(F(x)∧﹁G(x))§2 前束范式定义：设A是谓词公式，若A有如下形式Q1x1Q2x2…Q k x k B其中Q i(1≤i≤k)为?或?，B为不含量词的公式，则称A为前束范式。

离散数学2课件 第5章 一阶逻辑等值演算与推理

离散数学2课件 第5章 一阶逻辑等值演算与推理


15/58
求前束范式的实例
例4 求下列公式的前束范式 (3) xF(x)y(G(x,y)H(y))
解: xF(x)y(G(x,y)H(y)) zF(z)y(G(x,y)H(y)) 换名规则 zy(F(z)(G(x,y)H(y))) 辖域收缩扩张规则
或 xF(x)y(G(z,y)H(y)) 代替规则 xy(F(x)(G(z,y)H(y)))
x(F(x)G(x)) x(F(x)G(x)) x(F(x)G(x))
x(F(x)G(x))
量词否定等值式 置换
置换
7/58
实例
例1 将下面命题用两种形式符号化, 并证明两者等值. (2) 不是所有的人都爱看电影
解: 令F(x)：x是人，G(x)：爱看电影. x(F(x)G(x)) 或 x(F(x)G(x))
第二组 基本等值式生成的推理定律 如, xF(x) xF(x), xF(x) xF(x) xF(x)xF(x), xF(x) xF(x)
第三组 其他常用推理定律
(1) xA(x)xB(x) x(A(x)B(x))
(2) x(A(x)B(x)) xA(x)xB(x)
(3) x(A(x)B(x)) xA(x)xB(x)
x(F(x)G(x)) x(F(x)G(x)) x(F(x)G(x)) x(F(x)G(x))
量词否定等值式 置换 置换
8/58
实例
例2 将公式化成等值的不含既有约束出现、又有自
由出现的个体变项: x(F(x,y,z)yG(x,y,z)) 解: x(F(x,y,z)yG(x,y,z))
x(F(x,y,z)tG(x,t,z))
11/58
实例
例3 设个体域D={a,b,c}, 消去下述公式中的量词: (2) xyF(x,y)
一阶逻辑ppt课件

一阶逻辑ppt课件


；.
28
➢使用特性谓词M（x），所给命题就可以符号化为: 1. x（M（x）→F（x）） 2. x（M（x）∧G（x））
注意：特性谓词在不同量词下的不同用法
；.
29
使用量词时的注意点 ➢在不同的个体域中，命题符号化的形式可能不一样 ➢如果事先没有给出个体域，都应以全总个体域为个体域 ➢在引入特性谓词后，使用全称量词与存在量词符号化的形式是不同的 ➢个体域和谓词的含义确定之后，n元谓词要转化为命题至少需要n个量词
解 ：本题未指定个体域，因而取个体域为全总个体域。
；.
35
1. 凡偶数均能被2整除
F（x）：x 是偶数 G（x）：x 能被2整除 x（F（x）→G（x）） 2. 存在着偶素数。 F（x）：x 是偶数 H（x）：x 是素数 x（F（x）∧H（x））
；.
36
3.没有不犯错误的人 M（x）：x 是人
➢ 存在量词：对应日常语言中的“存在着”，“有一个”，“至少有一个”等 词，用符号“”表示
➢ x表示存在个体域里的个体， xF（x）表示至少存在个体域里的一个个体具有性质F
；.
25
带量词命题的符号化 例如： 1.所有的人要死的 2.有的人活百岁以上
由于量词与个体域之间有紧密的联系，在考虑命题符号化问题时，必须先明确个体 域 假设个体域D是人类的集合
一阶逻辑
离散数学
；.
1
Байду номын сангаас
内容回顾
命题逻辑的特点和局限性: 命题是命题演算的基本单位 不再对简单命题进行分解 无法研究命题的内部结构及命题之间内在的联系 在推理方面存在的局限性
例如，无法判断著名的“苏格拉底三段论”的正确性 课P37
；.
离散数学一阶逻辑.ppt

离散数学一阶逻辑.ppt

义可以看出，对于任意的谓词A(x), 都有：
xA(x) A(a1)∧A(a2) ∧…∧A(an); xA(x) A(a1)∨A(a2) ∨…∨A(an).
多个量词同时出现时，不能随意颠倒他们的顺序。
15
例题
对任意的x，存在着y，使得 x+y=5.
H(x,y)表示x+y=5 可符号化成：x y H(x,y) 不可符号化成： y x H(x,y)
P37. 例题2.2、2.3、2.4、2.5
16
第二章 一阶逻辑
第2章 一阶逻辑
2.1 一阶逻辑基本概念 2.2 一阶逻辑合式公式及解释 2.3 一阶逻辑等值式
17
2.2 一阶逻辑公式及解释
合式公式(简称公式) 个体变项的自由出现和约束出现 解释与分类
18
一阶逻辑合式公式采用字母表
个体词:是可以独立存在的客体. 个体常项:用小写的英文字母
a,b,c,d…. 个体变项:用小写的英文字母
x,y,z…. 个体域:个体的取值范围. 全总个体域:指宇宙中的一切事物.
7
2.谓词的相关概念
谓词: 表示个体词性质或相互之间关系的词
谓词常项：F(a)：a是人 谓词变项：F(x)：x具有性质F
在解释N下,下面那些公式为
真命题;
真?那些公式为假?
(3) x+y=y+z
(1)xF(g(x,a),x);
真值不确定,不是命题.
(2)xy(F(f(x,a),y)→F(f(y,a) ,x));
(3)F(f(x,y),f(y,z))
30
公式的分类
设A为一公式(谓词公式) 如果A在任何解释下都是真的, 称A为 逻辑有效式(或永真式); 如果A在任何解释下都是假的, 称A为 矛盾式(或永假式); 若至少存在一个解释使A为真, 则称A 是可满足式(协调式).
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
( F (a ) F (b) F (c )) (G(a ) G(b) G(c ))
18
例题
(3)当个体域D={a,b}
xy( F ( x, y ) G( x, y ))
x((F ( x, a ) G( x, a )) ( F ( x, b) G( x, b)))
((F (a , a ) G(a , a )) ( F (a , b) G(a , b))) ((F (b, a ) G(b, a )) ( F (b, b) G(b, b)))
x( F ( x ) G( x ))
这句话相当于“有些学生没有上课”。
x( F ( x ) G( x ))
4
一、等值式的概念
定义：若AB为永真式，则称A与B是等 值的，记作 AB，并称AB为等值式。
其中A、B是一阶逻辑中任意的两个合式公
式。
5
二、基本等值式
1. 命题逻辑中16组基本等值式的代换实例
7
二、基本等值式
“并不是所有的人都是黄皮肤。” xA( x ) 这句话相当于 “有的人不是黄定等值式
xA( x ) xA( x ) xA( x ) xA( x )
8
二、基本等值式
4.
量词辖域收缩与扩张等值式
设A(x)是含x自由出现的公式，B中不含x的出现。 关于全称量词：
x(A(x)B)xA(x)B
x(A(x)B)xA(x)B
x(A(x)B)xA(x)B
x(BA(x))BxA(x)
9
二、基本等值式
关于存在量词: x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(BA(x))BxA(x)
等值演算的基础： （1）一阶逻辑的基本等值式； （2）置换规则、换名规则、代替规则。
12
例题
例1：下面的命题都有两种不同的符号化形 式，写出其中的一种，然后通过等值演算
得到另一种。
(1) 没有不犯错误的人
(2) 不是所有的人都爱看电影
13
例题
(1) 没有不犯错误的人 令F(x)：x是人，G(x)：x犯错误
F (a ) F (b) F (c ) (G (a ) G (b) G (c ))
16
例题
解法二：
x( F ( x ) yG( y )) xF ( x ) yG( y ) 量词辖域收缩与扩张等值式 F (a ) F (b) F (c ) (G(a ) G(b) G(c ))
10
二、基本等值式
5.
量词分配等值式 x(A(x)B(x))xA(x)xB(x) x(A(x)B(x))xA(x)xB(x)
注意：对无分配律，对无分配律
11
三、等值演算与置换规则
置换规则：设(A)是含有公式A的公式， 用公式B置换(A)中所有的A后得到新的公
式(B)，若AB, 则(B)(A)
小结：采用不同的演算过程同样可以达到消去量词 的目的，但是如何演算才更简单呢？结论是将量词 辖域尽可能的缩小，然后再消量词。
17
例题
（ 2 ）xy( F ( x ) G( y ))
x((F ( x ) G(a )) ( F ( x ) G(b)) ( F ( x ) G(c ))) ((F (a ) G(a )) ( F (a ) G(b)) ( F (a ) G(c )))
例：xF(x)yG(y) xF(x)yG(y)
(xF(x)yG(y)) xF(x)yG(y)
即命题逻辑中的基本等值式在谓词逻 辑中均适用。
6
二、基本等值式
2.
有限个体域中，消去量词等值式 设个体域为D={a1,a2,…,an} xA(x) A(a1)A(a2)…A(an) xA(x) A(a1)A(a2)…A(an)
15
例题
例2：设个体域D={a,b,c}，在D中消去下列
公式中的量词。
（ 1 ）x( F ( x ) yG( y ))
x( F ( x ) yG( y ))
两次使用 x( F ( x ) (G (a ) G(b) G (c ))) “消去等值 F (a ) (G (a ) G(b) G (c )) 式” F (b) (G (a ) G (b) G (c )) F (c ) (G (a ) G (b) G (c ))
x( F ( x ) G( x ))
x( F ( x ) G( x )) x( F ( x ) G( x )) x(F ( x ) G( x )) x( F ( x ) G( x ))
量词否定等值式 德摩根律的代入实例 蕴涵等值式的代入实例
((F (b) G(a )) ( F (b) G(b)) ( F (b) G(c ))) ((F (c ) G(a )) ( F (c ) G(b)) ( F (c ) G(c )))
方法2：
xy( F ( x ) G( y )) xF( x ) yG( y )
14
例题
(2) 不是所有的人都爱看电影 令F(x)：x是人，G(x)：爱看电影
x( F ( x ) G( x ))
x( F ( x ) G ( x )) x(F ( x ) G ( x )) x(F ( x ) G ( x )) x( F ( x ) G ( x )) 蕴涵等值式的代入实例 量词否定等值式 德 摩根律的代入实例
第五章 一阶逻辑等值演算与推理
1
本章主要内容
5.1一阶逻辑等值式与置换规则 5.2一阶逻辑前束范式 5.3一阶逻辑的推理理论
2
5.1一阶逻辑等值式与置换规则

等值式的概念 基本等值式 等值演算与置换规则
3
所有的学生都上课了，这是错的。 令 F(x): x是学生, G(x): x上课了。