Foundation : predicate logic and quantifiers

오랜만의 포스팅입니다. 이 포스팅을 완료하고 공개로 전환한것이 2월 7일이니까... 포스팅을 같이하면서 미적분책을 독학하는데 첫 장부터 무리수를 도출하는 방법인 바빌로니아 메서드와 무리수와 관련된 증명 문제, 그리구 포물선과 관련된 기하학 문제를 푸는데 그리고 여러가지 고민거리를 안고 지내다가 ( precalculus...고등학교 1학년문젠데 막히니까 고민거리가 생길수 밖에요) 새벽에 삘 받아서 완성하게 되었습니다. 크,,, 아무 금전적 보상도 없지만 열심히하는 클라쓰,,,

수학 원리에서... *이번 토막문은 본문 포스팅과 내용이 중복되고 길지만, 다 해치우고 싶은 저의 욕심입니다 ㅎ.....

propositional function 명제 함수

ϕx를 변수 x를 포함하는 진술이라고 하자. 이 명제는 x가 어떤 의미가 부여되면 명제가 된다. 이제부터 ϕx는 "명제 함수propositional function"라고 부른다. x가 아직은 애매하기 때문에, 아무런 주장이 될수가 없고 그러므로 명제는 아니다. 즉, "x가 아파한다."는 우리가 x가 누구인지 정하기 전에는 어떤 것을 주장 한다는 의미를 가지지 않는다. 그러나 x가 애매한 변수이기 때문에, "x가 아파한다."라는 것은 적절하지 않은 예일 수도 있다. "x가 아파한다."에서 x의 모든 결정 가능성에 따라 이미 참 또는 거짓 명제일 수도 있다는 것이다. (x란 변수가 워낙 상투적으로 많이 쓰이기 때문에 x가 아파한다가 이미 명제 로 오해 할 수도 있겠다는 우려인 것일까?) 또한 만약, "x가 아파한다." 와 "y가 아파한다." 는 같은 맥락에서 등장한다면- 여기서 y는 다른 변수- 그렇다면 x와 y의 결정에 따라, 아마도 같은 명제가 될 수도 있고 또는 아마도 다른 명제가 될 수 도 있을 것이다. 일단은 x와 y를 결정하는 어떤 상황보다는, 이 둘은 해당 문맥에서 모호하면서 서로 다른 것이다. (they retain in that context their ambiguous differentation.) 즉, "x는 아파한다."는 명제 함수의 애매한 "값"이라고 할 수 있다. 따라서 앞서 설명한 "x가 아파한다."라는 의미의 명제 함수를 쓸 때는 "x^가 아파한다."라고 쓰면 된다. (x 위에 모자를 씌운 것, x-hat.. x hat을 표현못하는 html의 한계다 ㅎ). 따라서 "x^가 아파한다."는 명제 함수이고, "x가 아파한다."는 그 함수의 애매한 특정 값이라는 것이다. //즉, 명제 함수에서 추천하는 틀은 x^이고 그 자리에 들어갈 것은 x 또는 y와 같은 일반 변수라는 것이다. 이는 bertrand russell, whitehead의 의견이다.// 같은 문맥에서 "x가 아파한다." 와 "y가 아파한다."는 구별 가능하나, "x^가 아파한다"와 "y^가 아파한다"는 질적으로 아무런 차이가 없는 것이다. //둘 다 명제 함수이기 때문에,,// 그리고 일반적으로, ϕx는 명제 함수 ϕx^의 모호한 값이고, 확실하게 정의된 기호 a가 x를 대체하면, ϕa는 명제 함수 ϕx^의 명확한 값이 된다. //기호 x가 확실하게 정의되어있다면 ϕx도 명제 함수 ϕx^의 명확한 값이 된다.//

명제 함수는 일반적으로 사용되는 함수들 "sin x", "log x", "x의 부모//(그래프..이론?)//"를 유도할 수 있는- 보다 더 기초적인 것이다. 이 유도되는 함수들은 좀 더 나중에 이야기 될 것인데, "descriptive functions"라고 부른다. 위에서 이야기한 명제들의 함수는 명제 함수의 많은 역할 중에 특정한 케이스들인 것이다. 

//그래서 결국엔 1.01의 기초적인 명제 부터 시작하여 삼각함수 까지 도출해내려는 버트런드 러셀이 logicism이라는 것인가... 대단하다.

the range of values and total variation 값과 총 변화량의 범위 

어떠한 명제 함수 ϕx에도, 값의 범위 또는 값의 모음들이란 것이 존재한다. ϕx의 x를 결정하는 모든 경우들을 고려하여 얻어질 수 있는 모든 명제들 (참이든 거짓이든)이 그 값(명제)의 범위이다. ϕx가 참이 되는 x의 값은 명제함수 ϕx^를 "만족한다. satisfy"라고 표현한다. 자 이제 다음에 제시되는 범위 3가지가 반드시 정리되어야 한다. 다음 3가지 명제중 반드시 적어도 한 명제는 참이어야한다. (1) 명제의 모든 범위가 참이다. "(x).ϕx" (2) 범위의 어떤 명제가 참이다. "(∃x).ϕx" (3)범위의 어떠한 명제들도 참이아니다. "~(x).ϕx" 

명제 (3)의 경우는 다음과 같이 표현할 수 있다. 명제 "~ϕx"는 "ϕx"의 반대를 뜻한다. 따라서 "~ϕx^"는 명제함수 "ϕx^"의 값이 반대인 또 다른 명제함수이다. 따라서 "(x).~ϕx"는 "ϕx^"의 모든 값이 거짓이라는 명제이다. 그러나 (1)과 (3)이 서로 반대라는 것은 완전히 잘못된 착각이다. 명제 (1)의 반대는 "~{(x).ϕx}"이다. 기호정의는 다음과 같다. 

~(x).ϕx .=. ~{(x).ϕx} Df

