[CS 1-2 | 이산수학] 중첩 한정기호 3주차

대학수업을 기록하는 목적

내가 블로그에 대학수업을 기록하는 목적은

강의 때 학습한 개념을 나만의 언어로 표현하고, 나만의 관점으로 해석하는 연습을 하기 위함이다.

그래서, 앞으로 블로그를 꾸준히 할 것이고

모든 강의록을 정리하는 건 어려울 지라도 최대한 많은 강의를 나만의 언어로 블로그에 기록할 것이다.

"뇌는 마치 근육과 같아서 꾸준히 사용하게 되면 발전하고 성장한다. - 마지막 몰입 저서 중"

---

중첩 한정기호의 이해 - 중첩 반복문에 대한 고찰

∀x∀y P(x,y) 처럼 사용되었을 때

중첩 반복문을 통해 이해하면 다음과 같다.

 

여기서 주의할 점은 아래 코드는 이해를 돕기위한 예시 코드로써,
실제로 사용하는 건 아니다!

for(x = 0; x < 999999; x ++) {
   for (y = 0; y < 999999; y++) {
   if (P(x,y) != Ture) {
      return 0;
   }
   else {
   
   }
   
   }
}

return 1;

 

∀x∃y P(x, y) 처럼 사용되었을 때

중첩 반복문을 통해 이해하면 다음과 같다.

for(x = 0; x <= 999999; x++){
	for(y = 0; y <= 999999; y ++){
    	if(P(x,y) != Ture){
    
    	}
    	else{
    		return 1;
    	}
    }
    
}
return 0;

여기서 고려할 점은 return 0은 거짓을 의미하고, return 1은 참을 의미한다.

 

"위와 같이 중첩반복문 실행논리를 이용해 ∃x∀y P(x,y) 그리고 ∃x∃y P(x,y)를 이해하면 된다!"

1-1 때 논리학에서도 위를 배웠지만, 제대로 이해되지는 않았다.
하지만, 이산수학의 은재형 교수님이 가르쳐주시는
중첩반복문으로 연관지어 논리식에 대해 이해하니, 논리학에서 이해되지 않았던 것을 쉽게 이해할 수 있었다.

그러니깐, 은재형 교수님께서 가르쳐주신, 개념을 기존에 알고 있던 것과 연관지어 개념을 구조적으로 이해하면
쉽게 개념을 이해하고 학습할 수 있다는 사실을 깨달았다.

---

한정기호의 순서에 따른 차이

• ∀x∀y P(x,y) 와 ∀y∀x P(x,y) 는 같은 진리 값을 갖는다.
• 반면에, ∀x∃y Q(x, y) 와 ∃y∀x P(x, y) 는 다른 진리 값을 갖는다.
  Q(x,y) 가 "x + y = 0"을 나타낸다고 가정하고 정의역이 실수라 생각해보자.
  모든 x에 대하여 x = -y를 참으로 만드는 y 즉, -y 값이 존재하므로 참이다
  반면, 어떤 하나의 y에 대하여 모든 x가 y = -x를 참으로 만들 수 없으므로 거짓이다
  
  

위와 같이 하나의 사례를 들고, 이해를 하면 추상적인 개념일지라도
쉽고 빠르게 개념을 이해하고 학습할 수 있다.

 

예제를 통해 "한정기호의 순서에 따른" 진리 값 차이를 살펴보자!

• 예제 )) 정의역은 실수이고, P(x, y) : x * y = 0 이라 할 때, 아래 문장의 진리 값을 판단하라.

1. ∀x∀y P(x,y)

2. ∀x∃y P(x,y)

3. ∃x∀y P(x,y)

4. ∃x∃y P(x,y)

 

1. ∀x∀y P(x,y) 에 대한 해석

모든 x에 대해서 x가 증가할 때마다 각 x에 대해서 y를 아무리 바꿔도 P(x,y)가 거짓이다.

(x = 0, y = 0일 때 제외하고는)

 

결국, 모든 x, y에 대해 진리 값이 참을 만족시키지 않았기에
1. ∀x∀y P(x,y) 의 진리 값은 거짓이다.

 

 

2. ∀x∃y P(x,y) 에 대한 해석

