논리와 명제

(1)

 2장

논리와 명제

(2)

1. 논리와 명제

• 다양한 종류의 이치(理致, Logic)

• 천리(天理) : 천지 자연, 즉 온 세상의 보편적 이치

• 지리(地理) : 땅의 이치

• 물리(物理) : 물질 운동의 이치

• 심리(心理) : 마음이 움직이는 이치

• 순리(順理) : 순한 이치 또는 도리나 이치에 순종함

• 논리(論理) : ‘논(論)함’의 이치

• ‘논리’란 무엇인가?

• 논(論)함 : ‘말(言)’ + ‘순서를 배움(侖)’, 논함이란 생각의 결과인 말을 하는 순서를 의미한다고 볼 수 있음

• ‘논함’의 뜻으로 가능한 : ‘말하다’, ‘생각하다’, ‘의논하다’

• 이치 : ‘원리’ 또는 ‘까닭’

• 결론적으로 ‘논리’란 말을 말되게 하고, 생각을 생각되게 하는 근 거 또는 까닭으로 해석할 수 있음

• 문제를 해결해서 결과를 인간에게 돌려주는 컴퓨터에게 있어서 논리 라는 것은 매우 중요함

논리의 개념

(3)

1. 논리와 명제

• 명제논리(propositional logic)

• 주어(subject)와 술어(predicate)를 구분하지 않고, 전체를 하나의 식으로 처리하여 ‘참’ 또는 ‘거짓’을 판별하는 논리

• 명제가 최소의 단위이기 때문에 명제의 내부 구조에 대한 분석이 불가능하고, 지식표현을 일반화하는 것이 불가능함

명제논리와 술어논리

‘소크라테스는 사람이다’ : ‘참’

‘플라톤은 사람이다’ : ‘참’

‘모든 사람은 죽는다’ : ‘참’

‘소크라테스는 사람이고, 모든 사람은 죽기 때문에 소크라테스도 죽는다’

‘모름’

<예>

주어 술어

(4)

1. 논리와 명제

• 술어논리(predicate logic)

• 주어와 술어로 구분하여 ‘참’ 또는 ‘거짓’을 판별하는 논리

• 술어논리는 하나의 명제를 술어와 그 술어의 수식을 받는 객체로 분리하여 ‘술어(객체)’의 형태로 표현할 수 있음

• 예 1 : Man(소크라테스) 또는 Die(사람)

• 예 2 : 사람(소크라테스) 또는 죽는다(사람)

• 범위를 한정할 수 있는 한정기호 ∀(모든)과 ∃(어떤)을 사용할 수 있음

‘소크라테스는 사람이다’ 사람(소크라테스) : ‘참’

‘플라톤은 사람이다’ 사람(플라톤) : ‘참’

‘모든 사람은 죽는다’ ∀x(사람(x) → 죽는다(x)) : ‘참’

죽는다(소크라테스)와 죽는다(플라톤) : ‘참’

<예>

(5)

1. 논리와 명제

• 명제(proposition)

• 어떤 사고를 나타내는 문장 중에서 ‘참(true)’ 또는 ‘거짓(false)’

으로 명백하게 구분할 수 있는 문장이나 수학식을 말함

• 이 때 ‘참’ 또는 ‘거짓’을 진리값(truth value)이라고 말함

• 명제는 ‘참’ 또는 ‘거짓’의 2가지 진리값만 가지므로 이진논 리(binary logic)라고 말함

• 명제가 되는지를 알아 볼 수 있는 예

• 바나나는 맛있다.(ⅹ)

• 3x+4y=7(ⅹ)

• 28은 4의 배수이다.(○, 참)

• 지금 어디로 가는 중입니까?(ⅹ)

• 6<4(○, 거짓)

• 유채꽃은 노란색이다.(○, 참)

• 3ⅹ7의 결과는 홀수이다.(○, 참)

• 공기의 화학식은 H₂O이다.(○, 거짓) 명제

(6)

2. 논리 연산

• 단순명제(simple proposition)

• 하나의 문장이나 식으로 구성된 명제

• 명제가 ‘참’인가, ‘거짓’인가에 따라 진리값이 결정됨

• 예 : ‘장미꽃은 빨갛다.’

• 합성명제(composition proposition)

• 2개 이상의 단순명제들이 논리연산자들에 의해 연결된 명제

