¬(p∧q), prove (¬p∨¬q).
This is done by a truth table.
1. Negation: Rule for ¬x is: If x has a T, then ¬x has
an F and vice-versa.
2. Conjunction: Rule for x∧y is: If x and y both have
T's, x∧y has T, otherwise x∧y has F.
3. Disjunction: Rule for x∨y is: If x and y both have
F's, x∨y has F, otherwise x∨y has T.
4. Biconditional: Rule for x<->y is: If both x and y
have the same truth value, x<->y has T, otherwise F.
You need headings as listed below:
p | q | ¬p | ¬q | p∧q | ¬(p∧q) | ¬p∨¬q | ¬(p∧q) <-> (¬p∨¬q) |
---------------------------------------------------------------
T | T | F | F | T | F | F | T |
T | F | | | | | | |
F | T | | | | | | |
F | F | | | | | | |
The F under ¬p is because there is a T under p, rule 1 above.
The F under ¬q is because there is a T under q, rule 1 above.
The T under p∧q is because there is a T under both p and q,
rule 2 above.
The F under ¬(p∧q) is because there is a T under p∧q,
rule 1 above.
The F under ¬p∨¬q is because ¬p and ¬q both have F's
rule 3 above.
The T under ¬(p∧q) <-> (¬p∨¬q) is because both ¬(p∧q) and (¬p∨¬q)
have the same truth value F, rule 4
Now we fil in the next row:
p | q | ¬p | ¬q | p∧q | ¬(p∧q) | ¬p∨¬q | ¬(p∧q) <-> (¬p∨¬q) |
---------------------------------------------------------------
T | T | F | F | T | F | F | T |
T | F | F | T | F | T | T | T |
F | T | | | | | | |
F | F | | | | | | |
The F under ¬p is because there is a T under p, rule 1 above.
The T under ¬q is because there is a F under q, rule 1 above.
The F under p∧q is because p and q don't both have T's, rule 2
above.
The T under ¬(p∧q) is because there is a F under p∧q,
rule 1 above.
The T under ¬p∨¬q is because ¬p and ¬q don't both have F's
rule 3 above.
The T under ¬(p∧q) <-> (¬p∨¬q) is because both ¬(p∧q) and (¬p∨¬q)
have the same truth value T, rule 4
Now we fil in the third row:
p | q | ¬p | ¬q | p∧q | ¬(p∧q) | ¬p∨¬q | ¬(p∧q) <-> (¬p∨¬q) |
---------------------------------------------------------------
T | T | F | F | T | F | F | T |
T | F | F | T | F | T | T | T |
F | T | T | F | F | T | T | T |
F | F | | | | | | |
The T under ¬p is because there is a F under p, rule 1 above.
The F under ¬q is because there is a T under q, rule 1 above.
The F under p∧q is because p and q don't both have T's, rule 2
above.
The T under ¬(p∧q) is because there is a F under p∧q,
rule 1 above.
The T under ¬p∨¬q is because ¬p and ¬q don't both have F's
rule 3 above.
The T under ¬(p∧q) <-> (¬p∨¬q) is because both ¬(p∧q) and (¬p∨¬q)
have the same truth value T, rule 4
Now we fill in the fourth row:
p | q | ¬p | ¬q | p∧q | ¬(p∧q) | ¬p∨¬q | ¬(p∧q) <-> (¬p∨¬q) |
---------------------------------------------------------------
T | T | F | F | T | F | F | T |
T | F | F | T | F | T | T | T |
F | T | T | F | F | T | T | T |
F | F | T | T | F | T | T | T |
The T under ¬p is because there is a F under p, rule 1 above.
The T under ¬q is because there is a F under q, rule 1 above.
The F under p∧q is because p and q don't both have T's, rule 2
above.
The T under ¬(p∧q) is because there is a F under p∧q,
rule 1 above.
The T under ¬p∨¬q is because ¬p and ¬q don't both have F's
rule 3 above.
The T under ¬(p∧q) <-> (¬p∨¬q) is because both ¬(p∧q) and (¬p∨¬q)
have the same truth value T, rule 4.
Now since there are only T's in the last column, that proves that
in every case, the biconditional ¬(p∧q) <-> (¬p∨¬q) is
true and therefore ¬(p∧q) and (¬p∨¬q) are equivalent
because the biconditional is a tautology.
Edwin
