논리적 사고를 기르는 알고리즘 수업(2025.01.17) - codeport/scala GitHub Wiki

논리적 사고를 기르는 알고리즘 수업

Ch 14.5 문제 6 ~ 10

체크인 (기분/근황/기대하는 바)

성큼이
- 좀 피곤하다
- 특별한 일 없다
- 문제 잘 풀었으면
상호
- 조금 피곤
- 관리 일이 조금 늘어나 더 피곤해짐
- 한 문제 이상 풀기
Wayne
- 살짝 피곤
- 특별한 것 없다
- 새로운 것 잘 배우고 갔으면

문제풀이

14.5

하나의 점 규칙 (14.5), 중첩 규칙 (14.2), 그리고 재배열 규칙 (14.3)으로부터 (14.8)을 유도하라.

힌트: 유도는 $f$가 전단사 함수라는 사실을 이용해야 한다. 즉, 모든 $j \in J$와 $k \in K$에 대해,

$f(j) = k \equiv j = g(k)$

를 만족하는 함수 $g$가 있다는 것이다. 하나의 점 규칙을 이용해, 두 번째 더미 변수를 만들어 보아라. 그러면 위 성질을 사용할 수 있게 될 것이다.

[(14.5) 하나의 점] $[\braket{\sum k : k = e: T} = T[k := e]]$

[(14.2) 중첩] $[\braket{\sum j, js : R \land S : T} = \braket{ \sum j : R : \braket{ \sum js : S : T}}]$

[(14.3) 재배열] $[\braket{\sum j, k : R : T} = \braket{\sum k, j: R : T}]$

[(14.8) 변형]

모든 $j \in J$와 $k \in K$에 대해,

$f(j) = k \equiv j = g(k)$

를 만족하는 함수 $g$가 있을 때, $[\braket{\sum k \in K : R : T} = \braket{\sum j \in J : R[k := f(j)] : T [k := f(j)]}]$

$\braket{\sum j \in J : R[k := f(j)] : T [k := f(j)]}$

= { (14.5) 에서 $e$ 대신 $f(j)$ }

$\braket{\sum j \in J : R[k := f(j)] : \braket{\sum k \in K : k = f(j) : T}}$

= { (14.2) 중첩에서 $js$ 대신 $k$, $S$ 대신 $k = f(j)$ }

$\braket{\sum j \in J, k \in K : R \land (k = f(j)) : T}$

= { (14.3) 재배열, 그리고 f가 전단사 함수}

$\braket{\sum k \in K, j \in J : R \land (j = g(k)) : T}$

= { (14.2) 중첩에서 $j$ 대신 $k$, $js$ 대신 $j$, $S$ 대신 $j =g(k)$ }

$\braket{\sum k \in K: R : \braket{\sum j \in J: j = g(k) : T}}$

= { (14.5) 하나의 점에서 $k$ 대신 $j$, $e$ 대신 $g(k)$}

$\braket{\sum k \in K: R : T[j := g(k)]}$

= { T 는 애초에 k에 대해 표현되는 식이었으므로 $[j:=g(k)]$생략가능 }

$\braket{\sum k \in K: R : T}$

다음과 같이 일반화된 분배 법칙을 증명하라.

$\braket{\sum j : P : S} \times \braket{\sum k : Q : T} = \braket{\sum j, k: P \land Q: S \times T}$

이 규칙을 적용할 때의 부가 조건은 무엇인가?

[(14.12) 분배법칙] $[\braket{\sum k: R : c \times T} = c \times \braket{\sum k : R : T}]$

를 이용한다.

$\braket{\sum j : P : S} \times \braket{\sum k : Q : T}$

= { (14.12) 분배법칙에서 $R$ 대신 $Q$, $c$ 대신 $\braket{\sum j : P : S}$ }

$\braket{\sum k: Q: \braket{\sum j: P: S} \times T}$

= { (14.12) 분배법칙에서 $k$ 대신 $j$, $R$ 대신 $P$, $T$ 대신 $S$, $c$ 대신 $T$ }

$\braket{\sum k: Q: \braket{\sum j: P: S \times T}}$

= { (14.2) 중첩에서 $k$ 대신 $j$, $js$ 대신 $j$, $R$ 대신 $Q$, $S$ 대신 $P$ }

$\braket{\sum k, j : Q \land P : S \times T}$

= { (14.3) 재배열, 논리곱의 대칭성 }

$\braket{\sum j, k: P \land Q: S \times T}$

여기서 $P, S$는 $k$에 대해 독립이어야 하고, $Q, T$는 $j$에 대해 독립이어야 한다.

다음 규칙 $\braket{\bigoplus k:P:T} = \braket{\bigoplus k: P \land Q: T} \oplus \braket{\bigoplus k: P \land \neg Q: T}$ 을 유도하라. 이 규칙을 이용해 $\oplus$가 멱등일 때에, (14.40)으로부터 (14.41)을 도출하라.

