程序代写 The Foundations: Logic and Proofs

The Foundations: Logic and Proofs

Chapter 1, Part II: 谓词逻辑
大连东软信息学院/大数据科学系 褚娜

Copyright By PowCoder代写 加微信 powcoder

谓词逻辑 (一阶逻辑, 谓词演算)
逻辑表达式到语句的翻译
语句到逻辑表达式的翻译

Section 1.4

“每名学生都要参加期末考试”。
“存在一个数是质数。”
“小华是三好学生。”
“小明是三好学生。”

谓词逻辑是一种表达能力更强的逻辑 :
变量: x, y, z
谓词: P, M
命题函数是命题的推广。
包括变量和一个谓词, 例如:P(x)
变量可以由其域中的元素替换。

“小华是三好学生。”
“小明是三好学生。”
P(x):x是三好学生
P(小华):小华是三好学生
P(小明):小明是三好学生

命题函数成为命题(有真值),当每个变量由其域中的元素替换时(或者被量词绑定, 后面介绍)。
语句 P(x)是命题函数 P 在 x的值。
例:令P(x) 表示 “x > 0” ,域是整数。 那么:
P(-3) 的真值是 F
P(0) 的真值是 F
P(3) 的真值是 T
通常域用U 表示。 该例中U 是整数。

令 “x + y = z” 表示为 R(x, y, z) , U (三个变量) 是整数。下列命题的真值是:
Solution: F
Solution: T
R(x, 3, z)
Solution: 不是命题

令 “x – y = z” 表示为 Q(x, y, z), U 是整数。下列命题的真值是:
Solution: T
Solution: F
Q(x, 3, z)
Solution: 不是命题

令P(x) 表示 “x > 0,” 下列演算的真值是:
P(3) ∨ P(-1) 答案: T
P(3) ∧ P(-1) 答案: F
P(3) → P(-1) 答案: F
P(3) → ¬P(-1) 答案: T
带有变量的表达式不是命题,因为没有真值。
P(3) ∧ P(y)
P(x) → P(y)
使用量化的方式,从命题函数生成一个命题

必须包括变量和谓词字母两个部分。
P(x) 称作一元谓词、一阶谓词
表示变量(个体)的性质
P(x1,x2,…,xn) 称作n元谓词
表示多个变量之间的关系

使用量词表示语句中的所有和有一些:
全称量词,符号: 
存在量词 , 符号: 
x P(x) 和 x P(x)

(1839-1914)

x P(x) 读作 “对所有 x, P(x)” 或 “对每个 x, P(x)”
如果P(x) 表示 “x > 0”,U 是整数, 那么 x P(x) 是假。
如果P(x) 表示 “x > 0”,U 是正整数, 那么 x P(x) 是真。
如果P(x) 表示“x 是奇数”,U 是整数, 那么  x P(x)是假。

