논리와 증명 (Logic and Proof)

이산수학 (Discrete Mathematics)

논리와 증명

(Logic and Proof)

강의 내용

논리 (Logic)

명제의 동치 (Propositional Equivalence)

술어와 한정기호 (Predicates and Quantifiers) 중첩된 한정기호 (Nested Quantifiers)

증명 방법 (Methods of Proof) 가설 (Conjectures)

Logic and Proof

논리 (Logic) 란 ?

논리 (logic) 란 수학적 표현의 의미를 정확하게 기술할 수 있게 함

논리는 회로 설계 , 프로그램 작성 , 프로그램 정확성 검증 등에 활용

Logic

명제 (Proposition)

명제의 정의

명제란 참 (true, T) 또는 거짓 (false, F) 을 판정할 수 있는 선언적 문장을 말한다 .

A proposition (p, q, r, s, …) is a declarative statement that is either true (T) or false (F), but not both.

명제의 예제

1 + 1 = 2. (T)

2 + 2 = 5. (F)

Seoul is the capital of Korea.

11213 is prime.

명제가 아닌 예제

Who is there? (not declarative, question)

Just do it! (command)

x + 2 = 5. (non-constant value, variable)

Logic

논리 연산자 (Logical Operator) (1/2)

논리 연산자 관련 용어 정의

 하나 또는 여러 명제를 조합하여 새로운 수학적 명제를 만들 수 있으며 , 이를 복합명제 (compound proposition) 라 한다 .

 복합명제를 만들 때 사용하는 연산자를 논리 연산자 (logical operator) 혹은 접속사 (connective) 라 한다 .

 논리 연산자는 명제 연산자 (propositional operator) 혹은 불리언 연산자

(Boolean operator) 라고도 불리며 , 피연산자 (operand) 로서 명제 혹은 진리 값 (truth value) 을 취한다 .

( 본 강의에서는 이들 용어를 동일한 의미로 혼용하여 사용할 예정임 )

Logic

논리 연산자 (Logical Operator) (2/2)

Boolean Operator 의 예

명칭 ( 영어 ) 명칭 ( 한글 )

Nickname Arity Symbol

Negation operator 부정 연산자 NOT Unary ¬

Conjunction operator 논리곱 연산자 AND Binary 

Disjunction operator 논리합 연산자 OR Binary 

Exclusive-OR operator 배타적 OR 연산자 XOR Binary 

Implication operator 함축 연산자 IMPLIES Binary 

Biconditional operator 상호조건 연산자 IFF Binary ↔

Logic

부정 (Negation) (1/2)

부정의 정의

p 가 명제이면 , “It is not the case that p” 역시 명제이며 , 이를 p 의 부정 (negation) 이라 하며 , ¬p(not p) 로 표기한다 .

The unary negation operator “¬” (NOT) transforms a proposition into its log- ical negation.

부정 명제의 예제

 명제 (p) “I have brown hair.” 의 부정 명제 (¬p) 는 “ I do NOT have brown hair.” 이다 .

 명제 “ Today is Sunday.” 의 부정 명제는 “ Today is NOT Sunday.” 이다 .

Logic

부정 (Negation) (2/2)

Negation operator 의 truth table

p ¬p

T F

F T

Operand column Result column

Logic

논리곱 (Conjunction) (1/2) 논리곱의 정의

p 와 q 가 명제이면 , “p and q” 도 명제이며 , 이를 p 와 q 의 논리곱 (conjunction) 이라 하고 , pq 라 표기한다 .

이 명제는 p, q 가 모두 참일 때만 참이 되며 , 그 외는 모두 거짓이 된다 .

The binary conjunction operator “” (AND) combines two propositions to form their logical conjunction.

논리곱 사용의 예제

p = “I will have salad for lunch.”, q = “I will have a steak for dinner.”

pq = “I will have salad for lunch

and I will have steak for dinner.”

Logic

논리곱 (Conjunction) (2/2)

Conjunction operator 의 truth table

p q pq

T T T

T F F

F T F

F F F

Logic

논리합 (Disjunction) (1/2)

논리합의 정의

p 와 q 가 명제이면 , “p or q” 도 명제이며 , 이를 p 와 q 의 논리합 (disjunction) 이라 하고 , pq 라 표기한다 .

이 명제는 p, q 가 모두 거짓일 때만 거짓이 되며 , 그 외는 모두 참이 된다 .

The binary disjunction operator “” (OR) combines two propositions to form their logical disjunction.

논리합 사용의 예제

p = “My car has a bad engine.”, q = “My car has a bad carburetor.”

pq = “My car has a bad engine, or my car has a bad carburetor.”

Logic

논리합 (Disjunction) (2/2)

Disjunction operator 의 truth table

p q pq

T T T

T F T

F T T

F F F

Logic

배타적 -OR (Exclusive-OR) (1/2)

배타적 -OR 의 정의

p 와 q 가 명제이면 , “p exclusive-or q” 도 명제이며 , 이를 p 와 q 의 배타 적 -OR(exclusive-or) 라 하고 , pq 라 표기한다 .

이 명제는 p, q 중 어느 하나만이 참일 때만 참이 , 그 외는 모두 거짓이 된 다 .

The binary exclusive-or operator “” (XOR) combines two propositions to form their logical “exclusive or”.

배타적 -OR 사용의 예제

p = “I will earn an A in this course.”, q = “I will drop this course.”

pq = “I will either earn an A for this course, or I will drop it

Logic

배타적 -OR (Exclusive-OR) (2/2)

Exclusive-OR operator 의 truth table

p q pq

T T F

T F T

F T T

F F F

Logic

함축 (Implication) (1/2)

함축의 정의

p 와 q 가 명제이면 , 함축 (implication) “pq” 도 명제이며 , 이 명제는 p 가 참이고 q 가 거짓일 경우에만 거짓이 되며 , 그 외는 모두 참이 된다 . 이때 , p 를 hypothesis, antec edent 라 부르고 , q 를 conclusion, conse- quent 라 부른다 .

The implication pq states that p implies q. That is, if p is true, then q is true; but p is not true, then q could be either true or false.

함축 사용의 예제

p = “You study hard.”, q = “You will get a good grade.”

pq = “If you study hard, then you will get a good grade.”

Logic

함축 (Implication) (2/2)

Implication operator 의 truth table

p q pq

T T T

T F F