명제 (x).ϕx는 명제 함수 ϕx^의 "total variation 총 변화량"//전체 정량자// 이다. 챕터 2에서 설명해 줄 어떤 이유 때문에 (x).ϕx와 (∃x).ϕx을 사용할 때 그 부정형을 기초적인 아이디어(공리)로 취하거나 하지는 않을것이다. 그렇지만, (x).ϕx의 부정형을 다음과 같이 정의할 수는 있다. "ϕx는 항상 참이다." 그리고 "ϕx는 가끔씩 거짓이다."를 (∃x).~ϕx로 그리고 유사하게 (∃x).ϕx의 부정형을 (x).~ϕx로 정의할 수 있다. 따라서 다음과 같이 표현할 수 있다.

~{(x).ϕx} .=. (∃x).~ϕx Df,

~{(∃x).ϕx} .=. (x).~ϕx Df,

우리는 명제 함수와 명제 변수의 논리합disjunction을 다음과 같이 표현할 수 있다.

(x).ϕx.∨.p :=.(x).ϕx∨p Df,

예로 "ϕx가 항상 참이거나, p가 참이다."는 "'ϕx 또는 p'는 항상 참이다."와 같은 의미이다. 이 주제는 챕터 2에서, *9에서 다시 등장할 것 이다. 

.... (이전 포스팅에서 다루었던 기본적인 명제논리 들에 관한 내용... 생략)....

이제까지의 원리는 명제로부터 명제를 추론하는 데에 사용될 수 있다. 그러나 지금부터 작업에서 주장하려는 것들 중 대다수가 명제 함수propositional functions로 표현한 주장들이다. 설명을 하자면, 명제함수는 결정되지 않은 변수undetermined variable를 포함한다. 명제 함수로 표현한 주장은 명제로 표현하는 주장과는 기본적인 아이디어가 다르기 때문에, 우리는 1.1과 다른-비슷하지만, 다름- 기본적인 명제를 제시해서 명제 함수로 표현하는 주장 Q(x)를 두 명제함수 P(x)와 P(x)→Q(x)로 부터 추론할 수 있게 만들어야 한다. 이 기본적인 명제는 다음과 같다.

1.11 ϕx와  ϕx→ψx가 주장될 수 있다면, 그 때 ψx가 주장될 수 있다. 여기서 x는 실제 변수real variable이다.

단, 여기서 x는 ϕx가 의미가 있게 만드는 임의의 변수여야한다. 무작위의 어떤 변수가 할당되는 것이아니다. (예로 x>3, x=5. 이 명제 함수는 x=5일 때 참이다. 하지만 x>3, x=민수. 이는 어떠한 의미도 없다.) 

또한 ϕx→ψx에서도 똑같이 변수 x는 ϕx→ψx가 의미가 있게 만드는 임의의 변수여야한다. 그렇다고 해서 이 기초명제(공리)와는 별개로, ϕx에서 중요한 변수x가 ϕx→ψx에서 중요한 변수 x와 같은 변수라고는 미리 알 수는 없다. 

위 기초 명제 1.11은 한 명제 함수로부터 다른 명제 함수로 추론을 하는데 사용된다. 기초 명제가 우리의 작업에서 가장 처음 쓰이는 곳, 2.06을 미리 살펴보겠다. 

2.06 (p→q)→[(q→r)→(p→r)]

2.06가 어떻게 도출되었는지 살펴보기 위해 그 전 명제 2.05을 살펴보자.

2.05 (q→r)→[(p→q)→(p→r)]

2.05에서 어떻게 2.06을 도출할 수 있었을까? 이 것은 그 전 명제 2.04를 살펴보면 이해가 가능하다. 2.05에서 2.04를 이용해서 2.06을 도출하는 것은 자명하다. 2.04 명제는 다음과 같다.

2.04 [p→(q→r)]→[q→(p→r)]

2.04 구조에 2.05 명제를 대입한다. 2.04에서 p를 q→r, q를 p→q, r를 p→r로 대체한다. 그렇다면 다음과 같은 명제를 얻는다.

{(q→r)→[(p→q)→(p→r)]} → {(p→q)→[(q→r)→(p→r)]}

따라서, 우리는 기초 명제 1.11를 이용하여 2.04과 2.05로부터 2.06을 얻게 되었다.  

* 위는 명제 함수의 기본적인 아이디어입니다. 각 명제들은

*... 아 번호가 붙어져있는 추론하는 방법, 논리적 구조는 이해가 가능한데 기본적인 아이디어에 관한 문장이 너무 옛날 문장이라서 설명하는게 와닿지가 않을까봐 의역을 조금 보탰습니다.. 더 쉬운 설명이 아래에 또 있습니다.!

Foundation : predicate logic and quantifiers

우리는 앞서 명제 논리에 관해 학습했습니다. 명제만으로는 수학과 자연 언어에서의 모든 진술들의 의미를 적절하게 표현할 수 없습니다. 예로, 다음과 같은 진술을 알고 있다고 가정합시다. 

"교내 네트워크에 연결된 모든 컴퓨터들은 잘 작동하고 있다."

이때, 다음과 같은 진술의 진리값을 도출할 수 있는 명제논리 규칙은 없습니다.

"MATH3은 잘 작동하고 있다.", 여기서 수학3은 교내 네트워크에 연결된 컴퓨터들 중 하나.

반면에, 다음과 같은 진술들 또한 명제논리 규칙으로 진리값을 도출 할 수 없습니다.

"CS2는 침입자에게 공격받고 있다.", 여기서 CS2는 교내 네트워크에 연결된 컴퓨터들 중 하나.

"교내 컴퓨터들 중에 침입자로부터 공격받고 있는 컴퓨터가 있다."

(물론 -.ㅡ 우리는 이들의 진리값을 이미 알고 있죠. 그러나 순수히 이제까지 배워온 명제논리 규칙에 따라서 진리값을 판별할 수 없음 또한 인지하고 계셔야합니다.)

