컴공생의 공부LOG

[논리학] 3. The Boolean Connectives 본문

학교 수업/1학년 1학기

[논리학] 3. The Boolean Connectives

푸우키 2024. 11. 18. 01:47

Boolean Connectives (=Truth Functional Connectives)

Simple Connectives

- Conjunction(= and)

- Disjunction(= or)

- Negation(= not)

 

-> Truth table을 이용해 complex sentence의 truth 판단을 할 때,

    complex sentence를 simpler sentence로 쪼갤 때 사용 

 

Negation (¬)

- 부정하려는 문장 에 붙여 씀 (= not에 대응)

- 문장 앞에 몇 개든지 붙여 쓸 수 있음 

 

ex) John isn't home.

->  ¬Home(john)

 

ex) 동일성 부정에 사용 가능

-> ¬(b=c) -> b ≠ c

 

- Atomic sentence 또는 atomic sentence에 ¬을 붙였을 때, 이를 literal 하다고 함 

- FOL 문장 P가 있다면, ¬P도 FOL 문장이 됨

- ¬P는 P가 참이 아닐 때만 참이 됨 (iff)

 iff: if and only if

Truth Table - Negation

 

Conjunction (∧)

- 영어에서 and, moreover, but에 대응

- 두 문장 사이에 위치함

-> 즉, P 와 Q 두 문장이 주어지면 P ∧ Q 로 사용

 

ex) John is home and Mary is home

->   Home(john) Home(mary)

 

영어 문장에서 and가 없는 경우

ex) d is a large cube

->  Large(d) Cube(d)

 

- P와 Q가 FOL의 문장이면, P ∧ Q도 FOL 문장

- FOL 문장 P ∧ Q는 P와 Q가 모두 참일 경우에만 참이 됨 (iff)

- 따라서, P ∧ Q는 P 또는 Q가 거짓일 때, 거짓이 됨

Truth Table - Conjunction

 

Disjunction (∨)

- 영어에서 or에 대응

- 두 문장 사이에 위치

-> 즉, P 와 Q 두 문장이 주어지면 P ∨ Q 로 사용

Semantic : 인 경우

- P ∨ Q 는 P나 Q 둘 중 하나만 참이거나 둘 모두 참일 때는 참

P ∨ QP 가 참이거나 Q가 참이면 참임 (또는 둘 다 참일 때 참)

 

ex) John is home or Mary is home

->   Home(john) Home(mary) 

 

Semantic : 인 경우는 아래와 같음

– John is home 이 참이지만 Mary is not 인 경우 (exclusive)

– Mary is home 이 참이지만 John is not 인 경우 (exclusive)

– John 과 Mary 모두 home 인 경우 (inclusive)

 

항상 exclusive한 경우와 inclusive한 경우 모두 포함

-> exclusive를 표현할 때는 아래와 같이 씀

[Home(john) Home(mary)] ∧ ¬[Home(john) Home(mary)]

 

Either or

-영어에서는 둘 중 하나만 선택

- 그러나 FOL 번역할 때, disjunction 그대로 사용 (inclusive, exclusive)

 

ex) Either Pris bit Scruffy or Scruffy bit Pris

->   Bit(pris, scruffy) Bit(scruffy, pris)

 

Neither nor

- 둘 모두 선택 못하는 경우이므로 아래와 같이 사용

 

ex) Neither John nor Mary is at home

->  ¬(Home(john) Home(mary))

-> 두 명 중 한 명도 집에 없고, 둘 모두 다 집에 없음

 

- P 와 Q 가 FOL 의 문장이라면, P ∨ Q 도 FOL의 문장임

Truth Table - Disjunction

 

Ambiguity and Parentheses

- 불분명한 문장은 괄호를 사용하여 명확하게 표현

- 순서: ¬ > ∧ > ∨

- 다른 connective 를 쓸 때는 conjunction 과 disjunction 에 괄호 사용