• 예 : ‘장미꽃은 빨갛고, 유채꽃은 노랗다.’

• 합성명제를 구성하는 단순명제 각각의 진리값과 논리연산자를 연산시켜서 최종적으로 진리값을 얻음

• 합성명제를 구성하는 단순명제의 개수가 n개인 경우, 진리 값의 개수는 2ⁿ개임. ‘장미꽃은 빨갛고(p), 유채꽃은 노랗고 (q), 바닷물은 파랗다(r).’는 단순명제가 3개이므로 2³, 즉 총 8개의 진리값이 만들어질 수 있음

• 논리연산자(logical operator)

• 단순명제들을 연결시켜주는 연결자로 부정(∼), 논리곱(∧), 논 리합(∨), 배타적 논리합(⊕), 조건(→), 쌍방조건(↔) 등이 있음 단순명제와 합성명제

(7)

2. 논리 연산

• 부정(negation)

• 임의의 명제 p가 주어졌을 때 그 명제의 부정은 p의 진리값과 반 대의 진리값을 갖게 됨

• ∼p라고 쓰고, ‘not p’ 또는 ‘p가 아니다’라고 읽음

• ‘서울은 대한민국의 수도이다’ : ‘참’, ‘서울은 대한민국의 수도가 아니다’ : ‘거짓’

• 논리곱(conjunction)

• 임의의 명제 p와 q의 논리곱은 p와 q 모두의 진리값이 ‘참’인 경 우에만 ‘참’인 진리값을 갖게 됨

• p∧q라고 쓰고, ‘p and q’ 또는 ‘p 그리고 q’로 읽음

• ‘서울은 대한민국의 수도이고, 런던은 영국의 수도이다’ : ‘참’

• 논리합(disjunction)

• 임의의 명제 p와 q의 논리합은 p와 q 중 한 개라도 진리값이 ‘참’

인 경우에는 ‘참’인 진리값을 갖게 됨

• p∨q라고 쓰고, ‘p or q’ 또는 ‘p 또는 q’로 읽음

• ‘부산은 대한민국의 수도거나, 동경은 영국의 수도이다’ : ‘거짓’

논리연산자

(8)

2. 논리 연산

• 배타적 논리합(Exclusive OR 또는 E-OR)

• 임의의 명제 p와 q의 배타적 논리합은 p와 q의 진리값이 같은 경우에는 ‘거짓’, 다를 경우에는 ‘참’인 진리값을 갖게 됨

• p⊕q라고 쓰고, ‘Exclusive OR’로 읽음

• 조건 또는 함축(implication)

• 임의의 명제 p와 q의 조건은 p의 진리값이 ‘참’이고, q의 진리값 은 ‘거짓’일 때만 ‘거짓’의 진리값을 갖게 됨

• p→q라고 쓰고, ‘p이면 q이다’로 읽음’

• ‘p는 q의 충분조건이다.’, ‘q는 p의 필요조건이다.’, ‘p는 q를 함 축한다.’ 등과 같은 의미로 사용함

• 쌍방조건 또는 쌍방함축(if and only if)

• 임의의 명제 p와 q의 쌍방조건은 p와 q의 진리값이 같은 경우에 는 ‘참’, 다를 경우에는 ‘거짓’의 진리값을 갖게 됨

• p↔q라고 쓰고, ‘p이면 q이고, q이면 p이다’로 읽음’

• 논리연산자의 우선순위

• 괄호가 있는 경우에는 괄호가 우선이고, 없는 경우에는 부정 (∼)- 논리곱(∧)-논리합(∨)-배타적 논리합(⊕)-조건(→)-쌍방 조건(↔)의 순서임

(9)

p ~p

T F

F T

논리연산자의 진리표

부정(∼p)

p q p∧q

T T T

T F F

F T F

F F F

논리곱(p∧q)

p q p∨q

T T T

T F T

F T T

F F F

논리합(p∨q)

p q p⊕q

T T F

T F T

F T T

F F F

배타적 논리합(p⊕q)

p q p↔q

T T T

T F F

F T F

F F T

쌍방조건(p↔q)

• 다음 명제에 대한 진리값을 구하라.

• 사과는 과일이고, 시금치는 채소이다.

• 사과는 과일이거나 시금치는 채소이다.

• 바다가 육지라면, 런던은 영국의 수도이다.

• 유채꽃이 노랗다면, 수요일 전날은 토요일이다.

