Propositions
- Tags
- logic
Sentences or expressions which are either true or false.
Can be [see page 27, subdivided] into:
- Atomic Propositions: statements that can only be either true or false.
For example my dog has 2 eyes.
- Compound Propositions: States the relationship between propositions.
For example I've got black hair AND I've got brown eyes.
Propositional Connectives
Are the operations of propositional logic which operates on or between
propositional variables.
Each connective has its own semantic meaning.
Table 1:
Listing of the basic propositional connectives in order of highest precedence first.
| Connective | expression | Description |
|---|
| [see page 34, Negation] | \( \neg p \) | The proposition \( p \) is false. |
| [see page 38, Conjunction] | \( p \land q \) | Both \( p \) and \( q \) is true. |
| [see page 36, Disjunction] | \( p \lor q \) | Either \( p \) is true or \( q \) is true or both. |
| [see page 40, Implication] | \( p \implies q \) | \( p \) implies \( q \) (AKA if \( p \) then \( q \)). |
| [see page 14, Equivalence] | \( p \iff q \) | \( p \) if and only if \( q \). |
| Rule | LHS | RHS | Description |
|---|
| Law of Double Negation | \( \neg (\neg p) \) | \( p \) | Double negation cancels out. |
| Law of Excluded Middle | \( p \lor \neg p \) | true | A proposition is always either true or false. |
| \( p \land \neg p \) | false | |
| Law of Conjunction | \( p \land \neg p \) | false | Something cannot be both true and false. |
| Contrapositive | \( p \implies q \) | \( \neg q \implies \neg p \) | If \( q \) is false then \( p \) cannot possibly be true. |
| Material Implication | \( p \implies q \) | \( \neg p \lor q \) | \( q \) can be true if \( p \) is false, but not vice versa. |
| Law for equivalence | \( p \iff q \) | \( (p \implies q) \land (q \implies p) \) | \( p \) implies \( q \) and \( q \) implies \( p \). |
| Commutativity | \( p \lor q \) | \( q \lor p \) | |
| Associativity | \( p \lor (q \lor r) \) | \( (p \lor q) \lor r \) | |
| \( p \land (q \land r) \) | \( (p \land q) \land r \) | |
| Idempotence | \( p \lor p \) | \( p \) | |
| \( p \land p \) | \( p \) | |
| Distributivity | \( p \lor (q \land r) \) | \( (p \lor q) \land (p \lor r) \) | |
| \( p \land (q \lor r) \) | \( (p \land q) \lor (p \land r) \) | |
| De Morgan's Laws | \( \neg (p \lor q) \) | \( \neg p \land \neg q \) | |
| \( \neg (p \land q) \) | \( \neg p \lor \neg q \) | |
| Tautology Laws | \( p \lor \text{true} \) | true | |
| \( p \and \text{true} \) | \( p \) | |
| Contradiction Laws | \( p \lor \text{false} \) | \( p \) | |
| \( p \land false \) | false | |
| Absorption Laws | \( p \lor (p \land q) \) | \( p \) | |
| \( p \land (p \lor q) \) | \( p \) | |
Truth Tables
Are a way to exhaustively list the value of an proposition based on the complete
list of permutations of its dependants.
If the truth table of two propositional expressions have the same final column
then the two expression are said to be equivalent.
| \( p \) | \( q \) | \( p \lor q \) |
|---|
| F | F | F |
| F | T | T |
| T | F | T |
| T | T | T |
| \( p \) | \( q \) | \( p \land q \) |
|---|
| F | F | F |
| F | T | F |
| T | F | F |
| T | T | T |
| \( p \) | \( q \) | \( p \implies q \) |
|---|
| F | F | T |
| F | T | T |
| T | F | F |
| T | T | T |
Note: The truth table for implication (tbl:truth-imp) might be a bit
confusing.
Recall that implication is an if condition then body relation. When the condition
fails then the body is never run, which corresponds to the false case above. But
in the cases where \( p \) is false, we don't know what \( q \) is. It could be
true, or it could be false but the implication can't guarantee either way so it
leaves the possibility that it is true open and evaluates to true as a whole.
To put it another way the expression \( p \implies q \) could also be [see page 13, read] as
\( p \) is false OR \( q \) is true.
| \( p \) | \( q \) | \( p \iff q \) |
|---|
| F | F | T |
| F | T | F |
| T | F | F |
| T | T | T |