Propositional Logic
Propositional Logic is concerned with statements to which the truth values can be assigned.
- “2 is an even number” is a true statement, hence it is a proposition.
- “$x$ is an even number” can be either true or false. Without quantifying it, we can’t assign a truth value to it. However, if it existed in a contect where $x$ is defined, then it could be a proposition.
Without proper definitions, we are unable to verify and prood statements. Therefere, it is important for us to define everything clearly and precisely to avoid ambiguity.
1 Basic Operators
| Operator | Symbol | Description |
|---|---|---|
| Conjunction | $∧$ | p $∧$ q $≡$ p AND q |
| Disjunction | $∨$ | p $∨$ q $≡$ p OR q |
| Negation | $¬$ | $¬$p $≡$ NOT p |
| Implication | $→$ | p $→$ q $≡$ if p, then q |
| Biconditional | $↔$ | p $↔$ q $≡$ p if and only if q |
$≡$ is the mathematical symbol for logical equivalence.
2 Truth Tables
| p | q | p $∧$ q | p $∨$ q | $¬$ p |
|---|---|---|---|---|
| T | T | T | T | F |
| T | F | F | T | F |
| F | T | F | T | T |
| F | F | F | F | T |
A truth table displays the relationship among the truth values of statements. The symbol $T$ can also be represented with $1$, while $F$ can be represented with $0$.
-
Given a truth table representing an argument, the rows where all the premises(assumptions) are true are called the critical rows. When checking for validity of an argument, we only need to look at the critical row.
-
If all the premises are true and the conclusion is true, it is a valid argument.
-
If the premises are all true but the conclusion is false, then it is invalid.
-
-
If all the conclusion is true regardless of the truth values of the premises, then the statement is called a tautology.
-
If all the conclusion is false regardless of the truth values of the premises, then the statement is called a contradiction.
3 Laws of Logic
3.1 Precedence for Operations
From most significant to least:
- $¬$
- $∧$
- $∨$
- $→$
- $↔$
p $∧$ $¬$q $→$ r is logically quivalent to (((p $∧$ ($¬$ q)) $→$ s)
- It is good practice to parenthesize the logical statement to avoid ambiguity.
3.2 Important Laws
| Law(s) | ||
|---|---|---|
| Associative | (p $∧$ q) $∧$ r $≡$ p $∧$ (q $∧$ r) | (p $∨$ q) $∨$ r $≡$ p $∧$ (q $∨$ r) |
| Absorption | p $∨$ (p $∧$ q) $≡$ p | p $∧$ (p $∨$ q) $≡$ p |
| Commutative | p $∧$ q $≡$ q $∧$ p | p $∨$ q $≡$ q $∨$ p |
| Distributive | p $∨$ (q $∧$ r) $≡$ (p $∨$ q) $∧$ (p $∨$ r) | p $∧$ (q $∨$ r) $≡$ (p $∧$ q) $∨$ (p $∧$ r) |
| De Morgan’s | $¬$(p $∧$ q) $≡$ $¬$ p $∨$ $¬$ q | $¬$(p $∨$ q) $≡$ $¬$ p $∧$ $¬$ q |
| Domination | p $∨$ $T$ $≡$ $T$ | p $∧$ $F$ $≡$ $F$ |
| Double negation | $¬$($¬$p)) $≡$ p | |
| Identity | p $∧$ $T$ $≡$ p | p $∨$ $F$ $≡$ p |
| Idempotent | p $∧$ p $≡$ p | p $∨$ p $≡$ p |
| Implication | p $→$ q $≡$ $¬$p $∨$ q | |
| Inverse | p $∨$ $¬$p $≡$ $T$ | p $∧$ $¬$p $≡$ $F$ |
Proof that $p → (p ∨ q)$ is true by using:
-
a truth table
p q p ∨ q T T T T F T F T T F F F In this statement, the premise is p and the conclusion is p ∨ q. In the critical row, both the premise and the conclusion are all true, therefore the statement is true.
-
logical laws
p → (p ∨ q) ≡ ¬p ∨ (p ∨ q) (by De Morgan's laws) ≡ (¬p ∨ p) ∨ (¬p ∨ q) (by distributive laws) ≡ T ∨ (¬p ∨ q) (by inverse laws) ≡ T (by identity laws)Using the laws of propositional logic, we are able to deduce that the statement is true. It is good practice to state the laws used to avoid errors.
3.3 Vacously True
In logic, implications of the form $p → q$ are said to be vacously true(true by default) regardless of the truth value of $q$ when the proposition $p$ is false.
For example, the statement “If cats can fly, then Rachel will win the lottery.” is vacously true even if cats being able to fly is obviously false. This is because a false premise does not license us to infer the conclusion. In other words, the conditional is “useless”.
Truth table for p → q
| p | q | p → q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
4 Rules of Inferences
Another method to check for validity of arguments is by using rules of inferences.
4.1 Modus Ponens
Let $p$ be the statement “I study hard.”
Let $q$ be the statement “I score distinction.”
Modus ponens states that if $p → q$ and $p$, then $q$.
In other words, if i study hard, then I score distinction. I studied hard, therefore I scored distinction.
4.2 Modus Tollens
Let $p$ be the statement “The weather is good.”
Let $q$ be the statement “I play football.”
Modus tollens states that if $p → q$ and $¬q$, then $¬p$.
In other words, if the weather is good, then I will play football. I did not play football, therefore the weather was bad.
4.3 Hypothetical Syllogism(Transitivity)
Let $p$ be the statement “$x > 100$”.
Let $q$ be the statement “$x > 10$”.
Let $r$ be the statement “$x > 1$”.
Hypothetical syllogism states that if $p → q$ and $q → r$, then $p → r$.
In other words, if “$x > 100$” implies “$x > 10$” and “$x > 10$” implies “$x > 1$”, then “$x > 100$” implies “$x > 1$”.
4.4 Disjunctive Syllogism(Elimination)
Let $p$ be the statement “I drink coffee”.
Let $q$ be the statement “I drink tea”.
Disjunctive syllogism states that if $p ∨ q$ and $¬p$, then $q$.
In other words, if I either drink coffee or tea, then me not drinking coffee implies that I drank tea.
Other rules of inferences
For a more detailed explaination on this topic, click here.
5 Quantifiers
Types of quantifiers:
- Existential quantifier ( $∃$ )
- $∃x$ $p(x)$ is true if there exits an element $x$ in the universe where $p(x)$ is true.
- $∃x$ $p(x)$ is false if for all elements $x$ in the universe, $p(x)$ is false.
- Universal quantifier ( $∀$ )
- $∀$ $p(x)$ is true if and only if for all elements $x$ in the universe, $p(x)$ is true.
- $∀$ $p(x)$ is false if there exists some element $x$ in the universe where $p(x)$ is false.
- Suppose the universe is the set of real numbers.
- Let $p(x)$ be the statement “$x≥0$”
- Let $q(x)$ be the statement “$x^2-3x-4=0$”
- Let $r(x)$ be the statement “$x^2≥0$”
Determine if the following universal statements are true or false:
- $∀x$ $(p(x)∧q(x))$
This is false as the solutions for “$x^2-3x-4=0$” are -1 and 4, and -1 is not equal or larger than 0. - $∀x$ $(p(x)→r(x))$
This is true because if $x$ is positive, then its square value must also be positive. - $∀x$ $(r(x)→p(x))$
This is false. Counterexample: -3 is less than 0, but -3$^2$ is 9, which is larger than 0, contradicting the statement.
Notice that for all real numbers, $(p(x)→q(x))$ is true but $(q(x)→p(x))$ is false. This is because the two statements are not logically equivalent. This is commonly known as the converse error.
6 Converse, Inverse, Contrapositive
Let’s define a statement as $p(x)→q(x)$.
- Its converse is $q(x)→p(x)$.
- Its inverse is $¬p(x)→¬q(x)$.
- Its contrapositive is $¬q(x)→¬p(x)$. A statement’s contrapositive is logically equivalent to itself. We can prove this using implication law and De Morgan’s laws.
A statement is not logically equivalent to its converse and inverse. Do note this as converse and inverse errors are common mistakes.