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.

  1. If x is a real number and \(x^2\) < 0, then \(x^4\) ≥ 0.
  2. If x is a real number and \(x^2\) < 0 then \(x^4\) < 0.
  3. If n is a positive integer, then \(n^2\) +13 is not a perfect square.
  4. 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.