Question

Use a truth table to verify the first De Morgan law ¬(p ∧ q) ≡ ¬p ∨ ¬q.

Answer 1

Answer:

p q output ¬(p ∧ q)

0 0 1

0 1 1

1 0 1

0 0 0

p q output ¬p ∨ ¬q

0 0 1

0 1 1

1 0 1

0 0 0

Explanation:

We'll create two separate truth tables for both sides of the equation, and see if they match.

The expressions in the question use AND, OR and NOT operators.

1. The AND operation needs both inputs to be 1 to return a 1.
2. The OR operation needs at least 1 of the inputs to be 1 to return a 1.
3. The NOT operation takes a 1 and turns it into a 0, or takes a 0 and turns it into a 1.

Let's start with ¬(p ∧ q)

• NOT (0 AND 0) = NOT (0) = 1
• NOT (0 AND 1) = NOT (0) = 1
• NOT (1 AND 0) = NOT (0) = 1
• NOT (1 AND 1) = NOT (1) = 0

Now let's move on to the second expression ¬p ∨ ¬q

• NOT(0) OR NOT(0) = 1 OR 1 = 1
• NOT(0) OR NOT(1) = 1 OR 0 = 1
• NOT(1) OR NOT(0) = 0 OR 1 = 1
• NOT(0) OR NOT(0) = 0 OR 0 = 0

Therefore we can say the two expressions are equivalent.