Foundation: propositional equivalence

사실은...

이런 기호를 이용한 논리학 즉, 기호 논리학의 시작이라고 부를 수 있는 George Boole은 그의 저서 Law s of thoughts에서 다음과 같은 표현을 이용했습니다. 

x를 남자, y를 여자라고 하자. 그렇다면 "남자와 여자"는 x+y이며, "여자와 남자"는 y+x이다. 따라서 x+y=y+x 이다.

이때 z를 유럽인이라고 한다면, "유럽인 남자와 여자" 는 z(x+y)이며, "유럽인 남자와 유럽인 여자"는 zx+zy이다. 따라서, z(x+y) = zx+zy 라 할 수 있다.

여기서 남자와 여자, 즉 논리합은 "+" 라는 연산자와 같습니다. 또한, 유럽인이면서도 남자임으로 - 논리곱으로 zx 로 나타내었습니다. 이해하시겠죠? 

ㅈ ㅏ. 이제 계속해서 동치라는 것을 살펴보겠습니다.

정의1 

가장 작은 명제atomic proposition의 진리값의 모든 경우에서 항상 참인 복합 명제compound proposition를 항진tautology이라고 한다. 가장 작은 명제의 진리값의 모든 경우에서 항상 거짓인 복합 명제를 모순contradiction이라고 한다. *항진=항상 진실임

예제1 다음의 복합명제 p∨¬p와 p∧¬p를 살펴봅시다. p∨¬p는 p의 진리값에 상관없이 항상 참입니다. p∧¬p는 p의 진리값에 상관없이 항상 거짓입니다. 아래의 진리표에서 확인합시다.

p	¬p	p∨¬p	p∧¬p
T	F	T	F
F	T	T	F

정의2

다음의 "복합명제 p↔q가 항진"임은 명제 "p와 q는 논리적으로 동치이다"의 필요충분조건입니다. p≡q는 p와 q가 논리적으로 동치임을 표현합니다.

notice: ≡는 논리 연산자입니다. p≡q는 복합명제이기보다는 p↔q가 항진명제라는 진술에 가깝습니다. 기호 ⇔는 ≡를 대신하여 사용되기도 합니다.

복합명제의 논리적 동치 예들 중에 중요하고 유용한 것으로는 드 모르간의 법칙De Morgan laws이 있습니다.

1) ¬(p∧q)≡¬p∨¬q         2)¬(p∨q)≡¬p∧¬q

예제2 ¬(p∧q)와 ¬p∨¬q가 논리적 동치임을 보여라

*** ¬(p∧q)와 ¬p∨¬q가 동치임을 확인하려면 atomic propositions의 모든 경우 진리값이 같음을 확인하면 됩니다. 이는 진리표를 작성해서 확인할 수 있습니다. 

p	q	p∨q	¬(p∨q)	¬p	¬q	¬p∧¬q
T	T	T	F	F	F	F
T	F	T	F	F	T	F
F	T	T	F	T	F	F
F	F	F	T	T	T	T

예제3 p→q와 ¬p∨q가 논리적 동치임을 보여라

*** 

p	q	¬p	¬p∨q	p→q
T	T	F	T	T
T	F	F	F	F
F	T	T	T	T
F	F	T	T	T

예제4 p∨(q∧r)과 (p∨q)∧(p∨r)이 논리적 동치임을 보여라.

***

p	q	r	p∨(q∧r)	p∨q	q∨r	p∨r	(p∨q)∧(p∨r)
T	T	T	T	T	T	T	T
T	T	F	T	T	T	T	T
T	F	T	T	T	T	T	T
T	F	F	T	T	F	T	T
F	T	T	T	T	T	T	T
F	T	F	F	F	T	F	F
F	F	T	F	F	F	T	F
F	F	F	F	F	F	F	F

notice: 아래의 테이블은 동치인 복합명제들을 보여줍니다. 오른쪽의 논리적 동치의 이름은 외우실 필요는 없습니다. (외우지 않아도 자명합니다 -ㅅ-) 하지만 우리가 다음으로 할 새로운 동치를 증명하는 것에서 참조할 때 쓰이기도 합니다. 이름을 외우건 안외우건, 매우 기초적인 -다르게 말하면 매우 필수적인 논리구조이므로 반드시 확인하고 넘어갑시다.

