이산수학 벼락치기 (작성중)

논리와 명제

명제는 참과 거짓을 명확하게 구분할 수 있는 문장이다.

 

'명확하게 구분할 수 있다'는 의미는 주관적인 기준이 아니라 명확한 기준을 갖는다는 의미이고, '구분할 수 있는 문장'이라는 의미는 오직 평서문만 명제가 될 수 있다는 것을 의미한다. 명제는 논리의 기본 구성 요소이다. 참과 거짓을 진릿값이라 하고, 명제는 진리값을 갖는다. 가능한 모든 경우를 나열한 것을 진리표라고 한다. 

논리 연산

논리 연산자

하나 이상의 단순명제가 연산에 의해 합쳐지면 합성명제가 된다. 합성명제의 진릿값은 구성하고 있는 단순명제들에 의해 정해진다. 합성명제를 구성하는 논리 연산자에는 논리합, 논리곱, 부정, 배타적 논리합, 함축이 있다.

 

• 논리합 ($\lor$, or)
  • '또는'의 의미
  • 두 명제 중 하나 이상이 참이면 논리합이 참이다
• 논리곱 ($\land$, and)
  • '그리고'의 의미
  • 두 명제가 모두 참이면 논리곱이 참이다
• 부정 ($\lnot$, not)
  • '아니다'의 의미
  • 명제가 참이면 부정은 거짓, 거짓이면 부정은 참이다
• 배타적 논리합 ($\oplus$, xor)
  • 두 명제 중 하나만 참이면 배타적 논리합이 참이다
  • 둘 다 참이면 거짓, 둘 다 거짓이면 참. '두 명제의 논리값이 다르면 참이다'라고 생각할 수도 있다
  • 이는 $\mathbb{Z}/2\mathbb{Z}$ 위에서의 덧셈과 같다.

위 연산들의 진리표를 나열하면 다음과 같다.

$p$	$q$	$p \lor q$	$p \land q$	$p \oplus q$
T	T	T	T	F
T	F	T	F	T
F	T	T	F	T
F	F	F	F	F

 

 

추가 1) 어떤 명제가 조건-결론 관계로 이루어질 수도 있다. 이런 관계를 함축 또는 조건명제라고 한다. 명제의 함축관계는 추론규칙에서 유용하게 사용된다. 

• 함축 ($\implies$)
  • 'p이면 q이다'라는 의미. p는 조건(충분조건), q는 결론(필요조건)이 된다
  • p가 참이면 q는 참이여야 함축이 참이다. 그런데 p가 거짓이면, q의 논리값에 상관없이 함축이 참이다
• 동치 ($\iff$)
  • iff(If and only IF): 필요충분조건
  • 두 명제의 진리값이 같다는 것을 의미한다

함축의 진리표는 다음과 같다.

$p$	$q$	$p \implies q$	$p \iff q$
T	T	T	T
T	F	F	F
F	T	T	F
F	F	T	T

 

 

추가 1) $\not p \lor q$의 진리표와 $p \implies q$의 진리표를 비교하면 다음과 같다.

$p$	$q$	$p \implies q$	$\not p \lor q$
T	T	T	T
T	F	F	F
F	T	T	T
F	F	T	T

 

동치의 정의에 의해, 두 명제가 같은 진리표를 갖는다면 두 명제는 동치이다. 따라서 $p \implies q \iff \not p \lor q$가 된다. 명제의 함축을 논리 연산자를 이용해 표현할 수 있다는 성질은(함축법칙) 귀류법을 이용한 증명이나 추론 규칙에서 유용하게 사용된다. 자세한 내용은 후술한다. 

 

추가 2) 기본 논리 연산자(논리합, 논리곱, 논리부정, 배타적 논리합)들은 논리 게이트를 만든다. 이때 논리부정과 다른 연산자를 조합해 특수한 게이트를 만들기도 한다. xor 게이트의 출력에 not 게이트를 연결하면 xnor 게이트를 만드는 식이다. 자세한 내용은 후술한다. 

 

논리적 동치법칙

