A statement is a declaration or a question whose truth value may or may not be evaluated. Some examples are:
- Tuesday is the day after Monday
- $x+2=5$
- What is your name?
Out of these statements, only the first is a proposition. A proposition is a statement whose truth value can be evaluated.
The second statement is not a proposition as we do not know the value of $x$ and thus cannot say whether the statement is true or false. The third is not a proposition because it is a question and thus does not even declare anything we can evaluate the truth value for.
Representing propositions
We usually use common letters like $p$, $q$ and $r$ to represent propositions e.g. let $p$ be the proposition “All dogs are brown”. We can say that in real life, $p$ is always false because dogs can be of various colours. We assign a truth value to the statement and thus the letter representing the statement.
Compound propositions
There are ways we can modify a proposition in order to produce a new proposition:
- Negation
- Conjunction
- Disjunction (both inclusive and exclusive)
Negation (NOT)
This is used to invert the truth value of a proposition. It is represented by the symbol $\neg$. It says “NOT $p$”. Let $p$ be the proposition “The first day in the weekend is Saturday”. Then, the proposition $\neg p$ will read as “The first day in the weekend is not Saturday”.
A truth table can be used to show these statements:
| $p$ | $\neg p$ |
|---|---|
| $T$ | $F$ |
| $F$ | $T$ |
For any $n$ number of starting propositions, we will have $2^n$ combinations of inputs for our truth table. Because p was the only starting proposition, we have $2^1=2$ inputs.
Conjunction (AND)
Conjunction and disjunction are used to chain together multiple propositions. Conjunction says “$p$ AND $q$”. Conjunction is known as the logical AND. The symbol for conjunction is $\land$.
Pro tip: The conjunction of two propositions is true when both propositions are true, otherwise false.
Using two propositions $p$ and $q$:
| $p$ | $q$ | $p\land q$ |
|---|---|---|
| $T$ | $T$ | $T$ |
| $T$ | $F$ | $F$ |
| $F$ | $T$ | $F$ |
| $F$ | $F$ | $F$ |
Because there are two starting propositions ($p$ and $q$), we will have $2^2=4$ unique combinations of inputs.
Disjunction (OR)
Disjunction says “$p$ OR $q$”. This is known as the logical OR. The symbol is $\lor$.
Pro tip: The disjunction of two propositions is false when both propositions are false, otherwise true.
Using two propositions $p$ and $q$:
| $p$ | $q$ | $p\lor q$ |
|---|---|---|
| $T$ | $T$ | $T$ |
| $T$ | $F$ | $T$ |
| $F$ | $T$ | $T$ |
| $F$ | $F$ | $F$ |
Exclusive disjunction (XOR)
This is a disjunction that says “$p$ OR $q$ but not both”.
| $p$ | $q$ | $p\oplus q$ |
|---|---|---|
| $T$ | $T$ | $F$ |
| $T$ | $F$ | $T$ |
| $F$ | $T$ | $T$ |
| $F$ | $F$ | $F$ |
Pro tip: For XOR, we simply ask “Are the two inputs different?” and the truth value is the answer to this question.
Implication (IF-THEN)
This is known as the conditional proposition. It says “if $p$ then $q$”. The symbol is $\implies$. The proposition before the implication arrow is known as the antecedent/hypothesis and the proposition after the arrow is the conclusion/consequent/result.
| $p$ | $q$ | $p\implies q$ |
|---|---|---|
| $T$ | $T$ | $T$ |
| $T$ | $F$ | $F$ |
| $F$ | $T$ | $T$ |
| $T$ | $T$ | $T$ |
Pro tip: The implication is false only when the antecedent is true and the conclusion is false ($T\implies F\equiv F$), otherwise true. True (before the arrow) followed by false (after the arrow) produces false otherwise true.
Created using natural intelligence