[논리학] 4. The Logic of Boolean Connectives

Logical Truth

Logical Consequence

- 어떤 전제 𝑃1,⋯,𝑃𝑛 로 이루어진 집합에 대하여, 전제들이 모두 참이라고 할 때, 결론 𝑆가 반드시 참인 경우

 

Logical Truth

- 어떤 경우는 전제에 상관없이 또는 전제 자체가 없어도 참인 결론이 있을 수 있음

- 필연적으로 참인 문장 예시 : a=a

 

Logical Possibility & Logical Necessity

Logical Possibility

- 어떤 논리적 상황을 바탕으로 했을 때, 참이 될 수도 있는 경우

 

Logically possible 예시 문장

ex) It is not physically possible to go faster than the speed of light.

 

Logically possible 이 아닌 문장

ex) An object is not identical to itself. (identity의 뜻 자체를 위배)

 

Logical necessity

- 모든 논리적 환경에서 항상 참인 경우

 

Logically possible vs. TW-possible

logical possible한 예시

 

만약 b가 구(sphere) 또는 정십이면체(icosahedron)이면 가능

-> 그러나 Tarski’s World 에서는 불가능 (impossible)

-> (Tetrahedron, cube, dodecahedron 중에서만 가능)

 

TW-possible

: Tarski’s World 내에서 논리적으로 가능한 경우를 말함

 

※ 차이점

- 앞서 logical possible의 예시에서는 물리적 세계에서 논리적 가능성을 봄

- TW-possible 에서는 Tarski’s World에서 논리적 가능성

예시

 

=> 따라서, 모든 TW-possible 은 logical possible (역은 성립 하지 않을 수 있음)

 

Truth Table Method

: 어떤 문장이 논리적으로 참이 될 수도 있음을 확실하게 보이기 위한 방법 중 하나

 

※ 테이블 그리는 관례

Truth Table 그리는 순서

 

A v B v C의 Truth Table

 

ex) 세 개의 atomic sentence 라면 8개의 줄이 필요

      1. 가장 왼쪽 atomic sentence에서 위 절반은 T, 아래 절반은 F

      2. 그 다음 atomic sentence에서 절반씩 T  채우고, 나머지는 F 채움

      3. 반복

      4. 관례에 따르면 T와 F는 항상 동일한 방법으로 채워짐

 

두 번째 예시

 

 

※  Atomic sentence와 complex sentence 사이에는 두 줄로 구분

 

1. Reference column 을 모두 채웠다면 가장 안쪽(innermost) connective부터 계산

-> 여기서는 negation에 해당

-> reference column의 Cube(a) 값을 보고 계산

 

2. 중간 단계의 connective 계산 결과를 바탕으로 main connective 계산

-> 여기서 main connective는 disjunction에 해당

 

※ connectives에서 T,F를 채우는 순서

- 괄호 먼저

- ¬ -> ∧ -> ∨

- 왼쪽에서 오른쪽

- 최종적으로 main connective 계산

 

※ 최종 False인 경우도 있음 -> Tautology가 아님 & Logically necessary도 아님 

 

Tautology vs. Logical Necessity

Tautology

- Truth table에서 main connective가 모두 T인 경우

 

※ 어떤 tautology도 모두 logical necessary임

(문장의 논리적인 의미를 따질 필요 없음)

 

※ 그러나 모든 logical necessary가 tautology는 아님

ex) atomic sentence가 한 개인 예시 ex) a=a -> truth table 그리면 T와 F 결과가 나옴

 

※ atomic sentence의 의미를

- 따지지 않고 모든 경우 참 : tautology

- 따졌을 때 모든 경우 참 : logically necessary

 

Tarski's World에서 Tautology

TW-possible

- Truth table에서 main connective 값 중에 하나라도 T가 있음 (어떤)

 

TW-necessary

- Truth table에서 main connective 모든 값이 T (모든)

 

※ 아래 명제가 성립