notice: 맨 위 표(표 6)에서 T, F는 항상 참이거나 거짓인 복합명제를 말합니다. 그러니까 차례로 항진명제, 모순명제가 되겠네요. 그 뒤로 따라오는 표 7과 표 8은 조건문과 쌍방조건문을 포함하는 동치관계의 모음입니다. 몇 개는 앞서 증명해본 것도 있고 또 몇 개는 뒤에서 문제로 증명해볼 것입니다. 

표 6에서 논리합의 결합법칙associative laws이 잘 정의된 것을 볼 수 있습니다. 이는 p와 q의 논리합을 먼저하여 r과 논리합을 수행하던, q와 r의 논리합을 먼저하여 p와 논리합을 수행하던 결과는 같다는 뜻입니다. 오해의 여지가 없으므로 잘 정의되어 있습니다. 유사하게, 논리곱의 결합법칙 또한 성립합니다. (바로아래) 이 논리를 확장 좀 더 시켜보면, p1, p2, p3 ... pn이 명제일 때 p1∧p2∧..∧pn 과 p1∨p2∨ ... ∨pn 또한 잘 정의되어 있습니다. 그래서, 드 모르간의 법칙은 다음처럼 확장될 수 있습니다.

 ¬(p1∨p2∨...∨pn)≡¬p1∧¬p2∧...∧¬pn  그리고  ¬(p1∧p2∧...∧pn)≡¬p1∨¬p2∨...∨¬pn

때론 다음과 같은 대형 연산자를 이용할 수도 있습니다.

는 p1∨p2∨...∨pn 를 의미 합니다. 그리고 는 p1∧p2∧...∧pn를 의미합니다. 이 대형연산자 표기법을 이용하여 드 모르간의 법칙을 기술하려면 다음과 같이 쓸 수 있습니다. 

 그리고  이를 증명하는 방법은 좀 더 추후에 제시 될 것입니다.

notice: 진리표를 이용하여 동치임을 증명하는 것 이외에 다른 방법이 있습니다. 다음으로 알아볼 것은 복합명제와 동치관계인 또 다른 복합명제들을 차례로 제시하며 우리가 원하는 것과 동치임을 증명해내는 것입니다.

예제5 다음 복합명제  ¬(p→q) 과 p∧¬q 가 논리적으로 동치임을 보여라.

*** ¬(p→q) ≡ ¬(¬p∨q)   //예제 2, 또는 Table 7의 1번째 예 확인

          ≡ ¬(¬p)∧¬q //드 모르간의 법칙에 의해서

          ≡ p∧¬q

예제6 다음 복합명제  ¬(p∨(¬p∧q))와 ¬p∧¬q가 논리적으로 동치임을 논리적 동치관계들을 이용하여 증명하시오.

*** ¬(p∨(¬p∧q)) ≡ ¬p∧¬(¬p∧q)) // 드모르간의 법칙에 의해서

                      ≡ ¬p∧(¬(¬p)∨¬q) // 드모르간의 법칙에 의해서

                      ≡ ¬p∧(p∨¬q) // 이중 부정 법칙double negation law에 의해서               

                      ≡ (¬p∧p)∨(¬p∧¬q) // 분배법칙distributive law에 의해서

     ≡ F∨(¬p∧¬q) // ¬p∧p ≡ F, 자기 자신과 자기 자신의 부정의 논리곱은 모순명제, F

     ≡ ¬p∧¬q  // 모순명제와 복합명제의 논리합 진리값은 복합명제에 의해 결정Identity           law

    Thus, ¬(p∨(¬p∧q)) ≡ ¬p∧¬q

명제의 만족가능성propositional satisfiability

