Are ~(p -> q) and p and ~q equivalent

Step by step

The question

Question: are ¬(p → q) and p ∧ ¬q equivalent?

1 Rows for p and q

Each letter can be true or false.

Two letters give 2 × 2 = 4 rows: every way they can go.

We make a table: a column for each letter, then a column for each part, from the inside out.

We write T for true and F for false.

p: the first half T, the second half F.

This way no row is missed.

q: T, F, T, F, down the column.

2 Column for p → q

We read the arrow as if, then.

p → q is a promise: if p, then q.

It is broken only when p is true and q is false.

So it is F only in row 2.

3 Column for ¬(p → q)

We read this sign as not.

¬(p → q) is the opposite of p → q: T becomes F, F becomes T.

So it is T only in row 2.

4 Column for ¬q

¬q is the opposite of q: T becomes F, F becomes T.

So it is T only in rows 2 and 4.

5 Column for p ∧ ¬q

We read this sign as and.

p ∧ ¬q is true only when p and ¬q are both true.

So it is T only in row 2.

6 Compare the columns

Now compare the two last columns.

¬(p → q) in red, p ∧ ¬q in purple.

Row by row they are the same: F, T, F, F and F, T, F, F.

So the opposite of an if-then is an and, not another if-then.

Careful!

To be equivalent they must match in every row.

One row that differs is enough to say no.

So they are equivalent.

We write ¬(p → q) ≡ p ∧ ¬q.

7 Check

Let's check row 2 by hand.

In row 2, p is true and q is false.

The first: ¬(T → F) gives T.

And the second: T ∧ ¬F gives T.

The same, as the table says.

Right!

Let's look back.

First: rows for p and q.

Then: column for p → q.

Then: column for ¬(p → q).

Then: column for ¬q.

Then: column for p ∧ ¬q.

Then: compare the columns.

Last: check.