Logically Equivalent
논리적 동치
- \(P \leftrightarrow Q\) 가 Tautology(항진명제)이면, \(P\), \(Q\)는 "논리적으로 동치"라 표현한다.
- "\(P \iff Q\)" 또는 "\(P \equiv Q\)"라 표기한다.
ex) \(\neg (P \lor Q) \iff \neg P \land \neg Q \qquad (De Morgan`s Laws)\)
ex) \(P \to Q \iff \neg P \lor Q\)
* 논리적 동치 관계의 증명
1. 진리표를 이용하는 방법 : 변수의 개수가 증가함에 따라 결과가 기하급수적으로 증가하는 문제가 있다.
2. 기증명된 논리적 동치관계를 이용해서 증명하는 방법
Sample QUIZ
Q.1 Prove the proposition "\((P \to Q) \iff \neg P \lor Q\)" by truth table.
\(pf)\)
| \(P\) | \(Q\) | \(\neg P\) | \(\neg P \lor Q\) | \(P \to Q\) |
| \(T\) | \(T\) | \(F\) | \(T\) | \(T\) |
| \(T\) | \(F\) | \(F\) | \(F\) | \(F\) |
| \(F\) | \(T\) | \(T\) | \(T\) | \(T\) |
| \(F\) | \(F\) | \(T\) | \(T\) | \(T\) |
\(\mathrm{As\ you\ can\ see\ that\ truth\ table,\ the\ truth\ values\ of}\ \neg P \lor Q\ \mathrm{and}\ P \to Q\ \mathrm{are\ the\ same.}\)
\(\therefore (P \to Q) \equiv \neg P \lor Q\)
Q.2 Prove that "\(\neg (P \lor (\neg P \land Q)) \iff \neg P \land \neg Q\)" is true.
Logically Equivalent
논리적 동치
- \(P \leftrightarrow Q\) 가 Tautology(항진명제)이면, \(P\), \(Q\)는 "논리적으로 동치"라 표현한다.
- "\(P \iff Q\)" 또는 "\(P \equiv Q\)"라 표기한다.
ex) \(\neg (P \lor Q) \iff \neg P \land \neg Q \qquad (De Morgan`s Laws)\)
ex) \(P \to Q \iff \neg P \lor Q\)
* 논리적 동치 관계의 증명
1. 진리표를 이용하는 방법 : 변수의 개수가 증가함에 따라 결과가 기하급수적으로 증가하는 문제가 있다.
2. 기증명된 논리적 동치관계를 이용해서 증명하는 방법
Sample QUIZ
Q.1 Prove the proposition "\((P \to Q) \iff \neg P \lor Q\)" by truth table.
\(pf)\)
| \(P\) | \(Q\) | \(\neg P\) | \(\neg P \lor Q\) | \(P \to Q\) |
| \(T\) | \(T\) | \(F\) | \(T\) | \(T\) |
| \(T\) | \(F\) | \(F\) | \(F\) | \(F\) |
| \(F\) | \(T\) | \(T\) | \(T\) | \(T\) |
| \(F\) | \(F\) | \(T\) | \(T\) | \(T\) |
\(\mathrm{As\ you\ can\ see\ that\ truth\ table,\ the\ truth\ values\ of}\ \neg P \lor Q\ \mathrm{and}\ P \to Q\ \mathrm{are\ the\ same.}\)
\(\therefore (P \to Q) \equiv \neg P \lor Q\)
Q.2 Prove that "\(\neg (P \lor (\neg P \land Q)) \iff \neg P \land \neg Q\)" is true.
