내용 소개

제 5 장 불(Boole) 연결자 논리

이계식

한경대학교 컴퓨터웹정보공학과

내용 소개

1

2

3

4

내용 소개

1

2

3

4

논리적 진리와 논리적 가능성

a= a 문장처럼 논리적으로 가능한 모든 상황에서 문장이 참이면, 그 문장은논리적으로 진리logically true또는논리적으로 필연 logically necessary이라고 한다.

a= b 문장의 경우는 논리적으로 가능하다고 말한다. 즉, 경우에 따라 가능하기도 하고 그렇지 않기도 하다는 의미임.

반면에 a6= a 문장은 논리적으로 절대 불가능하다. 등호의 개념에 반하기 때문이다.

하지만 정의가 좀애매모호하다.

아래 개념들에 대한 보다 엄밀한 정의가 필요

논리적 진리와 논리적 가능성

a= a 문장처럼 논리적으로 가능한 모든 상황에서 문장이 참이면, 그 문장은논리적으로 진리logically true또는논리적으로 필연 logically necessary이라고 한다.

a= b 문장의 경우는 논리적으로 가능하다고 말한다. 즉, 경우에 따라 가능하기도 하고 그렇지 않기도 하다는 의미임.

반면에 a6= a 문장은 논리적으로 절대 불가능하다. 등호의 개념에 반하기 때문이다.

하지만 정의가 좀애매모호하다.

아래 개념들에 대한 보다 엄밀한 정의가 필요

TW-진리와 TW-가능성

아래 문장의 경우

Cube(a) ∨ Larger(a, b)

TW-가능이라고 한다. 어떤 Tarski’s World에서 a라는 이름의 정6 면제가 있고 b보다 클 수 있기 때문이다.

반면에 아래 문장과 같이 모든 가능한 Tarski’s World에서 참인 문장을 TW-진리명제라 한다.

Tet(b) ∨ Cube(b) ∨ Dodec(b)

TW-진리와 TW-가능성

Tarski’s World와 같은 특정 모델이 아닌 가능한 모든 모델을 염두하며 진리값을 계산할 수 있는가?

진리표Truth Table를이용하면 가능하다.

TW-진리와 TW-가능성

Tarski’s World와 같은 특정 모델이 아닌 가능한 모든 모델을 염두하며 진리값을 계산할 수 있는가?

진리표Truth Table를이용하면 가능하다.

내용 소개

1

2

3

4

진리표를 이용한 Boole 연결자 해석

¬(A ∧ (¬A ∨ (B ∧ C))) ∨ B의 진리값은? (단, A, B, C는 단순문장을 나타내는 이름이다.)

진리표를 이용하여 판단.

Boole 프로그램 이용 진리표 작성

진리표를 완성시키는 과정은 Boole 프로그램 이용하여 습득할 것.

연습: 진리표를 만들어 보자. (교재 100쪽 You Try It 참조)

TT-진리와 TT-가능성

앞의 경우와 같이 어떤 경우에도 참일 수밖에 없는 문장을 항진명제tautology또는TT-진리(필연)명제라고 한다.

I 진리표Truth Table에서 모든 행이 true 값을 가진다.

I 예: P ∨ ¬P

A∨ B 처럼 진리표에서 한 줄이라도 참이되게 하는 명제를 TT-가능하다라고 한다.

항진명제(TT-진리명제) 예제

Tet(a) ∨ ¬Tet(a) (A ∧ B) ∨ (¬A ∨ ¬B) 반례: A ∨ B, (¬A ∨ B) ∨ C

논리적으로 진리인 명제 예제

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

반례: a = b

TW-진리명제 예제

Tet(b) ∨ Cube(b) ∨ Dodec(b)

반례: Cube(a) ∧ Larger(a, b) (하지만 TW-가능함)

오일러 원 다이어그램(Euler Circle Diagram)

내용 소개

1

2

3

4

타당한 주장: 논리적 결과 vs. 항진적 결과

P₁ ... P_n Q

주장의 타당성에는 두 종류가 있다.

논리적으로 타당한 주장: Q가 P₁, . . . , Pn의논리적 결과일 경우

논리적 결과 vs. 항진적 결과

P₁, . . . , Pn, Q가 모두 문장이라고 하자.

Q는 P₁, . . . , Pn의논리적 결과라 함은 P₁, . . . , Pn를 모두 참이라고 가정할 때 Q가 참이 됨을 의미한다.

