Search
Duplicate

데코수학/ 집합론/ 명제논리

(유튜브 동영상인데 현재는 삭제되어서 내용만 남김)

1

개념

4대 논리학자 - 아리스토텔레스, 라이프니츠, 프레게, 괴델
시대가 지나다보니 논리가 기호화됨. 그래서 수학처럼 계산할 수 있게 되어서 기호논리학이 수학의 일부가 됨.
명제 (p,q,r)(p, q, r)
참이거나 거짓, 둘 중 하나의 진리값을 가지는 식이나 문장
명제함수
변수 xx에 값을 대입하면 명제가 되는 식이나 문장
동치 (pq)(p \equiv q)
명제 ppqq의 진리값이 같은 경우
명제의 연산 - 부정(not), 논리합(or), 논리곱(and), 조건문(if p, q)
부정은 원래 명제의 부정
논리합은 p,qp, q 중 하나 이상이 참인 경우 참, 그 외엔 거짓
논리곱은 p,qp, q 가 모두 참이고, 그 외엔 거짓
조건문은 pp가 거짓이면 무조건 참, ppqq가 참이면 참
Show All
Search
p
q
¬p
p ∨ q
p ∧ q
p → q
p ↔ q
1
1
1
0
1
0
0
0
1
0
0
0
1
0
1
1
1
1
항진명제 (t)(t)
모든 경우에 참(1)인 명제
모순명제 (c)(c)
모든 경우에 거짓(0)인 명제
함의
같다는 것보다는 좀 더 약한 개념 (ex 부등호)
pq:pqtp \Rightarrow q : p \to q \equiv t

논리식

pq¬pqp \to q \equiv \neg p \vee q
pq(pq)(qp)p \leftrightarrow q \equiv (p \to q) \wedge (q \to p)
pq:pqp \Leftrightarrow q : p \equiv q
pttp \vee t \equiv t
ptpp \wedge t \equiv p
pcpp \vee c \equiv p
pccp \wedge c \equiv c
p¬ptp \vee \neg p \equiv t
p¬pcp \wedge \neg p \equiv c
ptp \Rightarrow t
cpc \Rightarrow p
pppp \vee p \equiv p
pppp \wedge p \equiv p
¬(¬p)p\neg(\neg p) \equiv p
pqqpp \vee q \equiv q \vee p
pqqpp \wedge q \equiv q \wedge p
¬(pq)¬p¬q\neg(p \vee q) \equiv \neg p \wedge \neg q
¬(pq)¬p¬q\neg(p \wedge q) \equiv \neg p \vee \neg q
p(qr)(pq)rp \vee (q \vee r) \equiv (p \vee q) \vee r
p(qr)(pq)rp \wedge (q \wedge r) \equiv (p \wedge q) \wedge r
p(qr)(pq)(pr)p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)
p(qr)(pq)(pr)p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)
pq¬q¬pp \to q \equiv \neg q \to \neg p (대우)
pqp¬qcp \to q \equiv p \wedge \neg q \to c (귀류법)

2

개념

카르노맵이란 논리식을 간단하게 바꾸는 방법. 아래와 같이 생긴 표를 사용한다.
표에서는 인접한 것끼리 1번만 변하는 형태로 열을 쓴다. 그래야 묶을 수 있음.
Show All
Search
p \ qr
00
01
11
10
쌍대원리
모든 명제논리 법칙들에 대하여 ,tc,\wedge \leftrightarrow \vee, t \leftrightarrow c, \Rightarrow \leftrightarrow \Leftarrow 바꿔도 법칙이 성립한다.
XOR ()(\veebar)
ppqq가 다를 때만 참

논리식

ppqp \Rightarrow p \vee q
pqpp \wedge q \Rightarrow p
(pq)(qr)pr(p \to q) \wedge (q \to r) \Rightarrow p \to r
(pq)¬qp(p \vee q) \wedge \neg q \Rightarrow p
(pq)pq(p \to q) \wedge p \Rightarrow q
(pq)¬q¬p(p \to q) \wedge \neg q \Rightarrow \neg p
p(pq)pp \vee (p \wedge q) \equiv p
p(pq)pp \wedge (p \vee q) \equiv p
(pq)(rs)(prqs)(p \to q) \wedge (r \to s) \Rightarrow (p \vee r \to q \vee s)
(pq)(rs)(prqs)(p \to q) \wedge (r \to s) \Rightarrow (p \wedge r \to q \wedge s)
¬(pqr)¬p¬q¬r\neg(p \vee q \vee r) \equiv \neg p \wedge \neg q \wedge \neg r
항의 개수가 무한히 많아도 성립한다.
¬(p1p2...pn)¬p1¬p2...¬pn\neg(p_{1} \vee p_{2} \vee ... \vee p_{n}) \equiv \neg p_{1} \wedge \neg p_{2} \wedge ... \wedge \neg p_{n}
pq(¬pq)(p¬q)p \veebar q \equiv (\neg p \wedge q) \vee (p \wedge \neg q)
pqqpp \veebar q \equiv q \veebar p
p(qr)(pq)rp \veebar (q \veebar r) \equiv (p \veebar q) \veebar r
pqp \Rightarrow q일 때
rprqr \vee p \Rightarrow r \vee q
rprqr \wedge p \Rightarrow r \wedge q