이번에는 강력한 논리 형식인 술어 논리predicate logic에 대해서 배울 것입니다. 술어 논리는 어떤 진술statement의 범위를 표현하기 위해서 사용된다는 것을 보게 될 겁니다. 그리고 어떤 두 종류class 간의 관계를 추론하고 표현하는데에 사용되는 것을 보게 될 겁니다. 거기서 정량자quantifier 개념이 나오게 됩니다. 우선은 술어 논리의 개념에 대해서 살펴볼 것 입니다. 그다음 정량자의 표기법에 대해서 배울 것입니다. (전혀 어려운 것이 아닙니다.)

술어Predicate

변수를 포함하는 다음과 같은 진술들 "x>3" "x=y+3" "x+y=z" "컴퓨터 x는 침입자에게 공격받고 있다." "컴퓨터 x는 잘 작동하고 있다." 은 주변에서 자주 볼 수 있습니다. 이런 진술들은 변수에 값이 지정되지 않는한 참이나 거짓으로 분류될 수 없습니다. 따라서 명제가 아닙니다.

진술 "x는 3보다 크다" 은 정확히 2부분으로 나눌 수 있습니다. 첫 부분은 변수 x로서 진술에서 관심있어하는 주제입니다. 두번째 부분은 "3보다 크다."라는 서술부predicate 입니다. "3보다 크다"라는 서술부를 명제함수propositional function P(x)로 표현할 수 있습니다. (술어는 그냥 명제함수라고 합니다.) 여기서 x는 변수입니다. 다음의 예제를 살펴봅시다.

예제 1

P(x)가 진술 "x>3"라 하자. P(4)와 P(2)의 진리값은 무엇인가?

*** 진술 P(4)의 진리값은 진술 "x>3"에 x=4를 할당한다. 따라서 P(4)는 진술 "4>3"과 같으며 참이다. 반면에 P(2)는 진술 "2>3"이며 거짓이다.

예제 2

Q(x, y)가 진술 "x=y+3"라 하자. 다음 명제들의 진리값은 무엇인가? Q(1,2), Q(3,0)

*** Q(1,2)는 진술 "x=y+3"에 x=1, y=2를 할당한다. 따라서 Q(1,2)는 진술 "1=2+3"과 같으며 거짓이다. 반면에 Q(3,0)은 진술 "3=0+3"이며 참이다.

예제 3

R(x, y, z)가 진술 "x+y=z"라고 하자. 다음 명제들의 진리값은 무엇인가? R(1,2,3), R(0,0,1)

*** R(1,2,3)는 진술 "x+y=z"에 x=1, y=2, z=3를 할당한다. 따라서 R(1,2,3)는 진술 "1+2=3"이며 참이다. 반면에 R(0,0,1)는 진술 "0+0=1"이며 거짓이다.

정량자Quantifier

명제함수의 변수들에게 값이 할당될 때, 진술은 특정 진리값을 가진 명제가 됩니다. 그러나, 명제함수로부터 명제를 만드는 또 다른 방법이 있습니다. 이를 보고 정량화quantification라고 합니다. 정량화는 서술부가 참인 원소들의 범위를 표현할 수 있습니다. 정량자의 기본적인 분류는 다음과 같습니다. 모든 원소들이 참임을 표현하는 전체universal 정량자와 하나 이상의 원소가 참임을 표현하는 존재existential 정량자가 있습니다. 술어와 정량자를 이용하는 논리 영역을 술어연사predicate calculus라고도 합니다.

전체 정량자universal quantifier

P(x)의 전체 정량자가 특정 정의역에서 참이라면, P(x)는 해당 정의역의 어떤 x에 대해서도 참이라는 것입니다. 정의역이 변경될 때 P(x)의 전체정량자의 의미가 바뀝니다. 이 때, 정의역이 항상 어딘지 서술되어야합니다. 이는 어떤 정량자를 사용하던 반드시 그래야합니다 ㅎㅎ..

정의 definition

P(x)의 전체정량universal quantification은 다음 진술과 같다. "정의역의 모든 x에 대해 P(x)이다."

∀xP(x)는 명제 함수 P(x)의 전체 정량입니다. 버트런드 러셀, 화이트헤드 공저 <수학원리>에서는 (x).ϕx^로 표현되었습니다. 정량quantification은 값과 변화량의 범위range of values and variation 이라고 표현했었습니다. 다시 돌아오면 여기서 ∀는 전체 정량자라고 부릅니다. "모든 x에 대한 P(x)"라고 읽습니다. P(x)를 거짓으로 만드는 임의의 원소 x를 ∀xP(x)의 반례counterexample 이라고 합니다.

전체 정량자에 관한 요약은 다음 표와 같습니다.

Statement	언제 참인가?	언제 거짓인가?
∀xP(x)	P(x)는 모든 x에 대해 참이다.	P(x)를 거짓으로 하는 x가 존재한다.
∃xP(x)	P(x)를 참으로 하는 x가 존재한다.	P(x)가 모든 x에 대해 거짓이다.

예제4

P(x)를 진술 "x+1 > x"라 하자. 진술 ∀xP(x)의 진리값은 무엇인가? 여기서 정의역은 모든 실수를 포함한다. 

*** 명제함수 P(x)는 모든 실수에 대해서 참이므로, ∀xP(x)는 참이다.

일반적으로, 정량자를 사용할 때 정의역이 비어있지 않다고 가정합니다. 그래도 만약에 정의역이 비어있다면, ∀xP(x)는 어떠한 명제함수 P(x)에 대해 항상 참입니다. 왜냐하면 P(x)를 거짓으로 만드는 어떠한 원소도 없기 때문입니다.

게다가 "모든" 이라는 전체 정량자는 다음과 같이 표현될 수 있습니다. "임의의", "어떠한". 그러나 어떠한 이라는 표현보다는 모든 이라는 것이 좀 더 명확하므로 사용하기를 추천합니다. 