- Tautology -> logically necessary -> TW-necessary

Diagram : Tautology -> Logically Necessary -> TW-necessary

 

Logical Equivalence, Tautological Equivalence

Logically equivalent sentences

- 모든 가능한 환경 각각에 대해 동일한 truth value를 가지는 문장들을 말함

 

Tautological equivalent sentences

- Truth table에서 main connectives 값이 모두 같은 문장들

 

※ 모든 tautological equivalent sentences 는 logically equivalent

-> 역이 항상 성립하지는 않음

 

Joint Truth Table

- 두 문장 이상의 tautological equivalence 확인을 위해 truth table 에 작성

- 예를 들어 어떤 문장 S와 S’ 의 tautological equivalence 를 따질 때, S 와 S’ 사이에 세로선을 그어 구분

- Main connectives 의 값이 모두 동일하면 tautological equivalence

 

- S와 S’ 는 tautological equivalent (iff) joint truth table 에서 S와 S’의 최종값이 모두 동일

- S와 S’가 tautologically equivalent라면, 이 둘은 logically equivalent

- 어떤 문장이 logical equivalence라도 tautological equivalence가 아닐 수 있음

 

Tautological Consequence

- Truth-functional connectives 로 이루어진, 두 문장 P와 Q가 주어졌을때, Q가 P의 consequence인지 알아보고 싶다면 P와 Q에 대한 joint truth table을 그리면 됨 (tautological equivalence 따질 때와 유사)

- P와 Q에 대한 truth 값을 채우고 난 후, P가 true인 경우를 확인

- 만약 P가 참인 모든 경우에 대해서 Q도 참이라면, Q를 P에 대한 tautological consequence라고 함

- Tautological consequence 라면 logical consequence (역은 성립하지 않을 수 있음)

 

Truth table이 만능일까?

-> Atomic sentence 개수가 많아지면 테이블이 매우 커짐

-> Fitch에서 어떤 종류의 consequence인지 확인 가능 (Taut Con, FO Con, Ana Con)

 

Taut Con, FO Con, Ana Con

Taut Con

-Tautological consequence

-Truth table을 이용한 검증과 동일

-Boolean connectives의 연결 관계만 따짐

-predicate의 의미는 따지지 않음

 

FO Con

-First-order consequence

-a=c와 같은 문장의 의미를 안다고 가정 (다른 predicate의 의미는 따지지 않음)

 

Ana Con

-Analytic consequence

-Tarski's World의 대부분의 predicate의 의미를 안다고 가정

 

Valid Inference Steps

- Informal Proof에서 사용하는 유효한 증명 패턴

 

Conjunction elimination (simplification)

- P ∧ Q 문장이 주어지면, conjunction의 의미에 따라서 P 와 Q 문장 각각이 모두 참이라는 것을 알 수 있음

 

Conjunction introduction

- 위의 역으로 ∧ 의 의미에 따라서, P와 Q 문장으로부터 P ∧Q 문장이 logical consequence 임

 

Disjunction introduction (addition)

- 어떤 문장 P가 참이라는 사실을 증명하였다면, P에 어떤 disjunction을 연결한 문장도 참이 됨. 즉 P ∨Q 도 참이 됨

 

Proof by Cases (=Disjunction Elimination)

-Formal proof에서는 disjunction elimination이라고도 부름

 

※ 증명 패턴

    - 어떤 문장 S가 전제 P ∨ Q 로부터 logical consequence라는 사실을 증명 할 때,

    - P가 참인 경우에 S가 참인 경우를 보이고

    - Q가 참인 경우에 S가 참인 경우를 보임

 

Proof by Contradiction (=Negation Introduction)

-Formal proof에서 negation introduction으로 부름

 

※ 증명 방법

 

어떻게 이게 증명이 됨?

 

Contradiction Symbol ⊥

- 결론이 논리적으로 불가능하다는 점을 의미

- Contradiction, the absurd, the false 등으로 읽음