Propositional Logic
Propositions
A proposition is a statement that either true or false. The reason we have propositions is so that we can write math in an unambiguous way.
Things that are Propositions
Some examples of propositions are:
- An octagon has 12 sides. (false)
- My name is Jackson. (true)
- if \(a, b, c\) satisfy \(a^2 + b^2 = c^2\) then they can make a right triangle. (true)
Things that are not Propositions
However there are things that aren’t propositions, this fall into a few categories:
- Opinions
- Bread is good.
- Question
- What is the weather today?
- Commands / Exclamations
- Do ten jumping jacks!
- Contradictions
- This statement is false.
Propositional Logic Operators
If we have \(p\) and \(q\), both of which are propositions. If we wanted to combine these things we could use a lot of different statements.
- AND (\(\land\))
- \(p \land q\) will only will only be true if both \(p\) and \(q\) are true.
- OR (\(\lor\))
- \(p \lor q\) will be true when either \(p\) or \(q\) are true.
- NOT (\(\neg\))
- \(\neg p\) will be the opposite of \(p\).
- XOR (\(\oplus\))
- The “exclusive or” is the opposite of the Biconditional. \(p \oplus q = \neg(p \Leftrightarrow q)\).
- NAND (\(|\))
- This is the opposite of
AND. So \(p | q = \neg ( p \land q )\).
Truth Tables
When dealing with a complicated combination of propositions, the easiest way to handle it is with a truth table.
For example say we had the expression \((p \lor \neg q) \land (\neg (q \lor r))\), and we wanted to know which vales of \(p\), \(q\) and \(r\) made it true. To figure this out, we could make a truth table.
| \(p\) | \(q\) | \(r\) | \(q \lor r\) | \(\neg (q \lor r)\) | \(\neg q\) | \(p \lor \neg q\) | \((p \lor \neg q) \land (\neg (q \lor r))\) |
|---|---|---|---|---|---|---|---|
| T | T | T | T | F | F | T | F |
| T | T | F | T | F | F | T | F |
| T | F | T | T | F | T | T | F |
| T | F | F | F | T | T | T | T |
| F | T | T | T | F | F | F | F |
| F | T | F | T | F | T | T | F |
| F | F | T | T | F | T | T | F |
| F | F | F | F | T | T | T | T |
So the answer to this problem would be the rightmost column of the truth table.
There are different types of truth tables that we can classify:
- Tautology
- A tautology is a propositional statement that is always true.
- Contradiction
- A contradiction is a propositional statement that is always false.
- Contingency
- A contingency depends on its input.
Implication
This is essentially an if then statement.
This is represented in notation with \(\Rightarrow\). So if p then q can be written as \(p \Rightarrow q\). Whenever \(p\) is true, \(q\) must also be true. This is only false when \(true \Rightarrow false\) or true implies false.
| \(p\) | \(q\) | \(p \Rightarrow q\) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
An implication is not the same both ways, \(p \Rightarrow q\) and \(q \Rightarrow q\) are both different expressions. These are referred to as converse statements.
- However \(\neg q \Rightarrow \neg p\) is the same as \(p \Rightarrow q\). This is called the contrapositive.
Biconditional
Can be said as p if and only if q. Which just means that it is only true when \(p\) and \(q\) have the same value. This can be written as \(p \Leftrightarrow q\).
| \(p\) | \(q\) | \(p \Leftrightarrow q\) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
Boolean Algebra
Booleans follow a similar logic to that of algebra. Using the following rules, we can simplify complicated boolean expressions:
- \(\neg (p \land q) \equiv \neg p \lor \neg q\)
- \(\neg (p \lor q) \equiv \neg p \land \neg q\)
- \(\neg \neg p \equiv p\)
- \(p \Rightarrow q \equiv \neg p \lor q\)
- \(\neg (p \Rightarrow q) \equiv p \land \neg q\), the negation of an
if-thenis not andif-then - \(p \land q \equiv q \land p\)
- \(p \lor q \equiv q \lor p\)
- \(p \land (q \land r) \equiv (p \land q) \land r\)
- \(p \lor (q \lor r) \equiv (p \lor q) \lor r\)
- \(p \land (q \lor r) \equiv (p \land q) \lor (p \land r)\)
- \(p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)\)