Please help to transform a propositional formula to a particular equivalent formula

Question

My homework is to transform this formula

$$(A \wedge \neg B) \wedge (A \vee \neg C)$$ into this equivalent form: $A \wedge \neg B$. Do you have any ideas?

Answer 1

The 'correct' transformation depends on what rules you have ....

Here is a transformation that uses pretty elementary equivalence principles:

$$(A \wedge \neg B) \wedge (A \vee \neg C)$$

$$\overset{Commutation}{=}$$

$$(\neg B \land A) \wedge (A \vee \neg C)$$

$$\overset{Association}{=}$$

$$\neg B \land (A \wedge (A \vee \neg C))$$

$$\overset{Identity}{=}$$

$$\neg B \land ((A \lor \bot) \wedge (A \vee \neg C))$$

$$\overset{Distribution}{=}$$

$$\neg B \land (A \lor (\bot \land \neg C))$$

$$\overset{Annihilation}{=}$$

$$\neg B \land A$$

$$\overset{Commutation}{=}$$

$$A \land \neg B$$

If you are given

Absorption

$A \land (A \lor B) = A$

then you canuse that to go from $$\neg B \land (A \wedge (A \vee \neg C))$$ to $$\neg B \land A$$ in one step

Answer 2

Note that $A\land\neg B\to A$ and $A\to A\lor\neg C$, so your original statement is equivalent to $A\land\neg B$ by repeated use of $(p\to q)\to((p\land q)\equiv p)$.