불 연 결 자 논 리 제 5 장

불 연 결자 논리

논리곱 연결자 (∧), 논리합 연결자 (∨), 논리역 연결자 (¬) 들은 모두 진리값 함수형 연결자이다. 즉, 복합명제의 진리값이 연결자로 연결된 명제들의 진 리값에 의해 결정된다. 예를 들어, P ∨Q 이 참인지를 알기 위해서는 P 와 Q 의 진리값만 확인하면 된다. 이와같이 불 연결자의 의미는 진리표를 이용 하여 확인할 수 있다.

더 나아가, 어떠한 복잡한 명제가 주어진다 하더라도 그 명제 안에 나 타나는 단순명제들의 진리값만을 확인하면 주어진 복합명제의 진리값을 알 수 있다. 즉, 주어진 명제 S 가 전제 P1, . . . , P_n들의 논리적인 결과인지 여부 를 판단하는 데에 진리표가 유용하게 활용될 수 있다.

본 장 (章) 에서는 논리적 진리, 논리적 동치, 논리적 결과 등의 세 개념 이 진리표를 활용하는 것과 어떻게 연결될 수 있는지를 다룰 것이다. 먼저 논리적 결과란 어떤 의미인지를 알아보고, 다음으로 논리적 동치, 끝으로 논리적 결과에 대해 알아본다.

51

5.1 항진명제 (tautology) 와 논리적 진리

a₌a처럼 필연적으로 참일 수 밖에 없는 명제들이 있다. 이과 같은 명제 를 결론으로 갖는 논증은 그 논증의 전제들이 무엇이건 항상 타당하다. 즉, 결론이 전제들이 참이면 결론도 항상 참이다. 왜냐하면 결론이 어떠한 상 황에서도 거짓이 될 수 없기 때문이다. 또한 심지어 전제가 하나도 없어도 그 논증은 타당하다. 이와 같은 명제들을 “논리적 진리” 라 부른다.

어떤 논리적으로 가능한 상황에서는 참일 수 있는 명제를 “논리적으로 가능한 명제” 라고 말한다. 예를 들어 빛보다 빠르게 달리는 것이 물리학적 으로는 불가능하지만 논리적으로는 가능하다. 반면에 a _̸= a와 같이 어떤 사물이 사물 자신과 같지 않다라는 명제는 심지어 논리적으로도 가능하지 않다. a_̸=a가 참인 세상에서는 “동일하다” 라는 의미가 성립하지 않을 것 이기 때문이다.

어떤 주장이 어떤 논리적으로 가능한 상황에서는 참이될 수도 있으면 그 주장은 “논리적으로 가능한” 주장이라고 말하며, 모든 논리적으로 가능 한 상황에서 참인 주장을 “논리적으로 필연적인” 주장이라고 말한다.

하지만 이와 같은 개념들이 상당히 중요한 반면에 이해하기가 좀 애매 한 면들이 있다. 앞으로 위 개념들을 이해하는 데에 도움이 되는, 보다 엄 밀하게 정의될 수 있는 개념들을 다룰 것이다.

5.1.1 TW-

가능성

다음의 블록언어 명제를 살펴보자.

