[이산수학] 명제

시작하기

현재 공부하고 있는 이산수학을 그냥 대충 정리해둔 글이다.

명제의 정의

명제 (Proposition)
True 나 False 으로 구분할 수 있는 문장이나 수식 -> 영어 수식자 p,q,r 등 으로 표현
ex : 서울은 대한민국의 수도다 -> 명확하게 참이라 판별할 수 있으므로 명제다.

진릿값 (Truth Value)
True 이나 False을 가리키는 값 -> T, F 또는 0, 1
ex : 미국의 수도는 뉴욕이다 -> F

논리 연산자(명제의 결합)

부정 (Negation) NOT
문장 p가 명제일 때 "p가 아니다"도 명제 -> ㄱp 또는 ~p

부정 진리표

p	~p
T	F
F	T

논리곱 (Conjunction) AND p^q
T ^ T = T & F

논리곱 p^q의 진리표

p	q	p ^ q
T	T	T
T	F	F
F	T	F
F	F	F

논리합 (Disjunction) OR pvq
F v F = F % T

논리합 pvq의 진리표

p	q	p v q
T	T	F
T	F	F
F	T	F
F	F	F

배타적 논리합 (Exclusive OR) XOR p xor q
T xor F = T % F <- 하나만 T 일때 T

배타적 논리합 p xor q의 진리표

p	q	p xor q
T	T	F
T	F	T
F	T	T
F	F	F

합성명제 (명제의 합성)

합성명제 (Compound Proposition)
하나 이상의 명제들이 결합되어 만들어진 명제로, AND(^), OR(v), NOT(ㄱ) 등의 논리 연산자(Logical Operators)를 이용해 명제를 결합

논리 연산자의 우선순위

우선순위	논리 연산자
1	ㄱ
2	v , ^
3	->, <->

합성명제는 진릿값에 따라 3가지로 나뉜다.

항진명제 T
합성명제를 구성하는 단일 명제의 진릿값에 상관없이 합성명제의 진릿값이 항상 T 인 명제

모순명제 F
합성명제를 구성하는 단일 명제의 진릿값에 상관없이 합성명제의 진릿값이 항상 F 인 명제

사건명제
항진명제도, 모순명제도 아닌 명제

함축 (조건명제)

함축 (Implication) / 조건명제 (Conditional Proposition) p -> q

p(조건 T) -> q(결론 F) = F % T

p(조건 T) => q(결론 T)

함축 p->q의 진리표

p	q	p->q
T	T	T
T	F	F
F	T	T
F	F	T

 

쌍방조건명제 (Biconditional) p <-> q

문장 p, q가 명제일 때, 명제 p와 q가 모두 조건이면서 결론인 명제

(p->q) ^ (q->p)

p = q  T

p != q F

쌍방조건명제 p<->q의 진리표

p	q	p<->q
T	T	T
T	F	F
F	T	F
F	F	T

역 (Converse), 이 (Inverse), 대우 (Contraposition)

함축 p->q의 역은 q->p, 이는 ㄱp->ㄱq, 대우는 ㄱq->ㄱp

함축 p->q의 역, 이, 대우 진리표

p	q	p->q	q->p	ㄱp->ㄱq	ㄱq->ㄱp
T	T	T	T	T	T
T	F	F	T	T	F
F	T	T	F	F	T
F	F	T	T	T	T