2 minutes
Notes on Logic
In logic a statement is a declarative sentence that is either true or false.
Contrapositive
Given a statement of the form:
$$ \text{if} \ A, \ \text{then} \ B$$
also written as:
$$ A \implies B $$ Read as \(A\) implies \(B\). Such an implication statement is only considered false if the predicate \(A\) is true and the predicate \(B\) is false, otherwise it is true.
The contrapositive is defined to be:
$$ \text{If} \ B \ \text{is not true}, \ \text{then} \ A \text{ is not true} $$ or, $$ \overline{B} \implies \overline{A} $$
A statement and its contrapositive are logically equivalent.
if the statement $$A \implies B$$ is false, then \(A\) is true and \(B\) is false, otherwise the statement is true. Similarly, if $$ \overline{B} \implies \overline{A}$$ is false, then \(\overline{B}\) is true \((B\) is false) and \(\overline{A}\) is false (\(A\) is true), otherwise the statement is true.
Converse
The converse of the statement $$ A \implies B $$ is the statement: $$ B \implies A $$
Unlike with the contrapositive, a statement and its converse are not necessarily the same, e.g., the statement:
If a function is differentiable, then it is continuous
is true, but the converse isn’t.
iff
iff stands for “if and only if” and has logical symbol\(\iff\). If \(A \implies B \) is true and its converse \(B \implies A \) is also true, then we write \(A \iff B \), meaning \(A\) holds if and only if \(B\) holds.
Negation of logical quantifiers
The two logical quantifiers are: “for every (\(\forall\))” and “there exists (\(\exists\))”
The negation of the statement: $$ \forall \ x \in X, \ \text{statement} \ A \ \text{holds}$$ is $$ \exists \ x \in X, \ \text{statement} \ A \ \text{doesn’t hold}$$ and vice versa, for a given set \(X\) and a statement \(A\).