F T T

F F T

“pq” 를 표현하는 영어 문장

p implies q.

If p, then q.

p only if q.

p is sufficient for q.

q is necessary for p.

Logic

역 (converse), 이 (inverse), 대우 (contrapositive)

역 , 이 , 대우의 정의

역 (converse): q  p

이 (inverse): ¬p  ¬q

대우 (contrapositive): ¬q  ¬p

역 , 이 , 대우의 예제

명제 : “If it is raining, then the home team wins.”

역 : “If the home team wins, then it is raining.”

이 : “If it is not raining, then the home team does not win.”

대우 : “If the home team does not win, then it is not raining.”

Converse/Inverse/Contrapositive 의 truth table

p q ¬p ¬q pq qp ¬p¬q ¬q¬p

T T F F T T T T

동치 (equivalent)

Logic

상호조건명제 (Biconditional) (1/2)

상호조건명제의 정의

p 와 q 가 명제이면 , “p↔q” 를 상호조건명제 (biconditional) 라 하고 , p 와 q 가 동일한 진리 값을 가질 때 참이 되며 , 다른 진리 값을 가지면 거짓이 된 다 .

The biconditional p↔q states that p is true if and only if (IFF) q is true.

p↔q  (pq)(qp)  ¬(pq)

상호조건명제의 사용의 예제

p = “You can take the flight.”, q = “You buy a ticket.”

p↔q = “You can take the flight if and only if you buy a ticket.”

Logic

상호조건명제 (Biconditional) (2/2)

Biconditional operator 의 truth table

p q p↔q

T T T

T F F

F T F

F F T

“p↔q” 를 표현하는 영어 문장

p if and only if q.

p is necessary and sufficient for q.

q is necessary and sufficient for p.

Logic

논리 연산자의 우선순위 (Precedence)

우선 순위 테이블

Operator Precedence

¬ 1

 2

 3

 4

↔ 5

우선 순위를 명확히 하기 위하여 괄호 “ ()” 를 사용

 ¬pq 는 (¬p)q 를 의미하며 , ¬(pq) 를 의미하지 않는다 .

 pqr은 (pq)r 를 의미하며 , p(qr) 를 의미하지 않는다 .

Logic

Some Alternative Notations

Logic

Logic and Bit Operations

비트 (bit) 란 binary digit( 이진수 ) 에서 따온 단어임

비트는 1(true) 과 0(false) 의 값을 가짐

True 혹은 false 를 값으로 갖는 변수 (variable) 를 Boolean variable 이라 함

Bit operator(OR, AND, XOR) 의 truth table

Bit operation 의 예제 (refer to bitwise.c)

p q pq pq pq

0 0 0 0 0

0 1 1 0 1

1 0 1 0 1

1 1 1 1 0

01 1011 0110 11 0001 1101

11 1011 1111 bitwise OR 01 0001 0100 bitwise AND

Logic

강의 내용

논리 (Logic)

명제의 동치 (Propositional Equivalence)

술어와 한정기호 (Predicates and Quantifiers) 중첩된 한정기호 (Nested Quantifiers)

증명 방법 (Methods of Proof) 가설 (Conjectures)

Logic and Proof

항진 (Tautology) 과 부정 (Contradiction)

Propositional Equivalence

항진 명제

복합명제를 구성하는 단위명제의 진리 값이 어떠한 값을 가진다 하여도

해당 복합명제가 항시 참이면 이를 항진 (tautology) 명제라 한다 .

A tautology is a compound proposition that is true no matter what the truth values of its atomic propositions are!

예제 : p  ¬p

부정 명제

복합명제를 구성하는 단위명제의 진리 값이 어떠한 값을 가진다 하여도

해당 복합명제가 항시 거짓이면 이를 부정 (contradiction) 명제라 한다 .

A contradiction is a compound proposition that is false no matter what the truth val- ues of its atomic propositions are!

예제 : p

^

항진도 부정도 아닌 경우 불확정 명제 (cont ingency) 라 함

p ¬p p  ¬p p

¬p

T F T F

F T T F

논리적 동치 (Logical Equivalence) (1/2)

동치의 정의

만일 p↔q 가 항진이면 , p 와 q 는 논리적으로 동치이며 , p  q 혹은 pq 라 표기한다 .

Compound proposition p is logically equivalent to compound proposition q, written

pq, IFF the compound proposition p↔q is a tautology.

Truth Table 을 이용한 동치 판정 방법

예제 1: Prove that ¬(pq)  ¬p¬q [De Morgan’s Law]

 2개의 단위 명제로 구성된 경우 , 4(=2²) 개의 행이 필요

p q p  q ¬(p  q) ¬p ¬q ¬p  ¬q

T T T F F F F

T F T F F T F

F T T F T F F

F F F T T T T

Propositional Equivalence

논리적 동치 (Logical Equivalence) (2/2)

Truth Table 을 이용한 동치 판정 방법 ( 계속 )

예제 2: Prove that p(qr)  (pq)  (pr) [Distributive Law]

 3개의 단위 명제로 구성된 경우 , 8(=2³) 개의 행이 필요

복합명제가 n 개의 단위명제로 구성되는 경우 , 동치를 증명하기 위해 2ⁿ 개의 행이 필요

 Too much space!, Too expensive!

 동치 법칙 (Equivalence Laws) 을 활용

p q r q  r p  (q  r) p  q p  r (p  q)  (p  r)

T T T T T T T T

T T F F T T T T

T F T F T T T T

T F F F T T T T

F T T T T T T T

F T F F F T F F

F F T F F F T F

F F F F F F F F

Propositional Equivalence

동치 법칙 (Equivalence Laws) (1/4)

기본 법칙

동치 종류 법칙 이름

p  T  p, p  F  p Identity laws p  T  T, p  F  F Domination laws p  p  p, p  p  p Idempotent laws

¬(¬p)  p Double negation law

p  q  q  p

p  q  q  p Commutative laws ( 교환 법칙 )

(p  q)  r  p  (q  r)

(p  q)  r  p  (q  r) Associative laws ( 결합 법칙 ) p  (q  r)  (p  q)  (p  r)

p  (q  r)  (p  q)  (p  r) Distributive laws ( 분배 법칙 )

Propositional Equivalence

동치 법칙 (Equivalence Laws) (2/4)

기본 법칙

동치 종류 법칙 이름

