第2章-谓词逻辑

第二章第二章 谓词逻辑谓词逻辑 2 2 第第 43 页页 2 证明下列各式 1 xA xB x xB xx A x 证明 1 P xA xB x 2 US 1 A aB a 3 P xB x 4 US 3 B a 5 T 2 4 A a 6 EG 5 x A x 2 x A xx B xx A xB x 证明 1 P 假设前提 x A xB x 2 T xA xB x 3 T x A xB x 4 T x A xxB x 5 T x A x 6 T xB x 7 P x A xx B x 8 T 5 7 x B x 9 ES 6 B a 10 US 8 B a 11 T 9 10 B aB a 12 F 1 11 x A xB x 3 x A xB x x C xB xx C xA x 证明 1 P 假设前提 x C xA x 2 T 1 xC xA x 3 US 2 C aA a 4 T 3 C a 5 T 3 A a 6 P x A xB x 7 US 6 A aB a 8 T 5 7 B a 9 P x C xB x 10 US 8 C aB a 11 T 4 10 B a 12 T 8 11 B aB a 4 x A xB xx B xC xx C xx A x 证明 1 P x C x 2 US 1 C x 3 P x B xC x 4 US 3 B xC x 5 T 2 4 B x 6 P x A xB x 7 US 6 A xB x 8 T 5 7 A x 9 UG 8 x A x 3 用 CP 规则证明下列各式 1 x P xQ xx P xx Q x 证明 1 P 假设前提 x P x 2 US 1 P x 3 P x P xQ x 4 US 3 P xQ x 5 T 2 4 Q x 6 UG 5 x Q x 7 CP 1 6 x P xx Q x 2 x P xQ xx P xx Q x 证明 由于 x P xx Q xxQ xx P x xQ xx P x 因此 原题等价于证明 x P xQ xxQ xx P x 1 P 假设前提 xQ x 2 US 1 Q x 3 P x P xQ x 4 US 3 P xQ x 5 T 2 4 P x 6 UG 5 x P x 7 CP 1 6 xQ xx P x 4 将下列命题符号化并推证其结论 1 所有的有理数是实数 某些有理数是整数 因此某些实数是整数 解 首先定义如下谓词 是有理数 P xx 是实数 R xx 是整数 I xx 于是问题符号化为 x P xR xx P xI xx R xI x 推理如下 1 P x P xI x 2 ES 1 P aI a 3 P x P xR x 4 US 3 P aR a 5 T 2 P a 6 T 2 I a 7 T 4 5 R a 8 T 6 7 R aI a 9 EG 8 x R xI x 2 任何人如果他喜欢步行 他就不喜欢乘汽车 每一个人或者喜欢乘汽车或者喜欢骑自 行车 有的人不爱骑自行车 因而有的人不爱步行 解 首先定义如下谓词 是人 P xx 喜欢步行 F xx 喜欢乘汽车 C xx x 喜欢骑自行车 B x 于是问题符号化为 x P xF xC xx P xC xB x x P xB xx P xF x 推理如下 1 P x P xB x 2 ES 1 P aB a 3 T 2 P a 4 T 2 B a 5 P x P xC xB x 6 US 5 P aC aB a 7 T 3 6 C aB a 8 T 4 7 C a 9 P x P xF xC x 10 US 9 P aF aC a 11 T 8 10 P aF a 12 T 11 P aF a 13 T 3 12 F a 14 T 3 13 P aF a 15 EG 14 x P xF x 3 每个科学工作者都是刻苦钻研的 每个刻苦钻研而且聪明的科学工作者在他的事业中 都将获得成功 华为是科学工作者并且他是聪明的 所以 华为在他的事业中将获得成功 解 首先定义如下谓词 是科学工作者 P xx 是刻苦钻研的 Q xx 是聪明的 R xx 在他的事业中将获得成功 S xx 定义个体 a 华为 于是命题符号化为 x P xQ xx P xQ xR xS x P aR aS a 推理如下 1 P x P xQ x 2 US 1 P aQ a 3 P P aR a 4 T 3 P a 5 T 3 R a 6 T 2 4 Q a 7 P x P xQ xR xS x 8 US 7 P aQ aR aS a 9 T 3 6 P aQ aR a 10 T 8 9 S a 4 每位资深名士或是中科院院士或是国务院参事 所有的资深名士都是政协委员 张伟 是资深名士 但他不是中科院院士 因此 有的政协委员是国务院参事 解 首先定义如下谓词 是资深名士 P xx 是中科院院士 Q xx 是国务院参事 R xx 是政协委员 S xx 定义个体 a 张伟 于是命题符号化为 x P xQ xR xx P xS x P aQ ax S xR x 推理如下 1 P P aQ a 2 T 1 P a 3 T 1 Q a 4 P x P xS x 5 US 4 P aS a 6 T 2 5 S a 7 P x P xQ xR x 8 US 7 P aQ aR a 9 T 2 8 Q aR a 10 T 3 9 R a 11 T 6 10 S aR a 12 EG 11 x S xR x 5 每一个自然数不是奇数就是偶数 自然数是偶数当且仅当它能被 2 整除 并不是所有 的自然数都能被 2 所整除 因此 有的自然数是奇数 解 首先定义如下谓词 是自然数 N xx 是奇数 Q xx 是偶数 O xx 能被 2 整除 P xx 于是命题符号化为 x N xQ xO xx N xO xP x x N xP xx N xQ x 推理如下 1 P x N xP x 2 T 1 x N xP x 3 ES 2 N aP a 4 T 3 N a 5 T 3 P a 6 P x N xO xP x 7 US 6 N aO aP a 8 T 4 7 O aP a 9 T 5 8 O a 10 P x N xQ xO x 11 US 10 N aQ aO a 12 T 4 11 Q aO a 13 T 9 12 Q a 14 T 4 13 N aQ a 15 EG 14 x N xQ x 6 如果一个人怕困难 那么他就不会获得成功 每个人或者获得成功或者失败过 有些 人未曾失败过 所以 有些人不怕困难 解 首先定义如下谓词 是人 P xx 怕困难 Q xx 曾获得成功 R xx 曾获得失败 S xx 于是命题符号化为 x P xQ xR xx P xR xS x x P xS xx P xQ x 推理如下 1 P x P xS x 2 ES 1 P aS a 3 T 2 P a 4 T 2 S a 5 P x P xR xS x 6 US 5 P aR aS a 7 T 3 6 R aS a 8 T 4 7 R a 9 P x P xQ xR x 10 US 9 P aQ aR a 11 T 8 10 P aQ a 12 T 11 P aQ a 13 T 3 12 Q a 14 T 3 13 P aQ a 15 EG 14 x P xQ x 6 试找出下列推导过程中的错误 并问结论是否有效 如果有效 写出正确的推导过程 解 错误 第 2 行的 y 是泛指 第 4 行的 y 是特制 更改如下 1 P x P x 2 ES 1 P y 3 P x P xQ x 4 US 3 P yQ y 5 T 2 4 Q y 6 EG 5 x Q x 7 用构成推导过程的方法证明下列蕴含式 1 x P xxP xQ xR x x P xx Q xxy R xR y 证明 1 2 1 3 4 3 5 6 1 5 7 6 8 2 9 7 8 10 x P xP P aES x Q xP Q bES x P xxP xQ xR xP xP xQ xR xT P aQ aR aUS P aQ aT R aT P bQ bR bUS 6 11 4 12 10 11 13 9 12 14 13 15 14 P bQ bT R bT R aR bT y R aR yEG xy R xR yEG 2 x P xx Q xx P xQ x 证明 1 P x P xx Q x 2 T 1 x P xx Q x 3 T 2 xP xx Q x 4 T 3 xP xQ x 5 T 4 x P xQ x 2 3 第第 46 页页 1 将下列公式化为前束范式 1 x P xy Q y 解 x P xy Q y xP xy Q y xyP xQ y 2 xyz P x yP y zu Q x y u 解 xyz P x yP y zu Q x y u xyz P x yP y zu Q x y u xyzP x yP y zu Q x y u xyzuP x yP y zQ x y u 3 xy A x yxy B x yyA y xB x y 解 xy A x yxy B x yyA y xB x y xy A x yxy B x yyA y xB x y xy A x yxy B x yyA y xB x y xy A x yuv B u vzA z u B u z xyuvzA x yB u vA z uB u z 2 求等价于下面公式的前束主析取范式与前束主合取范式 1 xQxPxxQxxPx 解 前束主析取范式 xQxPxxQxxPx yQxQxPyx yQxQxPyx yQyPyxQxxPx xQxPxxQxxPx xQxPxxQxxPx 前束主合取范式 xQxPxxQxxPx yQxQyQxPyx yQxQxPyx yQyPyxQxxPx xQxPxxQxxPx xQxPxxQxxPx 2 x P xyz Q x zz R x y 解 前束析取范式 x P xyz Q x zy R x y xP xyz Q x zy R x y xP xyz Q x zy R x y xP xyz Q x zu R x u xP xyzQ x zuR x u xyzuP xQ x zR x u xyzuP xQ x zR x u 由于是基本和 因此前束合取范式与前束析取范式一样 P xQ x zR x u x P xyz Q x zz R x y xyzuP xQ x zR x u 3 zyxRzzxQzxxPx 前束主析取范式 zyxRzzxQzxxPx vyuRzuQxPvzux vyuRvzuQzuxPx zyxRzzxQzxxPx 前束主合取范式与前束主析取范式相同 4 x P xQ x yy P yz Q y z 解 前束析取范式 x P xQ x yy P yz Q y z x P xQ x yy P yz Q y z xP xQ x yy P yz Q y z x P xQ x yy P yz Q y z x P xQ x uy P yz Q u z xyzP xQ x uP yQ u z 前束合取范式 x P xQ x yy P yz Q y z xyzP xQ x uP yQ u z xyzP xP yQ u zQ x uP yQ u z xyzP xP yP xQ u zQ x uP yQ x u Q u z 3 将下列公式化为斯柯林范式 1 x P xy Q x y zuHxuHuGuGyxQxPzyxu zuHzxuHuGuGyxQxPyxu uGuGyxQxPyxu uGuGyxQxPyxu yxQxPyx yxQyxPx 2 xyz P x zP y zu Q x y u cyxvHzyxvJbxvIyxvI avHxvHvGv