한 복합명제의 만족가능성을 고려해본다는 것은, 그 복합명제의 진리값이 참인 경우가 존재하는지 확인 하는 것입니다. 만약 만족가능성이 없다는 뜻은 - 당연하게도 어떤 경우에서도 그 명제는 거짓말인 거겠죠. 하늘이 무너져도요. 그런 경우에는 이 명제는 어느 경우에도 만족가능하지 않다. 라고 표현합니다. 우리가 만약 복합명제의 단위 명제들의 진리값들을 결정했을 때 (p, q, r 등의 진리값) 그 복합명제의 진리값이 참이라면, 우린 그 특정한 만족가능한 문제의 솔루션solution을 찾았다고 합니다. 어려운 이야기가 아닙니다. 만약 문제가 3+x =7, where x is natural number 라면, x라는 변수의 값은 4가 되어야합니다. (물론 4는 진리값은 아니지만) 그렇지만 만약, 해당 문제가 만족가능하지 않다고 증명해보이려면 일이 좀 복잡해집니다. 만족가능한지에 대해서는 복합명제가 참임을 보여주는 단 하나의 예만 보여주면 되지만, 만족불가능하다라는 것은 모든 경우에서 다 그렇다는 것을 보여줘야합니다. 계란 한 판을 상상해보세요, 여기 안에 병아리가 있다는 것을 증명해보려고 합니다. (악, 그 건강식..?) 그렇다면 계란한판을 일렬로 세운 뒤에 차례로 깨면서 병아리가 존재하는지 확인해야합니다. 30개인 한 판을 다 깨는 동안 도중에 병아리가 존재한다면 거기서 멈춘다음, 병아리가 존재한다고 증명을 끝내면 됩니다. 하지만, 존재하지 않는다고 증명하려면 모든 계란을 다 깨보아야합니다. 중간에 병아리가 나오지 않는 이상 -즉, 예상을 뒤엎는 존재한다는 결과가 나오지 않는 이상- 매번 깨볼때마다 "어 병아리가 없구나" 하면서도 그 다음 계란에서 병아리가 나오지 않는 것을 기대하면서 또다시 계란을 깰 준비를 해야합니다. 이 이야기를 하는 이유는- 다시 한번 더-, 복합명제가 만족불가능하다는 것을 보이려면 단위 명제들의 모든 진리값 배치 경우에 대해서 고려해보야 한다는 것입니다. 자 다음의 예제를 확인해봅시다.

예제 7 다음의 복합명제가 만족가능한지 확인하시오. 

         1 (p∨¬q)∧(q∨¬r)∧(r∨¬p) 

         2 (p∨q∨r)∧(¬p∨¬q∨¬r) 

         3 (p∨¬q)∧(q∨¬r)∧(r∨¬p)∧(p∨q∨r)∧(¬p∨¬q∨¬r)

*** 1: p, q, r 모두 T 일 때 만족한다. 따라서, 만족가능하다. 2: p, q, r 중 서로 다른 진리값이 존재하면 만족한다. 따라서, 만족가능하다. 3: (복잡해 보인다.) p, q, r 모두 참 일때 만족하지 않는다. p, q, r 모두 거짓일 때 만족하지 않는다. 서로 다른 진리값이 존재하는 경우에도 만족하지 않는다. (이 경우는 앞에 세 항term의 논리곱이 항상 거짓이다.) 따라서 3은 만족가능하지 않다.

만족가능성의 응용applications of satisfiability

굉장히 다양한 분야에서 명제의 만족가능성이 응용되어 사용되고 있습니다. 단순히 학생들의 수학 문제집에서 나오는 것이 아니라 수학이 응용되는 분야 - 로보틱스, 소프트웨어 테스팅, computer-aided design(CAD, 캐드, 모델링 도구),  집적회로 디자인, 컴퓨터 네트웤 그리고 심지어 유전학에도요. 이제 우리는 주변의 간단한 예에서 명제의 만족가능성이 어떻게 응용되는지 살펴볼 것 입니다.  

스도쿠sudoku

스도쿠가 무엇인지 아실 겁니다. 스도쿠는 각 칸에 하나의 숫자만 넣을 수 있고 3x3 칸에는 1에서부터 9 까지의 숫자가 고유하게 배치되어야 하는 동시에 각 열에서도 1에서부터 9까지의 숫자가 고유하게 배치되어야 합니다. 스도쿠의 난이도는 얼마만큼의 수가 제시되는가에 따라 천차만별이죠. 