¬(p  q)  ¬p  ¬q

¬(p  q)  ¬p  ¬q De Morgan’s laws

p  (p  q)  p p  (p  q)  p

Absorption laws ( 흡수 법칙 )

( 집합의 Venn Diagram 으로 생각하면 쉽게 이해 됨 )

p  ¬p  T

p  ¬p  F Negation laws

Propositional Equivalence

동치 법칙 (Equivalence Laws) (3/4) 함축을 포함한 논리적 동치

 p  q  ¬p  q

p  q  ¬q  ¬p

p  q  ¬p  q

p  q  ¬(p  ¬q) [try it!]

(p  q)  (p  r)  p  (q  r)

(p  r)  (q  r)  (p  q)  r [try it!]

(p  q)  (p  r)  p  (q  r)

(p  r)  (q  r)  (p  q)  r

Propositional Equivalence

동치 법칙 (Equivalence Laws) (4/4) 상호조건을 포함한 논리적 동치

 p ↔ q  (p  q)  (q  p)

p ↔ q  ¬p ¬ ↔ q [try it!] ( 대우 활용 )

p ↔ q  (p  q)  (¬p  ¬q)

Propositional Equivalence

An Example Problem

Prove that ¬(p  (¬p  q))  ¬p  ¬q

¬(p  (¬p  q))  ¬p  ¬(¬p  q)) De Morgan’s laws

 ¬p  (¬(¬p)  ¬q)De Morgan’s laws optional

 ¬p  (p  ¬q) Double negation law

 (¬p  p)  (¬p  ¬q) Distributive laws

 F  (¬p  ¬q) Negation laws

 (¬p  ¬q)  F Commutative laws optional

 ¬p  ¬q Identity laws

Propositional Equivalence

강의 내용

논리 (Logic)

명제의 동치 (Propositional Equivalence)

술어와 한정기호 (Predicates and Quantifiers) 중첩된 한정기호 (Nested Quantifiers)

증명 방법 (Methods of Proof) 가설 (Conjectures)

Logic and Proof

술어 (Predicate), 명제 함수 (Propositional Func- tion)

“x is greater than 3.”

Predicates and Quantifiers

변수 (variable) = x 술어 (predicate) = P

P(x) = “x is greater than 3.”

명제 함수

(propositional function)

Q(x, y) = “x = y + 3”

R(x, y, z) = “x + y = z”

일반적으로 n 개의 변수 x

, x

, x

, …, x

을 포함하는 명제 함수는

한정기호 (Quantifiers)

명제 함수를 명제로 만드는 방법

1. 변수에 특정 값을 할당하는 방법

2. 한정 (quantification) 을 적용하는 방법

(1) 변수에 특정 값을 할당하는 방법

P(x) = “x > 3”

만일 x = 4 라면 P(x) 는 true 가 되고 , x = 2 라면 P(x) 는 false 가 된다 .

(2) Quantification 을 적용하는 방법

P(x) = “x > 3”

x 의 정의역 (domain) 이 “ 4 이상인 모든 실수”라면 , P(x) 는 true 가 된다 .

The collection of values that a variable x can take is called x’s domain or universal of discourse.

Predicates and Quantifiers

Universal Quantifier  (1/3)

정의

P(x) 의 Universal Quantifier 란

“ 정의역 (domain) 에 속하는 모든 값 x 에 대하여 P(x) 가 참이다 .” 라는 명제이 다 .

Universal Quantifier 의 표기 및 읽기

 표기 : xP(x)

 읽기 : “for all x in P(x)” 혹은 “ for every x in P(x)”

Predicates and Quantifiers

Universal Quantifier  (2/3)

Universal Quantifier 의 개념적 이해

Domain 의 모든 값을 x

, x

, …, x

으로 나열할 수 있다면 ,

xP(x) 는 다음과 동일하다 . P(x

)  P(x

)  ....  P(x

)

Universal Quantifier 의 사용 예

예 1: P(x) 가 “ x < 2” 이고 domain 이 모든 실수라 할 때 , xP(x) 의 진리 값은 ?  거짓

예 2: Q(x) 가 “ x²  0” 이고 domain 이 모든 실수라 할 때 , xQ(x) 의 진리 값은 ?  참

Predicates and Quantifiers

Universal Quantifier  (3/3)

반례 (counterexample)

P(x) 가 명제 함수라 할 때 , xP(x) 가 거짓임을 보이기 위해서는 domain 에 속 하는 값 중 단지 하나의 값이라도 P(x) 를 거짓으로 만드는 예를 보이면 된다 .

 이와 같이 P(x) 를 거짓으로 만드는 예를 반례 (counterexample) 이라 한다 .

Counterexample 사용의 예

P(x) 가 “ x

> 0” 이고 domain 이 모든 실수라 할 때 ,

xP(x) 의 counterexample 은 ?

− x = 0 이면 x

= 0 이 되어 , x

> 0 를 만족하지 않는다 .

− 따라서 , xP(x) 는 거짓이 되고 , 이때 x = 0 을 counterexample 이라 한 다 .

Predicates and Quantifiers

Existential Quantifier  (1/2)

정의

P(x) 의 Existential Quantifier 란

“Domain 에 속하는 적어도 하나의 값 x 에 대하여 P(x) 가 참이다 .” 라는 명제이 다 .

Existential Quantifier 의 표기 및 읽기

 표기 : xP(x)

 읽기 : “for some x in P(x)” 혹은 “ there is an x such that P(x)”

Predicates and Quantifiers

Existential Quantifier  (2/2)

Existential Quantifier 의 개념적 이해

Domain 의 모든 값을 x

, x

, …, x

으로 나열할 수 있다면 ,

xP(x) 는 다음과 동일하다 . P(x

)  P(x

)  ....  P(x

)

Existential Quantifier 의 사용 예

예 1: P(x) 가 “ x > 3” 이고 domain 이 모든 실수라 할 때 , xP(x) 의 진리 값은 ?  참

예 2: Q(x) 가 “ x = x+1” 이고 domain 이 모든 실수라 할 때 , xQ(x) 의 진리 값은 ?  거짓

Predicates and Quantifiers

Quantifier 개념 요약

Statement When true? When false?

xP(x)

P(x) is true for every x.

xP(x) There is an x for which P(x) is true. P(x) is false for every x.

Predicates and Quantifiers

Binding Variables