모든 x에 대하여 x를 증가시킬 때마다 다음식 (P(x,y) : x * y = 0)을 참으로 만드는 y가 하나이상 존재한다.

(모든 x에 대해서, y가 0일 때 x * y = 0을 만족한다.)

 

결국, 모든 x에 대해 y = 0일 때 진리 값이 참이 존재하므로
2. ∀x∃y P(x,y) 의 진리 값은 참이다.

 

 

3. ∃x∀y P(x,y) 에 대한 해석

x = 0일 때 y의 값을 아무리 바꾸더라도 P(x,y) : x * y = 0 을 참으로 만든다.

 

결국, 어떤 x에 대해 모든 y의 진리 값이 참이므로
3. ∃x∀y P(x,y) 의 진리 값은 참이다.

 

 

4. ∃x∃y P(x,y) 에 대한 해석

x = 0 일 때 또는 y = 0 일 때 다음식 (P(x,y) : x * y = 0)을 참으로 만든다.

 

결국, 어떤 x에 대해 어떤 y의 진리 값이 참이므로
4. ∃x∃y P(x,y) 의 진리 값은 참이다.

 

---

중첩한정 기호의 참/거짓에 따른 의미 변화

해당 내용은 위에서 설명한대로 똑같이 이해하면되니,
이 부분에 대해선 상세 내용설명은 생략하도록 하겠다. 

 

 

아래는 강의를 들으며 필기한 아이패드 필기본이다.

 

필기본을 보다시피, 논리문장은 순해를 통한 해석을 기본적인 규칙을 지니고 있다.

 

이산수학은 컴퓨터 내부의 연산을 탐구하기 위해 고안된 과목으로써

논리식 자체가 컴퓨터 내부 연산구조를 탐구하기 위해 설계된 사실임을 이해하면 

순해 해석의 배경을 알 수 있다.

 

그렇기에, 우리는 논리식 그 자체를 순해를 기본적인 것임을 받아드리고,

활용하면 되는 것이다.

 

"이렇게 설계된 논리식은 어렵더라도, 많이 사용하다보면 익숙해지고 이에 기반한 사고로
창의적인 설계 및 고안을 할 수 있다.
왜냐, 이미 논리식 기반으로 뛰어난 프로그램들을 설계해내고 있기 때문이다~"

---

중첩 한정기호를 문장으로 변환하기

• 논리식을 (자연어) 문장으로 변환하는 행위다.
  
  
• 논리식의 특성인 순해를 이용해서 (자연어) 문장으로 변환하면 된다.
  
  
  
• 예제를 통해 자연어 (문장)으로 변환해보자!
  
  

• 예제 1. )) ∀x (C(x) ∨∃y (C(y) ∧ F (x, y))) 을 (자연어) 문장으로 변환하라
  단, C(x)는 "x가 컴퓨터를 가지고 있다" 이고, F(x, y)는 "x와 y는 친구이다"이고, x와 y의 정의역은 교내에 있는
  모든 학생이라 하자

∀x (C(x) ∨∃y (C(y) ∧ F (x, y)))  {∀x 전개} -> ∀x C(x) ∨ ∀x∃y (C(y) ∧ F(x, y))

∀x C(x)∨∀x∃y (C(y)∧ F(x, y)) == 교내에 있는 모든 학생은 컴퓨터를 가지고 있거나, 컴퓨터를 가진 친구가 있다.

 

 

• 예제 2. )) ∃x∀y∀z((F(x, y) ∧ F(x, z) ∧(y != z)) -> ¬F(y, z)) 을 문장으로 변환하라
  단, F(x,y)는 예제 1. 과 동일하다.

어떤 학생 x는 y와 친구이고, x는 z와 친구이고, y와 z는 다르다. -> y와 z와 친구가 아니다.

 

어떤 학생 x는 y와 친구이고, x는 z와 친구이고, y와 z는 다르다. == 어떤 학생 x는 "서로 다른" y, z라는 친구가 있다.

어떤 학생 x는 "서로 다른" y, z라는 친구가 있다. -> y와 z와 친구가 아니다.

어떤 학생 x는 "서로 다른" y, z라는 친구가 있다면 y와 z와 친구가 아니다.