• 4+3=7이고, 4ⅹ7=9이다.

• 합성명제 ~(p∧~q)

• 합성명제 p∨(q∧r)

2. 논리 연산

p q p→q

T T T

T F F

F T T

F F T

조건(p→q)

(10)

2. 논리 연산

명제의 역, 이, 대우

• 역(converse)

• 임의의 명제 p와 q가 있을 때 p→q의 역은 q→p임

• 이(inverse)

• 임의의 명제 p와 q가 있을 때 p→q의 이는 ~p→~q임

• 대우(contrapositive)

• 임의의 명제 p와 q가 있을 때 p→q의 대우는 ~q→~p임

<명제> <역> <이> <대우>

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

T T F F T T T T

T F F T F T T F

F T T F T F F T

F F T T T T T T

동치 동치

(11)

3. 항진명제와 모순명제

• 항진명제(tautology)

• 합성명제를 구성하는 단순명제들의 진리값과 관계없이 항상 ‘참’

인 진리값을 갖는 명제

• 예 : p∨(~p)

• 모순명제(contradiction)

• 합성명제를 구성하는 단순명제들의 진리값과 관계없이 항상 ‘거짓’

인 진리값을 갖는 명제

• 예 : p∧(~p)

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

T F T F

F T T F

항진명제 모순명제

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

T T T T F F

T F F T F F

F T F T F F

F F F F T F

모순명제 항진명제와 모순명제

(12)

4. 논리적 동치관계

• 논리적 동치(logical equivalence)

• 2개의 명제, p와 q의 쌍방조건 p↔q가 항진명제이면 두 명제 p, q 를 논리적 동치라고 하고, p≡q 또는 p⇔q로 표시함

• 예 : p→q≡~p∨q

• 예 : ~(p∨q)≡(~p)∧(~q)

p q ~p p→q ~p∨q

T T F T T

T F F F F

F T T T T

F F T T T

논리적 동치

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

T T F F T F F

T F F T T F F

F T T F T F F

F F T T F T T

논리적 동치

논리적 동치관계

(13)

5. 추론

• 추론(argument)

• 주어진 명제가 ‘참’인 것을 바탕으로 새로운 명제가 ‘참’임을 유 도해내는 과정

• 주어진 명제 p₁, p₂, …, p_n을 전제(premise)라 하고, 새롭게 유도된 명제 q를 결론(conclusion)이라고 함

• 추론을 수학식으로 표현하면 p₁, p₂, …, p_n

⊢

q

• p→q, p ⊢ q를 이용한 추론의 예

• p : ‘오늘은 비가 온다.’, q : ‘나는 공부를 한다.’

• p→q : ‘오늘 비가 오면 나는 공부를 한다.’

• p→q, p ⊢ q : ‘오늘 비가 오면 나는 공부를 한다. 오늘 비가 온다. 따라서 나는 공부를 한다.’

• 유효추론(valid argument)과 허위추론(fallacious argument)

• 유효추론 : 주어진 명제가 ‘참’이고, 유도된 결론도 ‘참’인 경우

• 허위추론 : 주어진 명제는 ‘참’인데, 유도된 결론은 ‘거짓’인 경우 추론의 개념

(14)

5. 추론

• 여러 가지 추론 법칙

• 긍정법칙(modus ponens) : p, p→q ∴q

• 부정법칙(modus tollens) : ~q, p→q

∴~p

• 조건삼단법칙(hypothetical syllogism) : p→q, q→r ∴p→r

• 선언삼단법칙(disjunctive dilemma) : p∨q, ~p ∴q

• 양도법칙(constructive dilemma) : (p→q)∧(r→s), p∨r ∴q∨s

• 파괴법칙(destructive dilemma) : (p→q)∧(r→s), ~q∨~s ∴~p∨~r

• 선접법칙(disjunctive addition) : p

∴p∨q

• 분리법칙(simplication) : p∧q ∴p

• 연접법칙(conjunction) : p, q ∴p∧q

• 유효추론과 허위추론 판별법

• 예 1 : p→q, q ⊢ p를 이용한 판별

p q p→q

T T T

T F F

F T T

F F T

p→q와 q 모두 ‘참’인 경우 중 p는 하나는 ‘참’이고,

다른 하나는 ‘거짓’

p→q와 q 모두 ‘참’인 경우

• p : ‘오늘은 비가 온다.’, q : ‘나는 공부를 한다.’