x P(x) 读作“对某些x, 满足P(x)”, “有一个x 满足P(x),” “至少有一个x, 满足P(x).”
如果 P(x)表示 “x > 0” U 是整数, 那么 x P(x) 是真。 对U是正整数也是真。
如果 P(x) 表示 “x < 0” U 是正整数, 那么 x P(x) 是假。 如果 P(x) 表示 “x 是奇数” U 是整数, 那么 x P(x) 是真。 x P(x) 断言对于域中的所有x, P(x) 是真。 x P(x) 断言域中存在一个x,P(x) 是真。 在确定量化命题的真值时,借助循环与搜索来思考是有益的。 确定 x P(x)是否为真 ,在域里循环对每个 x 查看: 每次P(x) 为真, 那么 x P(x) 为真 如果在某次P(x) 为假, 那么 x P(x)为假,循环结束。 确定 x P(x)是否为真 ,在域里循环对每个 x 查看: 如果在某次, P(x)为真, 那么 x P(x)为真,循环结束。 如果直至循环结束,都没找到一个 x 使得P(x) 为真, 那么 x P(x) 为假。 尽管有时论域是无限的, 这种搜索过程不适用,但其思考方式是有益的。 命题 何时为真 何时为假 x P(x) ? ? x P(x) ? ? x P(x) 和  x P(x) 的真值依赖于命题函数P(x) 和论域 U。 如果 U 是正整数, P(x) 表示“x < 2”, 那么 x P(x) 为真,  x P(x) 为假。 如果 U是负整数,P(x)表示“x < 2”,那么x P(x) 和  x P(x) 均为真。 令P(x)为语句“x=x2”。如果论域是整数集合,下列各项的真值是什么? 如果论域是整数集合,下列各项的真值是什么? n(2n=3n) n(3n≤4n) 量词  和  优先级高于逻辑运算符 例: x P(x) ∨ Q(x) 表示 (x P(x))∨ Q(x) 而不是x (P(x) ∨ Q(x)) 当量词作用于变量x时,称此变量是约束的,否则称为自由的。 说明下列各式中量词的作用域与变元约束的情况。 唯一性量词(optional) !x P(x) 表示 “存在一个唯一的x使得P(x)为真”。 “恰好存在一个x 满足P(x)” “有且只有一个 x 满足P(x)” 如果 P(x) 表示 “x + 1 = 0” ,U是整数, 那么 !x P(x) 是真.。 如果 P(x) 表示 “x > 0,” 那么 !x P(x) 是假。
唯一性量词是可以避免的:
x (P(x) ∧y (P(y) → y =x))

例 1: 使用谓词和量词表达语句: “班上的每个学生都学过Java。”
首先,确定变量及其域U
定义命题函数 J(x) 表示 “x 学过Java”
解 1: 如果 U 是这个班上的所有学生
翻译为x J(x).
解 2: 如果 U 所有人
定义命题函数S(x) 表示 “x 是这个班的学生”
翻译为x (S(x)→ J(x)).
x (S(x) ∧ J(x)) 不对。 是什么意思?

例 2: 使用谓词逻辑翻译语句: “班上某些学生学过Java。”
解 1: 如果 U是这个班上的所有学生,
翻译为 x J(x)
解 2: 如果U 是所有人,
翻译为 x (S(x) ∧ J(x))
x (S(x)→ J(x)) 不对。 什么意思?

所有的人都是要呼吸的。
每个学生都要参加期末考试。
任何整数或是正的或是负的。

带有量词和谓词的命题是逻辑等价的当且仅当 有相同的真值 :
无论用什么谓词带入语句
无论表达式里的变量指定什么论域
S ≡T 表示 S 和 T 是逻辑等价的。
例: x ¬¬S(x) ≡ x S(x)

思考量词的合取、析取
一个全称量化命题等价于不带量词的命题的合取;
一个存在量化命题等价于不带量词的命题的析取。
如果 U 是整数 1,2, 和 3:

如果域是无限的,仍然可以如此认为:

假设命题函数P(x)的论域为0,1,2,3,4。使用析取、合取和否定写出下列命题。

量词与逻辑连接词的分配律问题?
逻辑等价? x (P(x) ∧ Q(x))≡ x P(x) ∧ x Q(x)
解: Yes! 左右两边总是有相同的真值,不论命题函数被 P(x) 和 Q(x)表示成什么.
逻辑等价? x (P(x) → Q(x))≡ x P(x) → x Q(x)
解: No! 左右两边可能有不同的真值。 P(x)为 “x 是鱼” , Q(x)为“x 有鳞”,域是所有动物。 那么设左边的真值为F, 因为有些鱼是没有鳞的. 但是右边的真值是T,因为不是所有的动物都是鱼

全称量词对于一个合取式是可分配的。
x (P(x) ∧ Q(x))≡ x P(x) ∧ x Q(x)
存在量词对于一个析取式是可分配的。
x (P(x) ∨ Q(x))≡ x P(x) ∨ x Q(x)