¬(Tet(b)_∨Cube(b)_∨Dodec(b)₎

위 명제는 “논리적” 으로는 가능하다. (b) 가 구이거나 20면체일 수도 있기 때문이다. 반면에 타스키 월드 프로그램을 이용해서는 위 명제가 참이되는

세상을 절대로 만들어낼 수 없다. 하지만 이것은 논리의 문제는 아니라, 타 스키 월드 프로그램이 갖고 있는 비논리적 법칙과 제한사항들 때문이다. 마 치우리가 살고 있는 세상에 비논리적인 법칙과 제한사항들이 있는 것처럼.

이제 타스키 월드 프로그램에 제한시켜 이야기를 해보자. 예를 들어, 아 래명제를 참이되게 하는 세상을 타스키 프로그램을 이용하여 생성할 수 있 다.

Cube(a)_∨Larger(a, b)

이와같은 명제를 TW-가능이라고 한다. TW-가능한 명제는 물론 논리적으로 가능한 명제이다.

참고사항 5.1. 아래 명제와 같이 모든 가능한 타스키 월드에서 참인 명제를 TW-진리라 한다.

Tet(b)_∨Cube(b)_∨Dodec(b) TW-진리에 대해서 아래에서 보다 자세히 다룬다.

5.1.2

진리표와 항진명제

앞서 타스키 월드에만 국한되는 TW-가능이란 개념을 이용하여 어떤 명제가 논리적 가능한지에 대한 예를 보였다. 이번에는 진리표를 이용하면 어떠한 특정 세상 모델을 사용하지 않으면서도 논리적 가능을 판단할 수 있음을 예 를 들어 설명하겠다.

먼저 다음 예제를 살펴보자.

Cube(a) Cube(a) _{∨ ¬}Cube(a)

T T F

T T T

위 진리표를 보면 명제 Cube(a)_{∨ ¬}Cube(a)가 절대로 거짓일 수 없음을 알 수 있다. 위와 같은 명제를 항진명제 (tautology) 라 부른다. 그런데 명제 Cube(a)_{∨ ¬}Cube(a)^는 P_{∨ ¬}P^{의 형태를} 가짐고 있으며, 이와 같은 형태의 명제를 배중률이라 한다. 배중률은P의 내용에 상관 없이 언제나 항진명제 이다.

좀 더 복잡한 명제의 진리표를 살펴보자.

(Cube(a)_∧Cube(b))_{∨ ¬}Cube(c) (5.1)

진리표를 보다 읽기 쉽게 만들기 위해 위 명제에 사용되는 단순명제들을 차 례대로 A, B, C^라고 줄여서 사용하겠다.

A B C (A _∧ B) _{∨ ¬}C

T T T T T F

T T F T T T

T F T F F F

T F F F T T

F T T F F F

F T F F T T

F F T F F F

F F F F T T

위 진리표에 의하면 우리 명제가 항진명제가 아님을 알 수 있다. 또한 c가 정육면체이고 a 또는 b가 정육면체가 아닌 타스키 블록 언어 월드가 존재 하므로 논리적으로 필연적이지도 않다.

You try it (

영어교재

쪽

Boole 프로그램을 이용하여 다음 명제의 진리표를 아래처럼 작성하여 항진 명제임을 확인해보도록 하자.

¬(A_∧(_¬A_∨(B_∧C_{))) ∨}B

A B C _¬(A _∧ (_¬A _∨ (B_∧C))) _∨ B

T T T F T F T T T

T T F T F F F F T

T F T T F F F F T

T F F T F F F F T

F T T T F T T T T

F T F T F T T F T

F F T T F T T F T

F F F T F T T F T

참고사항 5.2. 진리표를 작성할 경우 핵심 연결자를 명확하게 할 필요가 있 다. 예를 들어, 아래 명제의 경우

P_∧Q_∧R

핵심 연결자가 첫 번째 논리곱인지 두 번째 논리곱인지 명확하지 않다. 이 런 경우 가장 왼쪽에 있는 연결자가 핵심 연결자라고 간주한다. 즉, 아래 명제를 이용하여

(P_∧Q)_∧R 진리표를 작성한다.

항진명제는 항상 논리적으로도 필연적이다. 또한 항진명제의 경우 단순 명제들의 참, 거짓에 상관없이 언제나 참인 진리값을 갖는다. 즉, 어떤 세 상에서든 필연적으로 참일 수 밖에 없다

하지만 논리적으로 필연적인 명제라 해서 모두 항진명제인 것은 아니다.

예를 들어 1 차 논리 언어의 명제인 a = a의 경우 논리적으로 필연이지만 항진명제는 아니다. 왜냐하면 a = a를 단순명제를 의미하는 기호 P를 이 용하여 표기될 수 있기 때문이다.

다음 명제 또한 논리적으로 필연이지만 항진명제는 아니다.

¬(Larger(a, b)_∧Larger(b, a))

(왜 그런가 ?)

예제 5.3. 항진명제 예제 (1) Tet(a)_{∨ ¬}Tet(a) (2) (A_∧B)_∨(_¬A_{∨ ¬}B) (3) 반례 : A_∨B, (_¬A_∨B)_∨C 예제 5.4. 논리적 진리 예제

(1) ¬(Larger(a, b)_∧Larger(b, a)) (2) a = a_∧b = b

(3) 반례 : a = b

5.1.3

오일러 원 다이어그램

앞서 논리적 가능과 논리적 필연의 예를 타스키 월드와 진리표를 이용하여 설명하였다. 첫째, TW-가능에 대해 알아보았다. 즉, 어떤 명제가 어떤 타스 키 월드에서 참이면 그 명제를 TW-가능이라고 부른다. 그리고 TW-가능인 명제는 논리적으로도 가능인 명제이다. 참고로 모든 타스키 월드에서 참인 명제를 TW-진리라고 한다. 둘째, 진리표를 확인하여 주요 연결자 열의 모든 경우에서 참이라면 그 명제를 항진명제 또는TT-필연이라고 부른다. 반면에 최소 한 가지 경우에서 참이되는 명제를 TT-가능이라고 한다.

TW-가능, TW-진리, TT-가능, TT-진리 네 개념 모두 논리적 가능 또는 논 리적 진리에 정확히 부합하지는 않는다. 다만 엄밀한 정의를 이용하여 논 리적 가능 또는 논리적 진리의 예제를 제공할 수는 있음을 알아보았다.

그림 5.1.1: 오일러 원 다이어그램 : 항진명제, 논리적 진리, TW-진리 사이의 관계 및 경계

그림 5.1.1 은 TT-진리, 논리적 진리, TW-진리 사이의 관계를 나타내는 오일러 원 다이어그램이다. 그림에서 논리적 진리의 경계를 점선으로 표시 한 이유는 엄밀한 정의가 불가능하기 때문이다. 반면에 TW-진리의 경계는

선을 이용하여 명확하게 그어졌다.

참고사항 5.5. 주어진 명제가 논리적 진리인지를 판단하는 또 하나의 방법 이 있다. 증명기법을 이용하는 방식이며 다음 장에서 배울 것이다.

5.2 논리적 동일성과 항진적 동일성

앞 장 (章) 에서 어떤 상황에서든 같은 진리값을 갖는 두 명제들을 논리적으 로 동일하다고 하였다. 하지만 “어떤 상황에서든” 이란 표현 자체가 좀 애매 모호하다. 앞서 항진적 진리 (즉, TT-진리) 개념을 이용하여 논리적 진리를 이해하였듯이 이번에는항진적 동일성을 이용하여논리적 동일성을 이해하 는 방법을 설명하며, 이를 위해 통합진리표를 활용한다.

예제를 살펴보자.

예제 5.6. ¬(A_∧B)_{와 ¬}A_{∨ ¬}B의 항진적 동일성 A B _¬(A _∧ B) _¬A _{∨ ¬}B

T T F T F F F

T F T F F T T

F T T F T T F

F F T F T T T

통합 진리표에서 굵은 문자로 표시된 두 열의 진리값이 동일함을 확인 할 수 있다. 즉,A^와 B의 진리값이 무엇이건 두 명제의 진리값이 일치한다.

앞서 드 모르강 규칙을 적용하여 논리적으로 동일한 명제들을 확인한 것처 럼 여기서는 항진적으로 동일한 명제를 구할 수 있음을 확인하였다.

불 연결자들의 단순한 변형을 이용하여 논리적으로 동일한 명제를 구하 였다. 좀 더 복잡한 예제를 살펴보자.

예제 5.7. ¬((A_∨B)_{∧ ¬}C)^와 (_¬A_{∧ ¬}B)_∨C^{의 항진적 동일성} A B C _¬((A _∨ B) _{∧ ¬}C) (_¬A _{∧ ¬}B) _∨C

T T T T T F F F F F T

T T F F T T T F F F F

T F T T T F F F F T T

T F F F T T T F F T F

F T T T T F F T F F T

F T F F T T T T F F F

F F T T F F F T T T T

F F F T F F T T T T T

주요연결자 열을 확인하면 두 열이 모든 줄에서 동일한 진리값을 가짐 을 확인할 수 있다.

앞서의 두 예제를 통해서 살펴보았듯이 항진적으로 동일한 명제들은 논 리적으로도 동일하다. 그러나 논리적으로 동일하지만 항진적으로는 동일하 지 않은 명제들이 존재한다.

예제 5.8. 다음 두 명제는 논리적으로 동일하지만 항진적으로 동일하지는 않다.

a ₌ b _∧ Cube(a) a ₌ b _∧ Cube(b)

Proof. (1) 논리적 동일성 증명 : a=b ∧ Cube(a)가 참이라고 가정하자. 그 러면 a=b도 참이고 Cube(a)도 참이다. a와 b는 같으므로 (= 제거규 칙) Cube(b) 도 참이다. 따라서 a = b ∧ Cube(b)도 논리적으로 참이다.

거꾸로 a=b ∧ Cube(b)가 참이라고 가정하자. 그러면 b=a도 참이다.

그런데 b 와 a 는 같으므로 (= 제거규칙) Cube(a)도 참이다. 따라서 a

= b ∧ Cube(a)도 논리적으로 참이다.

양쪽방향으로 모두 서로를 논리적으로 유추해낼 수 있으므로 두 명제 는 논리적으로 동일하다.

(2) 항진적 동일성에 대한 반례 :

a=b Cube(a) Cube(b) a=b _∧ Cube(a) a=b _∧ Cube(b)

T T T T T

T T F T F

T F T F T

T F F F F

F T T F F

F T F F F

F F T F F

F F F F F

5.3 논리적 결과와 항진적 결과

논증이 타당하려면 (어떤 주어진 세상에서) 논증의 전제들이 모두 참이면 논증의 결론도 (그 세상에서) 참이어야 한다. 어떤 논증이 타당한 논증인지 를 한 눈에 알아볼 수 있는 방법이 있을까 ?

앞서 항진적 진리와 항진적 동일성을 활용하여 논리적 진리와 논리적 동일성을 확인할 수 있음을 배웠다. 이번 절 (節)에서는 항진적 결과를 이 용하여 논리적 결과를 알아보는 방법을 다룬다.

명제 P와 명제 Q의 통합진리표의 모든 줄에서 P의 진리값이 T일 때 Q의 진리값도 T이면 명제 Q가 명제 P의 항진적 결과이다라고 말한다.

Q가 P의 항진적 결과이면 Q는 P의 논리적 결과이기도 하다.

Proof. Q가 P의 항진적 결과이지만 논리적인 결과는 아니라고 가정하자.

그러면 P가 참이지만 Q가 거짓이 되는 세상이 존재한다. 그런데 하나의 세상이 존재하면 P와 Q의 진리값은 각각의 명제에서 나타나는 단순명제 들의 진리값에 의해 자동으로 결정된다. 즉, P와 Q^의 통합진리표에서 P 와 Q에 나타나는 단순명제들의 (주어진 세상에서의) 진리값들에 해당하는 줄이 있고 그 줄에서 P의 진리값은 T이고 Q의 진리값은 F_{가 되야 한다.}

하지만 이는 Q가 P의 항진적 결과가 될 수 없다는 의미이다. 즉 모순이 발생한다. 따라서 Q가 P의 항진적 결과이면 Q가 P의 논리적 결과가 되 야한다.

다음 예제에서A_∨B가 A_∧B의 논리적 결과임을 A_∨B가 A_∧B의 항진적 결과라는 사실을 보이는 것을 통해 증명한다. 즉, 통합진리표를 이용한다.

A B A_∧B A_∨B

T T T T

T F F T

F T F T

F F F F

여기에서 보면 A_∧B와 A_∨B가 항진적으로 동일하지 않음을 확인할 수 있다. 하지만 A_∧B가 A_∨B를 “논리적으로 암시” 하는 것은 확인할 수 있다.

또한 A_∧B가 A_∨B의 항진적 결과가 아님을 확인할 수 있다. 진리표에 서 A_∨B의 진리값이 참이지만 A_∧B의 진리값은 거짓인 경우가 존재하기 때문이다.

그렇다면 A_∧B는 A_∨B의 논리적 결과가 아니라는 말인가 ? 일반적으 로는 아니다. 하지만 경우에 따라서는A_∧B가 A_∨B의 논리적 결과일 수도 있다.

연습문제 3. ( 영어교재 연습문제 4.25 참조) A_∧B^가 A_∨B의 논리적 결과 가 되도록 하는 명제 A^와 B를 블록 언어를 이용하여 구하라. [ 힌트: A_∧A 는 A_∧A의 논리적 결과이다. 하지만 여기서는 서로 다른 A^와 B^{를 구해야} 한다.]

논리적 결과이지만 항진적 결과가 아닐 수도 있음에 주의해야 한다. 예 를 들어, 명제 a = c는 명제 (a = b_∧b = c)의 논리적 결과이다. 하지만 아래 통합진리표가 항진적 결과는 아님을 보여준다.

a=b b=c a=c a=b_∧b=c a=c

T T T T T

T T F T F

T F T F T

T F F F F

F T T F T

F T F F F

F F T F T

F F F F F

항진적 결과 따지고자 할 떼 전제가 하나가 아니라 여러 개일 수 있다.

이경우도 통합진리표를 이용하여 Q가 P₁, . . . ,P_n^{의 항진적} 결과인지를 쉽 게 확인할 수 있다. 즉, 통합진리표에서 P₁, . . . ,P_n가 모두 진리값 T를 갖는 줄에서 Q 또한 진리값 T를 가짐을 확인하면 된다.

연습문제 4. 통합진리표를 이용하여 A_∨C^가 A_{∨ ¬}B^와 B_∨C로부터의 항 진적 결과임을 확인하라.

연습문제 5. 통합진리표를 이용하여 A_{∨ ¬}B^가 B_∨C^와 A_∨C로부터의 항 진적 결과가 아님을 확인하라.

5.3.1 Fitch

에서의 항진적 결과

통합진리표를 이용하여 항진적 결과 여부를 따지는 방법은 효율적으로 보 이지만 반드시 그렇지는 않다. 예를 들어 다루어야 하는 단순명제가 여덟 개이면 64 개의 경우를 따져야 한다. 즉, 단순명제의 갯수에 따라 다루어야 하는 경우의 수가 기하급수적으로 증가하는데 이는 매우 비효율적이다.

다행히도 항진적 결과 여부를 기계적으로 판단할 수 있다. 다시 말해서 컴퓨터 프로그램을 이용하여 판단할 수 있다는 말이다. 그런 프로그램이 바 로 Fitch 프로그램이다. Fitch 에서 허용되는 규칙 중에 Taut Con을 이용하 면 항진적 결과 여부를 단번에 확인할 수 있다. Taut Con은 엄밀히 말해 추론규칙은 아니다. 하지만 항진적 결과 여부를 빠르게 확인하는 데에 매우 효율적으로 활용될 수 있다.

이제 영어교재 114 쪽과 115 쪽의 You Try It 을 따라하면서 Taut Con 을 어떻게 적용하는지 배우도록 한다.

영어교재 116 쪽의 You Try It 을 Fitch 로 풀기 위해 사용하는 규칙은 아 래의 세 가지 중에 하나이다.

(1) Taut Con : Tautological Consequence(항진적 결과)

진리표를 사용하지 않으면서 항진적 결과 여부를 확인해준다.

(2) FO Con : First-Order Consequence(논리적 결과)

항진적 결과 뿐만 아니라 =(등호)을 이해하며, 나중에 배우게 될 양 화사quantifiers 도 논리적으로 다룰 수 있다.

(3) Ana Con : Analytic Consequence: 분석적 결과

논리적 결과 뿐 아니라 블록 언어의 술어들고 이해하고 다를 수 있다.

연습을 통해 FO Con 규칙이 Taut Con 규칙보다 강력하고, Ana Con 규칙이 FO Con 규칙보다 강력함을 확인하며 각 규칙들 사이의 차이를 익

히도록 한다. 또한 위 세 가지 규칙중에서 적용할 수 있는 가장 약한 규칙을 알아낼 수 있어야 한다. 과제나 연습문제를 Fitch 를 이용하여 풀 경우 위 세 가지 규칙은 허용된 경우에만 사용할 수 있음에 주의하라.

5.3.2

항진적으로 동일한 명제 만들기

명제의 일부을 항진적으로 동일한 명제로 대체하는 방식을 이용하여 보다 단순하지만 항진적으로 동일한 명제를 만들어 낼 수 있다. 아래에서 ⇔ 는 항진적 동일성을 의미한다.

• 이중 논리역 법칙 : ¬¬P ⇔ P

• 드 모르강 법칙 : ¬(P ∧ Q) ⇔ (¬P ∨ ¬Q) 또는 ¬(P ∨ Q) ⇔ (¬P ∧ ¬Q)

• 결합법칙 :

P∧ (Q ∧ R) ⇔ (P ∧ Q) ∧ R ⇔ P ∧ Q ∧ R 또는

P∨ (Q ∨ R) ⇔ (P ∨ Q) ∨ R ⇔ P ∨ Q ∨ R

• 교환법칙 : P ∧ Q ⇔ Q ∧ P 또는 P ∨ Q ⇔ Q ∨ P

• 멱등법칙 : P ∧ P ⇔ P 또는 P ∨ P ⇔ P

• 분배법칙 :

P∧ (Q ∨ R) ⇔ (P ∧ Q) ∨ (P ∧ R) 또는

P∨ (Q ∧ R) ⇔ (P ∨ Q) ∧ (P ∨ R)

예제 5.9. 항진적으로 동일한 명제 만들기 예제 (각 단계에서 사용된 법칙 이 무엇인지를 확인해야 한다.)

(A_∨B)_∧C_∧(_¬(_¬B_{∧ ¬}A)_∨B)

⇔ (A_∨B)_∧C_∧((_¬¬B_{∨ ¬¬}A)_∨B)

⇔ (A_∨B)_∧C_∧((B_∨A)_∨B)

⇔ (A_∨B)_∧C_∧((A_∨B)_∨B)

⇔ (A_∨B)_∧C_∧(A_∨(B_∨B))

⇔ (A_∨B)_∧C_∧(A_∨B)

⇔ (A_∨B)_∧(A_∨B)_∧C

⇔ (A_∨B)_∧C