자, 스도쿠 퍼즐을 우리가 이제까지 배운 명제논리로 표현해 봅시다. 

명제 p(i, j, n)는 세 변수 i, j, n을 가진다. i 행, j 열, n 값. 위 그림에서 다음을 만족한다. p(2, 1, 6) ≡ T. 그러므로 다음을 또한 만족한다. P(2, j, 6) ≡ F, for j = 2, 3, ..., 9. 

자 이제 기본 규칙을 명제논리로 작성해봅시다.

1 명제 p(i, j, n)은 i 행 j 열에 n의 값이 있다고 하자.

2 모든 행은 예외없이 1에서부터 9까지 모든 숫자를 가지고 있다.

{[p(1, 1, 1) ∨ p(1, 2, 1) ∨ p(1, 3, 1) ∨ ... ∨ p(1, 9, 1)] ∧ [p(1, 1, 2) ∨ p(1, 2, 2) ∨ p(1, 3, 2) ∨ ... ∨ p(1, 9, 2)] ∧... ∧ [p(1, 1, 9) ∨ p(1, 2, 9) ∨ p(1, 3, 9) ∨ ... ∨ p(1, 9, 9)]} ∧

{[p(2, 1, 1) ∨ p(2, 2, 1) ∨ p(2, 3, 1) ∨ ... ∨ p(2, 9, 1)] ∧ [p(2, 1, 2) ∨ p(2, 2, 2) ∨ p(2, 3, 2) ∨ ... ∨ p(2, 9, 2)] ∧... ∧ [p(2, 1, 9) ∨ p(2, 2, 9) ∨ p(2, 3, 9) ∨ ... ∨ p(2, 9, 9)]} ∧ ... 

^{[p(9, 1, 1) ∨ p(9, 2, 1) ∨ p(9, 3, 1) ∨ ... ∨ p(9, 9, 1)] ∧ [p(9, 1, 2) ∨ p(9, 2, 2) ∨ p(9, 3, 2) ∨ ... ∨ p(9, 9, 2)] ∧... ∧ [p(9, 1, 9) ∨ p(9, 2, 9) ∨ p(9, 3, 9) ∨ ... ∨ p(9, 9, 9)]}

대형 연산자를 이용하면 다음과 같이 표현할 수 있습니다.

3 모든 열은 예외없이 1에서부터 9까지 모든 숫자를 가지고 있다.

대형 연산자를 이용하면 다음과 같이 표현할 수 있습니다.

4 각 3x3 블록들은 예외없이 1에서부터 9까지 모든 숫자를 가지고 있다.

{[p(1, 1, 1) ∨ p(1, 2, 1) ∨ p(1, 3, 1)] ∨ [p(2, 1, 1) ∨ p(2, 2, 1) ∨ p(2, 3, 1)] ∨[p(3, 1, 1) ∨ p(3, 2, 1) ∨ p(3, 3, 1)]} ∧ {[p(1, 1, 2) ∨ p(1, 2, 2) ∨ p(1, 3, 2)] ∨ [p(2, 1, 2) ∨ p(2, 2, 2) ∨ p(2, 3, 2)] ∨[p(3, 1, 2) ∨ p(3, 2, 2) ∨ p(3, 3, 2)]} ∧ .... ∧ {[p(1, 1, 9) ∨ p(1, 2, 9) ∨ p(1, 3, 9)] ∨ [p(2, 1, 9) ∨ p(2, 2, 9) ∨ p(2, 3, 9)] ∨[p(3, 1, 9) ∨ p(3, 2, 9) ∨ p(3, 3, 9)]} ∧

