离散数学第二章 谓词逻辑 习题课ppt课件

离散数学 第二章谓词逻辑习题课 一 命题符号化60页 2 x J x L x x L x S x x J x O x V x J j O j V j x L x J x 或者 x L x J x x S x L x C x x C x V x 或者 x C x V x h x C x O x L x i x W x C x H x j x W x J x C x k x L x y J y A x y l x S x y L y A x y 习题课 62页 2 x y P x P y E x y z L z R x y z t L t R x y t E t z 3 b 设R x x是实数 G x y x y x R x y R y G y x c 设R x x是实数 G x y x yf x y x yg x y xy x y z R x R y R z G f x y g x z 或者 x y z R x R y R z G x y xz 习题课 5 b 设N x x是数 A x y y是x的后继数 x N x A x 1 6 设A x x是戴眼镜的 B x x是用功的 C x x是大学生 D x x是大的 E x x是厚的 F x x是巨著 A x y x在看y a 那位 b 这本A a B a C a D b E b F b A a b 补充题 1 每个人的叔叔都是他父亲的弟弟 设 P x x是人 U x y y是x的叔叔 B x y x是y的弟弟 f x x的父亲 x P x y U x y B y f x 2 下面是判定一个年号是否为闰年的命题 年号能被4整除并且不能被100整除的为闰年 或者年号能被400整除的也是闰年 设Y x x是年号 D x y x可整除y R x x是闰年 x Y x D 4 x D 100 x R x D 400 x R x 66页 3 b P 2 1 Q x x 3 R x x 5 a 5 2 3 6 x P Q x R a P x Q x R a P Q 2 Q 3 Q 6 R 5 T T T F F T F F F F F4 b 对约束变元换名 x P x R x Q x x R x zS x z y P y R y Q y tR t uS x u 5 a 对自由变元代入 yA x y x B x z x zC x y z yA u y x B x v x zC x w z 习题课 72页 2 d 论域为 1 2 P 1 P 2 Q 1 1 Q 1 2 Q 2 1 Q 2 2 FTTTFF x y P x Q x y y P 1 Q 1 y y P 2 Q 2 y P 1 Q 1 1 P 1 Q 1 2 P 2 Q 2 1 P 2 Q 2 2 F T F T T F T F F F F F F 6 判断下面推证是否正确 x A x B x x A x B x x A x B x x A x B x x A x x B x x A x x B x x A x x B x x A x x B x 第 步错 由 到 用的是公式 x A x B x x A x x B x 无此公式 而是 x A x B x x A x x B x 应将 中的 换成 即 x A x B x x A x B x x A x B x x A x B x x A x B x x A x x B x x A x x B x x A x x B x x A x x B x 因为由公式E18P Q Q P x A x B x x A x x B x PQ得 x A x x B x x A x B x 75页 1 b x yP x y zQ z R x x yP x y zQ z R x x yP x y z Q z R x x yP x y z Q z R x x y z P x y Q z R x 2 c x P x x zQ x z zR x y z x P x x zQ x z zR x y z x P x x zQ x z zR x y z x P x u zQ u z tR u y t x u z t P x Q u z R u y t x u z t P x Q u z R u y t 此式既是前束析取范式 也是前束合取范式 79页 2 a 用CP规则证明 x P x Q x x P x x Q x 因为 x P x x Q x x P x x Q x x P x P 附加前提 x P x T E P a ES x P x Q x P P a Q a US Q a T I x Q x EG x P x x Q x CP 习题课 3 a 所有有理数是实数 某些有理数是整数 因此某些实数是整数 设Q x x是有理数R x x是实数I x x是整数 x Q x R x x Q x I x x R x I x x Q x I x P Q a I a ES Q a T I I a T I x Q x R x P Q a R a US R a T I R a I a T I x R x I x EG 习题课 b 任何人如果他喜欢步行 他就不喜欢乘汽车 每个人或者喜欢乘汽车或者喜欢骑自行车 有的人不爱骑自行车 因此有的人不爱步行 设A x x是人 B x x是喜欢步行 C x x喜欢乘汽车 D x x喜欢骑自行车 x A x B x C x x A x C x D x x A x D x x A x B x x A x D x P A a D a ES A a T I D a T I x A x B x C x P A a B a C a US B a C a T I x A x C x D x P A a C a D a US C a D a T I C a T I B a T I A a B a T I x A x B x EG 习题课 c 每个大学生不是文科生就是理工科生 有的大学生是优等生 小张不是理工科生 但他是优等生 因此如果小张是大学生 他就是文科生 设A x x是大学生 B x x是文科生 C x x是理工科生 D x x是优等生 a 小张 x A x B x C x x A x D x C a D a A a B a 习题课 x A x B x C x x A x D x C a D a A a B A A a P 附加前提 x A x B x C x P A a B a C a US B a C a T I C a D a P 习题课 补充题 小杨 小刘和小林为高山俱乐部成员 该俱乐部的每个成员是个滑雪者或登山者 没有一个登山者喜欢雨 而所有滑雪者都喜欢雪 凡是小杨喜欢的 小刘就不喜欢 小杨喜欢雨和雪 试证明该俱乐部是否有个是登山者而不是滑雪者的成员 如果有 他是谁 设 M x x是高山俱乐部成员 H x x是滑雪者 D x x是登山者 L x y x喜欢y a 小杨 b 小刘 c 小林 d 雨 e 雪 M x x是高山俱乐部成员 H x x是滑雪者 D x x是登山者 L x y x喜欢y a 小杨 b 小刘 c 小林 d 雨 e 雪 命题符号化为 M a M b M c x M x H x D x x D x L x d x H x L x e x L a x L b x L a d L a e L a d L a e P L a e T x L a x L b x P L a e L b e US L b e T I11 x H x L x e P H b L b e US H b T I12 x M x H x D x P M b H b D b US M b P H b D b T I11 D b T I10 D b H b T 谓词逻辑 解决这个问题的方法 在表示命题时 既表示出主语 也表示出谓语 就可以解决上述问题 这就提出了谓词的概念 令S x 表示x是大学生 a 小张 b 小李命题P表示成S a 小张是大学生 命题Q表示成S b 小李是大学生 从符号S a S b 可看出小张和小李都是大学生的共性 谓词逻辑 令N x x是自然数 I x x是整数 表示所有的 A x N x I x B N 8 C I 8 N 8 I 8 推理如此实现 N 8 I 8 符号S x N x I x 就是所谓的谓词 习题选讲 命题符号化 1 在一阶逻辑中将下列命题符号化 1 每个人都有心脏 2 有的狗会飞 3 没有不犯错误的人 4 发光的不都是金子 5 一切人都不一样高 6 并不是所有的汽车都比火车快 7 没有一个自然数大于等于任何自然数 8 有唯一的偶素数 9 不管黑猫白猫 抓住老鼠就是好猫 10 对平面上任意两点 有且仅有一条直线通过这两点 习题选讲 命题符号化 解 由于没指出个体域 故用全总个体域 1 每个人都有心脏 本命题的含义 对于每一个x 如果x是人 则x有心脏 因而应首先从宇宙间的一切事物中 将人分离出来 这就必须引入特性谓词 令M x x是人 H x x有心脏 命题符号化为 x M x H x 如果将其中的 改为 即 x P x H x 它表示的意思是 对于每个x x是人且x有心脏 这是一个假命题 而 每个人都有心脏 是真命题 这说明将命题 每个人都有心脏 符号化为 x P x H x 是错误的 习题选讲 命题符号化 2 有的狗会飞 命题的意思是 存在一个x 使得x是狗 并且x会飞 设D x x是狗 F x x会飞 命题符号化为 x D x F x 如果将其中的 改为 即 x D x F x 如果用a表示某只猫 则D a 为假 因而 D a F a 为真 所以 x D x F x 为真 而 有的狗会飞 为假 这说明将 有的狗会飞 符号化为 x D x F x 是错误的 3 没有不犯错误的人 命题的意思是 存在不犯错误的人是不可能的 只要是人 必然犯错误 设M x x是人 F x x犯错误命题符号化为 x M x F x x M x F x 4 发光的不都是金子 命题的意思是 不是发光的东西都是金子 存在着发光的东西不是金子 设L x x是发光的东西 G x x是金子 命题符号化为 x L x G x x L x G x 5 一切人都不一样高 设F x x是人 H x y x与y相同 L x y x与y一样高 命题符号化为 x F x y F y H x y L x y 或 x y F x F y H x y L x y 6 并不是所有的汽车都比火车快 设F x x是汽车 G y y是火车 H x y x比y快 命题符号化为 x y F x G y H x y 或 x y F x G y H x y 习题选讲 命题符号化 习题选讲 命题符号化 7 没有一个自然数大于等于任何自然数 设N x x是自然数 G x y x y命题符号化为 x N x y N y G x y 8 有唯一的偶素数 设 Q x x是偶数 P x x是素数 E x y x y命题符号化为 x Q x P x y Q y P y E x y 习题选讲 命题符号化 9 不管黑猫白猫 抓住老鼠就是好猫 需要考虑问题 只是限制黑猫白猫 还是包含其它颜色的猫 是指至少抓住一只就可以 还是抓住所有的 因此在描述命题时 总是将这些模糊概念做某种确切理解 设C x x是猫 W x x是白的 B x x是黑的G x x是好的 M x x是老鼠 K x x抓住y命题符号化为 x y C x M y B x W x K x y G x 习题选讲 命题符号化 10 对平面上任意两点 有且仅有一条直线通过这两点 设P x x是一个点 L x x是一条直线R x y z z通过x y E x y x等于y命题符号化为 x y P x P y E x y z L z R x y z u L u R x y u E u z 习题选讲 公式判断 2 判断下列各式是否是重言式 证明你的判断 1 x F x G x 2 x F x G x 3 x y F x G y H x y 4 x y P x y Q a y x y P x y Q x y 其中a是客体常量 解 1 不是重言式 2 不是重言式 3 不是重言式 4 不是重言式 习题选讲 公式判断 4 x y P x y Q a y x y P x y Q x y 其中a是客体常量 令个体域为某个元素个数大于等于2的有限整数集 其中a为最小的数 P x y x大于等于y Q x y x小于等于y x yP x y Q a y 解释为 存在一个x 对于所有的y 有x大于等于y 并且a小于等于y