[이산수학] 명제, 논리연산자, 조건, 대우

1. Mathematical Statement

universal statement: 모든 집합의 요소에 대해 참인 명제

 ex) 모든 양수는 0보다 크다

 

conditional statement: 하나가 참이면 다른 것도 참인 명제

 ex) 18이 378을 나눌 수 있다면, 6도 378을 나눌 수 있다.

 

existential statement: 참일수도, 아닐 수도 있는 속성이 주어지면 참인 속성이 적어도 하나는 있는 명제

 ex) 짝수인 소수(prime)이 적어도 하나 존재한다.

 

proposition(명제): True(참) /False(거짓)으로만 나타낼 수 있는 문장

 

"sky is Blue", "2+2 = 5" : 참/거짓으로 나타낼 수 있음, 명제 o
"come here", "x = 7" : 참/거짓으로 나타낼 수 없음, 명제 x

 

 

2. 항진명제와 모순명제

tautology(항진명제): 어떤 경우에도 항상 참인 명제

  

contradiction(모순명제): 어떤 경우에도 항상 거짓인 명제

항진명제도, 모순명제도 아닌 경우엔 contingency(불확정 명제): 때에 따라 참, 거짓이 존재한다.

 

logically equivalent(논리적 동치) ≡ ,↔ : 두 양쪽 문장이 항상 같은 진리표를 나타낸다. (양변의 논리 연산이 일치한다)

 

 

3. Logical operater(논리연산자)

위에서 아래 순으로 우선순위가 존재한다.

 

negation(부정, NOT) ¬                                             (c언어에선 ~)

conjunction(논리곱, AND) ∧                                    (c언어에선 &&)

disjuction(논리합, OR) ∨                                          (c언어에선 ||)

exclusive-or(베타적 논리합, XOR) ⊕                       (c언어에선 ^)  - 서로 다르면 T, 아니면 F

implication, or conditional operator(조건문)  →     

bi-conditional (필요충분조건)  ↔  

 

※ 추가 연산자:

nand |  : and연산에 not을 취한 것이다. 그러므로 ¬(p∧q)와 같다.

nor ↓ : or 연산에 not을 취한다. 그러므로 ¬(p∨q) 와 같다.

 

※ 진리표를 이용해 True/False 관계 설명하기: 

p	q	¬p	¬q	p ∧q	p∨ q	p ⊕ q	p  | q	p ↓q	p →q	p↔q
T	T	F	F	T	T	F	F	F	T	T
T	F	F	T	F	T	T	T	F	F	F
F	T	T	F	F	T	T	T	F	T	F
F	F	T	T	F	F	F	T	T	T	T

빨간색 관계는 무조건 기억하자!

 

 

 

4. Conditional(조건문) 진리표 쉽게 이해하기!

위 진리표에서 p →q 의 진리표가 왜 저렇게 생겼는지 이해가 쉽게 되지 않을 것이다. 예시를 통해 살펴보자.

 

예시:
p가 시험 질문, q가 내가 쓴 시험의 정답이라고 하고, p →q 를 내가 받는 시험점수라고 하자.

p	q	p→q
T	T	T
T	F	F
F	T	T
F	F	T

1. 시험 질문이 정확하고 정확한 정답을 작성했을 경우 -> 점수를 받는다
2. 시험 질문이 정확하고 틀린 답을 작성했을 경우 -> 점수를 못 받는다
3. 시험 질문 틀림, 정확한 답을 작성했을 경우 -> 시험 질문 자체가 틀렸으므로 답안과 관계없이 점수를 받는다.
4. 시험 질문 틀림, 틀린 답을 작성했을 경우 -> 시험 질문 자체가 틀렸으므로 답안과 관계없이 점수를 받는다.

 

p가 거짓이면 p →q 는 무조건 참!

q가 정답이면 p →q 무조건 거짓!

그리고,  p →q 와 ¬p∨q는 논리적 동치다. 이를 Definition of implication이라고 한다. (증명은 진리표로)

술어논리 or 논리 연산자 축약시 사용하는 스킬이다.

p → q	¬p∨q
T	T
F	F
T	T
T	T

 

 

 

5. Conditional(조건문)의 변형 4가지

conditional(조건명제):  p →q

inverse(이) : ¬p →¬q

converse(역) q →p

contra positive(대우)  ¬q →¬p

p →q	¬p →¬q	q →p	¬q →¬p
T	T	T	T
F	T	T	F
T	F	F	T
T	T	T	T

 

조건명제와 대우는 논리적으로 동치다! 기억하자. 또한 , 이와 역도 논리적 동치다.

p →q ≡ ¬q →¬p

¬p →¬q ≡ q →p

 

 

6. conditional - disjunction equivalence: 조건문을 설명하는 다양한 표현들

p →q를 설명하는 다양한 표현들:

p implies q

if p, then q

q if p

q whenever p

p is sufficienct for q (p는 q의 충분조건)

q is necessary for p (q는 p의 필요조건) - q가 화살표를 맞았으니 피를 흘린다는.. 식으로 외우기

p only if q

 

위 표현은 모두 같은 표현이다. 시험에서 조심하기!

 

 

 

7. 바닥함수와 천장함수

⌊ x ⌋ floor(x), 바닥함수: x보다 크지 않은 최대 정수 (고등학교때 배운 가우스함수와 같다)

⌈ x ⌉ ceil(x), 천장함수: x보다 작지 않은 최소 정수 

 

예시:

⌊ 3.72 ⌋ = 3

⌈ 3.72 ⌉ = 4