Math Logic Equiv

수리논리의 세계 로 돌아가기

논리적 등가 ($\equiv$) 에 덧붙여

논리적 등가와 항상 참인 명제식

아래 표의 왼쪽은 논리적으로 등가인 경우고, 오른쪽은 항상 참인 명제식이다.

논리적 등가	항상 참인 명제
$P\And P\ \equiv \ P$	$P\And P\ \leftrightarrow \ P$
$P\lor P\ \equiv \ P$	$P\lor P\ \leftrightarrow \ P$
$P\equiv \ \neg \neg P$	$P\leftrightarrow \ \neg \neg P$
$P\And (Q\lor P)\ \equiv \ P$	$P\And (Q\lor P)\ \leftrightarrow \ P$
$P\lor (Q\And P)\ \equiv \ P$	$P\lor (Q\And P)\ \leftrightarrow \ P$

항상 참이라고 믿을만한 구조를 가지면 것을 논리적 법칙이라고 믿을 수 있다.

예

중요한 결정사항이 있어서 위원회가 열렸다. 논쟁이 심하게 오갔지만, 결국 위원장 한 명과 두 위원인 위원회에서 찬반투표를 하기로 했다. 그동안 이 위원회에서는 위원회의 원칙에 따라 찬반일 경우를 모두 나열했다. 1 은 찬성, 0 은 거부 라고 하자. 기권은 없다고 가정하자. 다음 질문에 답해보라.

위원회 결정 원칙

위원장 P 씨	위원 Q 씨	위원 R 씨	찬반결론
1	1	1	1
1	1	0	1
1	0	1	1
1	0	0	0
0	1	1	0
0	1	0	0
0	0	1	0
0	0	0	0

• P 씨, Q 씨, R 씨는 진짜 성은 무엇이고 어떤 사람일까?
• 이 위원회는 어떤 '의사결정 원칙이 있을까? (아래 답)
• 기권이 있는 경우 가능한 표를 만들어보고 '의사결정 원칙'을 유도해보라.

이 위원회의 의사결정과정을 논리적 연산관계로 써보면 이렇게 된다. '찬성 결론 함수'를 만들 수 있는데 P, Q, R 의 찬반 여부가 모두 영향을 주기 때문에, 이를 F(P,Q,R) 이라 하자.

$F(P,Q,R):=(P\land Q\land R)\ \lor \ (P\land \neg Q\land R)\ \lor \ (P\land Q\land \neg R)$

일 때 찬성이라는 결론이 나온다. 이것을 간단히 하기 위해 우리가 받아들인 논리 규칙을 써서 풀어보자.

$(P\And Q\And R)\ \lor \ (P\And \neg Q\And R)\ \lor \ (P\And Q\And \neg R)$

$\equiv \ (P\And Q\And R)\ \lor \ (P\And \neg Q\And R)\ \lor \ (P\And Q\And R)\ (P\And Q\And \neg R)$

$\equiv \ (P\And R\And (Q\lor \ \neg Q))\ \lor \ (P\And Q\land (R\lor \ \neg R))$

$\equiv \ (P\And R\And \top )\ \lor \ (P\And Q\And \top )$

$\equiv \ (P\And R)\ \lor \ (P\And Q)$

$\equiv \ P\And (R\lor Q)$

결론적으로 이 이 위원회는 "위원장이 찬성하고 두 위원 중 한 명이 찬성하면 그 의제는 찬성 결론이 난다.

$F(P,Q,R):=P\And (R\lor Q)$

연산을 바꿔 표현하기

$P\leftrightarrow \ Q\ \equiv \ (P\rightarrow Q)\And (Q\rightarrow P)$

$P\rightarrow Q\ \equiv \ \neg P\lor Q$

$(P\And Q)\ \equiv \ \neg (\neg P\lor \neg Q)$

$(P\lor Q)\ \equiv \ \neg (\neg P\And \neg Q)$

$P\leftrightarrow Q\ \equiv \ (P\rightarrow Q)\And (Q\rightarrow R)$

$\equiv (\neg P\lor Q)\And (\neg Q\lor P)$

$\equiv ((\neg P\lor Q)\And \neg Q)\lor ((\neg P\lor Q)\And P)$

$\equiv ((\neg P\And \neg Q)\lor (Q\And \neg Q))\lor ((\neg P\And P)\lor (Q\And P))$

$\equiv (\neg P\And \neg Q)\lor \bot \lor \bot \lor (Q\And P)$

$\equiv (\neg P\And \neg Q)\lor (Q\And P)$

Note

Math : Math글쓰기 | Math번역 | MathBoard | Math&Culture | MathMoim
OnLineMathCenter | MathCamp | SoftMathJournal | MathBook | CyberAcademia | Academia