프로그래머 수학

프로그래머 수학

6주차 강의

술어논리

1. 술어와 한정화 명제의 개요

 논리(Logic)

 명제 논리( Propositional Logic )

 주어와 술어를 구분하지 않고 전체 문장을 하나의 식으로 처리하여 참 또는 거짓을 판별하고, 그에 대한 법칙을 다룸.

 술어 논리( Predicate Logic )

 주어와 술어를 구분하여 참 또는 거짓에 대한 법칙을 다룸.

 술어 계산( Predicate Calculus ) : 문장내의 주어와 술어를 구분하여 참과 거짓을 판별

 명제 함수(Propositional Function) She is a student.

 P(x) 자체는 명제가 아님  변수 x에 적절한 값으로 치환하면, 결과적으로 명제가 된다.

주어: She

술어: is a student.

x

P(x) : x is a student.

2. 전체 수량자와 존재 수량자

 수량자 (Quantifier)

 변수 x가 가질 수 있는 값들의 양을 제한하는 기호

 전체 수량자(Universal Quantifier) : ∀

 ∀xP(x) : “모든 x에 대하여 P(x)는 참이다”

 ∀xP(x)이 참이 되기 위한 필요충분 조건은

술어 P(x)가 x의 전체 집합 U에 대하여 성립하여야 한다.

 존재 수량자(Existential Quantifier ): ∃

 ∃xP(x) : “어떤 x에 대하여 P(x)가 참인 x가 존재한다.”

 ∃xP(x) 이 참이 되기 위한 필요 충분 조건은 전체 집합 U안에 P(x)를 만족시키는 x가 적어도 한 개 존재하여야 한다.

전체 수량자와 존재 수량자

 예제: 다음 명제를 서술하여라.

∀x ∈ H, Q(x) 모든 인간은 동물이다.

∃x ∈ H, P(x) 생각하는 인간이 존재한다.

∀x ∈ H, ( P(x)∧Q(x)) 모든 인간은 생각하는 동물이다.

∃x ∈ H, ~P(x) 생각하지 않은 인간도 있다.

도메인 H : 인간의 모든 집합

“x는 인간”, “P(x) : x는 생각한다.”, “Q(x) : x는 동물이다.”

 예제: x가 정수이고 p(x)가 ‘x = x²‟ 이라고 하자.

다음 명제의 진리 값은 무엇인가?

(1) ^∀x p(x) (2)  x p(x)

Implicit Quantification

 Implicit Quantification : ⇒, ⇔

 P(x), Q(x) : 술어, D: x의 정의역이라 두자

 P(x) ⇒ Q(x)는 P(x)를 참으로 하는 모든 원소들은 Q(x)를 참으로 하는 집합에 포함된다는 의미이다.

즉, ∀x, P(x) → Q(x).

 P(x) ⇔ Q(x)는 P(x)와Q(x)가 같은 진리집합을 갖는다는 의미이다.

즉, ∀x, P(x) ↔ Q(x).

 전체수량자(한정자)의 부정

 존재수량자(한정자)의 부정

~(∀x∈ D, P(x) ) ≡ ∃x∈ D, ~P(x).

„p(x)가 성립하지 않는 x가 존재한다’

~( ∃x∈ D, P(x) ) ≡ ∀x∈ D, ~P(x).

„모든 x는 p(x)가 성립하지 않는다’

Negation of Quantified Statements

Negation of Quantified Statements

 예제: 다음 전체수량자, 존재수량자의 부정을 서술하여라.

∀x ∈ H, P(x) 모든 인간은 생각한다.

~( ∀x ∈ H, P(x) ) ≡ ∃x ∈ H, ~P(x)

생각하지 않는 인간도 존재한다 ∃x ∈ H, P(x) 생각하는 인간이 존재한다.

~( ∃x ∈ H, P(x) ) ≡ ∀x ∈ H, ~P(x)

모든 인간은 생각하지 않는다.

도메인 H : 인간의 모든 집합

“x는 인간”, “P(x) : x는 생각한다.”

Negation of Quantified Statements

~( ∀x, P(x) → Q(x) ) ≡ ∃x, ~( P(x) → Q(x) )

≡ ∃x, ~( ~( P(x) ) ∨ Q(x) ) ≡ ∃x, P(x) ∧ ~Q(x)

~( ∀x, P(x) → Q(x) ) ≡ ∃x, P(x) ∧ ~Q(x)

Negation of Universal Conditional

Statements

3. 여러 개의 한정자를 포함하는 명제

 술어계산

 Predicate and Quantified Statement She is a Duksung Univ. student.

She : variable x, Duksung Univ : variable y P( x, y ) : x is a y student.

H = { 영희, 철수, … },

D = {Duksung Univ., ABC Univ., … } P( x, y ) : x is a y student.

Truth set of P(x, y) : {∀x ∈ H, ∃y ∈ D | P( x, y ) }

Which is read “∀x in set H, ∃y in set D such that P(x, y).”

 예제:

Let be x∈R, y∈R and P(x, y) : xy = 0

∀x∀y, P( x, y ) F

∀x∃y, P( x, y ) T

∃x ∀y, P( x, y ) T

∃x ∃y, P( x, y ) T

Negation of Multiple-Quantified Statements

 Recall that Negation of Quantified Statement

 Negation of Multiple-Quantified Statements

~( ∀x, P(x) ) ≡ ∃x, ~P(x)

~(∃x, P(x) ) ≡ ∀x, ~P(x)

~( ∀x∃y , P(x, y) ) ≡ ∃x∀y, ~P( x, y )

~( ∃x∀y , P(x, y) ) ≡ ∀x∃y, ~P( x, y )

 예제: x와 y가 실수이고, P(x, y): ‘x＋y＝y＋x’일 때 전체수량 ∀x∀yP(x, y)의 진리값은 무엇인가?

[풀이]

∀x∀y P(x, y) :

‘

실수에서 교환 법칙이 성립하므로 ∀x∀yP(x, y): 참

∀x∀y, P(x , y) means the same as ∀y∀x, P(x , y)

∃x∃y, P(x, y ) means the same as ∃y∃x, P(x, y )



ommutative Property

∃y∀x Q(x,y)와 ∀x∃y Q(x,y)는 논리적으로 동일하지 않음

∃y∀x Q(x,y) : 어떤 y 값에 대해 x가 모두 만족해야 참

∀x∃y Q(x,y) : 각 x값에 따라 y값이 하나만 존재하면 참

 만일, ∃y∀x Q(x, y)가 참이면 ∀x∃y Q(x, y)는 반드시 참.

그러나, 역은 항상 성립하지 않음

[비교] ∃y∀x Q(x, y)와 ∀x∃y Q(x, y)

예) x∈R, y∈R, Q(x, y): 'x＋y＝0'일 때, ∃y∀xQ(x, y)와

∀x∃yQ(x, y)의 진리값은 무엇인가?

[풀이]

(1) ∃y∀x Q(x, y): '어떤 실수 y가 존재하여, 그 y값에 대해 모든 x가 Q(x, y)를 만족한다'

그러나, y 값이 어떤 값이든 x＋y＝0을 만족하는 x 값은 하나만 존재 ⇒ ∃y∀x Q(x, y)은 거짓이다

(2) ∀x∃y Q(x, y): '모든 x에 대하여 Q(x, y)를 참으로 하는 y가 존재한다'

실수 x가 어떤 값을 갖든 x＋y＝0을 만족하는 y는 반드시 존재 (즉, y＝－x), ∀x∃y Q(x, y) 은 참이다

Quantifier의 순서는 매우 중요함

참고문헌

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

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

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

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