논리연산자들을 조합하면 동치인 명제들을 찾을 수 있다. 정리된 규칙들을 논리적 동치법칙이라고 하고, 논리적 동치법칙들을 이용해 명제를 정리하고 간소화할 수 있다. 이 동치법칙들은 진리표를 이용해 증명 가능하고, 어떤 법칙들을 이용해 다른 법칙을 유도할 수 있기도 하다. 

 

• 멱등법칙
  • $p \land p \equiv p$
  • $p \lor p \equiv p$
• 지배법칙
  • $p \lor T \equiv T$
  • $p \land F \equiv F$
• 항등법칙
  • $p \land T \equiv p$
  • $p \lor F \equiv p$
  • 지배법칙의 반대이다
• 부정법칙
  • $\lnot F \equiv T$, $\lnot T \equiv F$
  • $p \lor \lnot p \equiv T$
  • $p \land \lnot p \equiv F$
• 이중부정법칙
  • $\lnot (\lnot p) \equiv p$
• 교환법칙
  • $p \lor q \lor r \equiv r \lor q \lor p$
  • $p \land q \land r \ equiv r \land q \land p$
• 결합법칙
  
  • $p \lor q \lor r \equiv (p \lor q) \lor r$
  • $p \land q \land r \equiv (p \land q) \land r$
• 분배법칙
  • $p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$
  • $p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$
• 드모르간의 법칙
  • $\lnot (p \lor q) \equiv \lnot p \land \lnot q$
  • $\lnot (p \land q) \equiv \lnot p \lor \lnot q$
• 흡수법칙
  • $p \lor (p \land q) \equiv p$
  • $p \land (p \lor q) \equiv p$
• 함축법칙
  • $p \implies q \equiv \lnot p \lor q$
• 대우법칙
  • $p \implies q \equiv \lnot q \implies \lnot p$
• 귀류법칙
  • $p \implies q \equiv (p \land \lnot q) \implies F$

추가 1) 위 규칙들을 보면 후술할 집합의 연산법칙들과 유사하다는 것을 알 수 있다. 집합의 정의 '공통된 조건을 만족하는 원소들의 모임'에서 조건을 명제함수라고 생각하면 성질이 같다는 것을 생각해볼 수 있다.

 

추가 2) 논리적 동치법칙에서 양변이 동치($\equiv$)라는 것은, 양변을 대치할 수 있다는 것을 의미한다. 예를 들어, $\lnot p \land \lnot q \land p$를 교환법칙, 결합법칙에 의해 $(\not p \land p) \land q$, 부정법칙에 의해 $F \land q$, 다시 부정법칙에 의해 모순명제라는 것을 알 수 있다. 

 

술어 논리

명제함수

 

한정기호

 

추론

추론 규칙

 

 

 

---

증명법

명제의 증명 방법에는 직접증명법, 간접증명법, 수학적 귀납법이 있다.

 

수학적 귀납법

귀납추론은 개개의 사실을 모두 관찰하여 일반화하는 방법이다. 수학적 귀납법은 주로 자연수에 대해 증명할 때 사용되는데, 하나의 개별 사실이 참임을 보이고 그것을 일반화하는 방법으로 증명한다.

 

구체적인 증명 방법은 다음과 같다.

1. $P(1)$은 참임을 보인다
2. $P(k)$가 참이라고 가정하고, $P(k+1)$이 참이 됨을 보인다

$P(k)$가 참일 때 $P(k + 1)$이 참이라면, $P(1)$이 참이므로 $P(2)$가 참이다. 마찬가지로 $P(2)$가 참이므로 $P(3)$도 참이 된다. 따라서 1부터 시작해, 모든 자연수에 대해 이 명제가 참임을 증명할 수 있다.

 

예시를 들어 증명해보자.

$n >= 5$ 인 모든 자연수 n에 대해, $2 ^ n > n ^ 2$

1. $n = 5$일 때, $32 > 25$이므로 명제는 참이다.
2. $n = k$일 때 명제가 참이라고 가정하고, $n = k + 1$일 때를 살펴보면
   • $2 ^ (k + 1) = 2 ^ k * 2 = (k * 2) * 2$
   • $(k + 1) ^ 2 = k ^ 2 + 2 * k + 1$
   • $n >= 5$일 때 $k ^ 2 > 2 * k + 1$이므로 $n = k + 1$일때 명제가 성립한다

