신흥철 교수의 이산 수학 1, 2강 : 1장 명제와 논리

이산 수학은 불연속을 다루는 수학이다.

대체적으로 1과 0을 다룬다.

• 1은 전원이 켜져있는 상태(참)
• 0은 전원이 꺼져있는 상태(거짓)

 1장 명제와 논리 

명제(Propsition)

• 명제의 정의 : 참 또는 거짓으로 구분되는 문장이나 수식 (영어 소문자 p,q,r 등으로 표현)
  ex) 컴퓨터 가격은 비싸다. 참 거짓 구분이 불가능하므로 명제 x
  x + 1 = 2 -> x 값에 따라 참 거짓이 달라지므로 명제 x
• 진릿값(Truth Value) : 참 또는 거짓이라는 두 종류의 값
  
  예제) "2**n = n ** 2을 만족하는 정수 n이 하나 이상 존재한다."는 문장은 명제인가?
  n 이 2, 4인 경우 둘다 만족하므로 이 문장은 명제에 해당하며 진릿값은 참이다.
• 논리연산자(명제의 결합) : 사칙 연산이 있는 것과 마찬가지로 명제와 명제를 결합하기 위한 연산자가 있다.
  • 부정(Negation : NOT ~p)
    명제 p에 대하여 ~p도 명제이다.
  • 논리 곱(Conjunction : AND p^q)
    명제 p,q의 진릿값이 모두 참일 때만 참이되고 그렇지 않을 때는 거짓이 되는 명제
  • 논리 합(Disjunction : OR, pvq)
    명제 p,q 의 진릿값이 모두 거짓일 떄 거짓이 되고, 그렇지 않을 때는 참이 되는 명제
  • 배타적 논리합(Exclusive OR : XOR, p _ q)
    명제 p,q의 진릿값 중 하나만 참일 때 참이 되고 그렇지 않을 때는 거짓이 되는 명제
• 합성 명제(명제의 합성)
  • 하나 이상의 명제들이 결합되어 만들어진 명제
    논리 연산자를 이용해서 명제를 결합
  • 사칙연산과 같이 논리 연산자들 사이에서도 우선순위가 있다.
    1. not / ()
    2. and / or
    3. ->(조건 명제)
  • 항진 명제(Tautology) T : 구성 명제 진릿값에 상관없이 항상 참인 합성 명제
     ex) pv~p : p가 참이든 거짓이든 이 명제는 항상 참이다.
  • 모순 명제(Contradiction) F : 구성 명제 진릿값에 상관없이 항상 거짓인 합성 명제
     ex) p^~p : p가 참이든 거짓이든 이 명제는 항상 거짓이다.
  • 사건 명제(Contingency) : 항진 명제도 모순 명제도 아닌 합성 명제

ex)
p^F(모순 명제) /  pvT(항진 명제) : 이 합성 명제들과 같이 참이 OR을 지배하거나 거짓이 AND를 지배하는 경우를 지배 법칙이라고 한다.
p^T / pvF (사건 명제) : 이 명제들은 오로지 P의 진릿값에 따라만 합성명제의 진릿값이 결정되므로 T는 AND에 대하여 , F는 OR에 대하여 항등 명제라고 한다. (마치 사칙 연산에서 x + 0이나 x * 1을 항등식이라고 하는 것과 같다)

예제) 합성 명제 ~(p^q) _ (~pvq)에 대한 진리표는?

(진리표 : 진리표(眞理表)는 모든 명제 및 그 조합의 불 함수에 대한 입출력 결과, 즉 진릿값을 기록한 표이다.)

p q	p^q	~p	~(p^q)	~pvq	~(p^q)_(~pvq)
T T	T	F	F	T	T
T F	F	F	T	F	T
F T	F	T	T	T	F
F F	F	T	T	T	F

• 함축(Implication, 조건 명제, p(조건) -> q(결론))
  명제 p, q에 대해 p가 조건/원인으로 제시되고, q가 결론/결과로 제시되는 명제
  • p -> q에서 p가 참이고 q가 거짓일때만 p-> q가 거짓이고 나머지 경우는 참이다.
  • p -> q에서 p가 참일 때 반드시 q는 참인 경우에는 p => q 라고 표현하면 p는 q의 충분 조건 , q는 P의 필요 조건이라고 말한다.

