Search
Duplicate

이상엽/ 집합론/ 명제와 논리

명제와 증명

명제와 연결사

•
명제: 참, 거짓이 분명히 판단되는 문장
◦
단순 명제: p, q, r
◦
합성 명제: 몇 개의 단순 명제들이 연결사에 의해 결합된 명제
•
연결사: 두 명제 p와 q에 대해
◦
부정
▪
∼p\sim p
▪
not p
◦
논리곱
▪
p∧qp \wedge q
▪
p and q
◦
논리합
▪
p∨qp \vee q
▪
p or q
◦
조건
▪
p→qp \to q
▪
if p then q
◦
쌍조건
▪
p↔qp \leftrightarrow q
▪
p if and only if q
▪
줄여서 iff 라고도 함

진리표

•
진리표란 명제의 진리값을 표로 나타낸 것
Search
p
q
~p
p AND q
p OR q
p -> q
p <-> q
T
Open
T
F
T
T
T
T
T
Open
F
F
F
T
F
F
F
Open
T
T
F
T
T
F
F
Open
F
T
F
F
T
T
•
진리집합
◦
해당 명제가 참이 되도록 하는 모든 원소들의 집합
◦
집합이므로 대문자로 표기
•
명제 P가 거짓이라는 것은 진리집합에 해당 하는 원소들이 없다는 의미이고, P는 공집합이라는 의미가 된다.
•
p→qp \to q 는 p가 q의 부분집합인지를 묻는 것과 같다. 만일 p가 거짓이면 p가 공집합이 되는 것이므로, p가 거짓일 때는 q와 관계 없이 참이 된다.
•
진리표에 의해 다음 명제들은 참이다.
◦
p→q≡∼p∨qp \to q \equiv \sim p \vee q
◦
∼(p∧q)≡∼p∨∼q\sim (p \wedge q) \equiv \sim p \vee \sim q (드모르간의 법칙)
◦
p→q≡∼q→∼pp \to q \equiv \sim q \to \sim p (대우 법칙)
◦
(p∨q)∨r≡p∨(q∨r)(p \vee q) \vee r \equiv p \vee (q \vee r) (결합 법칙)
◦
p∨(q∧r)≡(p∨q)∧(p∨r)p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r) (분배 법칙)
◦
위 명제들의 and를 or로, or를 and로 동시에 바꾸면 결과는 같다.

연역적 추론

•
연역적 추론이란 이미 알고 있는 판단을 근거로 새로운 판단을 유도하는 것

명제 함수

명제함수와 한정기호

•
명제함수: 변수 x가 결정되어야만 참, 거짓이 판단되는 문장
◦
p(x),q(x)...p(x), q(x)...
•
한정기호: 전칭기호와 존재기호
◦
∀\forall: for every
◦
∃\exists: for some

명제의 부정

•
두 명제 p와 q에 대해, x의 모집단은 건드리지 않도록 하며 다음의 4가지 원리를 모두 적용한다.
◦
∀⇌∃\forall \rightleftharpoons \exists
◦
∧⇌∨\wedge \rightleftharpoons \vee
◦
p⇌∼pp \rightleftharpoons \sim p
◦
<⇌≥< \rightleftharpoons \geq

함의와 동치

항진명제와 모순명제

•
항진명제: 모든 논리적 가능성의 진리값들이 참인 명제. t
•
모순명제: 모든 논리적 가능성의 진리값들이 거짓인 명제. c
•
항진명제와 모순명제의 성질
◦
임의의 명제 p에 대하여
▪
p∨∼p≡tp \vee \sim p \equiv t
▪
p∧∼p≡cp \wedge \sim p \equiv c
▪
t∨p≡tt \vee p \equiv t
▪
c∨p≡pc \vee p \equiv p
▪
t∧p≡pt \wedge p \equiv p
▪
c∧p≡cc \wedge p \equiv c
•
항진명제, 모순명제의 정의에 따라 아래 명제는 참이다.
◦
∼p→c≡p\sim p \to c \equiv p
◦
(p→q)∧(q→r)→(p→r)≡t(p \to q) \wedge (q \to r) \to (p \to r) \equiv t
▪
p이면 q이고, q이면 r이면, p이면 r이다.

함의와 동치

•
함의: 항진인 조건문 p→pp \to p를 논리적 함의라 하고, p⇒pp \Rightarrow p 로 나타내며, p는 q의 충분조건, q는 p의 필요조건이라 한다.
•
동치: 항진인 쌍조건문 p↔pp \leftrightarrow p 를 동치라 하고, p⇔pp \Leftrightarrow p로 나타내며 p와 q는 서로의 필요충분조건이라 한다.
Made with