따라서 $n >= 5$인 모든 자연수 n에 대해 $2 ^ n > n ^ 2$이다.

 

직접증명법

연역추론은 알고 있는 규칙으로부터 다른 규칙을 유도하는 방식이다. 연역적인 증명 방법 중 명제를 변형하지 않고 증명하는 방식을 직접증명법, 그 외의 경우를 간접증명법이라 한다. 

 

직접증명법은 이미 참이라고 알고 있는 정리들과 공리들을 이용해 명제를 증명한다. "직각삼각형의 빗변의 길이의 제곱은 나머지 두 변의 길이 제곱의 합과 같다"라는 피타고라스의 정리는 이미 증명된 정리이고, "삼각형은 세 변과 각을 가지고 있다"는 별도의 증명 없이 참이라고 여기는 공리이다. 

 

예시를 들어 증명해 보자.

두 홀수의 곱은 홀수

• 어떤 홀수 $p$는 정수 $k$에 대해 $2k + 1$로 정의된다. (공리)
• 두 홀수 $p$, $q$를 각각 $2m + 1$, $2n + 1$이라 하자
• $p * q = (2m + 1) * (2n + 1) = 4mn + 2m + 2n + 1 = 2(2mn + m + n) + 1$
• 이때 $2mn + m + n$은 정수이므로, 다시 $2k + 1$형태로 나타낼 수 있다. 따라서 두 홀수의 곱은 홀수이다. 

 

간접증명법

간접증명법은 함축명제 $p \implies q$를 증명하려고 할 때, 이 명제를 변형해 증명하는 방법이다.

대우증명법

명제 $p \implies q$는 대우명제 $\neg q \implies \neg p$와 동치이다. 대우명제를 증명할 수 있다면 본 명제도 참임을 증명할 수 있다. 

 

예시를 들어 증명해 보자. 

정수 $n$에 대해, $3n + 2$가 짝수이면 $n$이 짝수

• 위 명제의 대우명제는 "$n$이 홀수이면 $3n + 2$가 홀수$"이다. 
• $n = 2k + 1$ (k는 정수)에 대해, $3n + 2 = 6k + 5 = 2(3k + 2) + 1$
• 이때 정수 k에 대해 $3k + 2$는 다시 정수이므로, $3n + 2$는 홀수이다
• 대우명제 $\neg q \implies \neg p$가 참이므로, 명제 $p \implies q$도 참이다

모순증명법(귀류법)

귀류법은 논리적 동치법칙을 이용한다. 명제 $p \implies q$는 $ \neg p \lor q$와 같고(함축법칙), 이는 $\neg (p \land \neg q)$와 같다(드모르간의 법칙). 이때 $\neg (p \land \neg q)$를 부정한 $p \land \neg q$가 거짓임을 보인다면 $\neg (p \land \neg q)$은 참이므로 본 명제가 참이 된다. 

 

예시 1.

$\sqrt {2}$는 무리수

• 명제의 부정은 "$\sqrt {2}$는 유리수"가 된다
• 유리수는 서로소인 정수 p, q에 대해 $\frac{p}{q}$ 형태로 나타낼 수 있다 (공리)
• $\sqrt{2} = \frac{p}{q}$의 양변을 제곱하고 정리하면 $2q^2 = p^2$
• 이때 좌변이 짝수이므로, 우변도 짝수이다 (공리)
• 짝수의 제곱은 짝수, 홀수의 제곱은 홀수이므로 (증명 가능한 정리) p는 짝수이다
• 정수 k에 대해 p를 $2k$ 형태로 나타내고 정리하면 $q^2 = 2k^2$
• 위의 과정을 반복해 q도 짝수이다
• 그런데 p, q 모두 짝수이면 약수로 2를 가지는데, 이는 서로소라는 가정에 모순이다
• 따라서 명제의 부정이 거짓이므로, 명제는 참이다

예시 2.

정수 n이 3의 배수이면 $n^3$도 3의 배수

