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

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

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

Ch 13 문제 4 모순 ~ 6

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

• 성큼이
  • 졸리다
  • 잠이 좀 부족하다
  • 문제 잘 풀어봤으면
• 상호
  • 좋다
  • 여전히 건강하게 살고 있음
  • 한 문제라도 꼭 풀어봤으면
• Wayne
  • 무난
  • 바쁘게 지내는 중
  • 문제 잘 풀고 갔으면

문제풀이

• [모순] $p \land \neg p \equiv false$

$p \land \neg p$

= { (13.5) }

$p \land (p \equiv false)$

= { 전건 긍정 }

$p \land false$

= { $false$는 논리곱의 영원 }

$false$

• [분배법칙] $p \land (q \equiv r \equiv s) \equiv p \land q \equiv p \land r \equiv p \land s$

우선 $p \land (q \equiv r) \equiv p \land q \equiv p \land r$ 을 먼저 증명한다

$p \land (q \equiv r)$

= { 황금률 }

$p \equiv (q \equiv r) \equiv p \lor (q \equiv r)$

= { (13.9) 분배법칙 }

$p \equiv q \equiv r \equiv p \lor q \equiv p \lor r$

= { 항 재배치 }

$p \equiv q \equiv p \lor q \equiv p \equiv r \equiv p \lor r$

= { 황금률 }

$p \land q \equiv p \land r$

$\therefore p \land (q \equiv r) \equiv p \land q \equiv p \land r$

$p \land (q \equiv r \equiv s)$

= { 위 보조정리에 $r$ 대신 $r \equiv s$ 적용}

$p \land q \equiv p \land (r \equiv s)$

= { 위 보조정리에 $q$ 대신 $r$, $r$ 대신 $s$ 적용}

$p \land q \equiv p \land r \equiv p \land s$

5. 십진법으로 적힌 수가 짝수인지 아닌지 판별하는 방법은 매우 간단하다. 단순하게 마지막 숫자가 짝수인지 확인하면 된다. 예를 들어 2437은 홀수이다. 마지막 숫자인 7이 홀수기 때문이다. 이 산술법칙을 수식화하고 증명하라. (힌트: $2437 = 243 \times 10 + 7$. 5.3.1절에서 논의한 분배법칙이 필요할 것이다. 또한, 두 수의 곱이 짝수인지 판별하는 방법을 수식화하고 증명해야 한다.)

$((10 \times m + n)이 짝수)$

= $(10 \times m)이 짝수 \equiv (n이 짝수)$

= $((2 \times (5 \times m))이 짝수) \equiv (n이 짝수)$

= $true \equiv (n이 짝수)$

= $(n이 짝수)$

6. 불리언은 단위원이 참, 영원이 거짓, 곱셈이 $\land$, 덧셈이 $\not\equiv$인 반환 $(Bool, true, false, \land, \not\equiv)$을 이룸을 증명하라. 이는 잘 알려진 성질로, 일부 저자는 논리곱 대신 (곱셈처럼 보이는) $\bullet$ 을, 부등호 대신에 (덧셈처럼 보이는) $\oplus$를 사용한다. 비슷한 내용의 정리 13.11은 이보다 훨씬 덜 알려져 있다. 사실 이 두 정리는 참과 거짓의 역할을 서로 바꿩 얻은 쌍대 관계의 정리들이다. 비동치와 논리곱의 조합은 종종 데이터 암호화에 사용된다. 쌍대 관계를 통해, 여기서의 동치와 논리합을 대신 사용할 수 있음을 알 수 있다.

$(Bool, true, false, \land, \not\equiv)$ 이 반환(semiring)이려면 다음 조건을 만족해야 한다

1. $(Bool, true, \land)$ 은 모노이드다.
2. $(Bool, false, \not\equiv)$은 대칭적인 모노이드다.
3. $false$는 $\land$의 영원이다.
4. $\land$는 $\not\equiv$에 대하여 분배 가능하다.

각각을 확인해보면,

1. $true$는 논리곱의 단위원이고, 논리곱은 결합법칙을 만족하므로 모노이드가 맞다.
2. $false$는 부등호의 단위원이고, 부등호는 대칭적고 결합법칙을 만족하므로 대칭적인 모노이드가 맞다.
3. $false$는 논리곱의 영원이 맞다.
4. $p \land (q \not\equiv r)$

= { 부등호의 정의 }

$p \land \neg(q \equiv r)$

= { (13.5) 부정 }

$p \land ((q \equiv r) \equiv false)$

= { 논리곱의 분배법칙 }

$p \land q \equiv p \land r \equiv p \land false$

= { $false$는 논리곱의 영원 }

$p \land q \equiv p \land r \equiv false$

= { (13.5) 부정 }

$\neg(p \land q \equiv p \land r)$

= { 부등호의 정의 }

$p \land q \not\equiv p \land r$

따라서 $\land$는 $\not\equiv$에 대하여 분배 가능하다.

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

• 성큼이
  • 열심히 문제를 풀어봤다. 감이 돌아오는 느낌
  • 특별히 없다
  • 함축 쪽 복습
• 상호
  • 대략 이해할 수 있었다
  • 없다
  • 문제를 좀 예습해오겠다
• Wayne
  • 진도 좀 나갔다
  • 어디에 쓰이는지 잘 모르겠다
  • 잘 쉬고 오겠다

나머지 공부