Binding Variables vs. Free Variables

 변수 x 에 quantifier 가 적용되거나 특정 값이 할당되면 , x 를 binding variable 이라 한다 .

 변수 x 에 quantifier 가 적용되지 않거나 특정 값이 할당되지 않았으면 , x 를 free variable 이라 한다 .

Quantifier 가 적용되는 부분을 quantifier 의 범위 (scope) 라 한다 .

xP(x, y)

binding variable

x(P(x)Q(x))  xR(x)

free variable

Predicates and Quantifiers

Negation with Quantifiers (1/2)

Negation 예제

x = student, P(x) = “x in the class has taken a course in calculus.”

xP(x) = “Every student in the class has taken a course in calculus.”

¬xP(x)

= “It is not the case that every student in the class has taken a course in calculus.”

= “There is a student in the class who has not taken a course in calculus.”

= x¬P(x)

Predicates and Quantifiers

Negation with Quantifiers (2/2) Negation 관련 법칙

Negation 관련 예제

 x(x

> x) 의 부정  ¬x(x

> x)  x¬(x

> x)  x(x

 x)

 x(x

= 2) 의 부정  ¬x(x

= 2)  x¬(x

= 2)  x(x

 2)

¬xP(x)  x¬P(x) ¬xP(x)  x¬P(x)

Predicates and Quantifiers

강의 내용

논리 (Logic)

명제의 동치 (Propositional Equivalence)

술어와 한정기호 (Predicates and Quantifiers) 중첩된 한정기호 (Nested Quantifiers)

증명 방법 (Methods of Proof) 가설 (Conjectures)

Logic and Proof

Nested Quantifiers  Statements (1/3)

Variable x 와 y 의 domain 이 실수 (all real numbers) 라 했을 때 ,

xy(x + y = y + x) 를 번역하면 ,

“For every real number x and for every real number y, x + y = y + x.” 이고 , 이는 실수의 덧셈에 있어서 교환법칙을 의미한다 .

xy(x + y = 0) 를 번역하면 ,

“For every real number x, there is a real number y such that x + y = 0.”

( 항등원과 역원을 의미한다 .)

xyz(x + (y + z) = (x + y) + z) 를 번역하면 ,

“For every real number x, for every real number y, and for every real number z,

x + (y + z) = (x + y) + z.”

이는 실수의 덧셈에 있어서 결합법칙을 나타낸다 .

Nested Quantifiers

Nested Quantifiers  Statements (2/3)

예제

Variable 의 domain 이 모두 실수일 때 , 다음을 번역하라 . xy((x > 0)  (y < 0)  (xy < 0))

 풀이 :

“For every real number x and for every real number y, if x > 0 and y < 0, then xy < 0.”

Nested Quantifiers

Nested Quantifiers  Statements (3/3)

예제

C(x) = “x has a computer.”, F(x, y) = “x and y are friends.” 이고 ,

