Are ~(p and q) and ~p or ~q equivalent Easy

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 this sign as and.

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

So it is T only in row 1.

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 F only in row 1.

4 Column for ¬p and ¬q

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

So it is T only in rows 3 and 4.

¬q is the opposite of q too.

5 Column for ¬p ∨ ¬q

We read this sign as or.

¬p ∨ ¬q is true when at least one of them is true.

It is false only when both are false.

So it is F only in row 1.

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, T, T and F, T, T, T.

This is De Morgan's law: the not goes onto each part, and the sign in the middle swaps.

Careful!

The not goes onto each part, and the and turns into or.

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 ¬p and ¬q.

Then: column for ¬p ∨ ¬q.

Then: compare the columns.

Last: check.

▶ Watch it solved

Are ~(p and q) and ~p and ~q equivalent Medium

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 this sign as and.

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

So it is T only in row 1.

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 F only in row 1.

4 Column for ¬p and ¬q

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

So it is T only in rows 3 and 4.

¬q is the opposite of q too.

5 Column for ¬p ∧ ¬q

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

So it is T only in row 4.

6 Compare the columns

Now compare the two last columns.

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

Row by row: the same, until row 2.

In row 2, one is T and the other is F.

One row is enough: they are not the same.

Careful!

When the not goes onto each part, the sign in the middle must swap.

That is De Morgan's law.

So they are not equivalent.

Row 2 shows it.

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 F.

Different, 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 ¬p and ¬q.

Then: column for ¬p ∧ ¬q.

Then: compare the columns.

Last: check.

▶ Watch it solved

Is p and (q or r) equivalent to (p and q) or (p and r) Harder

The question

Question: are p ∧ (q ∨ r) and (p ∧ q) ∨ (p ∧ r) equivalent?

1 Rows for p, q and r

Each letter can be true or false.

Three letters give 2 × 2 × 2 = 8 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: two T, two F, and again.

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

2 Column for q ∨ r

We read this sign as or.

q ∨ r is true when at least one of them is true.

It is false only when both are false.

So it is F only in rows 4 and 8.

3 Column for p ∧ (q ∨ r)

We read this sign as and.

p ∧ (q ∨ r) is true only when p and q ∨ r are both true.

So it is T only in rows 1, 2 and 3.

4 Column for p ∧ q

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

So it is T only in rows 1 and 2.

5 Column for p ∧ r

p ∧ r is true only when p and r are both true.

So it is T only in rows 1 and 3.

6 Column for (p ∧ q) ∨ (p ∧ r)

(p ∧ q) ∨ (p ∧ r) is true when at least one of them is true.

It is false only when both are false.

So it is T only in rows 1, 2 and 3.

7 Compare the columns

Now compare the two last columns.

p ∧ (q ∨ r) in red, (p ∧ q) ∨ (p ∧ r) in purple.

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

This is the distributive law, like opening brackets.

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 ∨ r) ≡ (p ∧ q) ∨ (p ∧ r).

8 Check

Let's check row 2 by hand.

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

The first: T ∧ (T ∨ F) gives T.

And the second: (T ∧ T) ∨ (T ∧ F) gives T.

The same, as the table says.

Right!

Let's look back.

First: rows for p, q and r.

Then: column for q ∨ r.

Then: column for p ∧ (q ∨ r).

Then: column for p ∧ q.

Then: column for p ∧ r.

Then: column for (p ∧ q) ∨ (p ∧ r).

Then: compare the columns.

Last: check.

▶ Watch it solved