이산수학 1.2 Aplication of Propositional Logic 명제이론의 응용

chapter 1. The Foundations: Logic and Proofs

 

1.1 Propositional Logic 명제이론(section 1.2)

 

Translating English Sentence

영문장 → 명제

1. atomic proposition 확인 → 명제변수로 나타내기

2. 적절한 logical connectives 결정

 

ex 1)  "If I go to Harry’s or to the country, I will not go shopping."

• p : I go to Harry’s
• q : I go to the country.
• r :  I will go shopping.

If p or q then not r.

 

ex 2)  “You can access the Internet from campus only if you are a computer science major or you are not a freshman.”

• a : “You can access the internet from campus,”
• c : “You are a computer science major,”
• f : “You are a freshman.”

a→ (c ∨ ¬ f )

 

 

Logic Puzzle (by Raymond Smullyan)

한 섬에 기사와 범죄자 두 종류의 거주민들이 존재한다. 기사는 늘 진실만 말하고 범죄자는 늘 거짓만 말한다.

당신은 섬에서 A와 B를 만났다. 

 

A : "B is a knight"

B : "The two of us are of opposite types"

 

Q. A와 B의 type(기사 or 범죄자)?

 

Solution

p, q를 다음과 같이 가정한다.

• p : A is knight
• q : B is knight

따라서

• ¬p : A is knave
• ¬q : B is knave

만약 A가 기사라면, p는 true이다. 또한 기사는 늘 진실만 말하기 때문에, q는 true여야 한다.

따라서 *(p ∧ ¬q) ∨ (¬p ∧ q) 는 true가 되어야만 하지만(B가 둘의 type이 다르다고 했으므로), 그렇지 않다.

따라서 A는 기사가 아니다.

따라서 ¬p가 true이다. 

 

만약 A가 범죄자라면, 범죄자는 늘 거짓만 말하기 때문에 B는 기사가 아니다(B는 A와 같은 type임). 따라서 둘 다 범죄자이므로 ¬p와 ¬q는 성립한다. 

 

따라서 A와 B는 둘 다 범죄자이다. 

 

 

*(p ∧ ¬q) ∨ (¬p ∧ q) 

• (A는 기사 and B는 기사X) or (A는 기사X and B는 기사)
• 둘 중 하나만 T여야 T
• p ⊕ q와 동치

 

 

 

 

---

출처: Discrete Mathematics and Its Applications (K. H. Rosen 저, McGraw Hill, 2007)