진술 ∀xP(x)가 거짓이라면, 정의역에서의 x일 때 P(x)가 항상 참이 아니며 또 정의역에서의 x일 때 P(x)가 항상 참이 아니라면 진술 ∀xP(x)가 거짓입니다. (필요충분조건) P(x)가 항상 참이 아님을 보이는 방법은 진술 ∀xP(x)의 반례를 정의역 내에 있는 x를 찾으면 됩니다. 단 하나의 반례도 ∀xP(x)가 거짓임을 보이는데 충분한 것을 기억해둡시다.

예제5

Q(x)를 진술 "x<2"라 하자. 진술 ∀xP(x)의 진리값은 무엇인가? 여기서 정의역은 모든 실수를 포함한다.

*** 명제함수 Q(x)는 모든 실수에 대해서 참인 것은 아니다. 예로, Q(3)은 거짓이다. 즉, x=3은 ∀x(x<2)의 반례이다. 따라서, ∀x(x<2), where x is real number은 거짓이다.

예제6

P(x)를 진술 "x²>0"라 하자. 진술 ∀xP(x)가 거짓임을 보여라 여기서 정의역은 모든 정수이다.

*** x=0은 ∀x(x²>0)의 반례이다. 따라서, ∀x(x²>0), where is integer은 거짓이다.

정의역의 모든 원소들이 x1, x2, ..., xn 식으로 나열될 때, ∀xP(x)는 다음과 같은 논리곱으로 표현될 수 있습니다. 

P(x1)∧P(x2)∧P(x3)∧...∧P(xn), 이 논리곱식이 참인것은 각 P(x1), P(x2), P(x3)... P(xn)이 모두 참인 것과 동치이기 때문입니다.

예제7 

∀xP(x)의 진리값은 무엇인가? 여기서 P(x)는 진술 "x^2<10"라 하고 정의역은 4를 넘지않는 양의 정수를 포함한다.

*** 진술 ∀xP(x)는 명제들의 논리곱 P(1)∧P(2)∧P(3)∧P(4)와 같습니다. P(4)는, 진술 "4²<10"이므로, ∀xP(x)는 거짓입니다.

존재 정량자 existential quantifier 

명제함수 P(x)의 존재 정량은 다음과 같은 명제입니다. "P(x)를 만족하는 x가 정의역내에 존재한다."

∃xP(x)는 P(x)의 존재 정량을 표현하는데 쓰입니다. ∃는 존재 정량자라고 부릅니다. 진술 ∃xP(x)을 사용할 때 항상 정의역이 기술되어야 합니다. 그리고, "존재한다." 라는 표현은 다음과 같은 표현으로 대체될 수 있습니다. "어떤" "적어도 하나 이상". 위 테이블에서 존재 정량자의 요약을 볼 수 있습니다. 아래에 주어지는 예제는 존재 정량자의 사용법을 보여줍니다.

예제8 

P(x)를 진술 "x>3"라 하자. 정의역이 모든 실수를 포함할 때 진술 ∃xP(x)의 진리 값은 무엇인가?

*** "x>3"은 x=4일 때 만족한다. 따라서 ∃xP(x)는 참이다.

예제9

Q(x)를 진술 "x=x+1"라 하자. ∃xQ(x)의 진리값은 무엇인가? 여기서 정의역은 모든 실수를 포함한다.

*** Q(x)는 모든 실수에서 거짓이므로, Q(x)의 참일 수 있는 정의역에서의 원소의 존재 범위는 없다. 따라서 진술 ∃xQ(x)는 거짓이다.

 

일반적으로, 존재 정량자를 사용할 때 정의역은 비어있지 않다고 암묵적으로(말을하지않아도..) 그렇다고 가정합니다. 만약 정의역이 비어있을 경우, Q(x)가 어떤 명제 함수이건간에, ∃xQ(x)는 거짓입니다. 왜냐하면 정의역이 비어있기에 Q(x)를 참으로 만들 수 있는 원소가 정의역내에 존재할 수 없기 떄문이죠

그리고 정의역내에 원소가 다음과 같이 나열 될 경우 -x1, x2, xx3, ... xn- 진술 ∃xP(x)는 다음과 같은 논리 합으로 정확하게 똑같이 표현될 수 있습니다. 

P(x1)∨P(x2)∨P(x3)∨....∨P(xn)

논리합이 참이라는 것은 P(x1), P(x2) ... P(xn) 중 적어도 한개 이상이 참이라는 것과 동치이기 때문입니다.

예제10

∃xP(x)의 진리값은 무엇인가? 여기서 P(x)는 진술 "x²>10"이고 정의역은 4를 넘지 않는 양의 정수를 포함한다.

*** 정의역이 {1, 2, 3, 4} 이므로, 진술 ∃xP(x)는 다음과 같이 논리합으로 표현할 수 있다.

P(1)∨P(2)∨P(3)∨P(4)

P(4)는 진술 "4²>10"이고 참이기 때문에, 명제 ∃xP(x)는 참이다.

존재 정량자나 전체 정량자를 이용할 때 진술의 참 거짓을 판별하는데에 "반복과 탐색looping and searching"이라는 단순하면서 유용한 방법을 이용하면 쉬울 수 있다. 자, 정의역에서 n개의 원소가 존재한다고 해보자. ∀xP(x)가 참임을 확인 하기 위해서는, 우리는 n개의 원소를 명제 함수 P(x)에 넣어보고 생성되는 진술이 명제인지, 그리고 모두 참인지 확인해야한다. 순서대로 진행하다가 거짓인 것이 발견되면 그 때 진술 ∀xP(x)가 거짓인지 확인한 것이다. 그렇지 않다면 ∀xP(x)가 참인 것이다. ∃xP(x)가 참인지 확인하기 위해서는 정의역의 n개의 원소들에서 P(x)에 넣어보아 참인 것을 찾기만 하면 된다. 만약 그런 임의의 원소를 찾지 못한다면, 진술 ∃xP(x)가 거짓임을 알 수 있다. (그러나, 만약 정의역 원소가 무한대라면 이 방법은 유용하지 않다. 그래도 정량의 진리값을 생각해보는데 유용한 방법이긴 합니다.)

