Truth Tables

Negation

Truth Table

A	B	A $\land$ B	A $\lor$ B
True	True	True	True
True	False	False	True
False	True	False	True
False	False	False	False

The $\land$ acts as “AND” and it is False when there is at least one False, and True otherwise.
The $\lor$ acts as “OR” and it is True when there is at least one True, and False otherwise.

$\lnot$ denotes a “NOT” sign

A	B	$\lnot$A
True	True	False
True	False	False
False	True	True
False	False	True

De Morgan’s Laws:

Law 1:

$\lnot$ ($\lnot$ A) = A

Law 2:

($\lnot$A)∨($\lnot$B) ≡ $\lnot$(A ∧ B)
($\lnot$A)∧($\lnot$B) ≡ $\lnot$(A ∨ B)

Law 3:

(A ∧ B) ∧ C ≡ A ∧ (B ∧ C)
(A ∨ B) ∨ C ≡ A ∨ (B ∨ C)
associativity law

Proving Law 2

Start out with: $\lnot$(($\lnot$A)∧($\lnot$B))
$\lnot$(($\lnot$A)∧($\lnot$B)) ≡ ($\lnot$($\lnot$A))∨($\lnot$($\lnot$B))
The ($\lnot$A)∧($\lnot$B) undergoes negation
≡ (A) ∨ (B)
This yields just (A) ∨ (B)

Knowing Law 1
($\lnot$A)∧($\lnot$B) ≡ $\lnot$($\lnot$($\lnot$A)∧($\lnot$B))) ≡ $\lnot$(A ∨ B)

By negating (A) ∨ (B), we can get: ($\lnot$A)∧($\lnot$B) ≡ $\lnot$(A ∨ B)

Implication

Hypothesis: If … then

Conclusion: then…

A	B	A $\Rightarrow$ B
True	True	True
True	False	False
False	True	True
False	False	True

If A, then B

Think of this like “If you give me $100, I will give you $200 tomorrow.” The implication is similar to if I keep my promise in this situation.

If the hypothesis is correct (I gave you $100 to begin with), then the implication is true if I give you back $200 tomorrow, or false I accept the money and do not give you back the money.

The hypothesis is false if you do not give me $100. I may give you $200 regardless tomorrow, making the implication true.

The hypothesis can also be false if you do not give me money, and I give you no money. In this case, the implication is also true.

Here are four implications. Only one is false. Identify the false implication.

If x is a real number and $x^2$ < 0, then $x^4$ ≥ 0.
If x is a real number and $x^2$ < 0 then $x^4$ < 0.
If n is a positive integer, then $n^2$ +13 is not a perfect square.
If n is an integer and $2^{2n}$ is an odd integer, then $2^{−2n}$ is an odd integer.

Only the implication “If n is a positive integer, then $n^2$ + 13 is not a perfect square.” is false.