안녕하세요.
문제풀이중 도움을 받고자 글 남깁니다.
조금의 도움이라도 좋습니다. 부탁드려요…
다음 식들을 증명하시오.
[1] ∀x(Fx → ¬Gx), ∀x(Hx → Gx), ∀x(¬Hx → (Gx ∨ Jx)) ⊢ ∀x(Fx → Jx)
[2] ∀x(Fx → Hx),∀x(¬Jx → Gx), ∃x(Fx ∧ ¬Gx) ⊢ ∃x(Hx ∧ Jx)
[3] ∃x(Fx ∧ Gx), ∀x(Fx → ∀y(Gy → Hxy)) ⊢ ∃x(Gx ∧ Hxx)
[4] ∀x(Fx → ∀y(Jy → Kxy)), ∀x∀y(Kxy → Kyx), ∃x(Fx ∧ Hx) ⊢ ∃x(Hx ∧ ∀y(Jy → Kyx))
[5] ∃x(Fx ∧ Gx), ∀x(Fx → ∃y(Hy ∧ Kxy)), ∀x(Hx → ∀y(Jy → (∃zKyz → Kxy))), ∀x(Gx → Jx) ⊢ ∃x∃y(Kxy ∧ Kyx)
문제풀이중 도움을 받고자 글 남깁니다.
조금의 도움이라도 좋습니다. 부탁드려요…
다음 식들을 증명하시오.
[1] ∀x(Fx → ¬Gx), ∀x(Hx → Gx), ∀x(¬Hx → (Gx ∨ Jx)) ⊢ ∀x(Fx → Jx)
[2] ∀x(Fx → Hx),∀x(¬Jx → Gx), ∃x(Fx ∧ ¬Gx) ⊢ ∃x(Hx ∧ Jx)
[3] ∃x(Fx ∧ Gx), ∀x(Fx → ∀y(Gy → Hxy)) ⊢ ∃x(Gx ∧ Hxx)
[4] ∀x(Fx → ∀y(Jy → Kxy)), ∀x∀y(Kxy → Kyx), ∃x(Fx ∧ Hx) ⊢ ∃x(Hx ∧ ∀y(Jy → Kyx))
[5] ∃x(Fx ∧ Gx), ∀x(Fx → ∃y(Hy ∧ Kxy)), ∀x(Hx → ∀y(Jy → (∃zKyz → Kxy))), ∀x(Gx → Jx) ⊢ ∃x∃y(Kxy ∧ Kyx)
1. (∀x. Px) → (∀y. Qy) = (∀x. Px → Qx) 임을 증명하면 명제논리처럼 단순히 풀림. 2. 존재양화식에서 x를 상수 c로 치환하고 결론식 꼴을 유도해서 다시 존재양화사 도입. 3. 마찬가지 치환해서 풀고 이때 전체양화식에서는 x,y에 모두 c를 적용. 4. 똑같은데 전체양화된 y에 arbitrary한 d 적용해서 결론꼴 유도하고 전체양화사 재도입. 5. 4번까지 풀었으면 풀 수 있음
1은 그냥 전체를 한 양화사로 묶어서 arbitrary한 상수 도입하는게 더 빠르다
감사합니다. 덕분에 1~3번은 해결을 했는데 4,5번은 힘드네요. 시간이 되시면 4,5번 풀이 부탁드려도 될까요....?
4는 존재양화식의 x를 c로 치환하고 양쪽 전체양화식의 x에 c적용하면 나머지는 자명. 5번은 복잡할 수 있는데 일단 1번식 c로 치환하고, 두번째 식에서 x에 c 대입하고 y는 d로 치환, 그 다음 식에서는 x에 d 대입하고 y에 c 대입하면 ∃zKyz가 만족됨에 따라 마지막 식에 x에 c, y에 d가 대입된 꼴이 증명돼서 존재양화사 재도입.
이런거 푸려면 공부 얼마나해야되나여
각 추론규칙에 익숙해지기만 하면 누구나 풂. 그냥 증명 여러개 직접 해보는게 최선의 공부임