[이산수학] 전칭예시화 일반화, 존재예시화 일반화

전칭예시화

∀xP(x)가 주어졌을 때, ∀xP(x)가 true라면 domain에 속하는 임의의 값 c에 대하여 p(c) 가 true임을 보이는데 활용된다. 

 

전칭일반화

∀xP(x)가 주어졌을 때, domain에 속하는 모든 값 c에 대하여 p(c)가 true이면 ∀xP(x)가 true임을 보일 때 사용하는 추룐 규칙이다.

 

존재예시화

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

 

존재일반화

∃xP(x)가 주어졌을 때, 특정값 c에 대하여 p(c)가 true이면 ∃xP(x)가 true라는 추론규칙이다. 

 

예시

다음 가정이 "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."

-가정  ∀x(D(X) -> C(x)), D(Maria)

-결론 C(Maria)

-추론과

 

 

증명

수학적 체계 : 공리, 정의, 미정의 용어로 구성됩니다.

 

여기서 공리는 수학적 체계에서 증명 없이 참으로 받아들여지는 명제이고 수학에서는 공리들이 여러가제 예제들이 있습니다. 유클리드 기하학에서의 공리 두가지 등이 있습니다.

 

미정의 용어  

수학적 체계의 시작 기점으로 인식되는 단어들을 미정의 용어라고 합니다. 

 

ex) 서로 다른 두 개의 점이 주어졌을 때, 두 점을 잇는 선은 정확히 한 개 존재한다.

 

여기서 점과 선은 정의하지 않아도 아는 미정의 용어라고 합니다. 

 

정의

정의는 새로운 개념을 만들기 위해서 미정의 용어와 기존의 받아진 용어들로 구성된 것을 정의라고 합니다. 만약 대응하는 변과 대응하는 각이 같도록 꼭지점들을 짝짓게 할 수 있다면, 두개의 삼각형은 합동이다. 측정값의 합이 180도이면 두 각은 서로 보각이다.

 

여기서 서로 보각이라는 정의를 보여주고 있습니다. 

 

정리

P이면 Q이라의 전제입니다. 논리적인 명제로 참이라고 보는 것입니다. 참인 것으로 증명해야하는 명제가 바로 정리가 됩니다. 참인 것으로 보이는 방법은 기존에 알려져있는 공리, definition 가설이 참이다라는 것을 보고 결론 q가 참이다라는 것을 보이면 됩니다. 

 

보조정리

더 큰 정리를 보기 위한 작은 정리입니다. 자신이 참이라는 것 자체는 큰 관심사가 아니지만, 다른 정리를 증명하는데 유용하게 사용되는 정리입니다.

 

따름정리

어떤 정리의 결과도 자연스럽게 참인 것으로 정리될 수 있는 정리입니다. 예를들어 삼각형의 두 변이 같다. 마주보는 변도 같다. 그렇다면 

 

가설

증명되지는 않았지만 참으로 밀어지는 정의입니다.

 

증명

정리가 참임을 확립하는 논법입니다. proof의 분석 수단으로서 logic(논리)를 이용합니다. 

 

직접증명

p -> q

p이면 q이다. 가정인 p로부터 결론 q를 하면서 직접증명이라고 합니다. p가 true라고 가정하고 공리 , 여러규칙, 기존에 true라고 증명된 정리들을 사용하여 q가 true라고 증명하는 것입니다. 

---

정수 n은 짝수다. n = 2k 만족하는 정수가 존재한다 그럼 짝수입니다. 정수 n이 홀수다 라는 것은 n = 2k+1을 만족하는 정수가 존재한다 그러면 홀수가 됩니다. 

---

n = -21은 결국 2 * (-11) + 1의 형태입니다.  따라서 2k + 1의 형태로 되기 때문에 홀수입니다. 

 

직접증명

가정으로부터 결론을 바로 참이다라는 것 을 꺼내는 것입니다.

m은 홀수면 m = 2k+1을 만족하는 정수가 존재합니다. 또한 n이 홀수면 n  = 2k가 존재합니다. 

m + n = 2k+1 형태로 나타낼 수 있으므로 m+n은 홀수입니다. 

'

반례

∀xP(x)

이거에 대한 거짓임을 하나만 존재하면 됩니다. 

여기서 2^n은 양의 정수에 속하는데 모든 양의정수 2^n+1은 소수인지 증명해야 합니다. 이것이 성립하지 않는 것을 하나 보이면 증명은 끝납니다. 

 

n= 3 일 때 값은 9가 나오기에 9는 소수가 아닙니다. 따라서 소수가 아닌 원소가 하나 이상 존재하기 때문에 거짓이 됩니다.