단일 정량자 uniqueness quantifier

정확하게 하나의 원소만이 참임을 주장하는 단일 정량자도 사용되곤 합니다. 표현은 다음과 같습니다. ∃!xP(x) 예는 다음과 같습니다. ∃!x(x-1=0), 여기서 x는 모든 실수. 그렇다면 x-1 = 0을 만족하는 실수는 x=1 단 하나 이기 때문에 참입니다. 다음과 같은 주장은 거짓입니다. ∃x(x<3), 여기서 x는 모든 양의 정수.

정량자의 표현 방법

이제까지 정량자에 관한 10가지의 예제를 살펴보았습니다. 여러가지 표기법이 정량자와 정의역을 표현하기 위해 사용됩니다. 다음과 같은 예제를 준비해보았습니다.

예제11

각 진술 ∀x<0(x²>0), ∀y≠0(y³≠0), ∃z>0(z²=2)의 의미를 해석하고 진리값을 제시하라. 여기서 각 정의역은 모든 실수를 포함한다.

*** ∀x<0(x²>0)는 다음과 동치입니다. "0보다 작은, 임의의 음의 실수를 제곱하면 0보다 크다." 이는 다음과 동치입니다. ∀x(x<0→x²>0). 따라서 참입니다.

∀y≠0(y³≠0)는 다음과 동치입니다. "0이 아닌, 임의의 실수를 세제곱하면 0보다 크다." 이는 다음과  동치입니다.∀y(y≠0→y³≠0). 따라서 참입니다.

∃z>0(z²=2)는 다음과 동치입니다. "0보다 큰, 임의의 실수 중에 제곱하면 2인 실수가 존재한다." 이는 다음과 동치입니다. ∃z(z>0∧z²=2). 따라서 참입니다.

왜 정량자가 다를 경우 두 명제를 연결하는 논리연산자가 다를까요? 한번 생각해봅시다. 조건문 →와 ∧의 차이를 기억하시나요?

p	q	p→q	p∧q
T	T	T	T
T	F	F	F
F	T	T	F
F	F	T	F

자, 위 명제 ∀x(x<0→x²>0)를 살펴봅시다. 분명한 것은 모든 음의 실수는 제곱하면 양의 실수로 됩니다. 그러나 이 명제가 참이되려면 모든 실수가 다음 명제 x<0→x²>0를 만족해야합니다. 이는 우리가 생각한 "0보다 작은, 임의의 음의 실수를 제곱하면 0보다 크다."와 정의역이 다르게 보입니다. 이렇게 생각해봅시다. 만약 x=>0이라면, 전 명제 x<0와 반대되므로 p≡F입니다. 위 테이블에서 확인할 수 있듯 조건문 p→q에서 p가 F의 진리값을 가진 경우 항상 참입니다. 따라서, 진술 ∀x(x<0→x²>0),(여기서 정의역은 모든 실수) 는 참입니다. 

다음 명제 ∃z(z>0∧z²=2)를 살펴봅시다. 분명한 것은 임의의 실수 중에 제곱하면 2인 실수가 존재 한다는 것은 사실입니다. (무리수 root 2). 그러나 다음과 같이 진술하면 문제가 생깁니다. ∃z(z>0→z²=2) 조건문인 경우 전 명제 z>0가 거짓인 경우 항상 참임을 기억합시다. 따라서 모든 실수 중에 z<=0인 실수가 반드시 존재하므로 ∃z(z>0→z²=2)는 항상 참이됩니다. 뒤 명제가 어떤것이여두요. 다음과 같은 명제도 참이됩니다. ∃z(z>0→z²=-2) (의도적이지 않게..) 따라서, 존재 정량자를 표현하기위해서는 논리곱 연산자가 필요합니다. ∃z(z>0∧z²=2) "z>0 이면서 z²=2을 만족하는 실수가 존재한다." 논리곱 연산자는 조건문보다 더 가혹하다 라고 이해해봅시다. (논리표에서 볼 수 있듯이)

자 그럼 다시 전체정량자로 돌아와봅시다. 왜 전체 정량자는 논리곱으로 표현할 수 없을까요? 다음 명제를 살펴봅시다. ∀y(y≠0→y³≠0) 이는 참일까요? 네 그렇습니다. y≠0인 임의의 실수는 그 세제곱으로 절대 0이 될 수 없습니다. (논리적으로 증명하는 방법은 언젠가 포스팅으로 다룰 예정입니다.) 그리고 정의역에서는 임의의 실수 y=0가 존재합니다. 따라서 모든 실수에 대하여 ∀y(y≠0→y³≠0)는 참입니다. 그러나 다음의 진술은 참일까요? ∀y(y≠0∧y³≠0) 이는 절대 참이 될 수 없습니다. 왜냐하면 모든 실수 중에는 y=0이 존재하기 때문이죠. 따라서 "0이 아닌 임의의 실수를 세제곱하면 0이 아니다" 라는 진술의 의도와는 다르게 작동하는 것을 확인할 수 있습니다. 왜냐하면 0 때문에요!

요약하자면 정량자의 명제 결합에서 연산자는 다음과 같이 사용될 수 있습니다.

∀x(P(x)→Q(x))    "모든 실수는 P(x)이면, Q(x)이다."

∃x(P(x)∧Q(x))     "P(x)이면, Q(x)를 만족하는 어떤 실수가 존재한다."

∀x(P(x)∧Q(x))    이 명제는 모든 실수가 P(x)를 만족하지 않을 수도 있으므로 의도와 다르게 사용된다. 

∃x(P(x)→Q(x))    이 명제는 어떤 실수가 P(x)를 만족하지 않을 수도 있으므로 의도와 다르게 사용된다. 

변수 바인딩 binding variables