• 쌍방 조건 명제(Bidonditional) p <-> q
  명제 p와 q가 조건이면서 결론인 명제
  • p, q의 진릿값이 같을 때만 참이 된다. (p->q) ^ (q->p)
  • p <-> q에서 p가 참일 때 q가 참인 동시에, q가 참일 때 p가 참인 경우 p <=> q : p,q는 서로 필요충분 조건이다.
  • ex) 합성 명제 (p->q) ^ (q->p)에 대한 진리표는?

p q	p->q	q->p	(p->q)^(q->p)	p<->q
T T	T	T	T	T
T F	F	T	F	F
F T	T	F	F	F
F F	T	T	T	T

• 역(Converse), 이(Inverse), 대우(Contraposition)
  • 함축(조건명제) p->q에 대하여
    • 역 : q -> p
    • 이: ~p -> ~q
    • 대우: ~q -> ~p
    • 명제 p에 대한 대우 명제는 p와 항상 진릿값이 같다.
    • 명제 p에 대한 역과 이는 서로 대우 관계로 진리값이 항상 서로 같다.

---

2. 논리적 동치(Logical Equivalance)

논리적 동치(Logical Equilvalence) p ≡ q (이 연산기호를 뜻하는 합동(도형), 상등(집합)이라는 용어도 있다.)

두 (합성) 명제 p와 q의 진릿값이 서로 같은 경우
ex ) p -> q와 ~pvq의 진릿값은? 정확히 동치

• p->q ≡ ~pvq ≡ ~q->~p
• ~q->~p <=> ~(~q)v~p ≡ qv~p

p q	~p	p->q	~pvq	~q	~q->~p
T T	F	T	T	F	T
T F	F	F	F	T	F
F T	T	T	T	F	T
F F	T	T	T	T	T

논리적 동치 법칙

논리적 동치	법칙
p^T ≡ p   pvF ≡ p  (두 명제의 관계는 쌍대, AND <-> OR, T <-> F)	항등법칙(Identity Law)
p^T ≡ F   pvT = T (두 명제의 관계는 쌍대, AND <-> OR, T <-> F)	지배법칙(Domination Law)
p^~p ≡ F  pv~p ≡T (두 명제의 관계는 쌍대, AND <-> OR, T <-> F)	부정법칙(Negation Law)
~(~p) ≡ p	이중 부정법칙(Double Negation Law)
p^p ≡ p   pvp ≡ p	역등법칙(Idempotent Law)
p^q ≡ q^p  pvq ≡ qvp	교환법칙(Commutative Law)
(p^q)^r ≡ p^(q^r)  (pvq)vr ≡ pv(qvr)	결합법칙(Associative Law)
(p^q)vr ≡ (pvr)^(qvr)  (pvq)^r ≡ (p^r)v(q^r)	분배법칙(Distribution Law)
~(p^q) ≡ ~pv~q  ~(pvq) ≡ ~p^~q	드모르간법칙(De Morgan`s Law) (증명 가능하여 드모르간 정리라고도 함)
p^(pvq) ≡ p  pv(p^q) ≡ p	흡수법칙(Absorption Law)
p->q ≡ ~pvq	함축법칙(Implication Law)

예제)  ~(pv(~p^q)) ≡ ~p^~q 임을 증명해라.

• ~(pv(~p^q)) ≡ ~p^~(~p^q)           드모르간
                      ≡ ~p^(~(~p)v~q)      드모르간
                      ≡ ~p^(pv~q)            이중부정
                      ≡ (~p^p)v(~p^~q)    분배법칙
                      ≡ Fv(~p^~q)           부정법칙
                      ≡ ~p^~q                  항등법칙
• 진리표를 통해 증명

p q	~p^q	pv(~p^q)	~(pv(~p^q))	~p^~q
T T	F	T	F	F
T F	F	T	F	F
F T	T	T	F	F
F F	F	F	T	T

예제) (p->q)^(p->~q)를 간략히 해라

• (p->q)^(p->~q)  ≡ (~pvq)^(~pv~q)       함축법칙
                             ≡ ~pv(q^~q)               분배법칙
                              ≡ ~pF                        부정법칙
                              ≡ ~p                          항등법칙