“班上的每个学生都学过Java”
谓词 J(x) 是 “x学过Java” 域是班上所有学生.
“并非班上每个学生都学过Java.”
也就是说“班上有个学生没有学过Java.”
符号化 ¬x J(x) 和 x ¬J(x) 是等价的

量化表达式的否定(续)
“班上有一个学生学过Java”其中 J(x) 是 “x学过Java.”
“并非班上有个学生学过Java” 也就是说“班上学生都没有学过Java”。
符号化 ¬ x J(x) 和  x ¬J(x) 是等价的

¬x P(x) ≡ x¬P(x)
¬x P(x) ≡ x¬P(x)

所有变量的论域是整数集合,写出下列量化语句的反例。
x(x>0 ∨ x<0) “班上的一些学生去过墨西哥。” 解: 令 M(x) 表示 “x 去过墨西哥” , S(x) 表示 “x 班上的学生,” U 是所有人。 x (S(x) ∧ M(x)) “班上的每个学生都去过墨西哥或加拿大。” 解: 令C(x) 表示 “x 去过加拿大。” x (S(x)→ (M(x)∨C(x))) Solution: 符号化 用谓词和量词表达下列语句 ① 航空公司的一位乘客可以被确认为贵宾资格,如果该乘客在一年中飞行里程超过25000英里,或在一年内乘坐航班的次数超过25次。 ② 一名男选手可获准参加本次马拉松比赛,如果他以往最好成绩在3小时内;而一名女选手可获准参加马拉松比赛,如果她以往最好成绩在3.5小时内。 R(x) :x爱慕虚荣 用量词、逻辑联结词和上述命题函数表达下列语句,假定论域是所有人的集合。 所有无知者均爱慕虚荣 Q(x):x的行为符合逻辑 R(x):x能管理鳄鱼 S(x):x被人轻视 用量词、逻辑联结词和上述命题函数表达下列语句,假定论域是所有人的集合。 能管理鳄鱼的人不被人轻视。 行为不合逻辑的人被人轻视。 系统规范说明书中量词的使用 许多系统规范说明书中涉及谓词和量词. 例, 翻译成谓词逻辑: “每封大于1MB的邮件会被压缩。” “如果一个用户处于活动状态, 那么至少有一条网络链路是有效的。” 确定语句的谓词及变量的域: 令 L(m, y) 表示 “邮件 m 大于 y MB” C(m)表示 “邮件m 会被压缩” A(u)表示 “用户 u 处于活动状态” S(n, x)表示 “网络链路n 处于x状态” 命题函数 Man(x) 表示 “x 是人” 并且 Mortal(x) 表示 “x 是凡人” ,域为所有人。 稍后,我们将展示如何证明该结论。 路易斯.卡罗尔的例子 前面两句称为前提,最后一句称为结论。 “所有的狮子都是凶猛的。” “有些狮子不喝咖啡。” “有些凶猛的狮子不喝咖啡。” 翻译上述语句为谓词逻辑。 令 P(x), Q(x), 和 R(x) 分别表示“x 是狮子,” “x 是凶猛的,” 和 “x 喝咖啡 ” (AKA Lewis Caroll) (1832-1898) 路易斯.卡罗尔的例子 “所有的狮子都是凶猛的。” “有些狮子不喝咖啡。” “有些凶猛的狮子不喝咖啡。” 令 P(x), Q(x), 和 R(x) 分别表示“x 是狮子,” “x 是凶猛的,” 和 “x 喝咖啡 ” x (P(x)→ Q(x)) x (P(x) ∧ ¬R(x)) x (Q(x) ∧ ¬R(x)) 后面我们将对其进行证明。 (AKA Lewis Caroll) (1832-1898) 逻辑程序设计(optional) Prolog是在上世纪70年代开发人工智能的研究人员的一种编程语言。 Prolog 程序包括Prolog 事实 和 Prolog 规则。 例,Prolog 事实包括: instructor(chan, math273). instructor(patel, ee222). instructor(grossman, cs301). enrolled(kevin, math273). enrolled(juana, ee222). enrolled(juana, cs301). enrolled(kiko, math273). enrolled(kiko, cs301). 谓词 instructor(p,c) 和 enrolled(s,c) 分别表示教授 p 教课程 c , 学生 s 选修了课程 c。 teaches(p,s) 表示 “教授 p 教学生 s”,用Prolog规则定义 : teaches(P,S) :- instructor(P,C), enrolled(S,C). 在逻辑上,这个Prolog 规则与下面的陈述是等价的. p c s(I(p,c) ∧ E(s,c)) → T(p,s)) Prolog程序被装入一个Prolog解释器。 Prolog解释器接收查询并返回使用Prolog程序答案。 例,使用我们的程序,可以给出以下查询: ?enrolled(kevin,math273). Prolog 产生应答: 注意 ? 表示 Prolog 解释器准备接收一个查询. ?enrolled(X,math273). X = kevin; ?teaches(X,juana). X = patel; X = grossman; Prolog解释器试图找到一个实例化的X。首先返回 X = kevin. Then the user types the ;表示另一个答案的请求。当无法找到另一个答案时,返回no. ?teaches(chan,X). X = kevin; Prolog 学习 http://www.learnprolognow.org/ 翻译自然语言到逻辑表达式 Section 1.5 嵌套量词,即一个量词出现在另一个量词的作用域内。 例: “每个实数都有逆” x y(x + y = 0) 其中,x 和 y 的域是实数。 x y(x + y = 0) 可以看作是x Q(x) 其中 Q(x) 是 y P(x, y) , P(x, y) 是 (x + y = 0) 如果xyP (x,y) 为真, 对x的所有值进行循环 : 对x的每个值, 对y的所有值进行循环 如果某个 x 和y, 使得P(x,y) 为假, 那么 x yP(x,y) 为假, 外层和内层循环均结束. x y P(x,y) 为真,对x的每个值, 对y的所有值P (x,y) 是真 如果x yP(x,y)为真, 对x的所有值进行循环 : 对x的每个值, 对y的所有值进行循环。 对x找到一个y,使得P(x, y) 为真,内层循环结束。 对x没有找到一个y ,使得P(x, y)为真, 外层循环结束,x yP(x,y) 为假. x y P(x,y) 为真,如果遍历了所有x之后外层循环结束。 如果变量的域是无限的, 那么这个过程不能执行。 xyP (x,y) x y P(x,y) 思考  x  yP(x,y) 是否为真,如何判断? 思考  x  yP(x,y) 是否为真,如何判断? 例1: 令 U 是实数域, 定义 P(x,y) : x ∙ y = 0, 下列语句的真值是什么: xyP(x,y) xyP(x,y) xy P(x,y) x  y P(x,y) 例 2:令 U 是实数域, , 定义 P(x,y) : x / y = 1, 确定下列语句的真值: xyP(x,y) xyP(x,y) xy P(x,y) x  y P(x,y) 令 P(x,y) 表示 “x + y = y + x”,假设U 是实数域。那么 x yP(x,y) 和y xP(x,y) 有相同的真值。 令Q(x,y)表示 “x + y = 0”假设U 是实数域。那么 x yQ(x,y) 为真, 但是 y xQ(x,y) 为假。 是否能交换量词的次序? 逻辑等价吗? xyP(x,y) ≡ yxP(x,y) Solution: Yes!左右两边总是有相同的真值。 x和y的值被选中的顺序无关紧要. 逻辑等价吗? xyP(x,y) ≡ yxP(x,y) Solution: No! 对于命题函数P左右两边有不同的真值. 如令P(x,y)为“x + y = 0” ,U 是整数。x和y的值被选中的顺序是重要的. 命题 何时为真 何时为假 xyP(x,y) yxP(x,y) 对每一对 x,y, P(x,y) 均为真 存在一对 x, y ,使得 P(x,y)为假 xyP(x,y) 对每个 x 都存在一个y使得 P(x,y) 为真 存在一个x ,使得P(x,y) 对每个 y总为假 xyP(x,y) 存在一个 x 使得P(x,y)对所有y均为真 对每个x ,存在一个y 使得 P(x,y) 为假 xyP(x,y) yxP(x,y) 存在一对x, y 使得P(x,y) 为真 对每一对x,y,P(x,y) 均为假 例 1: 翻译语句为汉语 x (C(x )∨ y (C(y ) ∧ F(x, y))) 其中, C(x) 是 “x 有一台计算机,” F(x,y) 是 “x 和 y 是朋友,” x 和 y 的域是学校全体学生。 解: 学校的每个学生或者有一台计算机或者有一个有计算机的朋友。 例 2: 翻译语句为汉语 xy z ((F(x, y)∧ F(x,z) ∧ (y ≠z))→¬F(y,z)) 解:有个学生,他的朋友之间都不是朋友。 例 : 翻译 “两个正整数的和是正整数。 “两个整数, 如果都是正的, 那么它们的和也是正的” 引入变量x 和 y, 定义域, 再重写为: “对所有的正整数 x 和 y, x + y 是正的。” x  y ((x > 0)∧ (y > 0)→ (x + y > 0))

