1 기초: 논리와 증명 5

//이 자료는 Discrete mathmatics and its application 7th edition에서 나오는 예제를 간추린 것입니다. 저는 코딩에 관심 있는 학생이며, 타인의 지적재산을 단지 학습을 위해 사용할 뿐 개인의 금리적 이윤을 위한 상업적인 용도로 쓰지 않습니다. 만약 저작권 관련 문제가 될 시 즉시 문서를 삭제하겠습니다.//

중첩 정량자

이전 장에서는 존재 정량자와 전체 정량자와 정량자를 통해 수학적 구문을 표현하는 방법을 살펴보았습니다. 영어 문장을 논리적 표현식으로 바꾸는 법도 살펴보았습니다. 이제는 중첩된 정량자를 사용하는 법을 살펴 볼 것입니다. 예로, ∀x∃y(x+y=0)는 ∀xQ(x)를 뜻합니다. Q(x)는 ∃yP(x, y)이고 P(x, y)는 x+y=0 입니다. 중첩 정량자는 수학과 컴퓨터 과학에서 자주 사용됩니다. 중첩 정량자가 가끔 이해하는데 어려울 수 있습니다. 이제 중첩 정량자를 사용하여 수학 구문을 표현하는 법을 알아 볼 것입니다. "두 양수의 합은 항상 양의 값이다." 또는 영어 구문을 논리 구문으로 표현할 수 있습니다. "모든 사람은 정확히 친한 친구 한 명을 가진다" 더, 중첩 정량자를 포함한 구문의 부정형도 배울 것입니다.

예제1 중첩 정량자를 표현하기

변수 x와 y의 정의역은 실수라고 해봅시다. 구문 ∀x∀y(x+y = y+x)는 x+y = y+x가 모든 실수 x와 y에 대해 성립한다는 것입니다. 이는 실수의 덧셈에 대한 교환법칙입니다. 반면에, 구문 ∀x∃y(x+y=0)는 모든 실수 x에 대해 어떤 실수 y가 x+y=0을 만족한다 입니다. 이는 모든 실수는 반수(반대되는 수)를 가진다는 말입니다. 유사하게, 구문 ∀x∀y∀z(z+(y+z)=(x+y)+z)는 실수 덧셈에 대한 결합 법칙을 뜻합니다.

 예제2 중첩 정량자 표현을 해석하기

 ∀x∀y((x>0)∧(y<0)→(xy<0)), 두 변수의 정의역은 모든 실수입니다.

***이는 모든 실수 x, y에 대해, 만약 x>0이고 y<0이면, xy<0입니다 로 표현됩니다. 즉, 이는 모든 실수 x와 y에 대해, x가 양수고 y가 음수이면, 그 곱 xy는 음수입니다 를 뜻합니다. 간결하게 "양의 실수와 음의 실수 곱은 항상 음의 실수입니다."로 표현 가능합니다.

중첩 정량자를 루프로 생각하기

정량자로 한 개 이상의 변수에 대해 적용할 때, 중첩 루프문이라고 생각하는게 가끔 도움이 됩니다. (물론, 어떤 변수가 무한 크기의 정의역을 가진다면, 모든 값에 대해 루프할 수는 없습니다. 그럼에도, 이런 사고 방법은 중첩 정량자를 이해하는데 유용합니다.) 예로, ∀x∀yP(x,y)가 참인지 확인하려면, 모든 x값에 대해 루프를 하고, 각 x에 대해 모든 y값을 루프하는 것입니다. 만약 P(x,y)가 모든 x와 y에 대해 참이면, ∀x∀yP(x,y)는 참이라고 결론내립니다. 만약 그렇지 않다면 ∀x∀yP(x, y)는 거짓입니다. 

유사하게, ∀x∃yP(x, y)가 참인지 결론내리려면, 모든 x값에 대해 루프합니다. 각 x 값에대해 y값을 루프합니다. 루프는 어떤 y값이 P(x, y)에 대해 참인 것을 찾을 때 까지 루프합니다. 만약 어떤 x에 대해 P(x,y)를 참으로 만드는 y를 찾지 못 한다면 ∀x∃yP(x,y)는 거짓이됩니다. ∃x∀yP(x, y)가 참인지 확인하기 위해서는, x에 대해 루프를 수행합니다. 어떤 x에 대해 모든 y를 루프하여 P(x,y)가 참인 것을 찾기 전까지 수행합니다. P(x,y) 만약 그런 x를 찾지 못하면, ∃x∀yP(x,y)는 거짓입니다. 마지막으로 ∃x∃yP(x,y)가 참인지 확인하려면, x에 대해 루프를 합니다. 루프는 어떤 x에대해 y값을 루프합니다. 루프는 어떤 x와 어떤 y가 P(x,y)를 참으로 만드는 것을 찾을 때 까지 수행됩니다.

