명제와 집합

1. 명제와 증명

(1) 명제와 연결사

명제 : 참, 거짓이 분명하게 판단되는 문장 단순 명제 : 한 개의 명제 합성 명제 : 몇 개의 단순 명제들이 연결사에 의해 결합된 명제

연결사 : 두 명제 p와 q에 대해 아래의 연결사가 있음

명칭	기호	읽는 법
부정	~$p$	not p
논리곱	$p \wedge q$	p and q
논리합	$p \vee q$	p or q
조건	$p \rightarrow q$	if p, then q
쌍조건	$p \leftrightarrow q$	p if and only if q

(2) 진리표

p	q	~p	$p \wedge q$	$p \vee q$	$p \rightarrow q$	$p \leftrightarrow q$
T	T	F	T	T	T	T
T	F	F	F	T	F	F
F	T	T	F	T	T	F
F	F	T	F	F	T	T

(3) 연역적 추론

이미 알고 있는 판단을 근거로 새로운 판단을 유도하는 것이다.

집합론에 들어가기 앞서 아래의 것들은 항상 참으로 알아두면 좋다.

• $ p \rightarrow q \equiv \sim p \vee q $
• $ \sim (p\wedge q) \equiv \sim p \vee \sim q $
• $ p \rightarrow q \equiv \sim q \rightarrow \sim p $
• $ (p \vee q)\vee r \equiv p \vee (q\vee r) $
• $ p \vee (q \wedge r) \equiv (p\vee q) \wedge (p \vee r) $

2. 명제함수와 부정

(1) 명제함수와 한정기호

명제함수 : 변수 x가 결정되어야만 참, 거짓이 판단되는 문장
한정 기호 : 전칭 기호와 존재기호

• 전칭기호 $\forall$ : 전체
• 존재기호 $\exists$ : 적어도 한 개 이상 있다

(2) 명제의 부정

두 명제 p와 q에 대해, x의 모집단은 건드리지 않도록 하며 다음 4가지 원리를 모두 적용한다.

$$\forall$$	$$\rightleftharpoons$$	$$\exists$$
$$\wedge$$	$$\rightleftharpoons$$	$$\vee$$
$$ㅔ$$	$$\rightleftharpoons$$	$$\sim p$$
>	$$\rightleftharpoons$$	$$\leq$$

3. 함의와 동치

(1) 항진명제와 모순명제

항진 명제 : 모든 논리적 가능성의 진리값들이 참인 명제 = t
모순 명제 : 모든 논리적 가능성의 진리값들이 거짓인 명제 = c

항진 명제와 모순 명제의 성질

임의의 명제 p에 대해서

• $ p \vee \sim p \equiv t $
• $ p \wedge \sim p \equiv c $
• $ t \vee p \equiv t $
• $ c \vee p \equiv p $
• $ t \wedge p \equiv p $
• $ c \wedge p \equiv c $

(2) 함의와 동치

함의

항진인 조건문 $p \rightarrow q$ 를 논리적 함의라 하고 $p \Rightarrow q$로 나타내며 p는 q의 충분조건, q는 p의 필요조건이라 한다.

동치

항진인 쌍조건문 $p \leftrightarrow q$ 를 동치라 하고 $p \Leftrightarrow q$로 나타내며 p와 q는 서로의 필요충분조건이라 한다.

참고 자료

• 이상엽Math - 집합론 1강. 명제와 논리