(A ⇔ B) ∧ (¬A ∨ B) is it satisfyable ? Artificial intelligence a modern approach by norvig

Question

Hi I am not able to solve this question, it's from book artificial intelligence a modern approach by Norvig and peter. Help would be appreciated.

Answer 1

Yes, the expression $(A \iff B) \land (\lnot A \lor B)$ is satisfiable. Consider the case where $A$ and $B$ are both true.

The first conjunct $A \iff B$ means that, if there is a satisfying assignment, it must assign the same truth value to $A$ and $B$ .

First consider what happens if $A$ and $B$ are both true, then $\lnot A \lor B$, which is equivalent to $A \implies B$, is also true.

We already found a satisfying assignment, but let's also note that assigning $A$ and $B$ to false also results in $(A \iff B) \land (\lnot A \lor B)$ being true.

One way of convincing yourself that this is true is to notice that $A \iff B$ is equivalent to $(A \implies B) \land (B \implies A)$ and that $\lnot A \lor B$ is equivalent to $(A \implies B)$ .

Therefore the entire expression is equivalent to

$$ (A \implies B) \land (B \implies A) $$

Which is equivalent to simply

$$ A \iff B $$