결론, 어떤 학생은 "서로 다른" 두 친구가 있다면 두 친구가 서로 친구가 아니다.

 

해당 예제에서는 한정기호를 전개하지 않았던 건, 모든 한정기호가 동일한 범위로 구속하고 있기 때문이다!
(한정기호는 변수를 구속해 구속변수로 만들어 명제로써 활용한다.)

 

---

(자연어) 문장 표현을 논리표현으로 변환하기

• (자연어) 문장을 논리표현으로 변환하는 행위다.
  
  
• (자연어) 문장을 순해로 해석하며, 논리 표현으로 변환하면 된다.
  
  
  
• 예제를 통해 논리표현으로 변환해보자!

 

• 예제 1. )) "두 양수를 더한 결과는 항상 양수이다." 를 논리표현으로 변환하라

방법 1. - 정의역 정수로 한정

위의 (자연어) 문장을 한정기호와 정의역이 명확해지도록 다음과 같이 변환할 수 있다.

"모든 두 정수에 대하여, 만일 두 정수가 모두 양수라면, 그 둘의 합은 양수이다."

변수 x와 y를 추가하고, 정의역을 "모든 정수"라고 정의하면 다음과 같이 표현할 수 있다.

"모든 양수와 x와 y에 대하여 x + y는 양수이다."

결론, 정의역이 "모든 정수" 이기에

논리 표현으로 다음과 같이 표현한다.

∀x∀y((x > 0) ∧ (y > 0)) -> (x + y > 0)

 

방법 2. - 정의역 양의 정수로 한정

위의 (자연어) 문장을 한정기호와 정의역이 명확해지도록 다음과 같이 변환할 수 있다.

"모든 양의 정수에 대하여, 그 둘의 합은 양수이다."

 

변수 x와 y를 추가하고, 정의역을 "양의 정수"라고 정의하면 다음과 같이 표현할 수 있다.

"x+y는 양수이다."

 

결론, 정의역이 "양의 정수" 이기에

논리 표현으로 다음과 같이 표현한다.

∀x∀y (x + y > 0)   (∀x > 0 ,∀y > 0)

 

따라서, 정의역을 어떠한 범위로 한정시키느냐에 따라 동일한 (자연어) 문장임에도 논리 표현은 약간식 다르다.
"논리 표현은 공식이 없지만, 동일한 의미라는 것을 이해하기"

 

 

• 예제 2. )) "모든 항공사에서 비행기를 타본 여성이 존재한다."를 논리표현으로 변환하라
  w의 정의역은 "모든 여성"
  f의 정의역은 "모든 비행기"
  a의 정의역은 "모든 항공사"
  P(w, f)는 "w가 f를 탔다", Q(f, a)는 "f는 a의 비행기이다"라고 하자.

예제 문장은 "모든 항공사에서" "비행기를 타본" "여성이 존재한다." 으로 한정사의 범위를 나눠서 해석할 수 있다.
이때, 한정사의 범위는 띄어쓰기로 한정사의 범위가 나눠짐을 알 수 있다.

 

그렇기에, 분석된 (자연어) 문장을 논리표현으로 바꾸면,

"모든 항공사에서" == ∀a

"비행기" == ∃f

"타본 여성이 존재한다." == ∃w

 

모든 항공사에서 비행기를 타본 여성이 존재한다 == 어떠한 여성이 비행기를 탔고, 그 비행기는 모든 항공사의 비행기이다.

결론, ∃w∀a∃f (P(w, f) ∧ Q(f, a))

 

---

중첩한정기호의 부정

• 중첩한정기호의 부정은 부정기호인 "¬" 을 전개해보면 쉽게 해석할 수 있다.
  ¬ 을 먼저 해석함으로써 문장전체의 의미를 이해가 가능하다. (해석 전략인 셈이다)
  
  
• ¬ 을 전개할 때는 드모르간 법칙을 통해서 전개하면 된다.
  
  
• 드모르간 법칙은 논리표현 정리를 통해 증명된 사례이고, 받아드려서 활용하면 된다.
  아래는 드모르간의 법칙 이용사례 사진이다.
  참고하길 바란다.

중첩한정기호에서의 드모르간 사용사례