GATE CS 2006 Q28 — Propositional and First Order Logic

To find the expression equivalent to $A \wedge B$, let us first determine the logical formula for the binary operator $\odot$ from the given truth table:

Observe that $A \odot B$ is False only when $A$ is False and $B$ is True. This corresponds to the implication $B \rightarrow A$, which can be written as:

Now, let us evaluate the given options using this equivalence:

• Option A: $(\sim A \odot B)$ $$\sim A \odot B \equiv \sim A \vee \sim B \equiv \sim(A \wedge B)$$
• Option B: $\sim(A \odot \sim B)$ $$A \odot \sim B \equiv A \vee \sim(\sim B) \equiv A \vee B$$ $$\text{Thus, } \sim(A \odot \sim B) \equiv \sim(A \vee B)$$
• Option C: $\sim(\sim A \odot \sim B)$ $$\sim A \odot \sim B \equiv \sim A \vee \sim(\sim B) \equiv \sim A \vee B$$ $$\text{Thus, } \sim(\sim A \odot \sim B) \equiv \sim(\sim A \vee B) \equiv A \wedge \sim B$$
• Option D: $\sim(\sim A \odot B)$ $$\sim A \odot B \equiv \sim A \vee \sim B$$ $$\text{Thus, } \sim(\sim A \odot B) \equiv \sim(\sim A \vee \sim B) \equiv A \wedge B \quad \text{(by De Morgan's Law)}$$

Therefore, Option D is equivalent to $A \wedge B$.