{[p(1, 4, 1) ∨ p(1, 5, 1) ∨ p(1, 6, 1)] ∨ [p(2, 4, 1) ∨ p(2, 5, 1) ∨ p(2, 6, 1)] ∨[p(3, 4, 1) ∨ p(3, 5, 1) ∨ p(3, 6, 1)]} ∧ {[p(1, 4, 2) ∨ p(1, 5, 2) ∨ p(1, 6, 2)] ∨ [p(2, 4, 2) ∨ p(2, 5, 2) ∨ p(2, 6, 2)] ∨[p(3, 4, 2) ∨ p(3, 5, 2) ∨ p(3, 6, 2)]} ∧ .... ∧ {[p(1, 4, 9) ∨ p(1, 5, 9) ∨ p(1, 6, 9)] ∨ [p(2, 4, 9) ∨ p(2, 5, 9) ∨ p(2, 6, 9)] ∨[p(3, 4, 9) ∨ p(3, 5, 9) ∨ p(3, 6, 9)]} ∧ ... ∧

{[p(7, 7, 1) ∨ p(7, 8, 1) ∨ p(7, 9, 1)] ∨ [p(8, 7, 1) ∨ p(8, 8, 1) ∨ p(8, 9, 1)] ∨[p(9, 7, 1) ∨ p(9, 8, 1) ∨ p(9, 9, 1)]} ∧ {[p(7, 7, 2) ∨ p(7, 8, 2) ∨ p(7, 9, 2)] ∨ [p(8, 7, 2) ∨ p(8, 8, 2) ∨ p(8, 9, 2)] ∨[p(9, 7, 2) ∨ p(9, 8, 2) ∨ p(9, 9, 2)]} ∧ .... ∧ {[p(7, 7, 9) ∨ p(7, 8, 9) ∨ p(7, 9, 9)] ∨ [p(8, 7, 9) ∨ p(8, 8, 9) ∨ p(8, 9, 9)] ∨[p(9, 7, 9) ∨ p(9, 8, 9) ∨ p(9, 9, 9)]}

대형 연산자를 이용하면 다음과 같이 표현할 수 있습니다.

5 어떠한 칸도 한 개 이상의 수를 가져선 안 된다. 

n≠l, p(i, j, n) → ¬p(i, j, l)

자, 먼저 우리는 i 행이 모든 수를 가진다고 표현하기 위해서, 

를 이용해서 각 행의 모든 열은 n을 가진다고 정의하였습니다. 그 뒤, 

를 이용해서 각 행의 모든 열은 모든 n값을 가진다고 정의하였습니다. 이를 중첩된 연산자라고 표현합니다. 어떻게 풀어서 해석해야할지 개념을 반드시 알아둡시다. 앞으로 만나볼 다른 연산자에서도 같은 순서로 적용이 됩니다. 제가 위에서 일부로 다 풀어 쓴 이유이기도 합니다. 

만족가능성 문제 해결하기

진리표가 복합명제의 만족가능성 문제를 해결할 때 사용될 수도 있습니다. 그러나 단위 명제(또는 변수)의 수가 늘 때마다 확인해야할 수는 엄청 빠르게 증가합니다. 만약 변수의 수가 20개인 복합명제의 만족가능성 문제를 해결하기 위해서는, 최악의 경우 2의 20승 즉 1,048,576번을 확인 하여야합니다. 

정말 응용적인 모델링을 할 때는 단위 명제의 수, 변수의 수가 수백개, 수천개, 수백만개가 되기도 합니다. 변수가 1천개이면, 단위 명제의 진리값이 배치될 수 있는 2의 1000승의 경우를 최악의 경우 모두 고려해보아야 합니다.  이를 컴퓨터로 수행하려고 해도 정말 수 억, 수 조년을 소요해야 합니다. 정말 비합리적일 만큼 큰 숫자이지만, 매우 합리적인 연산 결과입니다. -.ㅡ 이렇게 큰 숫자의 변수를 가진 임의의 복합명제가 만족가능한지 합리적인 시간 내에 판단하는 알고리즘은 없습니다. 이를 NP 문제라고도 하죠. 그러나 매우 특정한 복합 명제 형식에 대해서 만족가능한지에 대한 해결법은 점점 개발되고 있습니다. 특히 앞서 살펴본 스도쿠도 그 중 한 예입니다. 물론, 여기에 대해선 더이상 이야기 하지 않을겁니다. 우리의 목적은 컴퓨터가 아니니까요 - - ㅎ ;; 잠이와서 후다다닭 마치겠습니다.

다음 포스팅은 전반적인 review exercise 입니다.