Logic begins with statements that are already complete enough to be judged true or false. That sounds simple, but the distinction matters throughout the course: once a statement is not yet closed, it cannot be treated as a proposition.
Propositions and truth values
Definition
Proposition
A proposition is a statement with a definite truth value. It is either true or false, and nothing in between.
The point of the definition is not to make logic abstract for its own sake. It is to separate statements that can be tested from statements that are still unfinished.
Examples:
- is a proposition.
Every even number is divisible by 2is a proposition.Open the window.is not a proposition, because it is a command.- is not yet a proposition if
xhas not been fixed.
Common mistake
A formula with a free variable is not automatically a proposition
If the truth of a sentence still depends on an unspecified variable, then the sentence is open, not closed. You must either assign a value to the variable or bind it later with a quantifier.
Worked example
Decide which statements are propositions
Consider the following three statements:
7is prime.- .
Please hand in the worksheet.
Statement 1 is a proposition, and it is true. Statement 2 is not a proposition
yet, because its truth value depends on the choice of x. Statement 3 is not a
proposition, because it is a request rather than a claim.
Solution
Why the distinction matters
The Boolean alphabet
The course uses five connectives repeatedly:
| Symbol | Read as | Main idea |
| --- | --- | --- |
| | not | flips the truth value |
| | and | true only when both are true |
| | or | true when at least one is true |
| | if , then | false only when is true and is false |
| P ↔ Q | if and only if | true when the two sides match |
These are not just informal abbreviations. They are the basic symbols of the logic language, and they are the tools used to build more complicated statements.
The order of operations is also fixed:
- and
- and
↔
If that order still leaves ambiguity, add parentheses.
Worked example
Parse a formula before reading it
The formula is read as
The outer comes after the and the . So the statement says: either is false and is true, or is true.
If you meant something else, you must say so explicitly with parentheses.
Solution
Why this is not cosmetic
Truth tables and equivalence
A Boolean formula can be evaluated once the truth values of its component propositions are known. That is what a truth table records.
Theorem
Useful equivalences
The following equivalences are standard and should become automatic:
These are not philosophy statements. They are truth-table identities.
Worked example
Check implication with a truth table
The implication is false in exactly one case: when is true and is false. In every other case it is true.
| | | | | --- | --- | --- | | | | | | | | | | | | | | | | |
So does not mean that and are both true. It means that the case true and false is ruled out.
Solution
Why this matters
Rules of inference
The lecture notes and homework use several deduction patterns repeatedly.
Theorem
Common inference patterns
If and are true, then is true. This is modus ponens.
If and are true, then is true. This is modus tollens.
If and are true, then is true. This is hypothetical syllogism.
If and are true, then is true. This is disjunctive syllogism.
These patterns are important because they are the logic version of a valid calculation. If the premises are true, the conclusion must also be true.
Worked example
A valid chain of implications
Suppose you know
Then you may conclude from the first and third statements, and then from the second statement.
The conclusion follows from the premises because every step preserves truth.
Solution
How to recognize the argument
Common mistake
Do not confuse valid and invalid implication patterns
From and , you cannot conclude . That fallacy is called affirming the consequent.
From and , you cannot conclude . That fallacy is called denying the antecedent.
Quick checks
Quick check
Which of these are propositions: , Open the window., ?
is a proposition. Open the window. is not. is not a
proposition until x is fixed.
Solution
Answer
Quick check
Insert parentheses into using the standard order of operations.
Remember that binds first, then and .
Solution
Answer
Quick check
Which of the following is logically equivalent to : or ?
Check the truth condition of implication.
Solution
Answer
Quick check
Is the argument , , therefore valid?
Test the conclusion against the case where is false.
Solution
Answer
Embedded check
Use the interactive table to test formulas against the truth values you assign.
Read and try
Trace one truth table
The live builder lets you switch formulas and inspect how each row changes the final truth value.
| P | Q | P → Q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
Read this first
If you want the quantifier version of the language, read 1.3 Quantifiers and negation.