[Programming] Logical equivalence examples

1. p·1=p	11. p+(p·q) = p
2. p+1 = 1	12. p+¬p = 1
3. p+p = p	13. p+0 = p
4. ¬(¬p) = p	14. p·p = p
5. p+q = q+p	15. p·q = q·p
6. (p+q)+r = p+(q+r)	16. (p·q)·r = p·(q·r)
7. p+(q·r) = (p+q)	17. p·(q+r) = (p·q)+(p·r)
8. ¬(p+q) = ¬p·¬q	18. ¬(p·q) = ¬p+¬q
9. ¬(p+q+r) = ¬p·¬q·¬r	19. p·(p+q) = p
10.(p·q·r) = ¬p+¬q+¬r	20. p·¬p = 0

 

[Programming] Logical Equivalences

Logical equivalences를 이용해서 문제를 풀어보자.

풀기 전에 한 가지 중요한 공식을 이야기하자면,

p->q≡ ¬p+q 또는 p->q=p`+q 이라는 공식을 기억해두자.

 

예를 들어,

[x+(y+z)]->(x+y)·(x+z) 라는 식에 대해서 true인지를 증명해본다고 가정한다면,

[x+(y+z)]->(x+y)·(x+z)

화살표가 눈에 거슬리기 때문에 없애준다.

 

=(x+(y+z))'+(x+y)·(x+z)

위에 제시된 공식을 사용해서 만들어 준다.

 

=(x+(y+z))'+(x+y)·(x+(y+z))'+(x+z)

상단 표에 있는 7번 규칙을 적용하면 위와 같은 식이 나온다.

 

=(x+y)'+z'+(x+y)·(x+z)'+y'+(x+z)

여기서 6번 규칙을 사용해서 식을 간단히 할 수 있도록 만들어준다.

 

=1+z'·y'+1

12번 규칙을 적용하면 위와 같이 나온다.

 

=1

여기서 유의할 점은 이건 수학적 계산이 아니다.

따라서 참인지 거짓인지를 나타내기 때문에 2번 규칙을 사용하면 결과적으로 1이 산출된다.

 

Logical equivalences는 process, 즉 과정이 한 가지 있는 것은 아니다.

위의 example를 다른 규칙을 사용해서도 충분히 풀 수 있다.

다만 결과값은 동일하다.

솔직히 익숙하지 않으면 복잡하고 머리 아파 보이는 게 사실이다.

하지만 천천히 해본다면, 충분히 할 수 있기에 포기하지 말고 천천히 하다 보면 결괏값에 도달한다.