In the book by Artificial Intelligence by Norvig and Russel, I came across following problem:
Prove if correct: $(A ∧ B) \models (A ⇔ B).$
I quickly interpreted $\models$ as $\implies$ and tried to prove it using the truth table:
It seems that at least while interpreting $\models$ as $\implies$, the statement is true. Then I gave second thought and did some more reading to come across this thread. Now I know that the two are not same. But, it turns out, when we don't interpret $\models$ as $\implies$, the statement is still true (my course TA uploaded answers without proof).
So I am wondering:
Q1. How exactly the given statement is correct (given that $\models$ and $\implies$ are not same)?
Q2. Is my method to interpret both same and then forming truth table, a correct method for such problems? If not then how I should solve it?
Q3. If answer to Q2 is no, then will above method of interpreting $\models$ as $\implies$ and forming truth table always given correct answer? If not, when it will fail to give correct answer?
Q4. I also tried to solve the same using resolution:
$$\neg (A\Longleftrightarrow B)\equiv \neg((A\wedge B)\vee(\neg A\wedge\neg B))\equiv\neg(A\wedge B)\wedge \neg(\neg A\wedge \neg B)\equiv (\neg A\vee\neg B)\wedge (A \vee B)$$ So my clauses will be:
- $A$ (from $A\wedge B$)
- $B$ (from $A\wedge B$)
- $(\neg A\vee\neg B)$ from $(\neg A\vee\neg B)\wedge (A \vee B)$
- $(A \vee B)$ from $(\neg A\vee\neg B)\wedge (A \vee B)$
So I was able to derive empty clause, so my assumption $\neg (A\Longleftrightarrow B)$ was incorrect. So $(A ∧ B) \implies (A ⇔ B)$. Will application of resolution technique for $\models$ be exactly same?
[This is my updated understanding based on Graham's answer]
(a) After reading Graham's answer, I felt that the truth table above is proving the "tautology" $(A ∧ B) \implies (A ⇔ B)$, but not $(A ∧ B) \models (A ⇔ B)$.
(b) To prove $(A ∧ B) \models (A ⇔ B)$, I need another truth table, something like this:
(c) Also, I guess the resolution technique is used to prove tautology $(A ∧ B) \implies (A ⇔ B)$ and not $(A ∧ B) \models (A ⇔ B)$. However, I feel we can use the (first) truth table and resolution proving $\implies$ to also prove $\models$, because of the following fact:
$\varphi\vDash \psi$ iff $M(\varphi)\subseteq M(\psi)$: that is, iff every truth assignment that makes $\varphi$ true also make $\psi$ true. This is the case iff $\vDash \varphi\Rightarrow\psi$, i.e., if the formula $\varphi\Rightarrow\psi$ is true in all truth assignments (is a tautology). - source
Can someone please confirm if my understanding in the above points is correct?