정량자가 변수 x를 사용할 때, 변수가 "묶여있다" 라고 표현합니다. 보통은 영어로 "바운드 되어있다"라는 표현을 씁니다. i.e variable x is bound. 만약 변수가 묶여 있지 않은 경우 "자유롭다"라고 표현합니다. i.e variable x is free. 그러나 우리가 어떤 명제 함수를 생성하고 또 정량자와 함께 사용할 때 명제함수와 정량자에 사용되는 변수가 묶여있다거나 같아야 해당 진술이 명제로 사용될 수 있습니다. 

그리고 정량자가 사용되는 표현식을 이 정량자의 scope 범위 라고합니다. (프로그래밍 언어에서 변수의 scope은 중요한 개념입니다.) 따라서, 변수를 사용하느 수식이 정량자의 scope 바깥에 있을 때 변수가 자유롭다 라고 표현합니다. 다음의 예제를 살펴봅시다.

예제 12

진술 ∃x(x+y=1)에서 x는 존재정량자 ∃x에 바운드 되어있다. 하지만 변수 y는 정량자에 바운드 되어있지 않기 떄문에 자유롭다. 따라서 y에는 어떠한 값도 할당되지 않는다. 이는 y의 값이 별도로 설명되지 않는 이상 명제가 될 수 없다. 

진술 ∃x(P(x)∧Q(x))∨∀xR(x) 에서는 모든 변수가 바운드 되어있다. 존재정량자 ∃x의 범위는 다음 표현식 (P(x)∧Q(x)) 까지이다. 그리고 전체정량자 ∀x의 범위는 다음 표현식 R(x)이다. 이 표현식에서 각각의 정량자와 표현식이 바운드되어있기 때문에 만약 우리가 같은 정의역을 가지는 변수 x, y를 이용한다면 다음과 같은 똑같은 진술을 표현할 수 있음도 생각해보자. ∃x(P(x)∧Q(x))∨∀yR(y)

정량자를 포함하는 논리적 동치 Logical Equivalences Involving Quantifiers

명제함수와 정량자로 이루어진 진술이 논리적 동치라고 함은 진술에서 사용되는 명제함수가 대체되고 이 명제함수들의 변수의 정의역이 선언되었을때도 같은 진리값을 가진 경우와 동치입니다. 명제함수(술어논리)와 정량자를 포함하는 진술 S와 T가 동치인 경우 다음과 같이 표현합니다. S≡T

예제 13

다음의 진술 ∀x(P(x)∧Q(x))고 ∀xP(x)∧∀xQ(x)가 논리적 동치임을 보여라. 여기서 정의역은 같다. 이 논리적 동치는 논리곱에 전체 정량자를 분배법칙을 적용할 수 있다고 보여준다. 또, 존재정량자를 논리합에게 분배법칙을 적용할 수 있다. 그러나 전체 정량자를 논리합과 분배법칙을 사용할 수는 없다. 또 존재정량자를 논리곱과 분배법칙을 사용할 수는 없다. (후 문제에서 다뤄질 것입니다.) 

*** 위 두 진술이 논리적 동치임을 보이기 위해서, 진리값이 항상 같음을 보여야합니다. 명제함수 P, Q와 정의역이 무엇인지는 상관없습니다. 특정한 명제함수 P와 Q와 일반적인 정의역을 가정해봅시다. ∀x(P(x)∧Q(x))와 ∀xP(x)∧∀xQ(x)와 논리적 동치임을 보이기 위해서 두 가지를 수행해야합니다. 먼저, ∀x(P(x)∧Q(x))와 참이면, ∀xP(x)∧∀xQ(x)가 참임을 보여야합니다. 

우선, ∀x(P(x)∧Q(x))가 참이라고 가정합시다. 이는 정의역에 임의의 a가 있다면 P(a)∧Q(a)가 참입니다. 따라서, P(a)가 참이고 Q(a)가 참입니다. 정의역의 모든 원소에서 P(x)가 참이고 Q(x)가 참이기 때문에, 따라서 ∀xP(x)와 ∀xQ(x) 가 참입니다. 따라서 진술 ∀xP(x)∧∀xQ(x) 또한 참입니다.

그리고, ∀xP(x)∧∀xQ(x)가 참이라고 가정합시다. 그러면 ∀xP(x)가 참이고 ∀xQ(x)가 참입니다. 따라서, 정의역 내에 a가 있다면, P(a)가 참이고 Q(a)가 참입니다. 따라서, 정의역내에 모든 원소 x에 대해 P(x)∧Q(x)가 참입니다. 따라서 ∀x(P(x)∧Q(x))가 참입니다. 다음과 같이 결론을 내릴 수 있습니다.

∀x(P(x)∧Q(x))≡∀xP(x)∧∀xQ(x)

정량자 표현식의 부정형 Negating Quantified Expressions

정량자의 부정형은 자주 사용됩니다. 다음의 진술을 고려해봅시다.

"여기 강의를 듣는 모든 학생들은 이미 미적분을 수강했다." 이 진술은 다음과 같이 정량자를 이용하여 표현할 수 있습니다. 

∀xP(x), 여기서 P(x)는 "x는 이미 미적분을 수강했다."이고 정의역은 여기 강의를 듣는 학생들입니다. 이 진술의 부정은, "여기 강의를 듣는 모든 학생들이 이미 미적분을 수강했다는 것은 사실이 아니다." 입니다. 단 한 명이라도 미적분을 듣지 않아도 여기 강의를 듣는 모든 학생들은 이미 미적분을 수강했다를 부정한 것이니까요. 자 그렇다면, 존재 정량자를 이용하여 다음과 같이 표현할 수 있습니다.

∃x¬P(x)

따라서 다음 표현식은 논리적 동치입니다.

¬∀xP(x)≡∃x¬P(x)

"여기 강의를 듣는 모든 학생들이 이미 미적분을 수강했다는 것은 사실이 아니다." 는

