Search

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

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

1

개념

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

논리식

•
p→q≡¬p∨qp \to q \equiv \neg p \vee q
•
p↔q≡(p→q)∧(q→p)p \leftrightarrow q \equiv (p \to q) \wedge (q \to p)
•
p⇔q:p≡qp \Leftrightarrow q : p \equiv q
•
p∨t≡tp \vee t \equiv t
•
p∧t≡pp \wedge t \equiv p
•
p∨c≡pp \vee c \equiv p
•
p∧c≡cp \wedge c \equiv c
•
p∨¬p≡tp \vee \neg p \equiv t
•
p∧¬p≡cp \wedge \neg p \equiv c
•
p⇒tp \Rightarrow t
•
c⇒pc \Rightarrow p
•
p∨p≡pp \vee p \equiv p
•
p∧p≡pp \wedge p \equiv p
•
¬(¬p)≡p\neg(\neg p) \equiv p
•
p∨q≡q∨pp \vee q \equiv q \vee p
•
p∧q≡q∧pp \wedge q \equiv q \wedge p
•
¬(p∨q)≡¬p∧¬q\neg(p \vee q) \equiv \neg p \wedge \neg q
•
¬(p∧q)≡¬p∨¬q\neg(p \wedge q) \equiv \neg p \vee \neg q
•
p∨(q∨r)≡(p∨q)∨rp \vee (q \vee r) \equiv (p \vee q) \vee r
•
p∧(q∧r)≡(p∧q)∧rp \wedge (q \wedge r) \equiv (p \wedge q) \wedge r
•
p∧(q∨r)≡(p∧q)∨(p∧r)p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)
•
p∨(q∧r)≡(p∨q)∧(p∨r)p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)
•
p→q≡¬q→¬pp \to q \equiv \neg q \to \neg p (대우)
•
p→q≡p∧¬q→cp \to q \equiv p \wedge \neg q \to c (귀류법)

2

개념

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

논리식

•
p⇒p∨qp \Rightarrow p \vee q
•
p∧q⇒pp \wedge q \Rightarrow p
•
(p→q)∧(q→r)⇒p→r(p \to q) \wedge (q \to r) \Rightarrow p \to r
•
(p∨q)∧¬q⇒p(p \vee q) \wedge \neg q \Rightarrow p
•
(p→q)∧p⇒q(p \to q) \wedge p \Rightarrow q
•
(p→q)∧¬q⇒¬p(p \to q) \wedge \neg q \Rightarrow \neg p
•
p∨(p∧q)≡pp \vee (p \wedge q) \equiv p
•
p∧(p∨q)≡pp \wedge (p \vee q) \equiv p
•
(p→q)∧(r→s)⇒(p∨r→q∨s)(p \to q) \wedge (r \to s) \Rightarrow (p \vee r \to q \vee s)
•
(p→q)∧(r→s)⇒(p∧r→q∧s)(p \to q) \wedge (r \to s) \Rightarrow (p \wedge r \to q \wedge s)
•
¬(p∨q∨r)≡¬p∧¬q∧¬r\neg(p \vee q \vee r) \equiv \neg p \wedge \neg q \wedge \neg r
◦
항의 개수가 무한히 많아도 성립한다.
◦
¬(p1∨p2∨...∨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}
•
p⊻q≡(¬p∧q)∨(p∧¬q)p \veebar q \equiv (\neg p \wedge q) \vee (p \wedge \neg q)
•
p⊻q≡q⊻pp \veebar q \equiv q \veebar p
•
p⊻(q⊻r)≡(p⊻q)⊻rp \veebar (q \veebar r) \equiv (p \veebar q) \veebar r
•
p⇒qp \Rightarrow q일 때
◦
r∨p⇒r∨qr \vee p \Rightarrow r \vee q
◦
r∧p⇒r∧qr \wedge p \Rightarrow r \wedge q
Made with