정량자의 순서

많은 수학 구문들은 복수 정량자를 포함합니다. 명제 함수들의 복수 정량자는 변수 한 개 이상을 포함하고있습니다. 정량자의 순서는 중요하게 살펴보아야합니다. 모든 정량자가 전체 정량자인 경우나 존재 정량자인 경우는 예외입니다. 

예제3 복수 전체 정량자와 배치 순서의 영향

P(x, y)는 "x+y = y+x"라 합시다. 정량자들의 진리값은 무엇입니까? ∀x∀yP(x,y)와 ∀y∀xP(x,y), 두 변수의 정의역은 모든 실수입니다. 

***정량자 ∀x∀yP(x,y)는 명제 "모든 실수 x, 모든 실수 y에 대하여 x+y = y+x 입니다."로 표현됩니다. P(x,y)는 모든 실수 x와 y에 대해 참이므로 (덧셈의 교환법칙, 실수에 대한 공리), 명제 ∀x∀yP(x,y)는 참입니다. 구문 ∀y∀xP(x,y)는 "모든 실수 y, 모든 실수 x에 대하여 x+y = y+x 입니다."로 표현됩니다. 즉, ∀x∀yP(x,y)와 ∀y∀xP(x,y)는 같은 뜻을 가지며 모두 참입니다. 시사하는 바는, 중첩 정량자에서 동일한 정량자의 사용은 의미에 변화 없이도 순서를 바꿀 수 있다는 점입니다. 즉, 한 타입의 여러 정량자 사용은 정량자의 배치 순서에 대해 영향을 받지 않습니다.

예제4 존재, 전체 정량자의 혼용과 배치 순서의 영향

Q(x,y)는 "x+y=0"라 합시다. 정량자 ∃y∀xQ(x,y)와 ∃x∀yQ(x,y)의 진리값은 무엇입니까? 두 변수의 정의역은 모든 실수입니다. 

***정량자 ∃y∀xQ(x,y)는 명제 "어느 실수 y에 대해 모든 실수 x가 Q(x, y) 입니다."로 표현됩니다. 어느 y값이 선택되든, x+y=0를 만족하는 x는 하나가 존재합니다. 특정 y에 대해 x+y=0을 만족하는 모든 실수 x는 존재하지 않기때문입니다. 따라서 ∃y∀xQ(x,y)는 거짓입니다.

정량자 ∀x∃yQ(x,y)는 명제 "모든 실수 x에 대해 어느 실수 y가 Q(x, y) 입니다."로 표현됩니다. 주어진 실수 어느 실수 x에 대해서도, x+y=0을 만족하는 실수 y가 존재합니다. 따라서 ∀x∃yQ(x,y)는 참입니다.

예제 4가 시사하는 바는 정량자 배치 순서에 따라 의미가 달라지는 것입니다. 구문 ∃y∀xQ(x,y)와 ∀x∃yQ(x,y)는 논리적 동치가 아닙니다. 구문 ∃y∀xQ(x,y)는 어느 y에 대하여 모든 실수 x가 Q(x, y)를 참으로 만들때 참입니다. 이 구문이 참이 되기위해서는 Q(x, y)에 특정 y값이 주어졌을 때 x의 값에 상관없이 모든 x에 대해 Q(x, y)가 참이면 됩니다. 반대로, ∀x∃yQ(x,y)는 모든 x에 대하여 어느 실수 y가 P(x, y)가 참으로 만들 때 참입니다. 이 구문이 참이 되려면, 어느 x의 값에 상관없이 Q(x, y)를 참으로 만드는 y값이 존재해야합니다. 후자인 경우, y는 x에 값에 의존적이며, 전자인 경우는 y는 x에 대해 독립적인 경우입니다.

전자 ∃y∀xQ(x,y)가 참인경우 ∀x∃yQ(x,y)는 참입니다. 그러나 ∀x∃yQ(x,y)가 참인경우, ∃y∀xQ(x,y)가 반드시 참이지는 않습니다.

예제 5 

Q(x, y, z)를 구문 "x+y=z"라 합시다. 구문 ∀x∀y∃zQ(x, y, z)와 ∃z∀x∀yQ(x, y, z)의 진리값은 무엇입니까? 세 변수의 정의역은 모든 실수입니다.

