프로그래머 수학

프로그래머 수학

5주차 강의

명제논리

1. 기본 개념

 명제( Proposition)란?

 참(true)이나 거짓(false)이 명확하게 구분이 되는 문장(statement)이나 수식

 예제 : 다음의 문장이나 식에서 명제를 찾아보라.

오늘 날씨는 맑다.

x + y = 0 1+2 =5

컴퓨터 게임은 어렵다.

정 삼각형의 세 변의 길이가 모두 같다.

논리 연산자 (logical operators)

단순 명제들을 연결시켜 주는 역할을 하는 연결자(connectives)

합성 명제 (composition proposition 혹은 Compound statement )

여러 개의 단순 명제가 연결되어 만들어진 명제

2. 논리 연산

 진리값( Truth value )이란?

 명제에서 참(T)이나 거짓(F)으로 나타내는 값

 진리표( Truth Table )

 합성 명제의 진리값은 그 명제를 구성하고 있는 단순 명제들과 논리 연산자에 따라 값이 결정됨으로,

단순명제들과 논리연산자에 따라 단계적으로 나타낸 표

논리 연산자

Logical Operators

Name Symbol Meaning

Negation(부정) ~ ^혹은  Not

Conjunction(논리곱) ∧ ^And

Disjunction(논리합) ∨ ^Or

Exclusive OR (배타적논리합)

Exclusive OR

Condition(조건) → ^{If … then}

Bicondition(쌍방조건) ↔ If and only if( iff )



논리합(disjunction) : ∨

p q p ∨ q T T

T F F T F F

T T T F

배타적 합(exclusive or) : 

p



하나만 참일 때 참, 그 외에는 거짓

p q p  q T T

T F F T F F

T F T F

논리 연산자

부정(negation) : ㄱ

ㄱp (p의 부정) : p와 진리값이 반대가 됨.

p ㄱp

T

F F

T

논리곱(conjunction) : ∧

p∧q (p이고 q) : p, q의 값이 모두 참이면 참, 그렇지 않으면 거짓이 됨

p q p ∧ q T T

T F F T F F

T F F F

논리 연산자

조건 혹은 함축(implication) : →

명제 p→q (p이면 q이다) : p가 참, q가 거짓일 때만 거짓이고, 그 이외는 참.

논리 연산자

p q p  q T T T T F F F T T F F T

쌍방조건 : ↔

명제 p

q (p이면 q이고, q이면 p이다) : p와 q가

같은 값일때 참, 서로 다른 값이면 거짓.

논리 연산자

p q p ↔ q T T T T F F F T F F F T

 예제 : 다음 합성명제 ( p ∧ q ) ∨ ~r 의 진리값을 구하시오.

<풀이>

p q r p ∧ q ~r ( p ∧ q ) ∨ ~r

T T T T F T

T T F T T T

T F T F F F

T F F F T T

F T T F F F

F T F F T T

F F T F F F

F F F F T T

3. 항진 명제와 모순 명제

 항진 명제(Tautology)

 합성 명제에서 그 명제를 구성하는 단순 명제들의

진리값에 상관없이 그 합성 명제가 항상 참의 진리값을 갖는 명제

 모순명제(Contradiction)

 합성 명제에서 그 명제를 구성하는 단순 명제들의 진리값에 상관없이 그 합성 명제가 항상 거짓의 진리값을 갖는 명제

 예

p ~p p ∨ ~p p ∧ ~p

T F T F

F T T F

Contradiction Tautology

4. 논리적 동치

 논리적 동치( Logical Equivalence )

 각각의 다른 합성명제(또는 단순명제)가 동일한 진리표를

가진다면, 이 두 개의 명제는 논리적 동치라고 한다.

 명제 P 와 Q가 논리적 동치라면, P ≡ Q 표기

 논리적 동치의 예

 이중 부정( Double Negation )

 ~(~p) ≡ p

p ~p ~(~p)

T F T

F T F

 논리적 동치가 아닌 예

 ~(p ∧ q) and ~p ∧~q

 ~(p ∨ q) and ~p ∨ ~q

p q ~p ~q ~(p∧q) ~p∧~q p∨q ~(p∨q) ~p∨~q

T T F F F F T F F

T F F T T F T F T

F T T F T F T F T

F F T T T T F T T

논리적 동치

논리적 동치

 드모르간 법칙( De Morgan’s Laws )

p q p ∧ q ~( p ∧ q ) ~p ~q ~p ∨ ~q

T T T F F F F

T F F T F T T

F T F T T F T

F F F T T T T

~( p ∧ q ) ≡ ~p ∨ ~q

~( p ∨ q ) ≡ ~p ∧ ~q

논리적 동치

 예제: 다음 합성명제가 논리적 동치임을 보여라.

(p ∨ q)

→

→

→

p q r p ∨q p →r q →r p ∨q → r (p →r) ∧ (q →r) T T T

T T F T F T T F F F T T F T F F F T F F F

T T T T T T F F

T F T F T F T T T

F T F T T T T

T F T T T F T T

T F T F T F T T

진리값이 같음

논리적 동치

 예제: 다음 합성명제가 논리적 동치임을 보여라.

p

→

<풀이>

p q p → q ~p ~p ∨ q

