Fitch 시스템의 안전성과 완전성
• 지금까지 진리값과 관련이 있는 논리 연결자를 배웠으며 사용법을 익 혀 왔다.
• Fitch 시스템에 대해 더 배우기 전에 먼저 답해야 할 두 가지 질문이 있다.
• 지금까지 다뤄온 Fitch 시스템 F 의 안정성과 완전성에 대해 질문을 던 져야 한다.
10.1 안전성
10.1.1 System F
의 안전성
• 추론시스템 F 에서, 즉, Fitch 프로그램을 이용해서 증명한 명제가 모 두 타당하다고 할 수 있는가 ?
• 즉, 타당한 주장 또는 논리적으로 옳은 결론만 전제로부터 이끌어 내 었는가 ?
120
안전성 121
안전성은 명확한가 ?
• 아래와 같은 진리표를 갖는 “배타적인 또는” (exclusive or, `) 연결자 가 있다.
P Q P` Q T T F T F T F T T F F F
• 즉, P 와 Q 의 진리값이 서로 다를 때만 P` Q 의 진리값이 참이다.
• 앞서 소개된 배타적인 또는 (`) 연결자와 관련된 (` Elim) 규칙이 Fitch 시스템에 아래와 같이 포함되어 있다고 가정하자.
P` Q
P ... S
Q ... T S`
T `
Elim
• (` Elim) 규칙이 포함된 Fitch 시스템의 안전성을 확인할 수 있는가 ?
• 안전성이 그럴듯해 보이기는 하지만 실제로는 그렇지 않음을 다음과 같이 알 수 있다.
• 먼저 S 명제와 T 명제가 동일하다고 하면 위 규칙이 실제로는 타당한 규칙이 아님을 쉽게 알 수 있다.
• 왜냐하면 전제가 무엇이건간에 결론이 항상 거짓이기 때문이다. (S` S 는 절대로 참이 될 수 없다.)
따라서 Fitch 시스템의 안전성은 그렇게 명확하지 않고, 따라서 안정성 을 증명할 필요가 있다 !
또 하나의 예로 아래의 논증을 살펴보자.
¬(Happy(carl) ∧ Happy(scruffy))
¬Happy(carl)
위 논증이 타당하지 않음을 바로 알 수 있다.
하지만 Fitch 시스템 내에서는 Happy(carl) 이란 명제가 ¬(Happy(carl) ∧ Happy(scruffy)) 명제로부터 절대로 유추되지 않는다고 어떻게 보장할 수 있 는가 ?
• 가능한 모든 증명을 확인하여 절대로 위와 같은 일이 발생하지 않는 다고 확인할 수 있는 방법은 존재할 수 없다.
• 앞서의 질문에 답하려면 다른 방식을 찾아야 하며 다음과 같이 안전 성을 주장할 수 있다.
안전성 123
10.1.2 System F
의 안전성
:안전성 정리
• 안전성 정리Soundness Theorem:
P1 ...
Pn ...
Q
위 증명이 Fitch 시스템 (FT) 에서 증명 가능하면 Q 는 P1, . . . , Pn으로 부 터의 항진 결과 (tautological consequences) 이다.
안전성 정리가 성립하는 것을 직관적으로 확인할 수 있다. 하지만 엄밀 한 증명은 간단하지 않음. (궁금한 사람은 교재 참조)
안전성 정리를 그림으로 표현하면 아래와 같다.
완전성 125
10.2 완전성
안전성의 반대 개념도 성립할까 ?
• 눈으로 보았을 때 자명한 증명을 Fitch 프로그램을 이용해서는 제대로 증명을 실행할 수 었을 때가 많다.
• 그래서 다음과 같은 의심을 갖게 된다.
Fitch 시스템 F 의 완전성
• 안전성의 반대도 성립할까 ?
• 즉, 임의의 전제 P1, . . . , Pn들로부터 Q 항진적으로 이끌어낼 수 있다면 Fitch 시스템 (FT) 내에서 아래의 증명을 구할 수 있을까 ?
P1 ...
Pn ...(?)
Q
Fitch 시스템 F 의 완전성
• 답은 YES!
• 하지만 증명은 꽤 복잡하다. 궁금하면 ?
500 원
• 증명은 교재 17 장 참조.
Fitch 시스템 F 의 완전성
명심할 점
• 안전성과 완전성은 항진명제에 대해서만 이야기 한다.
• 하지만 다음과 같은 논리적 결과에 대헤서는 말하지 않는다 :
– Dodec(b) ∧ b = c 로 부터 Dodec(b) 를 증명하는 것은 논리연결 자만으로는 부족하며, 등호 (=)에 대한 규칙 또한 필요하다.
– Larger(b,c) 로 부터 ¬Larger(c,b) 를 증명할 수 있을 수 없다. 이에 대해서는 Larger 에 대한 규칙이 필요하다.
완전성 127
• 위와 같이 언어와 규칙이 확장된 경우에도 안전성과 완전성이 성립한 다는 것을 보일 수 있다. 하지만 이에 대한 증명은 본 강의의 수준을 벗어나므로 생략한다.
10.3 안전성과 완전성의 활용
안전성 어떻게 활용하나 ?
• 예를 들어 A → (A → B) 가 Fitch 에서 증명 불가능함을 보이고 싶다면 ?
• 위 명제가 항진명제가 아님을 확인만 하면 된다.
• 왜냐하면, 만약 Fitch 에서 증명 가능하다 하면 위 명제가 안전성 정리 에 의해 항진적으로 참이어야 하기 때문이다.
완전성은 어떻게 활용하나 ?
• 예를 들어 ¬((A∧ B) → (C ∨ D))) → (B ∧ ¬D) 가 Fitch 에서 증명 가능함 을 보이고 싶다면 ?
• 위 명제가 항진명제임을 확인만 하면 된다.
• 왜냐하면, 만약 위 명제가 항진명제임을 보인다면 완전성 정리에 의해 Fitch 에서 증명 가능이기 때문이다.
완전성은 어떻게 활용하나 ?
• 주의 : 완전성이 정형증명을 어떻게 할 수 있는지 / 해야 하느지를 말 해주지는 않는다. 다만 증명이 있다는 사실만 확인할 수 있을 뿐이다.
• (어떤 식으로든) 증명이 존재한다는 사실이 증명을 찾을 수 있다는 것 을 꼭 보장하는 것은 아니다.
안전성과 완전성의 활용 129
Taut Con 규칙의 할용
• Taut Con 을 사용해서 증명 가능함을 먼저 확인할 수 있다. 왜냐하면 모든 항진명제는 Taut Con 으로 풀리기 때문이다.
• 그만큼 Taut Con 규칙은 매우 강력하다. (Taut Con 규칙이 어떻게 원 하는 증명을 찾아낼 수 있는지 궁금해진다. 하지만 이에 대한 질문과 답 또한 본 강의의 수준을 벗어난다.)
• 그리고 Taut Con 을 사용하지 않고 증명할 수 있도록 연습해야 진정한 논리의 힘을 배울 수 있다.
증명할 수 있는가를 판단하고자 할 때 해야 할 일 :
• Fitch 에서
• Taut Con 으로 따져본 후
• 항진이면 열심히 증명을 찾아보고
• 항진이 아니면 바로 포기하면 된다. ᄒᄒ
• 그러나... Fitch 가 없는 세상에서는 진리표를 그려볼 수 밖에 없지.
기억할 것
• (FT의 완전성) 만약 S 가 P1, . . . , Pn으로부터의 항진적 결과이면 P1, . . . , Pn 을 가정한 후 S 를 정형적으로 증명할 수 있다. 증명에는 ¬, ∨, ∧, →, ↔ ,⊥ 와 연관된 생성 및 제거 규칙만 사용된다.
• (FT의 안전성) 만약 S 가 P1, . . . , Pn으로부터의 항진적 결과가 아니라 면 P1, . . . , Pn을 가정한 후 ¬, ∨, ∧, →, ↔, ⊥ 와 연관된 생성 및 제거 규 칙만 사용하여 S 를 정형적으로 증명할 수 있는 가능성은 존재하지 않 는다.
• 위 두 가지 경우중 어느 경우가 해당되는지 여부를 Taut Con 규칙을 이용하여 확인할 수 있다.
연습문제 : 안전성 활용
• 아래의 주장이 증명가능성 여부를 확인하라.
A∧ (B ∨ ¬A ∨ (C ∧ D)) E∧ (D ∨ ¬(A ∧ (B ∨ D))) A∧ B
• 진리표를 그려서 확인해 보아라.
• 아니면 좀 생각해 보면 위 주장의 결론이 가정으로부터 항진적으로 따 라오지 않음을 알 수 있다. 왜냐하면 A, C, D, E 가 참이라면 위 주장의 가정은 B 의 진리값에 상관없이 모두 참이다. 따라서 B 가 거짓이라면 위 주장은 타당하지 않다. 따라서 안전성에 의해 위 주장의 타당성을 정형적으로 증명할 수 없다.
연습문제 : 완전성 활용
안전성과 완전성의 활용 131
• 아래의 주장이 증명가능성 여부를 확인하라.
A∧ (B ∨ ¬A ∨ (C ∧ D)) ∧ ¬(A ∧ D)
¬(E ∧ (D ∨ ¬(A ∧ (B ∨ D))))
• 진리표를 그려서 확인해 보아라.
• 아니면 좀 생각해 보면 위 주장의 결론이 가정으로부터 항진적으로 따라옴을 알 수 있다. 왜냐하면 가정이 참이되기 위해서는 A, B 는 참, D 는 거짓이어야 한다. (왜 ?) 따라서 가정이 참이라면 결론 역시 참이 된다. 따라서 완전성에 의해 위 주장의 타당성을 정형적으로 보일 수 있다. (하지만 언제나 그렇듯이 “어떻게” 가 문제이다. 두드려라. 그러 면 열리느니라 !)
