面向计算机科学的数理逻辑答案.pdf

2 2 2 若 A Atom L p 则 n 0 m 1 m n 1 成立 若 B C Form L p B 中出现 的次数为 n1 次 出现原子公式的次 数为 m1 次 m1 n1 1 C 中出现 的次数为 n2 次 出现原子公式的次 数为 m2 次 m2 n2 2 A B C 则 m m1 m2 n n1 n2 1 故 m n 1 2 2 3 若 A Atom L p 则 deg A 0 此时 deg A 连接符在 A 中出现的次数 0 若 A B B Atom L p 则 deg A 1 此时 deg A 连接符在 A 中出现 的次数 1 若 A B C 则 deg A max deg A deg B 1 若 B C Atom L p 则 deg A 1 此时 deg A 连接符在 A 中出现的次数 1 若 B C Atom L p 即 B C D1 D2 Di Di Atom L p 则 deg A deg B 1 或 deg C 1 即B A A B A B A A A B A B ii A B A A B A iv A B C A B A A A B C A B A A B C A B C A B A B C A B C A B A A B A B C A B A B A B C A B A C A B C A B A C 定理定理 2 6 52 6 5 i A A A A A A A A iii A A A A A A A A A iV A A B A A A B A A A B v A A B A A A B A A A B A A B vi A A B A A A B A A A B A A B 定理定理 2 6 62 6 6 i A B B A A A B B A A B A B B A B A B B A B A B B A A B B A iii A B B A A A B B A A B A B B A B A B B A B A B B A A B B A iv A B B A A A B B A A B A B B A B A B B A B A B B A A B B A 2 6 72 6 7 i A A A A A A A A A A A A A A A A ii A A A A A A A A A A A A A A A A iii A B A B A A A B A B A A B A B A B A A B A B A B A B A B A B A B A B A B A iv A B A B B B A B A B B B A A B A B B B A A B A B B A A B A B B A A B A B B B vi A B B A B B A B A B B A B A B B 习题习题 2 6 2 6 5 5 A B A B A A B B A A B B A A B A A B A B A B A A 习题习题 2 6 2 6 6 6 A B A B A A B B A A B B A A B A A B A B A 习题习题 2 6 2 6 7 7 A B A B A A B B A A B B A A B A A B A B A B A 习题习题 2 6 2 6 8 8 A B A B A A B B A A B B A A B A A B A B A 定理定理 3 5 23 5 2 iii 先证 xA x A u 取 u 不在 x 中出现 xA x yA y 与上述相同 iv 先证 A u A u ref 取 u 不在 y 中出现 A u yA y xA x yA y 与上述相同 v 先证 x yA x y A u v 取不在 x y 中出现的 u v x yA x y y xA x y 与上述相同 vi A u v A u v 取不在 x y 中出现的 u v A u v y xA x y x yA x y y xA x y 与上述相同 vii xA x A u 取 u 不在 x 中出现 xA x xA x viii y A u y A u v 取不在 x y 中出现的 u v y A u y x A x v y A u y y x A x y x y A x y y x A x y 定理定理 3 5 33 5 3 1 1 A x x A x 1 A u x A x 取 u 不在 x 中出现 2 x A x A u x A x 3 x A x A u x A x 4 x A x A u 5 x A x x A x 6 x A x x A x 7 x A x x A x x A x 8 x A x x A x x A x 9 x A x x A x 1 xA x A u 取 u 不在 x 中出现 2 A u xA x 3 x A u xA x 2 2 xA x x A x 1 A u A u ref 取不在 x 中出现的 u 2 2 A u x A x 3 3 A u x A x x A x 4 4 A u x A x x A x ref 5 5 x A x A u 6 6 x A x x A x 7 x A x A u 取 u 不在 x 中出现 8 A u x A x 9 xA x x A x 10 x A x xA x x A x 11 x A x xA x x A x ref 12 x A x xA x 4 1 14 1 1 1 x y x y 2 y x x y 3 y x x y 4 x y z x1 x x1 x x1 z x1 5 x y z x y x z z y 4 1 24 1 2 1 x y x y 2 x y z x y x z z y 习题习题 4 2 24 2 2 假设 由 A1 A2 An 组成 A A1 A2 An A A1 A2 An 1 An A A1 A2 An 2 An 1 An A A1