T T T F T

T F F F F

F T T T T

F F T T T

진리값이 같음

논리적 동치관계의 기본 법칙

 교환법칙(Commutative laws)

 p ∧ q ≡ q ∧ p

 p ∨ q ≡ q ∨ p

 결합법칙(Associative laws)

 (p ∧ q) ∧ r ≡ p ∧ (q ∧ r)

 (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)

 분배법칙(Distributive laws)

 p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)

 p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)

 드모르간 법칙(De Morgan’s laws)

 ~(p ∧ q) ≡ ~p ∨ ~q

 ~(p ∨ q) ≡ ~p ∧ ~q

논리적 동치관계의 기본 법칙



 p ∨ ~p ≡ T (True)

 p ∧ ~p ≡ F (False)

 ~ T ≡ F

 ~ F ≡ T



 ~(~p) ≡ p



 p ∧ p ≡ p

 p ∨ p ≡ p

논리적 동치관계의 기본 법칙



 p ∨ T ≡ T

 p ∨ F ≡ p

 p ∧ T ≡ p

 p ∧ F ≡ F



 p ∨ (p ∧ q) ≡ p

 p ∧ (p ∨ q) ≡ p

두 명제의 논리적 동치를 증명하는 방법

방법 1

방법 2

두 명제의 논리적 동치를 증명하는 방법



~(p ∨ q) ≡ ~p ∧ ~q가 논리적 동치임을 방법1을 이용하여 증명하라.

<풀이>

p q T T T F F T F F

p ∨ q T T T F

~(p ∨ q) F

F F T

~p F F T T

~q F T F T

~p ∧ ~q F

F F T

두 명제의 논리적 동치를 증명하는 방법









<풀이>

≡ ~ (p ∧ q) ∨ r 조건법칙

≡ (~p∨~q) ∨ r 드 모르강의 법칙 ≡ (~p∨~q) ∨ r ∨ r 멱등법칙

≡ ~p∨ (~q∨r) ∨ r 결합 법칙 ≡ ~p ∨ r ∨ (~q ∨r) 교환 법칙 ≡ (p









조건명제의 역(converse)과 이(inverse)

 조건명제의 역(converse)

 조건명제 p

→

→

 조건명제의 이(inverse)

 조건명제 p

→

→

p q p → q q → p ~p ~q ~p → ~q

T T T F F

T F F F T

F T T T F

F F T T T

T T F T

T T F T

조건명제의 대우(contrapositive)

 조건명제의 대우(contraposition)

 조건명제 p

→

→

 조건명제와 그 조건명제의 대우는 동치이다.

p q p → q ~q ~p ~q → ~p

T T T F F T

T F F T F F

F T T F T T

F F T T T T

쌍방 조건

 p 와 q의 쌍방조건: p ↔ q

 p if, and only if, q

 p is necessary and sufficient for q

 p ↔ q ≡ ( p → q )∧( q → p )

 p ↔ q의 진리값

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

5. 추론

 추론( Argument )

 새로운 명제를 유도해 내는 방법 중에서 주어진 명제가 참인 것을 근거로 다른 명제가 참이 되는 것을 유도해 내는 방법

 전제(premise, assumption): 주어진 명제들 p₁, p₂, p₃, … p_n

 결론(conclusion): 새로이 유도된 명제 q p₁

, p

, ..., p

├ q

 Valid argument( 유효 추론 )

 주어진 전제가 참이고, 결론도 참인 추론

 Invalid argument( 허위 추론, fallacious argument )

 주어진 전제가 참이지만 결론은 거짓인 추론

 추론이 유효, 허위인지는 “Truth Table”를 이용해서 판별

추론

 예제: 다음 추론이 허위추론임을 보여라.

<풀이>

p q r ~r q ∨ ~r p ∧r p → q ∨ ~r q → p ∧ r p → r

T T T F T T T T T

T T F T T F T F F

T F T F F T F T T

T F F T T F T T F

F T T F T F T F T

F T F T T F T F T

F F T F F F T T T

F F F T T F T T T

p → q ∨ ~r q → p ∧ r

∴ p → r

premises conclusion

삼단논법

 삼단 논법(Syllogism) 일반적으로 추론에서 잘 알려진 방법

 두 전제와 하나의 결론

 긍정 논법(Modus ponens , Method of Affirming )

 부정 논법(Modus tollens, Method of Denying )

첫 번째 전제 두 번째 전제

∴ 결론

p q, qr ├ p r

p , p q ├ q

~ q , p q ├ ~ p

긍정논법, 부정논법

if p then q p

∴ q

긍정논법(Modus ponens)

if p then q ~q

∴ ~p

부정논법( Modus tollens)

p q p → q q p → q ~q ~p

T T T T T F F

T F F F F T F

F T T T T F T

F F F F T T T

premises conclusion premises conclusion

참고문헌

본 강의 자료에서 예제 등의 출처는 다음과 같은 참고문헌이다.

1) PLD: Programming Logic and Design using Flowchart, 주형석 저(IT미디어)

2) 이산수학: 논리,명제에서 알고리즘까지, 홍영진 저(한빛미디어) 3) 이산수학 및 응용, 임은기 번역(한티미디어)

4) 전산수학, 김대수 (생능)