Propositional logic
Propositional and predicate logic
Propositional logic includes sentence letters (A, B, C, etc), which are assigned truth values, and logical connectives (AND, OR, NOT, IMPLICATION, EQUIVALENCE), but not quantifiers. This is also called sentential logic (because it deals in sentences).
Predicate logic, also called first-order logic (FOL), uses the same connectives as propositional logic, but it also has variables for individual objects, quantifiers, and other features.
This covers the first, propositional logic.
Logical connectives (operators)
Propositional logic makes use of connectives, many of which may be familiar (apart from details of notation, perhaps).
\neg NOT (negation)
\land logical AND (conjunction)
\lor logical OR (disjunction)
\implies IMPLICATION
\Longleftrightarrow logical EQUIVALENCE
Well-formed formulas (WFFs)
The set of well-formed propositional logic formulas (WFFs, pronounced “whiffs”) is defined recursively:
- True, T, and false, F, are WFFs. You can think of these as primitive sentences with fixed truth values.
- Any sentence letter (A, B, C, etc.) is a WFF. We sometimes refer to these as atoms or atomic sentences.
- If P is a WFF, then \neg P is a WFF.
- If P and Q are WFFs, then \big(P \land Q\big), \big(P \lor Q\big), \big(P \implies Q\big), and \big(P \Longleftrightarrow Q\big) are formulas.
We can omit the outermost parentheses if meaning is clear. So, for example, \big(\big(P \land Q\big) \lor R\big) and \big(P \land Q\big) \lor R are equivalent, but P \land Q \lor R is not a WFF.
You should be able to distinguish WFFs from syntactically invalid forms.
Literals
A literal is an atomic sentence or its negation.
Subscripts
We could (possibly) run out of sentence letters, so we allow subscripting.
P_1, P_2, P_3, \ldots
Check-in
Which of the following is not a WFF? (There may be more than one!)
\neg\bigg(\big(P \implies Q\big) \implies \big(\neg Q \implies \neg P\big)\bigg)
P, Q \implies R
\big(A_1 \land A_2\big) \implies \neg\big(\neg A_1 \lor \neg A_2\big)
P \implies Q \implies R
P \land \big(A \lor B\big)
Semantics
We assign the following meanings to logical connectives:
\neg A : not A
A \land B : both A and B
A \lor B : A or B or possibly both (inclusive OR)
A \implies B: if A, then B
In an implication (as above) we refer to the proposition on the left as the antecedent and the proposition on the right as the consequent.
A \Longleftrightarrow B : A if and only if B (logical equivalence).
| Symbol | Meaning | Example | Read as |
|---|---|---|---|
| T | true | “true” | |
| F | false | “false” | |
| \neg | negation | \neg A | “not A” |
| \land | conjunction | A \land B | “A and B” |
| \lor | disjunction | A \lor B | “A or B (or both)” |
| \implies | implication | A \implies B | “if A, then B” |
| We refer to the proposition on the left as the antecedent and the proposition on the right as the consequent. | |||
| \Longleftrightarrow | equivalence | A \Longleftrightarrow B | “A if and only if B” |
Note: Different authors may use different symbols. For example, \sim or ! for negation.
Truth tables: Negation
\begin{array}{ c c } P & \neg P \\ \hline T & F \\ F & T \\ \end{array}Given some WFF, P, we say that P and \neg P are complementary, or are logical complements of one another, or that \neg P is the complement of P, and P is the complement of \neg A.
Truth tables: Logical OR (disjunction) and logical AND (conjunction)
\begin{array}{ c c c c } P & Q & P \lor \: Q & P \land \: Q \\ \hline T & T & T & T \\ T & F & T & F \\ F & T & T & F \\ F & F & F & F \end{array}Truth tables: Implication
\begin{array}{ c c c } P & Q & P \implies \: Q \\ \hline T & T & T \\ T & F & F \\ F & T & T \\ F & F & T \\ \end{array}Notice that P \implies Q is true whenever Q is false. Many people find this disconcerting at first (alarming even). It’s important to understand that in propositional logic we have no necessary causal relationship between antecedent and consequent. We are only concerned with the truth-functions as given.
For example, let P be “my hair is blue” and let Q be “four is a prime number.” Now, my hair is not blue, so P is false. Then it would be correct to say “If my hair is blue, then four is a prime number.” and this would be true! Notice that this does not make Q true. Rather, the implication P \implies Q is true. (Yeah, I know, this one takes a little getting used to.)
Notice that P \implies Q is logically equivalent to \neg P \lor Q—their truth tables are the same!
\begin{array}{ c c c c } P & Q & P \implies \: Q & \neg P \lor Q \\ \hline T & T & T & T \\ T & F & F & F \\ F & T & T & T \\ F & F & T & T \\ \end{array}Truth tables: Logical equivalence
\begin{array}{ c c c } P & Q & P \Longleftrightarrow \: Q \\ \hline T & T & T \\ T & F & F \\ F & T & F \\ F & F & T \\ \end{array}Commutativity and associativity
\land and \lor are commutative and associative, so the following hold:
\begin{aligned} P \land Q \quad &\Longleftrightarrow\quad Q \land P\\ P \lor Q \quad &\Longleftrightarrow\quad Q \lor P\\ \big(P \land Q\big) \land R \quad &\Longleftrightarrow\quad P \land \big(Q \land R\big)\\ \big(P \lor Q\big) \lor R \quad &\Longleftrightarrow\quad P \lor \big(Q \lor R\big) \end{aligned}
Precedence
Just as in algebra, where we have precedence of operators, +, -, \times, etc., we have precedence of these logical connectives. The order of precedence is: \neg, \land, \lor, \implies, \Longleftrightarrow. Terms grouped with parenthesis behave as you would expect.
It should come as no surprise that there’s a connection between operator precedence in logic and in programming languages, for example, in C, precedence of !, &&, ||.
De Morgan’s Laws
We often find De Morgan’s Laws useful. These state that the negation of a disjunction is the conjunction of the negations, and the negation of a conjunction is the disjunction of the negations. More succinctly,
\begin{aligned} \neg\big(P \land Q\big) \quad \Longleftrightarrow\quad \big(\neg P \lor \neg Q\big)\\ \neg\big(P \lor Q\big) \quad \Longleftrightarrow\quad \big(\neg P \land \neg Q\big) \end{aligned}
Some other equivalences
\big(P \implies Q\big) \: \Longleftrightarrow\: \big(\neg Q \implies \neg P\big) (contraposition)
\bigg(\big(P \implies Q\big) \land \big(Q \implies P\big)\bigg) \: \Longleftrightarrow\: \big(P \Longleftrightarrow Q\big)
\big(P \Longleftrightarrow Q\big) \: \Longleftrightarrow\: \bigg(\big(P \implies Q\big) \land \big(Q \implies P\big)\bigg) (biconditional elimination)
\neg (\neg P) \: \Longleftrightarrow\: P (negation elimination)
\big(P \implies Q \big) \Longleftrightarrow \big(\neg P \lor Q\big) (material implication)
Whenever it’s convenient, we can use these or De Morgan’s these to rewrite formulas.
Interpretation and models
Let \Sigma be the set of all propositions. A mapping \varphi : \Sigma \rightarrow \{T, F\} which assigns a truth value to every proposition variable is called an interpretation.
The truth value of any well-formed formula (WFF) thus depends on the truth value of the formula’s propositional variables. We call any interpretation that satisfies some WFF (makes it true), P, a model of P.
Equivalence
We have introduced the connective \Longleftrightarrow which is asyntactic element of propositional logic. When considering semantic equivalence, we use \equiv. Two formulas F and G are called semantically equivalent if they take on the same truth value for all interpretations, and we write F \equiv G.
This is not part of the language of propositional logic, but rather is part of the meta-language we use when discussing propositional logic.
Satisfiability, validity, and tautology
We call a WFF satisfiable if there is at least one interpretation for which it is true.
Conversely, we call a WFF unsatisfiable if it is not true for any interpretation.
We call a WFF valid if it is true for all interpretations.
A tautology is a WFF whose negation is unsatisfiable. In propositional logic, validity and tautology are equivalent (but this is not so in other logics).
Entailment
Recall that a model for any WFF is an interpretation which satisfies the WFF.
Given two WFFs P and Q, if every model of P is also a model of Q, we say A entails B, and we write this A \vDash B.
Check-in
Without using truth tables, show that \neg\big(A \implies B\big) \Longleftrightarrow \big(A \land \neg B\big).
Using truth tables, determine whether the following are logically equivalent, or not.
\big(P \lor Q\big) \implies R
\big(P \implies R\big) \land \big(Q \implies R\big)
First ask yourself, how many rows must the truth table have?
Deduction: modus ponens
\begin{array}{c} P \implies Q \\ P \\ \hline \therefore \quad Q \end{array}\begin{array}{ c c c } P & Q & P \implies Q \\ \hline T & T & T \\ T & F & F \\ F & T & T \\ F & T & T \end{array}
Answers to checkins
B and D
\neg\big(A \implies B\big)
\hspace{2em}Using the equivalence \big(P \implies Q \big) \Longleftrightarrow \big(\neg P \lor Q\big) (material implication), we can rewrite this as
\hspace{2em}\neg\big(\neg A \lor \: B\big).
\hspace{2em}Then we can use De Morgan
\hspace{2em}\neg\neg A \land \neg B
\hspace{2em}and then double-negation elimination
\hspace{2em}A \land \neg B
\hspace{2em}and we’re done.
Copyright © 2023–2025 Clayton Cafiero
No generative AI was used in producing this material. This was written the old-fashioned way.