논리적 동치[이산수학]

오늘은 논리적 동치에 대해서 알아볼 것이다.
논리적 동치란?
두개의 합성명제 P와 Q의 진릿값이 서로 같은 경우를 뜻한다.
두개의 합성명제가 논리적으로 동치인지 판별하는 방법에는 2가지가 있다.
첫번째는 진리표를 이용하는 방법,두번째는 논리적 동치법칙을 이용하는 방법이다.
첫번째 진리표는 손으로 직접 진리표를 적어서 두 합성명제의 진릿값이 서로 같으면 논리적동치라고 할 수 있다.
우리가 눈여겨봐야 할 것은 논리적 동치법칙이다.
아래는 논치적동치법칙을 정리해놓은 그림이다.

한번 흡수법칙을 증명해보겠다.

전 포스팅에서도 말했듯이 곱연산은 곱하기로 합연산은 더하기로 써줄 수 있다. 흡수법칙 증명에서 중요한 것은 항등원 1을 p에 곱해주는 것이다.

그렇다면 예제도 풀어보겠다.

어떤 법칙을 써서 간략히 풀어줄지 머릿속에 떠오른다면 당신은…멋진사람…

바로 이렇게 풀어줄 수 있다. 긴 식을 짧게 줄인다는게 참 재미있는것 같다. 논리적동치 법칙들은 외워줘야한다.. 아니면 문제를 못풀기 때문에…

추가로 XOR연산자는

이렇게 풀어줄 수 있다. 이것도 외워두길…
아 그리고 추가로 p XOR q의 부정은 p<->q와 논리적동치이다.그 반대도 마찬가지. 이걸 증명해보면
우선 p<->q를 정리해줘야 한다.

이렇게 정리된다. 그리고 p XOR q의 부정을 해보면

이렇게 논리적 동치가 된다. 반대로 p<->q의 부정은 p XOR q가 된다.

이렇게 된다. 따라서 결론은

이렇게 된다. 참..신기하죠..??
다음은 변수를 포함하는 명제로 돌아오겠다.