$\braket{\bigoplus k: P \land Q: T} \oplus \braket{\bigoplus k: P \land \neg Q: T}$

= { (14.40) 분리 }

$\braket{\bigoplus k: (P \land Q) \lor (P \land \neg Q): T} \oplus \braket{\bigoplus k: (P \land Q) \land (P \land \neg Q): T}$

= { $Q \lor \neg Q = true$, $Q \land \neg Q = false$ }

$\braket{\bigoplus k: P: T} \oplus \braket{\bigoplus k: false: T}$

= { (14.38) 빈 구간 }

$\braket{\bigoplus k: P: T} \oplus 1_{\oplus}$

= { 항등원 생략가능 }

$\braket{\bigoplus k: P: T}$

$\oplus$가 멱등이면 $P \lor Q \supset P \land Q$ 이므로 $\braket{\bigoplus k: P \lor Q: T} \oplus \braket{\bigoplus k: P \land Q: T} = \braket{\bigoplus k: P \lor Q: T}$

합에 대한 변형 규칙 (14.8)에서, $f$가 전단사 함수라는 조건이 있었다. 이 규칙은 합계뿐 아니라 다른 모든 한정 기호에 대해 적용할 수 있었다.

한정 기호가 멱등일 때, 이 규칙을 간략하게 할 수 있다. 멱등 한정 기호에 대한 변형 규칙은 다음과 같다. 함수 $f$가 더미 $j$의 자료형에서 더미 $k$의 자료형으로 가는 함수라고 하자. $f$가

$\braket{\forall k :: \braket{ \exists j :: k = f(j)}}$

를 만족하면, 다음이 성립한다.

$\braket{\bigoplus k:R:T} = \braket{\bigoplus j: R[k:=f(j)]:T[k:=f(j)]}$

위 규칙을 증명하라.

$\braket{\bigoplus j: R[k:=f(j)]:T[k:=f(j)]}$

= { (14.39) 하나의 점 }

$\braket{\bigoplus j: R[k:=f(j)]:\braket{\bigoplus k: k=f(j): T]}}$

= { (14.36) 중첩 }

$\braket{\bigoplus j, k: R \land (k = f(j)): T]}$

= { (14.37) 재배열, $f$는 전단사 }

$\braket{\bigoplus k, j: R \land (j = g(k)): T]}$

= { (14.36) 중첩 }

$\braket{\bigoplus k: R:\braket{\bigoplus j: j = g(k): T]}}$

= { (14.39) 하나의 점}

$\braket{\bigoplus k: R:T}$

아래 표는 결합법칙과 교환법칙을 만족하는 이진 연산자와 단위원을 함께 보여준다. 각각에 대해서, 본문에 명시되어 있지 않은 분배법칙 (14.46)의 예시를 대어라

연산자 단위원 한정기호

$\land$ 참 $\forall$

$\lor$ 거짓 $\exists$

$+$ $0$ $\sum$

$\times$ $1$ $\prod$

$\downarrow$ $\infty$ $\Downarrow$

$\uparrow$ $-\infty$ $\Uparrow$

$\equiv$ 참 $\equiv$

$\not\equiv$ 거짓 $\not\equiv$

$\cup$ $\emptyset$ $\bigcup$

$\cap$ $\mathcal{U}$ $\bigcap$

연산자	단위원	한정기호
$\land$	참	$\forall$
$\lor$	거짓	$\exists$
$+$	$0$	$\sum$
$\times$	$1$	$\prod$
$\downarrow$	$\infty$	$\Downarrow$
$\uparrow$	$-\infty$	$\Uparrow$
$\equiv$	참	$\equiv$
$\not\equiv$	거짓	$\not\equiv$
$\cup$	$\emptyset$	$\bigcup$
$\cap$	$\mathcal{U}$	$\bigcap$

$\downarrow, \uparrow$ 의 경우

$f(x) = - x$를 생각하면 $f(\infty) = -\infty$이고 $f(x \downarrow y) = -x \uparrow -y$이다. 따라서

$-\braket{\Downarrow k: R: T} = \braket{\Uparrow k: R: -T}$

$\equiv, \not\equiv$의 경우

$f(x) = \neg x$를 생각하면 $f(참) = 거짓$이고 $f(x \equiv y) = \neg x \not\equiv \neg y$ 이므로,

$\neg\braket{\equiv k: R: T} = \braket{\not\equiv k: R: \neg T}$

$\cup, \cap$의 경우

$f(x) = \neg x$를 생각하면 $f(\emptyset) = \mathcal{U}$이고 $f(x \cup y) = \neg(x \cup y) = \neg x \cap \neg y$ 이므로,

$\neg\braket{\bigcup k: R: T} = \braket{\bigcap k: R: \neg T}$

회고 (좋았던 점/ 아쉬웠던 점/ 다음주 이 시간까지 할 일)