***x와 y가 값이 할당되었다고 가정합시다. 그러면, x+y=z를 만족하는 실수 z가 존재합니다. 따라서, 정량자 ∀x∀y∃zQ(x, y, z) 는 "모든 실수 x와 모든 실수 y에 대하여, x+y=z인 어떤 실수 z가 존재한다."는 참입니다. 정량자의 배치 순서는 여기서 중요합니다. 정량자 ∃z∀x∀yQ(x, y, z) "어느 실수 z에 대해 모든 실수 x와 모든 실수 y가 x+y=z를 만족한다"는 거짓입니다. 모든 실수 x와 모든 실수 y의 합이 어느 주어진 z값에 대하여 항상 만족하지는 않기 때문입니다.

수학 구문을 중첩 정량자 구문으로 표현하기

예제 6

구문 "양의 저우 합은 항상 양수이다."을 논리 표현식으로 변환하세요.

*** 논리표현식으로 변환하기 위하여, 암묵적인 정량자와 정의역을 정확히 해야합니다. "모든 두 정수에 대하여, 두 정수가 모두 양수일 때, 두 정수의 합은 양수이다" 그다음, 변수 x와 y를 추가하여 "모든 양의 정수 x와 y에 대하여, x+y는 양수이다" 로 표현합니다. 따라서, 다음과 같은 구문을 표현할 수 있습니다.

∀x∀y((x>0)∧(y>0)→(x+y>0)), 두 변수의 정의역은 모든 정수입니다. 정의역을 양의 정수로도 바꿀수 있습니다. 그렇다면 구문은 "두 양의 정수 합은 항상 양이다"에서 "두 양의 정수에 대하여, 이 두 정수의 합은 양이다"로 바뀝니다. 표현식은 ∀x∀y(x+y>0), 두 변수의 정의역은 양의 정수입니다.

예제 7

"0을 제외한 모든 실수는 역수가 존재한다"(역수는 곱했을 때 1이되는 수를 말합니다. xy=1이라면, 실수 y는 실수 x에 대하여 역수입니다.)

*** 다음과 같이 쓸 수 있습니다. "0을 제외한 모든 실수 x에 대하여, x는 역수를 가진다." 그런다음 다음과 같이 쓸수 있습니다. "모든 실수 x에 대하여, x≠0이면, xy=1을 만족하는 실수 y가 존재한다." 논리적 표현으로 써보면 다음과 같습니다. ∀x((x≠0)→∃y(xy=1))

예제 8

정량자를 사용하여 정의역에서 실수 변수 x가 a에서 실수 함수 f(x) 극한을 정의하라. 

*** 정의는 lim f(x) = L (x→a) 입니다. "모든 실수 ε >0에 대하여, 0<|f(x) - L|<δ이면 |f(x) - L|<ε인 실수 δ >0가 존재한다." 를 뜻합니다. 이 극한 정의는 다음 정량자와 같이 표현될 수 있습니다. 

∀ε ∃δ ∀x (0<|x-a|<δ→|f(x)-L|<ε), ε과 δ의 정의역은 양의 실수 이며, x의 정의역은 실수입니다.

따라서 다음과 같이 다시 표현할 수 있습니다.

∀ε>0 ∃δ>0 ∀x (0<|x-a|<δ→|f(x)-L|<ε)

중첩 정량자를 자연어로 바꾸기

중첩 정량자를 자연어로 바꾸는 것은 꽤 복잡할 수 있습니다. 우선, 정량자와 술어가 표현식에서 어떤 의미인지 알아 내야합니다. 그다음은, 의미를 좀 더 간단한 문장으로 표현하는 것입니다.

예제9 자연어로 바꾸기

∀x(C(x) ∨ ∃y(C(y) ∧ F(x,y)))를 자연어로 바꿔봅시다. C(x)는 "x 는 컴퓨터를 가지고 있다.", F(x, y)는 "x와 y는 친구이다.", 정의역은 x와 y는 학교 내의 모든 학생입니다.

*** 학교내 모든 학생 x에 대하여, x는 컴퓨터를 가지고 있거나 어떤 y가 x와 친구이고 컴퓨터를 가지고 있다는 것을 만족한다. 즉, 학교내 모든 학생은 컴퓨터를 가지고 있거나, 컴퓨터를 가진 친구가 있다.

예제 10 

∃x∀y∀z((F(x,y)∧F(x,z)∧(y≠z))→¬F(y,z)), 를 자연어로 바꾸세요. F(a,b)는 a와 b가 친구라는 뜻입니다. 세 변수의 정의역은 학교내의 모든 학생입니다.

*** 어떤 학생 x에 대하여, 모든 학생 y와 모든학생 z는, 만약 x와 y가 친구이고, x와 z가 친구이고 y와 z가 동일 인물이 아닌경우에는 y와 z는 친구가 아니다. 를 뜻합니다. 서로 둘이 친구인 학생과 어떤 애들과도 친구가 아닌 아이가 있다. 입니다.