例: 用量词表示语句“有一位妇女已搭乘过世界上每一条航线上的一个航班。”
令 P(w,f) 为 “w 搭乘过航班 f ” , Q(f,a) 为 “f 是航线 a 上的一个航班。”
w 的域是世界上所有的妇女, f是所有空中的航班, a 的域是所有航线。
w a f (P(w,f ) ∧ Q(f,a))

w a f (P(w,f ) ∧ Q(f,a))
Part 1: 使用量词表达语句 “没有一个妇女已搭乘世界上每一条航线上的一个航班。”
解: ¬w a f (P(w,f ) ∧ Q(f,a))
Part 2: 应用量词的德摩根律将否定不断移入到量词内。
¬w a f (P(w,f ) ∧ Q(f,a))
w ¬ a f (P(w,f ) ∧ Q(f,a)) 由的德摩根律
w  a ¬ f (P(w,f ) ∧ Q(f,a)) 由的德摩根律
w  a f ¬ (P(w,f ) ∧ Q(f,a)) 由的德摩根律
w  a f (¬ P(w,f ) ∨ ¬ Q(f,a))由∧的德摩根律

¬w a f (P(w,f ) ∧ Q(f,a))
w  a f (¬ P(w,f ) ∨ ¬ Q(f,a))
Part 3: 将结果翻译为语句?
“对每位妇女,存在一条航线,使得所有的航班,这位妇女要么没有搭乘过该航班,要么该航班不在这条航线上”

表达出下列语句的否定,并且所有的否定词紧跟在谓词之前。

重写下列语句,使否定只出现在谓词中(即否定词不在量词外边,也不在逻辑联结词的表达式外边)。

① 班上每个学生至少选修了一门离散数学课程。
② 班上有个一学生至少选修了一门离散数学课程。
③ 班上每个学生都去过校园里的一座楼的每个房间。
④ 班上有个学生至少去过校园里的一座楼的每个房间。
⑤ 班上每个学生至少都去过校园里的每座楼的一个房间。

使用数学合逻辑运算符、谓词及量词表达下列语句,论域是全体整数。
两个负整数的和负数。
两个正整数的差不一定是正数。
两个整数的平方和大于等于它们的和的平方。
两个整数的积的绝对值等于它们的绝对值的积。

嵌套量词到自然语言的翻译
数学语句到嵌套量词的翻译
自然语言语句到逻辑表达式的翻译

程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com