《数理逻辑》课程考试模拟试卷 1.(每题2分,共10分)判断题(若正确,则在题前的括号中打√;否则,打 ): (a)()若合式公式A是永真式当且仅当合式公式B是永真式,则AB 是永真式。 (b)()若合式公式A是可满足的,则~A是不可满足的。 (c)()v((,x)y~(,y)是可满足的 (d)()设P是一个由P系统增加单个合式公式pq作为公理所得到 的系统,则P是协调的。 (e)()假定除个体常元外,一阶逻辑形式系统F1和F2的其余符号相 同。若F1F2,则Th(F1)CTh(F2)∩L(F1)。 2.(每题6分,共18分)简答题: (a)试证明P的推理规则MP是独立的 (b)试给出以下公式的矫正范式和前束范式 Vx( <u)((x+ <x+w)Vz(< w)) (c)试指出 Vx(P()^Q() y(~(y,)()) 中的自由变元与约束变元,并说明什么样的项t对这些自由变元是自 由的。 3.(每题8分,共计32分)请在F=系统中给出以下定理的证明序列。(只能 用F=的公理、推理规则、试卷给出的导出规则和定理) (a)~(AB)A(注:此小题不允许使用[P]规则) (b)若r,P(x)Q(x),则r,VxP(x)3xQ(x) (c)Vx(P()= =)P()(P()(y) x=) (d)F 3x(P(x)VxP() 4.(10分)设r1和2是一阶逻辑合式公式集,且r1与2不协调试证明: 必有一个合式公式A使得r1A且2~A。 5.(10分)在F系统中证明:若个体变元y在合式公式A中没有出现,则 SySJA=A 6.(10分)给定合式公式A: (~(,) VaVyVz( R) R(y, 2) ~(, 2)) VayR(,) 其中,R是二元谓词常元。试证明A的任何模型的论域不会是单元素集; 对任何自然数n≥2,给出一个论域中有n个元素且满足A的解释。 7.(10分)试给出一阶逻辑系统(带等词)F的一个合式公式集,使得对 的解释<D,>是T的等词模型当且仅当D是无穷集合,并证明你的结 论。 1
✂✁☎✄☎✆☎✝✟✞✡✠☞☛☞✌☞✍☞✎☞✏☞✍☞✑ 1. (✒✔✓ 2 ✕✔✖✂✗ 10 ✕) ✘✔✙✔✓✛✚✢✜✔✣✔✤✔✖✂✥✔✦✔✓✔✧✔★✔✩✔✪✬✫✮✭ √ ✯✂✰✥✔✖✂✭ × ✱✳✲ (a) ( ) ✜✵✴✵✶✵✷✵✶ A ✸✵✹✵✺✵✶✵✻✵✼✵✽✵✻✵✴✵✶✵✷✵✶ B ✸✵✹✵✺✵✶✵✖✾✥ A ⊃ B ✸✔✹✔✺✔✶✔✿ (b) ( ) ✜✔✴✔✶✔✷✔✶ A ✸✔❀✔❁✔❂✔★✔✖❃✥ ∼ A ✸✔❄✔❀✔❁✔❂✔★✔✿ (c) ( )∀x(P(x, x) ⊃ ∀y ∼ P(x, y)) ✸✔❀✔❁✔❂✔★✔✿ (d) ( ) ❅ P 0 ✸✔❆✔❇✬❈ P ❉✔❊✔❋✔●✔❍✔❇✔✴✔✶✔✷✔✶ p ⊃ q ■✔❏✔✷✔❑✔▲✔▼✔◆ ★✔❉✔❊✔✖❃✥ P 0 ✸✔❖✔P✔★✔✿ (e) ( ) ◗❙❘❙❚❙❇❙❯❙❱❙❲❙❳❙✖❃❆❙❨❙❩❙❬❙❭❙✶❙❉❙❊ F1 ❪ F2 ★❙❫❙❴❙❵❙✪❙❛ ❜ ✿❃✜ F1 ⊆ F2 ✖❃✥ Th(F1) ⊂ Th(F2) T L(F1) ✿ 2. (✒✔✓ 6 ✕✔✖❃✗ 18 ✕) ❝✔❞✔✓✔✲ (a) ❡✔❢✬❣ P ★✔❤✔❑✔✐✔✥ MP ✸✔❥✔❦✔★✔✿ (b) ❡✔❧✔♠✔♥✔♦✔✷✔✶✔★✔♣✔✣✔q✔✶❪✧✔r✔q✔✶✔✿ ∀x(x < u) ⊃ (∃v∀w(x + v < x + w) ⊃ ∀z(z × v < z × w)) (c) ❡✔s✔♠ ∀x(P(x) ∧ Q(y) ⊃ ∃y(∼ S(y, z) ∧ R(x))) ✫✮★✉t✮❈✮✈✔❲✔✇✔①✔r✔✈✔❲✔✖❃②✔③✬❣⑤④✔⑥❙⑦✔★❙⑧ t ⑨✔⑩✔❶✉t✮❈✮✈✔❲✔✸✉t ❈✮★✔✿ 3. (✒✔✓ 8 ✕✔✖❷✗✔❸ 32 ✕) ❹✔✦ F = ❉✔❊✬✫✮❧✔♠✔♥✔♦✔❘✔❑✔★✔❢✬❣✮❺✔❻✔✿ (❼✔❽ ❾✔❿ F = ★✔✷✔❑✔➀❃❤✔❑✔✐✔✥✔➀❃❡✔➁✔❧✔♠✔★✔➂✔♠✔✐✔✥❪❘✔❑) (a) `∼ (A ⊃ B) ⊃ A (➃✔✲❃➄✔➅✔✓✔❄✔➆✔➇❾✔❿ [P] ✐✔✥) (b) ✜ Γ, P(x) ` Q(x) ✖❃✥ Γ, ∀xP(x) ` ∃xQ(x) ✿ (c) ∀x(P(x) ≡ x = b) ` P(b) ∧ ∀x∀y(P(x) ∧ P(y) ⊃ x = y) (d) ` ∃x(P(x) ⊃ ∀xP(x)) 4. (10 ✕) ❅ Γ1 ❪ Γ2 ✸✔❆✔❨✔❩✔❬✔✴✔✶✔✷✔✶✔➈✔✖➉✼ Γ1 ✇ Γ2 ❄✔❖✔P✔✿➉❡✔❢✬❣✮✲ ➊✔➋❆✔❇✔✴✔✶✔✷✔✶ A ❾ ▼ Γ1 ` A ✼ Γ2 `∼ A ✿ 5. (10 ✕) ✦ F ❉✔❊✬✫✮❢✬❣✮✲❃✜✔❇✔❯✔✈✔❲ y ✦✔✴✔✶✔✷✔✶ A ✫✮➌➋ ♠✔➍✔✖❃✥ S y xS x y A = A 6. (10 ✕) ❧✔❘✔✴✔✶✔✷✔✶ A ✲ ∀x(∼ R(x, x)) ∧ ∀x∀y∀z(R(x, y) ∧ R(y, z) ⊃∼ R(x, z)) ∧ ∀x∃yR(x, y) ❫✬✫✮✖ R ✸✔➎✔❲✔➏✔➐✔❱✔❲✔✿➑❡✔❢✬❣ A ★✔➒✔➓✔➔✔→✔★✔➣✔↔✔❄✔↕✔✸✔❍✔❲✔➙✔➈✯ ⑨✔➒✔➓✉t➜➛✔➝ n ≥ 2 ✖❃❧✔♠✔❆✔❇✔➣✔↔✬✫➋ n ❇✔❲✔➙✔✼✔❁✔❂ A ★✔➞✔➟✔✿ 7. (10 ✕) ❡✵❧✵♠✵❆✵❨✵❩✵❬✵❉✵❊ (➠✵➡✵➐)F = ★✵❆✵❇✵✴✵✶✵✷✵✶✵➈ Γ ✖ ❾ ▼✵⑨ F = ★✔➞✔➟ < D, I0 > ✸ Γ ★✔➡✔➐✔➔✔→✔✻✔✼✔✽✔✻ D ✸✔➢✔➤✔➈✔✴✔✖⑤②✔❢✬❣✮➥✔★✔➦ ➣✔✿ 1
阶逻辑(带等词)演算系统=导出规则和定理 A∈r THA (∈+) TAF B TAFB T.NAHB I卜B I卜A A TAVB’T+BVA TAFC TBFC TFAVB THC AI卜B FA^B I卜A∧B I卜AAB F.A卜B I上AB THA TFADB FADB TAHB TAH B THNA I卜AF~A I卜B THA THA (≡+) TFADB TFBA r}A≡B IFA三B IA2B’IB2A I卜A≡B ~A三~B P卜A (-) xA(在r中无自由出现) (t对A中x是自由的) TA(对A中x是自由的) TAFB(x在rU{B}中不自由) F彐xAr,SAB y对A中的x是自由的且 I卜B y在PU{BxA,B}中不自由 (EA) x=x(x为个体变元) (EAS) x=3(S2A=S4)(x,y对A中的z是自由的) (a3) 三ySC (y在C中不自由且y对C中的x是自由的) ([P]) 若r}A1,……,P卜An,且A1∧…AAnB为P-永真的,则卜B 若A,M在A中为肯定的且MN,则r+AN (D suba) 若+A,M在A中为否定的且+NM,则AN (≡su) 若A,且M≡N,则r+A ([sub-x])若ThA,x在r中不自由且t对A中的x为自由的则rhSA ([sub-p)若rhA,p在r中不出现且D对A中的p为自由的则SA
➧➉➨➉➩➉➫ (➭➉➯➉➲) ➳➉➵➉➸➉➺ F = ➻➉➼➉➽➉➾➉➚➉➪➉➶ (∈) A ∈ Γ Γ ` A (∈+) Γ ` B Γ, A ` B (∈−) Γ, A ` B Γ, ∼ A ` B Γ ` B (∨+) Γ ` A Γ ` A ∨ B , Γ ` A Γ ` B ∨ A (∨−) Γ, A ` C Γ, B ` C Γ ` A ∨ B Γ ` C (∧+) Γ ` A Γ ` B Γ ` A ∧ B (∧−) Γ ` A ∧ B Γ ` A , Γ ` A ∧ B Γ ` B (⊃+) Γ, A ` B Γ ` A ⊃ B (⊃−) Γ ` A Γ ` A ⊃ B Γ ` B (⊃ ¬) Γ ` A ⊃ B Γ `∼ B ⊃∼ A (¬+) Γ, A ` B Γ, A `∼ B Γ `∼ A (¬−) Γ ` A Γ `∼ A Γ ` B (¬¬+) Γ ` A Γ `∼∼ A (¬¬−) Γ `∼∼ A Γ ` A (≡+) Γ ` A ⊃ B Γ ` B ⊃ A Γ ` A ≡ B (≡−) Γ ` A ≡ B Γ ` A ⊃ B , Γ ` A ≡ B Γ ` B ⊃ A (≡ ¬) Γ ` A ≡ B Γ `∼ A ≡∼ B (∀+) Γ ` A Γ ` ∀xA (x ➹ Γ ➘➉➴❃➷➉➬ ➼➉➮) (∀−) Γ ` ∀xA Γ ` S x t A (t ➱ A ➘ x ✃❃➷➉➬❒❐) (∃+) Γ ` S x t A Γ ` ∃xA (t ➱ A ➘ x ✃❃➷➉➬❒❐) (∃−) Γ, A ` B Γ, ∃xA ` B (x ➹ Γ ∪ {B} ➘➉❮❃➷➉➬) (C) Γ ` ∃xA Γ, S x yA ` B Γ ` B y ➱ A ➘➉❐ x ✃❃➷➉➬❒❐➉❰ y ➹ Γ ∪ {∃xA, B} ➘➉❮❃➷➉➬ (EA) Γ ` x = x (x Ï➉Ð➉Ñ➉Ò➉Ó) (EAS) ` x = y ⊃ (S z xA ≡ S z yA) (x, y ➱ A ➘➉❐ z ✃❃➷➉➬❒❐) (αβ) Γ ` A Γ ` A ∀xC ∀ySx y C , Γ ` A Γ ` A ∃xC ∃ySx y C (y ➹ C ➘➉❮❃➷➉➬❒❰ y ➱ C ➘➉❐ x ✃❃➷➉➬❒❐) ([P]) ÔΓ ` A1, · · · , Γ ` An, ❰A1 ∧ · · · ∧ An ⊃ BÏ P- Õ➉Ö➉❐, ➾Γ ` B ([⊃ sub1]) ÔΓ ` A, M ➹ A ➘➉Ï➉×➪❐➉❰ ` M ⊃ N, ➾Γ ` A M N . ([⊃ sub2]) ÔΓ ` A, M ➹ A ➘➉Ï➉Ø➪❐➉❰ ` N ⊃ M, ➾Γ ` A M N . ([≡ sub]) ÔΓ ` A, ❰ ` M ≡ N, ➾Γ ` A M N . ([sub − x]) Ô Γ ` A Ù x ➹ Γ ➘➉❮❃➷➉➬❒❰ t ➱ A ➘➉❐ x Ï❃➷➉➬❒❐ ➾Γ ` S x t A. ([sub − p]) Ô Γ ` A Ù p ➹ Γ ➘➉❮➼➉➮❰ D ➱ A ➘➉❐ p Ï❃➷➉➬❒❐ ➾Γ ` S p DA. 2