Q는 P₁, . . . , Pn의항진적 결과라 함은 진리표에서 P₁, . . . , Pn를 모두 참인 행에서는 Q도 참이 됨을 의미한다.

논리적 결과 vs. 항진적 결과

예: 통합 진리표를 이용한 항진적 결과의 판정

A∨ B는 A ∧ B의 항진적 결과tautological consequence이다.

A∨ B는 A ∧ B의 논리적 결과logical consequence이다.

논리적 결과 vs. 항진적 결과

Q가 P₁, . . . , Pn의 항진적 결과이면, Q가 P1, . . . , Pn의 논리적 결과이다.

증명:

(1) Q가 P

₁

_n

(2) 더불어 P

1

_n

(3) 이제 Q가 논리적으로 참임을 보이면 된다.

(4) 그런데 P

1

n

1

n

(5) 따라서 전제 (1)에 의해 Q도 참인 진리값을 갖는다. 따라서

논리적 결과 vs. 항진적 결과

논리적 결과인데 항진적 결과가 아닌 경우

문장 a = c는 문장 (a = b ∧ b = c)의 논리적 결과이지만 항진적 결과는 아니다. (통합 진리표 참조)

논리적 결과 vs. 항진적 결과

또 다른 항진적 결과의 예:

A∨ B

¬A B

A∨ ¬B B∨ C A∨ C

Boole 소프트웨어로 통합 진리표를 만들어 보고, 결론이 전제의 항진적 결과인지 검사해보자.

Fitch에서의 논리적/항진적 결과

Fitch에서 다음 파일을 열고 놀아보자.

Taut Con 1 (교재 114쪽 You Try It) Taut Con 2 (교재 116쪽 You Try It)

위 두 개의 예제를 Fitch로 풀기 위해 사용하는 규칙은 아래의 세 가지 중에 하나이다.

Taut Con :TautologicalConsequence

I 항진적 결과

FO Con :First-OrderConsequence

Fitch에서의 논리적/항진적 결과

FO Con 규칙이 Taut Con 규칙보다 강력하다.

Ana Con 규칙이 FO Con 규칙보다 강력하다.

따라서 교재 116쪽의 You Try It에서 다루는 Taut Con 2 파일에 나오는 각각의 주장을 Fitch를 이용하여 증명할 경우 위 세 가지 규칙중에서 적용할 수 있는 가장 약한 규칙을 알아내야 한다.

내용 소개

1

2

3

4

논리적 동일성 예제

a = b ∧ Cube(a) 와 a = b ∧ Cube(b) 는 논리적으로 동일하다 즉, 다음 두 개의 주장이 논리적으로 타당하다:

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

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

논리적 동일성 예제 증명

증명:

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)도 논리적으로 참이다.

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

항진적 동일성

두 문장이 항진적으로 동일하다함은통합 진리표의 모든 행이 동일함을 의미한다.

예제:

항진적 동일성 예제

예제: ¬((A ∨ B) ∧ ¬)C vs. (¬A ∧ ¬B) ∨ C

논리적 동일성 vs. 항진적 동일성

두 문장이 항진적으로 동일하면 논리적으로도 동일하다.

그러나, 논리적으로 동일하지만 항진적으로 동일하지 않을 수 있다.

논리적 동일성 vs. 항진적 동일성: 예제

예: 아래 두 문장은 논리적으로 동일하지만 항진적으로는 동일하지 않다.

a = b ∧ Cube(a) vs. a = b ∧ Cube(b)

항진적으로 동일한 문장 만들기

아래의 법칙들을 이용하며 문장의 일부를 대체하는 방식을 이용하여 항진적으로 동일하면서 보다 단순한 문장을 만들어 낼 수 있다.

이중 논리역Double Negation의 법칙: ¬¬P ⇔ P De Morgan의 법칙

I ¬(P ∧ Q) ⇔ (¬P ∨ ¬Q) 또는 ¬(P ∨ Q) ⇔ (¬P ∧ ¬Q) 결합법칙associativity

I P∧ (Q ∧ R) ⇔ (P ∧ Q) ∧ R ⇔ P ∧ Q ∧ R

I P∨ (Q ∨ R) ⇔ (P ∨ Q) ∨ R ⇔ P ∨ Q ∨ R 교환법칙commutativity

I P∧ Q ⇔ Q ∧ P 또는 P ∨ Q ⇔ Q ∨ P 멱등법칙idempotence

I P∧ P ⇔ P 또는 P ∨ P ⇔ P

항진적으로 동일한 문장 만들기 예제