• p→q : ‘오늘 비가 오면 나는 공부를 한다.’

• p→q, q ⊢ p : ‘오늘 비가 오면 나는 공부를 한다. 나 는 공부를 한다. 따라서 오 늘 비가 온다.’

∴ 허위추론!

(15)

5. 추론

p→q와 q→r 모두 ‘참’인 경우

∴ 유효추론!

p q r p→q q→r p→r

T T T T T T

T T F T F F

T F T F T T

T F F F T F

F T T T T T

F T F T F T

F F T T T T

F F F T T T

• 예 2 : 조건삼단법칙 p→q, q→r ∴p→r

p→q와 q→r 모두 ‘참’인 경우 중 p →r도 모두 ‘참’

p→q와 q→r 모두 ‘참’인 경우

(16)

6. 술어논리

• 명제술어(propositional predicate)

• 명제는 ‘참’과 ‘거짓’ 중의 하나로 명확하게 구분되지만 현실세계 에서는 변수가 어떤 값을 갖는가에 따라 ‘참’이 될 수도, ‘거짓’이 될 수도 있는 상황이 발생할 수 있음

• 예 1 : 방정식 x²+5x+6=0은 x가 -2 또는 -3일 경우 ‘참’이 되지만, 그 밖의 경우는 ‘거짓’이 됨

• 이와 같은 형태의 명제를 p(x)라 하고, p(x)를 변수 x에 대한 명 제술어라고 함

• 명제 술어에 대한 논리를 명제 논리와 구분하여 술어논리 (predicate logic)라고 함

• 술어한정자(predicate quantifier)

• 명제술어에서 변수 범위를 한정시키는 것을 술어한정자라고 함

• 전체한정자(universal quantifier) : ‘모든(for all)’을 의미하고,

‘∀’ 로 표기함

• 존재한정자(existential quantifier) : ‘어떤(there exist)’을 의미 하고, ‘∃’로 표기함

술어 논리

(17)

6. 술어논리

• 술어한정자의 사용 예

• x가 정수이고, p(x)가 ‘x=x²’이라고 할 때 ∀x p(x)는 ‘거짓’이고,

∃x p(x)는 ‘참’임

• ∀x의 부정은 ∃x임

• ∀x는 ‘x가 어떤 값을 갖든지 조건을 만족한다’는 뜻이기 때 문에 부정은 ‘조건을 만족하는 x가 단 1개도 존재하지 않는다’

로 생각될 수 있으나, 그렇지 않고 ‘조건을 만족하는 x가 1개 라도 존재한다’가 됨

• 이것을 식으로 표현하면 ~(∀x p(x))⇔∃x(~p(x))

•∃x의 부정은 ∀x임

• ∃x은 ‘조건을 만족하는 x가 1개라도 존재한다’이므로 그에 대한 부정은 ‘조건을 만족하는 x가 단 1개라도 존재하지 않는 다’가 됨

• 이것을 식으로 표현하면 ~(∃x p(x))⇔∀x(~p(x))

• 예 1 : x는 ‘학생은’이고, p(x)는 ‘x는 공부한다’일 때, ‘모든 학생은 공부한다.’의 부정은 ‘공부하지 않는 학생도 있다.’가 되고, 이것을 식으로 표현하면 ~(∀x p(x))⇔∃x(~p(x))임

(18)

7. 논리용 프로그래밍언어 - Prolog

• PROLOG(PROgramming in LOGic)

• 1972년에 프랑스의 코왈스키(R. Kowalski)가 개발한 인공지능언어 로 비절차적 논리형 언어임

• Prolog 프로그램 예 PROLOG

1 human(socrates). - 소크라테스는 사람이다(사실) 2 human(daesukim). - 김대수는 사람이다(사실) 3 animal(wurry). - 워리는 동물이다(사실)

4 animal(X):-human(X). – 모든 사람은 동물이다(추론규칙, X는 변수) 5 die(X):-animal(X). - 모든 동물은 죽는다(추론규칙)

6 ?-die(socrates). - 소크라테스는 죽는가를 질의함 7 Yes - 시스템은 ‘yes’라고 대답함

8 ?-die(X). - 모든 죽는 것의 이름 X를 입력하면서 질의함 9 X=socrates. - 입력값이 소크라테스임

10 X=daesukim. - 입력값이 김대수임 11 X=wurry. - 입력값이 워리임