• 함축명제 형태로 나타내면 "p: 정수 n이 3의 배수, q: $n^3$이 3의 배수, $p \implies q$"
• 이 명제의 부정은 $p \land \neg q$, 즉 "n이 3의 배수이면서 $n ^ 3$이 3의 배수가 아니다"가 된다
• 부정을 참이라고 가정하고 증명하면,
• $n$은 3의 배수이므로 정수 k에 대해 $3k$형태로 나타낼 수 있고, 이때 $n ^ 3 = 27k^3 = 3(9k^3)$
• $9k^3$은 정수이므로 $n^3$을 $3p$형태로 나타낼 수 있고, $n^3$은 3의 배수가 된다
• 따라서 명제의 부정이 거짓이므로, 명제는 참이다.

반례증명법

함축명제 $p \implies q$가 참이라면, 명제 p가 참이 되는 모든 경우에 대해 q도 참이어야 한다. 만약 명제 p의 진리값이 참이지만 q의 진리값이 거짓인 경우가 있다면 이 명제는 거짓이다. 반례증명법은 이러한 경우를 찾아 명제가 거짓임을 증명한다. 

 

예시를 들어 증명해보자.

$\forall x \in \mathbb{R}, \forall y \in \mathbb{R}, x>y \implies x^2 > y^2$

• x = 1, y = -2라면 $x > y$이지만 $x^2 < y^2$이다. 따라서 모든 실수에 대해 위 명제가 성립하지 않는다.

---

정리

수학적인 증명법에는 귀납적인 수학적 귀납법, 연역적인 직접증명법/간접증명법(반례증명법, 모순증명법, 대우증명법)이 있다. 하나의 명제를 여러 방법으로 증명할 수도 있다.

 

예시.

정수 n에 대해, $3n + 2$이 짝수이면 $n$이 짝수

• 대우증명법
  • 명제의 대우는 "$n$이 홀수이면 $3n + 2$는 홀수"이다.
  • $n = 2k + 1$(k는 정수)에서, $3n + 2 = 6k + 5 = 2(3k + 2) + 1$
  • 따라서 대우가 참이므로 명제는 참이다
• 모순증명법
  • 명제의 부정은 "3n + 2가 짝수이면서 n이 홀수"이다.
  • $n = 2k + 1$(k는 정수)에서, $3n + 2 = 6k + 5 = 2(3k + 2) + 1$
  • 이는 3n + 2가 짝수라는 가정에 모순된다
  • 따라서 부정이 거짓이므로, 명제는 참이다
• 직접증명법
  • 3n + 2가 짝수라면 $3n + 2 = 2k$, $n = \frac{2(k - 1)}{3}$
  • 이때 $n \in \mathbb{Z}$이므로, $k - 1$은 3의 배수이다
  • 따라서 $n = 2p$형태이므로 짝수이다
• 수학적 귀납법
  • n = 0일때 3n + 2는 짝수이고 n도 짝수이므로 명제가 성립한다.
  • $n = k$일때 명제가 성립한다고 가정하자
  • $n = k + 1$일때 명제가 성립하는지 보이면
    
    • $3(n + 1) + 2 = (3n + 2) + 3 = 2k + 3 = 2(k + 1) + 1$
    • 함축명제 $p \implies q$에서 명제 $p$가 거짓이므로, 명제 $q$의 진리값과 관계없이 이 명제는 참이 된다
  • $n = k - 1$일때 명제가 성립하는지 보이면
    • $3(n - 1) + 2 = (3n + 2) - 5 = 2k - 5 = 2(k - 3) + 1$
    • 함축명제 $p \implies q$에서 명제 $p$가 거짓이므로, 명제 $q$의 진리값과 관계없이 이 명제는 참이 된다
  • 따라서 모든 정수에 대해 명제가 성립한다
  • 흠... 함축명제의 성질에 따라 k+1, k-1 모두 명제가 참이 되므로 귀납적으로 참이다라고 말하고 싶은데 확실하지가 않다...

---

 

부울 대수와 논리회로

