이산수학 1.1 Propositional Logic 명제이론(+implication함축을 쉽게 이해하기)

chapter 1. The Foundations: Logic and Proofs

 

1.1 Propositional Logic 명제이론(section 1.1)

 

Propositions(명제)

명제: True / False로 정의할 수 있는 서술문.

 

명제의 예

1. 지구는 둥글다

2. 1 + 0 = 0

3. 7 + 7 = 14

 

명제가 아닌 경우

1. 자리에 앉아라.

2. 오늘 몇 일이지?

3. x + 3 = 5    // x값에 따라 결과가 달라짐

 

 

propositional Logic

명제 변수 propositional variable

p, q, r, s, ....

 

복합 명제 Compound Propositions

하나 이상의 명제와 논리 연산, 괄호로 이루어진 명제

 

논리연산

• Negation 부정 ¬
• Conjunction ∧ 논리곱(and)
• Disjunction ∨ 논리합(or)
• Implication → 만약 A이면 B이다. 
• Biconditional ↔ A와 B가 모두 참이거나 모두 거짓일 때 성립

 

Compound Propositions 복합 명제

Negation 부정(not)

ex.

p: "The earth is round." 

¬p: "It is not the case that the earth is round." or "The earth is not round."

 

 

Conjunction(and)

☞ p, q 둘 다 True 인 경우에만 True

 

ex. 

p: "I am at home."

q: "It is rainning."

p∧q: "I am at home and It is rainning."

 

 

Disjunction(or)

☞ p, q 둘 다 False 인 경우에만 False

 

ex.

p: "I am at home."

q: "It is rainning."

p∧q: "I am at home or It is rainning."

 

 

The Connective Or in English

-Exclusive Or (XOR) 배타적 논리합

☞ p, q 가 서로 다른 경우에만 True

 

ex.

“Soup or salad comes with this entrée”

→수프나 샐러드 둘 중 하나만 나옴. 둘 다 나오지 X

 

 

Implication(함축)

출처: 위키피디아

• p→q
• "if p, then q"
• 만약 A이면(가정), B이다(결론).
• A가 참이면 B도 참이다. 

ex.

p: "I am at home."

q: "It is rainning."

p→q: “If I am at home then it is raining.”

 

 

Implication(함축)의 이해

전제조건(p) - 결론(q) 사이의  connection이 없어도 상관없다.

p→q의 "meaning"은 오로지 p와 q의 진리값에만 의존한다. 

즉,

 

"만약 달이 녹색 치즈로 만들어졌다면, 나는 빌게이츠보다 더 많은 돈을 가지고 있다."
"if the moon is made of green cheese then I'm on welfare."
"If 1 + 1 = 3, then your grandma wears combat boots."

 

이런 말도 안 되는 소리도 참 거짓을 판별할 수만 있다면 p→q명제이다. 

 

논리적 조건을 바라보는 방법 중 하나는 obligation(의무) 또는 contract(계약)을 고려하는 것이다. 

 

"만약 제가 당선된다면, 세금을 낮추겠습니다."
"기말고사에서 100점을 받으면, A를 받을 것입니다."

 

만약 정치인이 당선되고 세금을 낮추지 않는다면 유권자들은 정치인이 선거공약을 어겼다고 말할 수 있다. 교수의 발언도 동일하다. 이를 p가 참이고 q가 거짓인 경우라고 할 수 있다. 

만약 정치인이 당선되지 않았거나 학생이 기말고사에서 100점을 받지 못한 경우라면, 정치인과 교수는 거짓을 말하지 않았으므로 해당 진술은 참이다.

 

 

함축p →q의 다양한 표현

• if p, then q                    
• p implies q (p는 q를 의미한다.)
• if p, q                             
• p only if q (q해야만 p이다.)       
• q unless  ¬p (¬p가 아닐 때 q이다.)              
• q when p
• q if p            
• q whenever p (p할 때는 언제나 q이다.)               
• p is sufficient for q
• q follows from p         
• q is necessary for p
• a necessary condition for p is q (q는 p의 필요조건)
• a sufficient condition for q is p (p는 q의 충분조건)

-가정p: 충분조건

-결론q: 필요조건

 

*필요 조건 / 충분 조건 / 필요충분 조건

필요조건

P → Q가 참일 때 그 정의에 의해 명제 P가 참이 되기 위해 먼저 명제 Q가 참일 필요가 있다. 즉 Q는 P가 성립하기 위한 필요조건이다. Q가 P를 포함하는 개념으로 볼 수 있다.

• '펭수는 동물이다(q)'는 '펭수는 펭귄이다(p)'의 필요조건이다. (펭수가 펭귄이기 위해서는 펭수가 동물일 필요가 있다)
• 여대에 입학하려면(p) 여자여야 한다(q).(여자는 여대에 입학하기 위한 필요조건이다.)
• 공무원이 되려면(p) 공무원 시험에 합격해야 한다(q).(공무원이기 위해서는 공무원 시험에 합격할 필요가 있다.)

충분조건 

P → Q가 참일 때 그 정의에 의해 명제 P가 참이라면 명제 Q는 참임이 충분히 보장된다. 즉 P는 Q가 성립하기 위한 충분조건이다. P가 Q에 포함되는 개념으로 볼 수 있다.

• '철수는 농구를 한다'는 '철수는 운동을 한다'의 충분조건이다.('철수가 농구를 한다'면 '철수는 운동을 한다'라고도 충분히 말 할 수 있다.)

필요충분조건

P → Q가 참이고 Q → P가 참이면 그 정의에 의해 P가 참이면 Q가 참이고 P가 거짓이면 Q는 거짓이다.
P → Q가 참일 때 P이면 Q이고, Q → P가 참일 때 P가 아니면 Q가 아니기 때문이다. 즉 P는 Q의 필요충분조건임과 동시에 Q는 P의 필요충분조건이다.

 

"P는 Q의 필요충분조건이다"와 그 의미가 같은 문장들은 다음과 같다:

• "P ⇔ Q"
• "P이면 Q이며, Q이면 P이다."
• "P가 아니면 Q가 아니며 Q가 아니면 P가 아니다."
• "P인 경우 오직 그 경우에만 Q이다."
• "P if and only if Q"
  • "P iff Q"로 줄여쓰는 경우가 잦다.
• "Q는 P의 필요충분조건이다."

P와 Q가 서로의 필요충분조건인 경우 P와 Q는 '동치'가 된다.

 

출처: 나무위키 <필요조건과 충분조건>

 

 

Converse, Contrapositive, and Inverse

• q →p            is the converse of p →q (역)
• ¬q → ¬ p    is the contrapositive  of p →q (대우)
• ¬ p → ¬ q     is the inverse of p →q (이)

 

Biconditional (상호조건문)

• 둘이 같으면 T / 다르면 F
• p ⊕ q와 반대
• “p  if and only if q .”
• (p → q) ∧ (q → p)
• p is necessary and sufficient for q
• if p then q, and conversely
• p iff q

 

ex.

p: "I am at home."

q: "It is rainning."

p↔q: “I am at home if and only if it is raining.”

 

 

Example Truth Table

진리표 작성하기의 예시

 

 

 

Equivalent Propositions 동치명제

p →q와  ¬q →¬p (대우)가 동치임을 보이고 있는 진리표

 

 

Precedence of Logical Operators

논리 연산 시 우선순위를 고려해야 한다. 

 

 

 

 

 

 

---

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