4
$\begingroup$

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:

enter image description here

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)$

enter image description here

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?

Update

[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: enter image description here

(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?

$\endgroup$

2 Answers 2

3
$\begingroup$

$\mathcal A \vDash \varphi$ says: "statement $\varphi$ is a semantic consequence of the list of statements $\mathcal A$ (often called the premises, or assumptions)" and a semantic consequence must be true when all the premises are interpreted as true. [Note: this list may be of zero, one, or several statements.]

In propositional logic, you can use a truth table to establish such a semantic consequence: and $(A\land B)\vDash(A\leftrightarrow B)$ since indeed "every assignment that values $A\land B$ as true will also value $A\leftrightarrow B$ as true," will be shown by a table of every assignment of $A,B$ and the corresponding evaluations of the statements.

$$\boxed{\begin{array}{c4|c}A&B & A\land B& A\leftrightarrow B\\\hline\top&\top &\top &\top&\star\\\top&\bot&\bot &\bot\\\bot&\top&\bot&\bot\\\bot&\bot&\bot&\top\\\end{array}}\\\text{the consequent is true in the only row where the premise is true}$$

[Note: the trend this century is to use single bar arrows, $\to,\leftrightarrow$, for logical connectives, and double edge for metalogic inferences, though not all authors do so.]


$(A\land B)\to(A\leftrightarrow B)$ is a statement, and moreover one which is a tautology.   That means that it is a logical consequence of no premises at all. Thus:$$\vDash (A\land B)\to(A\leftrightarrow B)$$

This can also be demonstrated by a truth table, where we show that "every assignment of $A,B$ will value the whole statement as true."

$$\boxed{\begin{array}{c4|c}A&B & (A\land B)\to(A\leftrightarrow B)\\\hline\top&\top &\top\\\top&\bot&\top\\\bot&\top&\top\\\bot&\bot&\top\\\end{array}}\\\text{the consequent is true in every row}$$

That is not exactly the same test, but it is clearly the case that where one works the other will too.


It should be noted, truth tables work as semantic proofs only in classic propositional logic. They are less applicable in higher order logics, modal logics, among others.

$\endgroup$
4
  • $\begingroup$ Hi, I have understood some points after reading your answer. I have added this understanding at the end of the original question as an update. Can you please confirm if this understanding is correct? $\endgroup$
    – Mahesha999
    Feb 18, 2021 at 3:46
  • $\begingroup$ No, truth tables can prove semantic entailment for other than tautologies, in propositional logic. Semantic entailment is proven when you demonstrate that "Every model where the premises are valued true will also value the consequent as true." Truth tables do this by listing every possible valuation of the literals, and corresponding valuation of the propositions. $\quad$ PS: Resolution also proves this by establishing that a contradiction occurs when valuing the premises as true and the consequent as false. $\endgroup$ Feb 18, 2021 at 4:28
  • $\begingroup$ They are just different tables: with different premises and consequent. $\endgroup$ Feb 18, 2021 at 4:41
  • $\begingroup$ However, the resolution process for both semantics does have the same conjunctive normal form for the premise-and-negated-consequent list. $\endgroup$ Feb 18, 2021 at 4:52
1
$\begingroup$

(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: enter image description here

To be absolutely clear: the difference is this (here, $\psi$ and $\theta$ are compound propositional formulae):

  1. using a truth table to verify that $(\psi\to \theta)$ is a tautology: construct the truth table of $(\psi\to \theta),$ then verify that the column with the main connective is filled only with 1's;
  2. using a truth table to verify that $(\psi\models \theta):$ construct a truth table containing both $\psi$ and $\theta,$ then verify that in every row where $\psi$ has value 1, $\theta$ also has value 1.

(1) and (2) are equivalent (the Deduction Theorem and its converse formally justifies this).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .