Search
Duplicate

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

명제와 증명

명제와 연결사

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

진리표

진리표란 명제의 진리값을 표로 나타낸 것
Show All
Search
p
q
~p
p AND q
p OR q
p -> q
p <-> q
F
F
F
T
F
F
T
T
F
T
T
F
F
T
F
F
T
T
진리집합
해당 명제가 참이 되도록 하는 모든 원소들의 집합
집합이므로 대문자로 표기
명제 P가 거짓이라는 것은 진리집합에 해당 하는 원소들이 없다는 의미이고, P는 공집합이라는 의미가 된다.
pqp \to q 는 p가 q의 부분집합인지를 묻는 것과 같다. 만일 p가 거짓이면 p가 공집합이 되는 것이므로, p가 거짓일 때는 q와 관계 없이 참이 된다.
진리표에 의해 다음 명제들은 참이다.
pqpqp \to q \equiv \sim p \vee q
(pq)pq\sim (p \wedge q) \equiv \sim p \vee \sim q (드모르간의 법칙)
pqqpp \to q \equiv \sim q \to \sim p (대우 법칙)
(pq)rp(qr)(p \vee q) \vee r \equiv p \vee (q \vee r) (결합 법칙)
p(qr)(pq)(pr)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
ppp \rightleftharpoons \sim p
<< \rightleftharpoons \geq

함의와 동치

항진명제와 모순명제

항진명제: 모든 논리적 가능성의 진리값들이 참인 명제. t
모순명제: 모든 논리적 가능성의 진리값들이 거짓인 명제. c
항진명제와 모순명제의 성질
임의의 명제 p에 대하여
pptp \vee \sim p \equiv t
ppcp \wedge \sim p \equiv c
tptt \vee p \equiv t
cppc \vee p \equiv p
tppt \wedge p \equiv p
cpcc \wedge p \equiv c
항진명제, 모순명제의 정의에 따라 아래 명제는 참이다.
pcp\sim p \to c \equiv p
(pq)(qr)(pr)t(p \to q) \wedge (q \to r) \to (p \to r) \equiv t
p이면 q이고, q이면 r이면, p이면 r이다.

함의와 동치

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