1 기초: 논리와 증명 3

//이 자료는 Discrete mathmatics and its application 7th edition에서 나오는 예제를 간추린 것입니다. 저는 코딩에 관심 있는 학생이며, 타인의 지적재산을 단지 학습을 위해 사용할 뿐 개인의 금리적 이윤을 위한 상업적인 용도로 쓰지 않습니다. 만약 저작권 관련 문제가 될 시 즉시 문서를 삭제하겠습니다.//

1.3 논리적 동치 logical equivalent

동어반복 tautology 모순 contradiction

수학적 논증에서 사용되는 중요한 접근법은 한 명제를 같은 진리값을 가지는 다른 명제로 대체하는 것입니다. 주어진 복합명제와 같은 진리값을 가지는 명제를 만드는 방법론은 수학적 논증을 만드는데 보편적으로 사용됩니다. 복합명제는 p^q와 같이 논리 연결사를 이용해 명제 변수로 이루어진 표현식을 말합니다.

정의 1

명제 변수의 진리값에 상관없이 항상 참인 복합명제는 동어반복이라고 불립니다. 항상 거짓인 복합명제는 모순이라고 불립니다. 동어반복이나 모순이 아닌 복합명제는 contingeny 입니다.

명제변수 하나와 논리연결사를 이용하여 동어반복과 모순의 예를 만들 수 있습니다. 아래의 진리표는 p v ¬p, p ^ ¬p에 관한 것입니다. p v ¬p 는 항상 참이므로 동어반복이고 p ^ ¬p는 항상 거짓이므로 모순입니다.

논리적 동치

모든 경우에 같은 진리값을 가지는 복합 명제를 논리적 동치라고 부릅니다.

정의 2

p<->q가 동어반복이라면 p와 q는 논리적 동치라고 불립니다. 기호 p≡q는 p와 q가 논리적 동치임을 표현합니다.

주의

기호≡는 논리 연결사가 아니며, p≡q는 p <-> q가 동어반복임을 나타내는 명제입니다. 두 복합명제가 동치인지 확인하는 방법은 진리표를 사용하는 것입니다.

예제 2

¬(p v q) 와 ¬p^¬q가 논리적 동치인 것을 보이세요

정답

복합명제들은 아래의 진리표에서 확인 가능합니다. ¬(p v q) 와 ¬p^¬q 두 복합명제의 진리 값은 어떠한 p 와 q의 어떠한 진리값 조합조건과 같습니다. ¬(p v q) <-> (¬p^¬q)는 동어반복이고 두 복합명제는 논리적 동치입니다.

예제 3

p -> q와 ¬p v q는 논리적 동치인 것을 보이세요.

정답

아래의 진리표를 확인합시다. ¬p v q 와 p -> q의 진리값은 일치하므로 논리적 동치입니다.

서로 다른 세가지 명제변수 p, q, r을 포함하는 두 복합명제를 논리적 동치로 만들 것입니다. 세가지 변수의 진리값 조합 수는 8 열을 가집니다. 8개 조합 조건의 진리값은 다음과 같습니다. TTT, TTF, TFT, TFF, FTT, FTF, FFT 그리고 FFF 입니다. 진리표의 열을 표현할 때 이 순서를 사용할 것입니다. 추가적인 명제변수로, 복합명제가 논리적인 동치임을 보여주기 위해서는 열의 수는 2배가 됩니다. 보통, n 개의 명제변수를 포함한 복합명제는 2^n 열이 필요로 합니다.

예제 4

p v (q ^ r)과 (p v q) ^ (p v r)은 논리적 동치인지 확인합시다. 이를 논리곱의 분배법칙이라 합니다.

정답

문제의 복합명제로 아래의 진리표를 만들 수 있습니다. 두 복합명제의 진리값이 일치하므로, 논리적 동치입니다.

예제 5

“미구엘은 핸드폰을 가지고있고 노트북을 가지고 있다”와 “헤서는 콘서트에 가거나 스티브가 콘서트에 갈 것이다”의 부정형을 드 모르간의 법칙을 이용하여 표현하세요

정답

P를 “미구엘은 핸드폰을 가지고 있다”와 q는 “미구엘은 노트북을 가지고 있다”라고 하자. “미구엘은 핸드폰과 노트북을 가지고 있다”는 p^q로 표현될 수 있습니다. 드 모르간 법칙의 첫 번째를 따르면, ¬(p^q)가 ¬p v ¬q 와 같습니다. 따라서, 원 명제의 부정형으로 "미구엘은 핸드폰을 가지고 있지 않거나 노트북을 가지고 있지 않다."로 쓸 수 있습니다.

r을 "헤서는 콘서트에 갑니다" 와 s는 "스티브는 콘서트에 갑니다"라 합시다. 그렇다면 "헤서는 콘서트에 가거나 스티브가 콘서트에 갑니다"를 r v s로 표현할 수 있습니다. 드 모르간의 법칙에 따라, ¬(r v s)는 ¬r ^ ¬s와 같습니다. 결과적으로, 우리는 원 명제의 부정형으로 "헤서는 콘서트에 가지 않을 것이고 스티브는 콘서트에 가지 않을것 입니다."로 쓸 수 있습니다.

