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.
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 be “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$.
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$ inputs.
Disjunction (OR)
Disjunction says “p OR q”. This is known as the logical OR. The symbol is $\lor$.
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 |
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$:
| $p$ | $q$ | $p\implies q$ |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| T | T | T |
The proposition before the implication arrow is known as the antecedent/hypothesis and the proposition after the arrow is the conclusion/consequent/result.
The implication is false only when the antecedent is true and the conclusion is false.