x 와 y 의 domain 이 “ all students in your school.” 일 때 , 다음을 번역하라 . x(C(x)  y((C(y)  F(x, y)))

 풀이 :

“For every student x in your school, x has a computer, or there is a student y (in your school) such that y has a computer and x and y are friends.”

Nested Quantifiers

Statements  Nested Quantifiers (1/2)

예제

“If a person is female and is a parent, this person is someone’s mother.” 를 predicate, domain = “all people” 인 quantifier, logic operator 로 표현하라 .

풀이

− 상기 문장은 다음과 같이 다시 쓸 수 있다 .

“For every person x, if person x is female and person x is a parent, then there ex- ists a person y such that person x is the mother of person y.”

− 명제 함수로 표현 :

F(x) = “x is female.”

P(x) = “x is a parent.”

M(x, y) = “x is the mother of y.”

− 상기 명제 함수를 사용하여 표현하면 다음과 같다 . x((F(x)  P(x))  yM(x, y))

Nested Quantifiers

Statements  Nested Quantifiers (2/2)

예제

“Everyone has exactly one best friend.” 를 predicate, domain = “all people” 인 quan- tifier, logic operator 로 표현하라 .

풀이

− 상기 문장은 다음과 같이 다시 쓸 수 있다 .

“For every person x, person x has exactly one best friend.”

= “x(person x has exactly one best friend)”

− 명제 함수로 표현 :

B(x, y) = “y is the best friend of x.”

− “person x has exactly one best friend.” 를 명제 함수를 사용하여 표현 : y(B(x, y)  z((z  y)  ¬B(x, z)))

 상기 명제 함수를 사용하여 표현하면 다음과 같다 .

Nested Quantifiers

Negating Nested Quantifiers

예제

다음 식의 부정을 표현하라 .

xy(xy = 1)

풀이

Negation of xy(xy = 1)

“ 모든 x 에 대해서 xy = 1 을 만족하는 y 가 존재한다 .” T or F ^?

 ¬(xy(xy = 1))

 ¬xy(xy = 1)

 x¬y(xy = 1)

 xy¬(xy = 1)

 xy(xy  1) “어떤

x

y 가 xy  1 을 만족하는 x 가 존 재한다 .” T ^{or F?}

(x = 0)

Nested Quantifiers

Order of Quantifiers (1/3)

예제

 술어 P(x, y) = “x+y = y+x” 이고 x 와 y 의 domain 이 실수일 때 ,

xyP(x, y) 의 진리 값은 ?

그리고 , yxP(x, y) 의 진리 값은 ?

 풀이

− 모든 실수에 대하여 덧셈의 교환법칙이 성립하므로 , xyP(x, y) 의 진리 값 은 true 이다 . 마찬가지로 , yxP(x, y) 의 진리 값 역시 참이다 .

 xy 와  yx 에 있어서 , x 와  y 의 순서는 진리 값에 영향을 주지 않는다 .

Nested Quantifiers

Order of Quantifiers (2/3)

예제

 술어 Q(x, y) = “x + y = 0” 이고 x 와 y 의 domain 이 실수일 때 , yxQ(x, y) 와 xyQ(x, y) 의 진리 값은 ?

 풀이

− yxQ(x, y): 어떤 y 에 대해 모든 x 가 “ x + y = 0” 을 만족하는 y 가 존재 한다 .  false (

만일 Q(x,y) = “xy = 0” 이라면 ?

− xyQ(x, y): 모든 x 에 대해 “ x + y = 0” 을 만족하는 y 가 존재한다 .  true

 yx 와  xy 에 있어서 , x 와  y 의 순서는 진리 값에 영향을 준다 .

Nested Quantifiers

Order of Quantifiers (3/3)

변수가 두 개인 경우의 Quantifier 순서의 영향

Statement When true?

xyP(x, y)

yxP(x, y)

P(x, y) is true for every pair x and y.

xyP(x, y) For every x, there is a y for which P(x, y) is true.

xyP(x, y) There is an x for which P(x, y) is true for every y.

xyP(x, y)

yxP(x, y) There is a pair x and y for which P(x, y) is true.

모든 x 에 대해서 적어도 P(x, y) 를 true 로 하는 y 가 존재하면 , 해당 식은 true 가 된다 .

어떤 x 에 대해 모든 y 가 P(x, y) 를 true 로 하면 , 해당 식은 true 가 된다 .

Nested Quantifiers

유용한 Equivalence Laws

xP(x) 

x

P(x)

xP(x) 

x

P(x)

상기 두 표현 식은 앞서 소개한 Quantifier 정의를 이용해 증명이 가능하다 .(try it!)

(Remind) Quantifier 의 정의 :

xP(x)  P(x

)  P(x

)  ....  P(x

)

xP(x)  P(x

)  P(x

)  ....  P(x

)

x(P(x)  Q(x))  (xP(x))  (xQ(x))

x(P(x)  Q(x))  (xP(x))  (xQ(x))

상기 표현 식 역시 Quantifier 정의를 이용해 증명이 가능하다 .(try it!)

Nested Quantifiers

강의 내용

논리 (Logic)

명제의 동치 (Propositional Equivalence)

술어와 한정기호 (Predicates and Quantifiers) 중첩된 한정기호 (Nested Quantifiers)

증명 방법 (Methods of Proof) 가설 (Conjectures)

Logic and Proof

증명의 중요성

수학에서 증명이란

수학적 문장의 진실성을 정밀하고 부정할 수 없도록 설명하는 정확 (correct)하고 완전 (complete) 한 기술이다 .

A correct (well-reasoned, logically valid) and complete (clear, detailed) argument that rigorously and undeniably establishes the truth of a mathematical statement

증명에서의 기본적 사항

정확성 : Correctness prevents us from fooling ourselves.

완전성 : Completeness allows anyone to verify the result.

Methods of Proof

증명의 응용 분야

학문의 많은 분야에서 , 논리적이고 정확한 의사 교환 (clear communication) 을 위해 사용한다 .

수학 분야의 기본적인 행동 ( 연구 ) 은 흥미롭고 밝혀지지 않은 많은 정리 (theorem) 를 증명을 통해 발견하는 것이다 .

정리의 증명은 프로그램 검증 (program verification), 컴퓨터 보안 , 자동화된 추 론 시스템 (automated reasoning system) 등에서 사용된다 .

. . .

Methods of Proof

용어 (Terminology) (1/3)

정리 (theorem)

 정리란 참 (true) 으로 밝혀진 명제이다 .

A statement that has been proven to be true.

공리 (axiom, postulates)

 증명된 정리 혹은 증명하고자 하는 정리의 가정 / 명제이다 . ( 증명이 불필요 한 )

Assumptions (often unproven) defining the structures about which we are reasoning. ( 예 : n 이 짝수라면 n = 2k 라 나타낼 수 있다 .)

추론 규칙 (rules of inference)

 논리적으로 유효한 주장 (logically valid deductions) 을 사용하여 , 가정을 결 론으로 이끌어가는 증명의 과정이다 .

Methods of Proof

용어 (Terminology) (2/3)

보조정리 (lemma)

 다른 정리를 증명하는데 사용하는 간단한 정리이다 .

 A minor theorem used as a stepping-stone to proving a major theorem.

“ 복잡한 내용이 정리이고 , 간단한 내용이 보조정리”를 의미하는 것은 아님에 유 의 !

따름정리 (corollary)

 어떤 정리가 증명되면 , 이에 의하여 자연스럽게 증명되는 정리이다 .

 A minor theorem proved as an easy consequence of a major theorem.

Methods of Proof

용어 (Terminology) (3/3)

가설 (conjecture)

 증명되지는 않았지만 참으로 믿어지는 명제이다 .

A statement whose truth values has not been proven.

(A conjecture may be widely believed to be true, regardless.)

이론 (theory)

 주어진 공리 (axiom) 로부터 증명이 가능한 모든 정리 (theorem) 의 집합이다 .

The set of all theorems that can be proven from a given set of axioms.

Methods of Proof

추론 규칙 (Inference Rules) (1/2) 추론 규칙의 의미

 주어진 가정 (antecedent) 이 참 (true) 일 때 , 결론 (consequent) 이 참이라는 패턴

“x = 3”(= p) 이면 , “x + 1 = 4”(= q) 이다 .

- 상기 예에서 p( 가정 ) 가 참이면 , q( 결론 ) 은 참이 된다 .

추론 규칙의 표기

antecedent 1 antecedent 2 …

 consequent

가정 결론

“” 은 “ therefore” 를 의미한다 .

Methods of Proof

추론 규칙 (Inference Rules) (2/2)

각 추론 규칙은 “항진 명제인 함축 (implication)” 에 해당한 다 .

ant.1 ant.2 …

 con. 에 해당하는 tautology 는 “ ((ant.1  ant.2  … )  con.” 이다 .

Methods of Proof

추론 규칙 예제 (1/2)

예제

“It is below freezing now. Therefore, it is either below freezing or raining now.” 가 참인 것은 어떤 추론 규칙에 근거하는가 ?

 풀이

− p = “It is below freezing now.”, q = “It is raining now.”

− 주어진 문장은 다음과 같은 추론 규칙에 근거하며 , 이를 addition rule 이라 한다 .

p

 p

 q

Methods of Proof

추론 규칙 예제 (2/2)

예제

“If it rains today, then we will not have a barbecue today.

If we do not have a barbecue today, then we will have a barbecue tomorrow.

Therefore, if it rains today, then we will have a barbecue tomorrow.” 의 추론 근거는 ?

 풀이

− p = “It is raining today.”

− q = “We will not have a barbecue today”

− r = “We will have a barbecue tomorrow.”

p  q q  r

 p  r

Hypothetical syllogism ( 삼단논법 )

Methods of Proof

추론 규칙 종류 (1/2)

Rule of inference Tautology Name

p



p  q p  (p  q)

p  q



p

p q



p  q

((p)  (q))  (p  q) Conjunction

p

p  q



q

(p  (p  q))  q Modus ponens ( 긍정 논법 ) (the mode of affirming)

¬ q p  q



¬ p

(

¬ q  (p  q))  ¬ p

Methods of Proof

추론 규칙 종류 (2/2)

Rule of inference Tautology Name

p  q q  r



p  r

((p  q)  (q  r))  (p  r) Hypothetical syllogism ( 삼단 논법 )

p  q

¬ p



q

((p  q) 

¬ p)  q

p  q

¬ p  r



q  r

((p  q)  (

^¬ p  r))  (q  r)

p 가 false 이고 p  q 이 true 이면 , 당연히 q 는 true 이다 .

Methods of Proof

Formal Proofs (1/2)

Formal Proof 의 정의

Formal proof 란 주어진 가정 (antecedent) 에 기반하여 추론 규칙을 적용한 일 련의 단계 (step) 를 거쳐서 결론 (consequent) 을 도출하는 과정이다 .

− A formal proof of a conclusion C, given antecedents p

, p

, …, p

consists of a sequence of steps, each of which applies some inference rule to an- tecedents or to previously proven statements to yield a new true state- ment (the consequent).

 증명 (proof) 은 주어진 모든 가정이 true 일 때 결론이 true 임을 보이는 과정 이다 .

− A proof demonstrates that if the antecedents are true, then the conclu- sion is true.

Methods of Proof

Formal Proofs (2/2) 예제

다음 가정이 “ We will be home by sunset.” 이라는 결론을 도출함을 보여라 .

− “It is not sunny this afternoon and it is colder than yesterday.”

− “We will go swimming only if it is sunny.” ( If we will go swimming, then it is sunny this …)

− “If we do not go swimming, then we will take a canoe trip.”

− “If we take a canoe trip, then we will be home by sunset.”

풀이

− p = “It is sunny this afternoon.”

− q = “It is colder than yesterday.”

− r = “We will go swimming.”

− s = “We will take a canoe trip.”

− t = “We will be home by sunset.”

단계 과정 이유

1

¬ p  q ^가정

2

¬ p 단계 1 의 simplification

3

r  p ^가정

4

¬ r 단계 2, 3 기반의 Modus tollens

5

¬ r  s ^가정

6

s 단계 4, 5 기반의 Modus ponens

7

s  t ^가정

8

t 단계 6, 7 기반의 Modus ponens

p p  q

 q

Modus ponens

¬q

p  q Modus tollens

Methods of Proof

Inference Rules for Quantifiers (1/3)

Quantifier 를 포함하는 추론 규칙

Universal instantiation

− xP(x) 가 주어졌을 때 , xP(x) 이 true 라면 , domain 에 속하는 임의의 값 ( 요소 ) c 에 대해서 P(c) 가 true 임을 보이는데 사용되는 추론 규칙이다 .

Universal generalization

− xP(x) 가 주어졌을 때 , domain 에 속하는 모든 값 ( 요소 ) c 에 대해서 P(c) 가 true 이면 , xP(x) 가 true 임을 보일 때 사용되는 추론 규칙이다 .

Existential instantiation

− xP(x) 가 주어졌을 때 , xP(x) 가 true 라면 , domain 안에 P(c) 를 true 로 하는 값 ( 요소 ) c 가 적어도 하나 이상 있다는 것을 나타내는 추론 규칙이다 .

Existential generalization

− xP(x) 가 주어졌을 때 , 특정 값 ( 요소 ) c 에 대해서 P(c) 가 true 이면 , xP(x) 이

Methods of Proof

Inference Rules for Quantifiers (2/3)

Quantifier 사용 명제의 추론 규칙 정리

Rule of inference Tautology Name

xP(x)



P(c)

tiation

P(c) for an arbitrary

c

 xP(x)

P(c) for an arbitrary c  xP(x)

xP(x)



P(c) for some c

P(c) for some c

 xP(x)

P(c) for an some c  xP(x)

Methods of Proof

Inference Rules for Quantifiers (3/3)

예제

다음 가정이 “ Maria has taken a course in computer science.” 이라는 결론을 도출함을 보여라 .

− “Everyone in this discrete mathematics class has taken a course in computer science.”

− “Maria is a student in this class.”

풀이

− D(x)

= “ x is in this discrete mathematics class.”

− C(x)

= “ x has taken a course in computer science.”

− 가정 :

− 결론 : C(Maria)

− 추론 과정

단계 과정 이유

1 x(D(x)  C(x))

^가정

2

D(Maria)  C(Maria) 단계 1 의 universal instantiation

Methods of Proof

Summary of Proof Methods

함축 (implication) p  q 의 증명을 위하여 , 다음 방법들을 사용한다 .

Direct proof: Assume p is true, and prove q.

Indirect proof: Assume ¬q, and prove ¬p. ( 대우의 증명에 해당 )

Vacuous proof: Prove ¬p by itself. ( 가정이 false 임을 증명하면 , pq 는 true)

Trivial proof: Prove q by itself. ( 결론이 항시 true 임을 증명 )

Proof by cases:

To prove (p₁  p₂  ....  p_n)  q,

prove ((p₁  q)  (p₂  q)  ....  (p_n  q))

Methods of Proof

Direct Proof ( 직접 증명 )

Implication p  q 의 증명을 위하여 , p 가 true 라 가정하고 여러 규칙과 기존에 true 로 증명된 정리를 사용하여 q 가 true 임을 증명한다 .

예제

Definition: An integer n is called odd iff n=2k+1 for some integer k; n is even iff n=2k for some k.

Axiom: Every integer is either odd or even.

Theorem: (For all numbers n) If n is an odd integer, then n² is an odd integer.

Proof:

− If n is odd, then n = 2k+1 for some integer k.

− Thus, n² = (2k+1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1.

− Therefore, n² is of the form 2j + 1 (with j the integer 2k² + 2k), thus n² is odd. □

Methods of Proof

Indirect Proof ( 간접 증명 )

Implication p  q 대신 이의 대우인 ¬q  ¬p 를 증명한다 . 예제

Theorem: (For all integers n) If 3n+2 is odd, then n is odd.

Proof:

− Suppose that the conclusion is false, i.e., n is even.

− Then n=2k for some integer k.

− Then 3n+2 = 3(2k)+2 = 6k+2 = 2(3k+1).

− Thus 3n+2 is even, because it equals 2j for integer j = 3k+1.

− So 3n+2 is not odd.

− We have shown that ¬(n is odd) ¬(3→

n+2 is odd), thus its contra-positive (3n+2 is

Methods of Proof

Vacuous Proof ( 무의미한 증명 )

가정 (p) 이 false 임을 보임으로서 , p  q 가 true 임을 증명한다 . 예제

Theorem: (For all n) If n is both odd and even, then n² = n + n.

Proof:

− The statement “n is both odd and even” is obviously false since no number can be both odd and even.

− So, the theorem is vacuously true. □

Methods of Proof

Trivial Proof ( 자명한 증명 )

Implication p  q 에서 , 결론 (q) 이 trivial 하게 true 임을 증명한다 . 예제

Theorem: (For integers n) If n is the sum of two prime numbers, then either n is odd or n is even.

Proof:

− Any integer n is either odd or even.

− So the conclusion of the implication is true regardless of the truth of the an- tecedent.

− Thus the implication is true trivially. □

Methods of Proof

Proof by Contradiction ( 모순에 의한 증명 ) (1/2)

증명 방법

A method for proving p.

(p 를 증명하고자 하는 방법이다 .)

Assume ¬p, and prove some proposition q is contradiction (i.e., q is always false.) (p 를 부정하면 항시 거짓이 되는 명제가 있음을 보인다 . 즉 , ¬pF 을 보인다 .)

Then, ¬pF, which is only true if

¬ p=F

(¬pF 이 참이 되기 위해서는 ¬p 가 거짓이어야 한다 .)

Thus, p is true. ( 따라서 , p 는 참이 된다 .)

주어진 가정 (p) 을 부정 (false) 했을 때 항상 false 가 되는 명제 q 가 있음을 보이면 ,

p

( 가정을 부정했을 때 , 결론이 항시 거짓이 되면 , “ 가정을 부정”한 것이 잘못된 것이다 . 따라서 , 가정은 참이다 .)

* 타임 머신의 예 : “ 우리는 과거로 돌아갈 수 없다 .” 왜 ? 내가 과거로 돌아갈 수 있다 하

Methods of Proof

개념적인 다른 예제 : n 이 정수라 할 때 , 2n 은 짝수이다 .

− 만일 , 2n 이 홀수라 하자 . 그러면 , 2n = 2k+1 인 정수 k 가 존재한다 .

− 그러면 , k = (2n – 1)/2 가 되는데 , 이는 정수가 아니다 .

− 따라서 , 2n 은 홀수가 아니고 , 이는 가정 (2n 이 홀수 ) 이 잘못되었음을 의미한다 .

− 따라서 , 2n 은 짝수이다 .

Proof by Contradiction ( 모순에 의한 증명 ) (2/2)

Methods of Proof

Proof by Cases ( 사례에 의한 증명 ) (1/2)

가정이 논리합으로 구성된 (p

 p

 ....  p

)  q 형태를 증명하기 위 하여 , 다음과 같은 tautology 를 사용한다

(p

 p

 ....  p

)  q  ((p

 q)  (p

 q)  ....  (p

 q))

즉 , 각각의 (p

 q) 를 증명함으로써 전체를 증명하는 방법이다 .

Methods of Proof

Proof by Cases ( 사례에 의한 증명 ) (2/2)

예제

Theorem: |xy| = |x||y|, where x and y are real numbers.

(|x| = x if x  0, |x| = -x if x < 0)

Proof:

− p = x and y are real numbers, q = |xy| = |x||y|

− p = {x  0, y  0}  {x  0, y < 0}  {x < 0, y  0}  {x < 0, y < 0}

▫ {x  0, y  0}  q: |xy| = xy = |x||y|

▫ {x  0, y < 0}  q: |xy| = -xy = x(-y) = |x||y|

▫ …

− All the possible cases are proven to true, and thus, the theorem is proven.□

Methods of Proof

Proof of Equivalence ( 동치 증명 )

상호조건 p ↔ q(“p if and only if q”) 을 증명하기 위해서는 다음과 같은 tautology 를 사용한다 .

(p ↔ q)  ((p  q)  (q  p))

즉 , (p q) 를 증명하고 (q p) 를 증명함으로써 , (p ↔ q) 를 증명한다 .

Methods of Proof

Existence Proof ( 존재 증명 ) (1/2)

증명하고자 하는 문장에  xP(x) 형태의 quantifier/predicate 가 포함된 경우를 존재 증명 (existence proof) 이라 한다 .

If the proof of a statement of the form xP(x) is called an existence proof.

Methods of Proof

Existence Proof ( 존재 증명 ) (2/2)

예제

Theorem: There exists a positive integer n that is the sum of two perfect cubes in two different ways.

( 두 수의 세제곱의 합을 두 가지 방법으로 나타낼 수 있는 정수가 존재한다 .) (In other words, there exists a positive integer n such that n = j

+ k

= l

+ m

, where j, k, l, and m are positive integers, and {j, k}  {l, m}.)

Proof: Consider n = 1729, j = 9, k = 10, l = 1, m = 12. Now just check that the equalities hold. □

Methods of Proof

Uniqueness Proof ( 유일성 증명 )

유일하게 하나의 값 ( 요소 ) 만이 주어진 특성을 만족하는 경우를 유일성 이라 하고 , 이의 증명을 유일성 증명 (uniqueness proof) 이라 한다 .

유일성의 증명 과정

존재 : x 가 주어진 특성을 가짐을 보인다 .

유일성 : 만일 y  x 이면 , y 는 주어진 특성을 갖지 않음을 보인다 .

“P(x) 를 만족하는 x 가 유일하게 하나 존재함을 증명하는 과정은 다음 표 현을 증명하는 것과 동일하다 . ( 가장 절친한 친구는 오직 한 명이다 .)

x(P(x)  y(y  x  ¬P(y)))

Methods of Proof

Mistakes in Proofs

예제 (mistakes in proof)

Theorem: Prove 1 = 2.

Proof:

− Let a and b be the same positive integers.

− a = b [ 주어진 정의 ]

− a² = ab [ 양변에 a 를 곱함 ]

− a² - b² = ab - b² [ 양변에서 b² 를 뺌 ]

− (a – b)(a + b) = b(a – b) [ 인수분해 ]

− a + b = b [ 양변을 (a-b) 로 나눔 ]

− 2b = b [since a = b]

− 2 = 1. [ 양변을 b 로 나눔 ]

What is wrong?

 (a – b) is zero since a = b, and thus, we cannot use (a – b) as a divisor.

Methods of Proof

강의 내용

논리 (Logic)

명제의 동치 (Propositional Equivalence)

술어와 한정기호 (Predicates and Quantifiers) 중첩된 한정기호 (Nested Quantifiers)

증명 방법 (Methods of Proof) 가설 (Conjectures)

Logic and Proof

가설과 증명 (Conjecture & Proof)

가설의 형식화

가능한 많은 형태의 증거에 기초하여 가설을 형식화한다 .

기존 정리나 명제를 사용하여 원하는 가설을 만들어내거나 , 직관이나 결과가 성립한다 는 믿음에 기초하여 가설을 만들어 낸다 .

가설의 증명

가설이 형식화되면 목표는 이를 증명하는 것이다 . 증명하게 되면 , 가설은 정리가 된 다 .

증명하지 못하면 , 가설은 결국 가설로 남게 된다 .

예제

가설 : a > 2 이고 n 이 양의 정수이면 , aⁿ

− 1

( 누군가가 직관 ( 뛰어난 통찰력 ) 을 사용하여 이런 가설을 생각했다 하자 .)

증명 :

− aⁿ − 1 = (a − 1)(a^n-1 + … + a + 1)

Conjectures

가설과 반례 (Conjecture & Conterexample)

가설에 대한 반례

그럴듯한 가설을 제시하였는데 , 이의 증명이 어려운 경우 , 반례를 생각하게 된다 .

반례를 들 수 있으면 , 그 가설은 false 가 되어 정리가 되지 못한다 .

예제 (Leonhard Euler)

가설 : n  3 인 모든 정수 n 에 대해서 , n − 1 개의 양의 정수들의 n 제곱의 합은 어떤 수의 n 제곱이 될 수 없다 . ⁽ 예 : n = 3, a³ + b³을 만족하는 c³은 없다 .)

반례 1(n = 4): 95,800⁴ + 217,519⁴ + 414,560⁴ = 422,481⁴ (1988, Noam Elkies)

반례 2(n = 5): 27⁵ + 84⁵ + 110⁵ + 133⁵ = 144⁵ (1966, Lander & Parkin)

나머지는 밝혀진 반례가 없다 .

그렇다면 , 다른 경우 ( 예 : n  6) 에 대해서는 가설이 혹시 참이 아닐까 ?

Conjectures

유명한 가설들 (1/2)

페르마 (Fermat) 의 마지막 정리 방정식

가설 : xⁿ + yⁿ = zⁿ 은 n > 2 인 정수일 때 , xyz  0 인 x, y, z 에 대해 해를 갖지 않는다 .

− n = 3 인 경우에 대해서는 Euler 에 의해 증명됨

− n = 4 인 경우에 대해서는 Fermat 에 의해 증명됨

− 나머지에 대해서는 타원 곡선 이론이라는 매우 복잡한 정수론 분야에 의해서 1990 년 대에 Andrew Wiles 에 의해 비로소 증명됨 (350 년 만에 증명됨 )

비로소 , 페르마의 마지막 방정식은 가설에서 정리가 되었다 .

Conjectures

유명한 가설들 (2/2)

골드바흐 (Christian Goldbach)

가설 : n > 2 인 짝수 n 은 두 소수의 합이다 .

− 예 : 4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3, 10 = 7 + 3, 12 = 7 + 5, …

− 컴퓨터 이전 : 백만 단위까지 증명 (by hand)

− 컴퓨터 이후 : 4∙10¹⁴ 까지 증명 (2002 년 중반 )

− 아직 (?) 증명되지는 않았으나 대부분 수학자는 true 라 믿고 있음

유사 가설 : n > 2 인 짝수 n 은 적어도 6 개의 소수의 합으로 표현됨 (1995, Ramare 증 명 )

Conjectures

The Halting Problem ( 정지 문제 ) (1/2) - skip

Alan Turing discovered in the 1930’s that there are prob- lems unsolvable by any algorithm.

( 튜링은 “어떠한 알고리즘으로도 풀 수 없는 문제가 있음”을 밝혔다 .)

The desired function is H(P,I) = the truth value of the statement

“Program P, given input I, eventually halts”.

(H(P,I) = “ 프로그램 P 와 P 의 입력 I 가 주어졌을 때 , 이 프로그램 P 가 정지하는지”의 여부를 판단하는 함수 )

 튜링은 이러한 함수 H(P,I) 가 존재하지 않음을 증명하였다 .

Implies general impossibility of predictive analysis of arbitrary com- puter programs.

( 임의의 프로그램에 대한 예측 분석이 일반적으로 불가능함을 의미한다 .)

Conjectures

The Halting Problem ( 정지 문제 ) (2/2) - skip

정지 문제의 증명 (by contradiction)

H(P,I) =

− 만일 P 가 정지하면 “정지”를 출력하고 ,

− 그렇지 않으면 ( 만일 P 가 무한루프이면 ) “ 무한루프”를 출력한다 .

K(P) =

− H(P,P) 가 “정지”를 출력하면 , 무한루프를 수행하고 ,

− H(P,P) 가 “무한루프”를 출력하면 , 정지한다 .

H(K,K) =

− H(K,K) 가 “정지”를 출력하면 , K(K) 는 무한루프를 수행한다 .  모순 !

 H() 는 출력으로 Program K 가 정지한다고 하였는데 , 실제 K 는 무한루프를 수행하므로 모순 이다 .

− H(K,K) 가 “무한루프”를 출력하면 , K(K) 는 정지한다 .  모순 !

 H() 는 출력으로 Program K 가 무한루프를 수행한다 하였는데 , 실제 K 는 정지하므로 모순이 다 .

Conjectures

강의 내용

논리 (Logic)

명제의 동치 (Propositional Equivalence)

술어와 한정기호 (Predicates and Quantifiers) 중첩된 한정기호 (Nested Quantifiers)

증명 방법 (Methods of Proof) 가설 (Conjectures)

Logic and Proof

Homework #1

Logic and Proof