새로운 논리적 동치를 만들기

예제 6

¬(p -> q)와 p ^ ¬q는 논리적 동치임을 보이세요.

정답

복합명제들이 같다는 것을 보여주기위해 진리표를 사용할 수 있습니다. 해보면 어렵지 않습니다만, 기존에 알고 있는 논리적 동치를 이용해 새로운 논리적 동치를 만들 것입니다. 

¬(p->q)  ≡ ¬(¬p v q)    //예제 3참고

 ≡ ¬(¬p)^¬q   //드 모르간의 법칙

 ≡ p^¬q         //이중부정

예제 7

¬(p v (¬p ^ q))와 ¬p ^ ¬q가 논리적 동치임을 보이시오.

정답

¬(p v (¬p ^ q)) ≡ ¬p ^ ¬(¬p ^ q)    //드 모르간의 법칙

    ≡ ¬p ^ [¬(¬p) v ¬q]   //드 모르간의 법칙

    ≡ ¬p ^ (p v ¬q)   //이중부정

    ≡ (¬p ^ p) v (¬p ^ ¬q)    //분배법칙

    ≡ F v (¬p ^ ¬q)    //¬p ^ p ≡ F

    ≡ (¬p ^ ¬q) v F    //교환법칙이 성립

    ≡ ¬p ^ ¬q

예제 8 

(p ^ q) -> (p v q) 가 동어반복임을 보이시오.

정답

해당 명제가 동어반복임을 보이긴 위해서는, T와 논리적 동치임을 증명하면 됩니다.

(p ^ q) -> (p v q) ≡ ¬(p ^ q) v (p v q)    //예제 3

 ≡ (¬p v ¬q) v (p v q)    //드 모르간의 법칙

 ≡ (¬p v p) v (¬q v q)    //교환법칙과 결합법칙

 ≡ T v T    //예제 1과 교환법칙

 ≡ T

명제 만족 가능성 Propositional Satisfiability

명제변수가 특정 진리값을 가질 때, 복합명제가 참이된다면 복합명제는 만족될 수 있다(satisfiable)고 표현합니다. 어떠한 경우에도 복합명제가 참을 가질 수 없을 때 만족될 수 없다(unsatisfiable)고 표현합니다. 명제변수에 할당되었을 때 복합명제를 참으로 만드는 특정한 진리값을 찾았을 때, 복합명제는 만족될 수 있다고 합니다. 할당된 진리값을 해당 만족 문제에 대한 솔루션이라고 부릅니다. 그러나, 해당 복합명제가 만족 될 수 없다고 보이기 위해서는, 모든 진리 값을 명제변수에 넣어야 합니다. 진리표를 활용하여 복합명제가 만족 될 수 있음을 보일 수는 있어도, 보통 그런 방법보다는 아래의 방법을 사용하는것이 더 효율적입니다.

예제 9

다음의 복합명제들 (p v ¬q) ^ (q v ¬r) ^ (r v ¬p), (p v q v r) ^ (¬p v ¬q ¬r) 그리고 (p v ¬q) v (q v ¬r) ^(r v ¬p) ^ (p v q v r) ^ (¬p v ¬q v ¬r) 이 만족될 수 있음을 보이시오.

정답

진리표를 사용하여 위 문제를 푸는것보다는, 진리값에 대해 추론할 것입니다. (p v ¬q) ^ (q v ¬r) ^ (r v ¬p)는 p, q, r 변수의 진리값이 같을 때 참입니다. 따라서, 복합명제를 참으로 만드는 데에 p, q, r 한 개 이상의 진리값 할당이 있습니다. 비슷하게, (p v q v r) ^ (¬p v ¬q ¬r)는 p, q, r 변수 중에 적어도 한 개가 참이고 적어도 한 개가 거짓일 때 참 입니다. 따라서, 복합명제를 참으로 만드는데에 p,q,r 한 개 이상의 진리값 할당이 있으므로, (p v q v r) ^ (¬p v ¬q ¬r)은 만족될 수 있습니다. 

마지막 복합명제 (p v ¬q) v (q v ¬r) ^(r v ¬p) ^ (p v q v r) ^ (¬p v ¬q v ¬r)가 참이 되려면 앞의 두 복합명제들 모두 참이여야 합니다. 그러나 앞선 복합명제는 모든 명제변수들의 값이 같아야하고, 뒷 복합명제는 다른 진리값의 명제변수를 포함하고 있어야합니다. 그러므로 해당 복합명제를 참으로 만드는 진리값 할당법이 없으므로, 이 복합명제는 만족될 수 없습니다.

만족 가능성의 응용

로보틱스, 소프트웨어 검사, 컴퓨터 디자인, 컴퓨터 비젼, 집적 회로 디자인, 컴퓨터 네트워크, 유전학 등 분야에서 다양한 문제들이 명제 만족 가능성 문제로 모델링 될 수 있습니다. 이런 많은 응용물들은 책의 범위를 뛰어넘지만, 한 가지 응용사례를 앞으로 살펴볼 것 입니다. 다음은 스도쿠 퍼즐을 모델링하는법을 볼 것입니다.

..생략..

문제 9 다음이 동어반복임을 진리표를 이용하여 보이시오

a) (p ^ q) -> p