Propositional logic basics
Sentences, connectives, and four ideas that every tool builds on: validity, consistency, equivalence and tautology. Start here if logic is new to you.
The basics
Logic studies which claims follow from which. Propositional logic is its simplest part: it looks only at how whole sentences are combined with words such as “not”, “and”, “or” and “if”. Every tool in this app works with it, and this guide covers the ideas they all share.
Sentences and sentence letters
In logic, a sentence is a statement that is either true or false, such as “Paris is in France” or “The moon is made of cheese”. Questions and commands are not sentences in this sense: “Is it raining?” and “Close the door” are neither true nor false. Many books call sentences propositions.
Whether a sentence is true or false is its truth value. There are just two truth values: true, written T, and false, written F.
Some sentences are built from shorter ones. “It is raining and it is cold” is built from “It is raining” and “It is cold”. A sentence that is not built from shorter sentences is atomic.
Atomic sentences are written as capital letters, called sentence letters or atoms. P might stand for “It is raining” and Q for “It is cold”. Logic never asks what a letter means, only whether it is true or false. In the app, a sentence letter is a capital, optionally followed by a number: P, Q or P1 (shown as P₁).
Connectives and truth tables
A connective builds a longer sentence from shorter ones. Propositional logic has five: ¬ (not), ∧ (and), ∨ (or), → (if … then) and ↔ (if and only if). It also has ⊥, a sentence that is always false. A sentence written with letters and connectives is a formula.
The connectives are truth-functional: the truth value of the whole depends only on the truth values of its parts. So a small table, its truth table, says everything about a connective: one row for each way of giving values to the parts, with the value of the whole in that row. The tables use P and Q, but work the same for any sentences.
Not: ¬
¬P is the negation of P. Read it “not P”, or “it is not the case that P”. It has the opposite truth value to P.
| P | ¬P |
|---|---|
| T | F |
| F | T |
Common mistake
A ¬ applies only to the shortest complete formula that follows it. ¬P ∧ Q negates only P: it says “not P, and Q”. To deny the whole conjunction, use brackets: ¬(P ∧ Q).
And: ∧
P ∧ Q is the conjunction of P and Q, read “P and Q”. It is true when both are true, and false otherwise.
| P | Q | P ∧ Q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
Common mistake
“But” and “although” become ∧ too, since they also claim that both parts are true. And ∧ ignores order: P ∧ Q and Q ∧ P always have the same truth value, even where English “and” hints at a sequence.
Or: ∨
P ∨ Q is the disjunction of P and Q, read “P or Q”. It is true when at least one of them is true, and false only when both are false.
| P | Q | P ∨ Q |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
Common mistake
∨ is inclusive: P ∨ Q is true when P and Q are both true. Everyday “or” is sometimes exclusive, as in “soup or salad” on a menu, which rules out having both. To say “P or Q, but not both”, write (P ∨ Q) ∧ ¬(P ∧ Q).
If … then: →
P → Q is a conditional, read “if P then Q”. P is its antecedent and Q its consequent. It is false in just one case: when P is true and Q is false.
| P | Q | P → Q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
The last two rows surprise most people: whenever P is false, P → Q is true. This is what logicians mean by “a falsehood implies anything”. “If a number is greater than 10, it is greater than 5” is true of every number. For 7, the antecedent is false and the consequent true; for 3, both are false. Neither number breaks the rule, so both of those rows must be true.
This is the material conditional. It does not claim that P causes Q, or has anything to do with it.
Common mistake
P → Q is not the same as Q → P, its converse. “If it is a dog, it is an animal” is true; “if it is an animal, it is a dog” is not. Watch “only if” too: “P only if Q” means P → Q, while “P if Q” means Q → P.
If and only if: ↔
P ↔ Q is a biconditional, read “P if and only if Q”. It is true when P and Q have the same truth value: both true, or both false.
| P | Q | P ↔ Q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
It says the same as (P → Q) ∧ (Q → P): if P then Q, and if Q then P.
Common mistake
P ↔ Q is not “P and Q”. It is also true when P and Q are both false: “I will go if and only if you go” is kept if neither of us goes.
The false: ⊥
⊥, called falsum or “the false”, is a sentence that is false whatever happens: its truth table is a single F. It marks that something has gone wrong. A proof writes ⊥ when it reaches a contradiction, and a tableau branch that contains ⊥ is closed.
Common mistake
⊥ is not a sentence letter. A letter such as P can be true or false, but ⊥ is always false, and so ¬⊥ is always true.
Tautology, contradiction, contingent
The words below name what the tools look for. Each talks about valuations: a valuation gives every sentence letter a truth value, so it is one row of a truth table.
A formula is a tautology if it is true on every valuation. P ∨ ¬P (“it is raining or it is not”) is one: whatever P says, the formula is true.
A formula is a contradiction if it is false on every valuation, like P ∧ ¬P.
A formula that is neither is contingent: true on some valuations and false on others. P → Q is contingent, as its truth table above shows.
A formula is satisfiable if it is true on at least one valuation. Every formula is satisfiable except the contradictions.
Valid and invalid arguments
An argument is a list of sentences, its premises, together with one more sentence, its conclusion. The app writes the conclusion after ∴, as in P → Q, P ∴ Q.
An argument is valid if no valuation makes every premise true and the conclusion false. Put another way: whenever the premises are all true, so is the conclusion. An argument that is not valid is invalid.
A valuation that makes every premise true and the conclusion false is a counterexample. So an argument is valid exactly when it has no counterexample.
P → Q, P ∴ Q is valid. P → Q, Q ∴ P is invalid: if P is false and Q is true, both premises are true and the conclusion is false.
Common mistake
Validity is not about whether the sentences are actually true. “If the moon is cheese, it is edible; the moon is cheese; so it is edible” is valid, though a premise is false. A valid argument whose premises are all true is called sound, and then its conclusion must be true. If a premise is false, validity guarantees nothing about the conclusion.
Consistent sets
A set of formulas is consistent if at least one valuation makes all of them true at once. If none does, the set is inconsistent.
The set P ∨ Q, ¬P is consistent: make P false and Q true, and both formulas are true. Add ¬Q and the set becomes inconsistent: P ∨ Q needs P or Q to be true, and ¬P and ¬Q rule out both.
Equivalent formulas
Two formulas are equivalent if they have the same truth value on every valuation. They say the same thing in different ways.
P → Q and ¬Q → ¬P are equivalent: each is false exactly when P is true and Q is false. A conditional and its converse, P → Q and Q → P, are not.
Step by step
Connectives can be applied again and again, to build formulas of any length. This part shows how they are built, how to work out their truth values, and how to type them.
Formulas and brackets
The rules for building formulas are short. Here A and B stand for any formulas, however long:
- Every sentence letter is a formula, and so is ⊥.
- If A is a formula, so is ¬A.
- If A and B are formulas, so are (A ∧ B), (A ∨ B), (A → B) and (A ↔ B).
Nothing else is a formula. So ¬P, (P ∧ Q) and ((P ∧ Q) → ¬R) are formulas, and P ∧ ∨ Q is not.
Brackets record how a formula was built, and where they go can change its meaning. (P ∧ Q) ∨ R and P ∧ (Q ∨ R) are different sentences. If P is false and R is true, the first is true and the second is false.
The outermost brackets add nothing, so they are usually dropped: (P ∧ Q) is written P ∧ Q.
Scope and the main connective
The scope of a connective is the part of the formula that it governs: the connective together with what it applies to. In ¬P ∧ Q, the scope of ¬ is just ¬P. In ¬(P ∧ Q), it is the whole formula.
The main connective is the one whose scope is the whole formula. It is the last connective added when the formula is built, and it says what kind of sentence the formula is: ¬P ∧ Q is a conjunction, while ¬(P ∧ Q) is a negation.
To find the main connective of a formula written with all its brackets:
- If the whole formula is wrapped in a pair of brackets, remove them.
- Look for a connective ∧, ∨, → or ↔ that is not inside any brackets. If there is one, it is the main connective.
- If there is none, the formula is either a negation, whose first ¬ is the main connective, or a single letter or ⊥, with no connective at all.
For example, ((P ∧ Q) → ¬R) loses its outer brackets to become (P ∧ Q) → ¬R, whose only connective outside brackets is →: it is a conditional. The syntax trees guide draws this structure as a tree.
Working out a truth value
To work out a formula’s truth value from the values of its letters, go from the inside out: the smallest parts first, the main connective last. Take ¬(P ∧ Q) → R, with P true, Q false and R false:
- P ∧ Q is F, because Q is F.
- ¬(P ∧ Q) is T, the opposite of F.
- The main connective is →. Its antecedent, ¬(P ∧ Q), is T and its consequent, R, is F, so the whole formula is F.
A truth table does this for every valuation at once.
Leaving out brackets
The app lets you leave out many brackets, because it follows a fixed order of strength. ¬ binds most tightly, then ∧, then ∨, then →, and ↔ binds least tightly. So:
- P ∧ Q ∨ R means (P ∧ Q) ∨ R.
- P ∨ Q → R means (P ∨ Q) → R.
A chain of ∧, or of ∨, groups from the left: P ∧ Q ∧ R means (P ∧ Q) ∧ R. A chain of → or of ↔ has no such rule, so the app refuses P → Q → R and asks for brackets.
The app prints formulas with the fewest brackets these rules allow, so you will meet them in its results. When in doubt, write the brackets: extra ones never hurt.
Typing formulas in the app
Formula fields accept the symbols, and also keyboard spellings, which they turn into symbols as you type:
| You type | You get | Meaning |
|---|---|---|
| ~ | ¬ | not |
| & | ∧ | and |
| v | ∨ | or |
| -> | → | if … then |
| <-> | ↔ | if and only if |
| # | ⊥ | the false |
| :. | ∴ | therefore |
Sentence letters are capitals, so a lowercase v always means “or”: P v Q becomes P ∨ Q. Spaces make no difference, and square brackets work like round ones.
Some tasks have several formulas. Separate them with commas, and put ∴ (“therefore”) before the conclusion of an argument: P → Q, P ∴ Q. Under each input field, the app says what it expects.
Going deeper
Precise definitions
In textbook notation, with A and B formulas, Γ (gamma) a set of formulas, and “iff” short for “if and only if”:
- A valuation v gives each sentence letter T or F, and the truth tables extend it to every formula: v(¬A) = T iff v(A) = F, and so on.
- Γ is satisfiable, or consistent, if some valuation makes every formula in Γ true.
- Γ entails A, written Γ ⊨ A, if every valuation that makes all of Γ true makes A true. The argument from premises Γ to the conclusion A is valid iff Γ ⊨ A.
- A is a tautology iff ⊨ A (the empty set entails it), and A and B are equivalent iff A ⊨ B and B ⊨ A.
How the ideas connect
These ideas are linked, and the tools rely on the links:
- A is a tautology iff ¬A is a contradiction.
- A and B are equivalent iff A ↔ B is a tautology.
- Γ ⊨ A iff Γ together with ¬A is unsatisfiable: a valuation that makes all of them true is exactly a counterexample.
The last link drives the tableau tool. To test P → Q, P ∴ Q, it asks whether P → Q, P and ¬Q can all be true together. They cannot, so the argument is valid.
Why these connectives
For any truth table at all, some formula built from these five connectives has exactly that table, so the set is truth-functionally complete. Fewer would do: ¬ and ∧ alone can express the rest. The truth tables guide shows why.
Where to go next
Each tool has its own guide: truth tables, tableaux, proofs, syntax trees and normal forms. For a fuller treatment, the first parts of the free textbook forall x: Calgary cover the same ground.