"여기 강의를 듣고 있는 학생들 중에 이미 미적분을 수강하지 않은 학생이 존재한다." 와 동치입니다.

예제를 떠나 정의역과 명제 함수에 상관없이 ¬∀xP(x)와 ∃x¬P(x)가 논리적 동치임을 보이기 위해서는, 먼저 ¬∀xP(x)가 참이면 ∀xP(x)가 거짓인것과 동치입니다. 이는, 정의역 내의 임의의 원소가 ¬P(x)를 만족하면 참입니다. 결과적으로, 정의역 내의 임의의 원소 x가 ¬P(x)를 만족하면 ∃x¬P(x)또한 참입니다. 따라서 다음 진술 ¬∀xP(x)와 ∃x¬P(x)는 동치입니다.

존재정량자의 부정을 고려해봅시다. 예로 명제 "여기 강의를 듣고 있는 학생들 중에 이미 미적분을 수강한 학생이 존재한다."의 부정은 "여기 강의를 듣고 있는 학생들 중에 이미 미적분을 수강한 학생이 존재한다는 것은 거짓이다."입니다. 이는 "여기 강의를 듣고 있는 모든 학생들은 미적분을 수강한 적이 없다." 와 같습니다. 그러므로 전체정량자를 이용하여 다음과 같이 표현할 수 있습니다.

∀x¬P(x)

따라서 다음 표현식은 논리적 동치입니다.

¬∃xP(x)≡∀x¬P(x)

정의역과 명제함수에 상관없이 ¬∃xP(x)와 ∀x¬P(x)가 동치임을 보이기 위해 다음을 먼저 확인하여야 합니다. ¬∃xP(x)가 참인 것은 ∃xP(x)가 거짓임과 동치입니다. 이는 정의역 내에 어떠한 원소도 P(x)를 만족하지 않음과 동치입니다. 정의역 내에 어떠한 원소도 P(x)를 만족하지 않음은 정의역 내의 모든 원소가 ¬P(x)를 만족해야합니다. 따라서 ¬∃xP(x)가 참인 것은 ∀x¬P(x)가 참임과 동치입니다. 따라서 ¬∃xP(x)는 ∀x¬P(x)와 논리적으로 동치입니다.

정량자를 부정하는 규칙은 "정량자에 대한 드 모르간의 법칙 De Morgan's laws for quantifiers"로 설명할 수 있습니다. 임의의 명제함수와 정의역에 구별되는 n개의 원소가 있을 때 ¬∀xP(x)는 다음과 같습니다. ¬(P(x1)∧P(x2)∧...∧P(xn)). 이는 드 모르간의 법칙에 의해 ¬P(x1)∨¬P(x2)∨¬P(x3)∨...∨¬P(xn)와 동치입니다. 이는 진술 ∃x¬P(x)와 동치입니다.

유사하게 ¬∃xP(x)는 다음과 같습니다. ¬(P(x1)∨P(x2)∨...∨P(xn)). 이는 드 모르간의 법칙에 의해 ¬P(x1)∧¬P(x2)∧¬P(x3)∧...∧¬P(xn)와 동치입니다. 이는 진술 ∀x¬P(x)와 동치입니다. 

아래 표는 정량자의 드 모르간 법칙입니다.

부정형	동치인 진술	부정형이 언제 참인가?	언제 거짓인가?
¬∀xP(x)	∃x¬P(x)	P(x)를 만족하지않는 x가 존재할 경우	모든 x에 대해 P(x)가 참인경우
¬∃xP(x)	∀x¬P(x)	모든 x에 대해 P(x)가 거짓인 경우	P(x)를 만족하는 x가 존재할 경우

예제14

다음 명제의 부정형을 쓰시오. "솔직한 정치인은 존재한다." "모든 미국인들은 치즈버거를 먹는다."

*** H(x)를 진술 "x는 솔직하다."라고 하자. 그렇다면 진술 "솔직한 정치인은 존재한다."는 다음과 같이 표현할 수 있다. ∃xH(x), 여기서 정의역은 모든 정치인들이다. 이 진술의 부정형은 다음과 같다. ¬∃xH(x). 이는 "솔직한 정치인은 존재하지 않는다.", "모든 정치인들은 솔직하지 못 하다."라고 할 수 있다.

S(x)를 진술 "x는 치즈버거를 먹는다."라고 하자. 그렇다면 진술 "모든 미국인들은 치즈버거를 먹는다."는 다음과 같이 표현할 수 있다. ∀xS(x). 이 진술의 부정형은 다음과 같다. ¬∀xS(x). 이는 "모든 미국인들은 치즈버거를 먹는다는 것은 사실이 아니다.", 그리고 동치인 진술 ∃x¬S(x), "치즈버거를 먹지 않는 어느 미국인이 존재한다." 라고 할 수 있다.

예제15

다음의 진술 ∀x(x²>x)과 ∃x(x²=2)의 부정형은 무엇인가? 여기서 정의역은 모든 실수이다.

*** 진술 ∀x(x²>x)의 부정형은 ¬∀x(x²>x)이다. 따라서 "모든 실수가 자신의 제곱이 자신보다 크다는 것은 사실이 아니다."이다. 이는 다음 진술과 동치이다. ∃x¬(x²>x). ∃x(x²<=x). 이는 참이다. (0<x<1)

진술 ∃x(x²=2)의 부정형은 ¬∃x(x²=2)이다. 따라서 "자신의 제곱을 해서 2인 실수는 존재하지 않는다." 이다. 이는 다음 진술과 동치이다. ∀x¬(x²=2). ∀x(x²≠2). 이는 거짓이다. 반례 x=root 2

예제16

다음 두 명제가 논리적 동치임을 보이시오. ¬∀x(P(x)→Q(x)), ∃x(P(x)∧¬Q(x))