부울 대수(boolean algebra)는 0과 1만을 갖는 수 체계에서의 연산 규칙이다. 디지털 회로는 부울 대수를 조합해 논리회로를 만드므로, 부울 대수의 연산규칙을 이해해야 논리게이트를 조합한 논리회로에 대해 설명할 수 있다.

 

부울 대수의 연산규칙

• 모든 변수는 1(참) 또는 0(거짓)의 값을 갖는다
• 연산기호는 논리연산자와 비슷하다
  • AND 연산 ($\cdot$)
    • 논리곱 연산($\land$)과 같은 기능을 한다. 두 값이 모두 1이어야 1을 반환하고, 그 외의 경우에 0을 반환한다
    • $1 \cdot 1 = 1$, $0 \cdot 1 = 0$
  • OR 연산 ($+$)
    • 논리합 연산($\lor$)과 같은 기능을 한다. 두 값이 모두 0이어야 0을 반환하고, 그 외의 경우에 1을 반환한다
    • $1 + 0 = 1$, $0 + 0 = 0$
  • XOR 연산 ($\oplus$)
    • 배타적 논리합 연산($\oplus)과 같은 기능을 한다. 두 값중 하나만 1이어야 1을 반환한다. 다시 말해, 1이 홀수 개 있으면 1을 반환하고 짝수 개 있으면 0을 반환한다.
    • $1 \oplus 1 = 0$, $1 \oplus 0 = 1$
  • NOT 연산 (보수 연산, $\overline{x}$)
    • 여집합($A\complement$)과 같은 기능을 한다. 값을 부정한다. 1이면 0을, 0이면 1로 바꾼다. 1의 보수를 취하는 것과 같다.
    • $\overline{0} = 1$, $\overline{1} = 0$
  • AND, OR, XOR을 부정한 연산을 NAND, NOR, XNOR연산이라고 한다. 논리회로에서 후술.
• 논리적 동치법칙과 유사한 부울 대수 법칙이 있다. 이 규칙들은 항등 관계를 정의한다
  • 이중 보수법칙: $\overline{\overline{a}} = a$
  • 멱등법칙: $x = x + x = x \cdot x$
  • 항등법칙: $x + 0 = x \cdot = x$
  • 지배법칙: $x + 1 = 1$, $x \cdot 0 = 0$
  • 교환법칙, 결합법칙: $x + y + z = z + y + x = (x + y) + x$, $x \cdot y \cdot z = z \cdot x \cdot y = (x \cdot y) \cdot z)$
  • 분배법칙: $x + yz = (x + y)(x + z)$, $xy + xz = x(y + z)$
    • $x(y + z) = xy + yz$는 진리표를 이용해 확인 가능하고, 
    • $(x + y)(x + z) = x + yz$는 다른 법칙들을 이용해 유도할 수 있다: $(x + y)(x + z) = xx + xy + xz + yz = x(1 + y + z) + yz = x \cdot 1 + yz = x + yz$
  • 드모르간의 법칙: $\overline{x + y} = \overline{x} \oplus \overline{y}$, $\overline{xy} = \overline{x} + \overline{y}$
  • 흡수법칙: $x + xy = x$, $x(x + y) = x$
    • 다른 법칙들을 이용해 유도할 수 있다.
    • $x + xy = x \cdot 1 + x \cdot y = x(1 + y) = x \cdot 1 = x$
    • $x(x + y) = xx + xy = x + xy = x$
• 쌍대성의 원리
  • 항등관계로 나타낸 부울 표현은 쌍대가 존재한다. 이 쌍대도 항등관계를 만족한다.
  • 쌍대는 1을 0으로, $+$를 $\cdot$으로 바꿔 구할 수 있다.
  • 예) $x(x + y) = x$의 쌍대는 $(x) + (x \cdot y) = x$이고, 이는 마찬가지로 항등관계이다. (흡수법칙)

 

부울 함수

 

논리회로

---

행렬

---

집합과 관계

집합

집합의 특성

 

집합 연산

 

관계

관계의 정의

 

관계의 표현

 

특수한 관계 (반사관계, 대칭관계, 추이관계, 동치관계)

 

함수

함수의 정의

 

여러 가지 함수

 

---

그래프

---

오토마타