Logic
Definition: a statement is a sentence that is either true or false, never both.
Definition - Logical operators: let \(A\) and \(B\) be assertions.
- The assertion \(A\) and \(B\) (\(A \land B\)) is true, iff both \(A\) and \(B\) are true.
- The assertion \(A\) or \(B\) (\(A \lor B\)) is true, iff at least one of \(A\) and \(B\) is true.
- The negation of \(A\) (\(\neg A\)) is true iff \(A\) is false.
Definition - Implies: if \(A\) and \(B\) are assertions then the assertion if \(A\) then \(B\) (\(A \implies B\)) is true iff
- \(A\) is true and \(B\) is true,
- \(A\) is false and \(B\) is true,
- \(A\) is false and \(B\) is false.
This also works the opposite way, if \(B\) then \(A\) (\(A \Longleftarrow B\))
Definition - If and only if: if \(A\) and \(B\) are assertions then the assertion \(A\) if and only if \(B\) (A \iff B) is true iff
- \((A \Longleftarrow B) \land (a \implies B)\).
This leads to the following table.
| \(A\) | \(B\) | \(A \implies B\) | \(A \Longleftarrow B\) | \(A \iff B\) |
|---|---|---|---|---|
| true | true | true | true | true |
| true | false | false | true | false |
| false | true | true | false | false |
| false | false | true | true | true |
Definition: suppose \(P\) and \(Q\) are assertions. \(P\) implies \(Q\) if \(P \implies Q\) is true. \(P\) and \(Q\) are equivalent if \(P\) implies \(Q\) and \(Q\) implies \(P\).
Methods of proof
Direct proof: for proving \(P \implies Q\) only consider the case where \(P\) is true.
Proof by contraposition: proving \(P \implies Q\) to be true by showing that \(\neg Q \implies \neg P\) is true.
Proof by contradiction: using the equivalence of \(P \implies Q\) and \(\neg Q \implies \neg P\) by assuming \(P\) is not true and deducing a contradiction with some obviously true statement \(Q\).
Proof by cases: dividing a proof into cases which makes use of the equivalence of \((P \lor Q) \implies R\) and \((P \implies R) \land (Q \implies R)\). Which together cover all situations under consideration.