*** 드 모르간의 법칙에 의해 ¬∀x(P(x)→Q(x))와 ∃x(¬(P(x)→Q(x)))가 동치임을 알 수 있다. ¬(P(x)→Q(x))는 ¬(¬P(x)∨Q(x))), P(x)∧¬Q(x)와 동치이다. 명제함수가 동치이므로 해당 진술에서 명제함수를 대체할 수 있다. 따라서 다음 진술 ¬∀x(P(x)→Q(x))는 ∃x(P(x)∧¬Q(x))와 동치이다.

논리 표현식을 언어로, 언어를 논리 표현식으로

이제까지 논리 표현식에 대해 많이 배웠습니다. "논쟁이 없는 절대적인" 주제였지만, 우리가 앞으로 다뤄야할 많은 주제와 내용들은 논리적이며 - 논리 표현식으로 충분히 표현할 수 있습니다. 앞으로 독자분들이 마주하게 될 제 블로그 포스팅, 더욱 더 진지하게 다가가서 접하게 되실 수학, 프로그래밍, 인공 지능 등 많은 분야에서 언어 또는 생각을 논리 표현식으로 바꾸게 될 것입니다. 그런 언어나 생각을 논리표현식으로 바꾸는데에 명제변수뿐만 아니라 명제함수와 정량자를 필요로 할 땐 더 복잡해집니다. 그리고 특정 문장을 변환하는데 여러 방법이 있을 수도 있습니다. 이제부터 예제에서는 영어를 논리표현식으로, 논리표현식을 영어로 바꾸는 것을 다룰 것입니다. 이 작업의 목표는 간단하고 유용한 논리표현식을 만드는데에 있습니다. 다음의 예제를 살펴봅시다.

예제17

다음 진술을 명제 함수와 정량자를 이용하여 표현하시오. "이 수업의 모든 학생들은 이미 미적분을 수강했다."

*** 먼저, 명제함수 C(x)를 "x는 미적분을 수강했다."라고 하자. 그렇다면 정량자를 이용하여 표현하면 다음과 같다. ∀xC(x), 여기서 정의역은 이 수업을 듣고 있는 모든 학생을 포함한다.

다음과 같은 표현도 가능합니다. 명제함수 S(x)를 "x는 이 수업을 수강하고 있다.", C(x)를 "x는 이미 미적분을 수강하였다."라 합시다. 그렇다면 다음과 같은 진술로 표현할 수 있습니다. ∀x(S(x)→C(x)),여기서 x는 모든 학생들. 

∀x(S(x)∧C(x)),여기서 x는 모든학생들. 는 모든 학생들이 이 수업을 수강하고 있으며 미적분을 수강하였다 이므로 우리의 의도와 다릅니다. 

예제18

다음 진술들을 정량자와 명제함수를 이용하여 표현해보자. "이 강의를 수강하는 몇 몇 학생들은 멕시코에 다녀와본적이 있다." "이 강의의 모든 학생들은 캐나다 또는 멕시코에 다녀와본적이 있다."

*** M(x)를 "x는 멕시코를 다녀온적이 있다." 그렇다면 다음과 같은 진술로 표현할 수 있다. ∃xM(x), 여기서 x는 이 강의를 수강하는 모든 학생들을 의미한다. 또는 C(x)를 "x는 이 강의를 수강하고 있다."라 하자. 그렇다면 다음과 같이 표현할 수 있다. ∃x(C(x)∧M(x)), 여기서 x는 모든 학생들이다. 

진술 ∃x(C(x)→M(x))는 이 강의를 수강하지 않는 학생이 존재하기만 해도 참이므로 우리의 의도와 다름을 알 수 있습니다. (조건문에서는 전제가 거짓이여도 항상 참입니다. F→T, F→F)

 C(x)를 진술 "x는 캐나다를 다녀온적이 있다."라 하자. 다음과 같이 표현할 수 있다. ∀x(C(x)∨M(x)), 여기서 x는 이 강의를 수강하는 모든 학생들이다. 

또는 S(x)를 "x는 이 강의를 수강하고 있다."라 하자. 다음과 같이 표현할 수 있다. ∀x(S(x)→(C(x)∨M(x)), 여기서 x는 모든 학생들이다. 

Lewis Carroll (이상한 나라의 앨리스 저자)의 저서 Symbolic Logic에서는 정량자를 이용한 추론 예제가 많이 등장합니다. 다음 예제는 그의 저서 Symbolic Logic에서 등장하는 것들입니다. 이 예제들은 정량자들이 어떻게 다양한 형식의 진술들을 표현하는데 쓰이는지 방법을 보여줍니다.

예제19

다음 진술들을 살펴보자. 앞의 두 진술은 전제premise이며 세번째 진술은 결론conclusion이다. 이 세 진술들을 논증argument이라고 한다. 

"모든 사자들은 사납다."

"어떤 사자들은 커피를 마시지 않는다."

"어떤 사나운 생물체들은 커피를 마시지 않는다."

*** P(x) "x는 사자이다." Q(x) "x는 사납다." R(x) "x는 커피를 마신다."라 하자. 각 진술은 다음과 같다.

1) ∀x(P(x)→Q(x))

2) ∃x(P(x)∧¬R(x))

3) ∃x(Q(x)∧¬R(x))

예제20

다음의 진술들이 있다고 하자. 첫 세 진술은 전제이고 네 번째 진술은 결론이다.

"모든 벌새는 색이 화려하다."

"몸집이 큰 새는 꿀을 먹고 살지 않는다."

"꿀을 먹고 살지 않는 새는 색이 단조롭다."

"벌새는 몸집이 작다."

*** P(x) "x는 벌새이다." Q(x) "x는 색이 화려하다." R(x) "x는 몸집이 크다." S(x) "x는 꿀을 먹는다" 라고 하자. 

1) ∀x(P(x)→Q(x))

2) ∀x(R(x)→¬S(x))

3) ∀x(¬S(x)→¬Q(x))

4) ∀x(P(x)→¬R(x))

다음 포스팅에서는 핸드북을 살펴보겠습니다 !