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)
如果xyP (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之后外层循环结束。
如果变量的域是无限的, 那么这个过程不能执行。
xyP (x,y)
x y P(x,y)
思考 x yP(x,y) 是否为真，如何判断？
思考 x yP(x,y) 是否为真，如何判断？
例1: 令 U 是实数域, 定义 P(x,y) : x ∙ y = 0， 下列语句的真值是什么：
xyP(x,y)
xyP(x,y)
xy P(x,y)
x y P(x,y)
例 2:令 U 是实数域, , 定义 P(x,y) : x / y = 1， 确定下列语句的真值：
xyP(x,y)
xyP(x,y)
xy 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) 为假。
是否能交换量词的次序?
逻辑等价吗? xyP(x,y) ≡ yxP(x,y)
Solution: Yes!左右两边总是有相同的真值。 x和y的值被选中的顺序无关紧要.
逻辑等价吗? xyP(x,y) ≡ yxP(x,y)
Solution: No! 对于命题函数P左右两边有不同的真值. 如令P(x,y)为“x + y = 0” ，U 是整数。x和y的值被选中的顺序是重要的.
命题 何时为真 何时为假
xyP(x,y)
yxP(x,y) 对每一对 x,y， P(x,y) 均为真 存在一对 x, y ，使得 P(x,y)为假
xyP(x,y) 对每个 x 都存在一个y使得 P(x,y) 为真 存在一个x ，使得P(x,y) 对每个 y总为假
xyP(x,y) 存在一个 x 使得P(x,y)对所有y均为真 对每个x ，存在一个y 使得 P(x,y) 为假
xyP(x,y)
yxP(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: 翻译语句为汉语
xy 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