Skip to main content

Formulas

This section introduces formulas of propositional logic. Each formula is an expression that represents a statement, or a proposition.

The first step is to settle on notation for the basic statements that are used to build up more complex statements.

Atomic Propositions

Capital letters from the beginning and middle of the alphabet (A,B,…,P,Q,R,…,U,V,WA, B, \ldots, P, Q, R, \ldots, U, V, W) are atomic proposition (also called a sentence letter). Sometimes we will use subscripts to denote atomic propositions, i.e., P1,P2,…P_1, P_2, \ldots. This will ensure that we never run out of symbols to use for atomic propositions.

Variables

Capital letters from the end of the alphabet (XX, YY, and ZZ), possibly with subscripts (e.g., X1X_1, X2X_2, …\ldots), are variables that range over any formula.

In addition to atomic propositions, formulas will be constructed using the symbols (the left and right parentheses and the Boolean connectives):

)(¬∧∨→)\qquad ( \qquad \neg\qquad \wedge\qquad \vee\qquad \rightarrow

Formulas are constructed according to the following rules.

Rules to Construct Formulas
  1. Any atomic proposition A,B,…,P,Q,R,…,U,V,WA, B, \ldots, P, Q, R, \ldots, U, V, W, P1,P2,…P_1, P_2, \ldots is a formula.
  2. If XX is a formula, then ¬X\neg X is a formula.
  3. If XX and YY are formulas, then so is (X∨Y)(X\vee Y), (X∧Y)(X\wedge Y), and (X→Y)(X\rightarrow Y).
  4. Nothing else is a formula.

Examples of formulas constructed using these rules include:

  • (P∨¬P)(P\vee\neg P),
  • ¬(P→Q)\neg (P\rightarrow Q),
  • ((P∨Q)∧¬R)((P\vee Q)\wedge \neg R), and
  • ¬¬(P∨R)\neg\neg(P\vee R).

It is important to understand exactly how the above rules are used to construct these formulas:

Example

(P∨¬P)(P\vee \neg P) is a formula:

  1. Since PP is an atomic proposition, PP is a formula according to rule 1.
  2. Since PP is a formula, ¬P\neg P is a formula according to rule 2.
  3. Since PP and ¬P\neg P are formulas, (P∨¬P)(P\vee \neg P) is a formula according to rule 3.
Example

¬(P→Q)\neg(P\rightarrow Q) is a formula:

  1. Since PP and QQ are atomic propositions, they are formulas according to rule 1.
  2. Since PP and QQ are formulas, (P→Q)(P\rightarrow Q) is a formula according to rule 3.
  3. Since (P→Q)(P\rightarrow Q) is a formula, ¬(P→Q)\neg (P\rightarrow Q) is a formula according to rule 2.
Example

((P∨Q)∧¬R)((P\vee Q)\wedge \neg R) is a formula:

  1. Since PP, QQ and RR are atomic propositions, they are formulas according to rule 1.
  2. Since RR is a formula, ¬R\neg R is a formula according to rule 2.
  3. Since PP and QQ are formulas, (P∨Q)(P\vee Q) is a formula according to rule 3.
  4. Since (P∨Q)(P\vee Q) and ¬R\neg R are formulas, ((P∨Q)∧¬R)((P\vee Q)\wedge \neg R) is a formula according to rule 3.
Example

¬¬(P∨R)\neg\neg(P\vee R) is a formula:

  1. Since PP and RR are atomic propositions, they are formulas according to rule 1.
  2. Since PP and RR are formulas, (P∨R)(P\vee R) is a formula according to rule 3.
  3. Since (P∨R)(P\vee R) is a formula, ¬(P∨R)\neg(P\vee R) is a formula according to rule 2.
  4. Since ¬(P∨R)\neg(P\vee R) is a formula, ¬¬(P∨R)\neg\neg(P\vee R) is a formula according to rule 2.

Examples of strings of symbols that are not formulas according to the above rules include:

  • (P∨∧ Q)(P\vee\wedge\ Q): Rule 3 requires that a single connective is written between two formulas.
  • ∨P\vee P: Rule 3 requires that a connectives is written between two formulas.
  • ¬(P)\neg (P) or (¬P)(\neg P): Rule 2 does not use parentheses when constructing a formula.
  • P∨QP\vee Q: Rule 3 requires that parentheses are placed around the constructed formula. Note that we will introduce some conventions to simplify our notation. According to these conventions, P∨QP\vee Q will be a formula.
  • (p∨q)(p\vee q): According to the official definition, only capital letters can be used as atomic propositions. Of course, there is no difficulty if we decide that lowercase letters can also be used as symbols to represent atomic propositions.
Variables vs. Atomic Propositions

In many situations, we treat variables and atomic propositions similarly. However, there is an important difference between formulas with variables and formulas with atomic propositions. For example, consider the following two formulas, the one on the left is constructed using variables XX and YY and the one on the right is constructed using atomic propositions PP and QQ:

(X∨¬Y)(P∨¬Q)(X\vee \neg Y)\qquad\qquad (P\vee \neg Q)

The formula on the right is a single formula consisting of the atomic proposition PP and the formula ¬Q\neg Q connected by "∨\vee". The formula on the left represents any formula consisting of two formulas connected with a "∨\vee", where the second formula starts with a "¬\neg". For example, the following are all instances of the formula on the left:

  1. (P∨¬Q)(P\vee \neg Q): Let XX be PP and YY be QQ.
  2. ((P∧Q)∨¬¬R)((P\wedge Q) \vee \neg \neg R): Let XX be (P∧Q)(P\wedge Q) and YY be ¬R\neg R.
  3. ((P∨¬Q)∨¬(P∨¬Q))((P\vee \neg Q) \vee \neg (P\vee \neg Q)): Let XX be (P∨¬Q)(P\vee \neg Q) and YY be (P∨¬Q)(P\vee \neg Q)

Note that we might encounter formulas that includes both variables and atomic propositions. For instance,

(X∨P)(X\vee P)

is a formula with one variable combined with the atomic proposition PP by the Boolean connnective "∨\vee". The following are instances of the above formula:

  1. (Q∨P)(Q\vee P): Let XX be QQ.
  2. (P∨P)(P\vee P): Let XX be PP.
  3. (((A∨B)∧¬C)∨P)(((A\vee B) \wedge \neg C)\vee P): Let XX be ((A∨B)∧¬C)((A\vee B) \wedge \neg C).

Terminology#

The following terminology will be used to refer to different parts of a formula:

formula terminology

Main Connective#

When reading a formula, the first thing you should do is identify the main connective. This will help identify the type of formula you are reading (i.e., is the formula a negation? a conjunction? a disjunction? a conditional?). The main connective of a formula is identified as follows:

  1. If the first symbol in the formula is "¬\neg", then the first occurrence of "¬\neg" is the main connective.
  2. Otherwise, the main connective is the first occurrence of the binary connective that is surrounded by the fewest number of parentheses.

For example, the main connective of (¬P∨Q)(\neg P\vee Q) is ∨\vee, and the main connective of ¬(P∨Q)\neg(P\vee Q) is ¬\neg.

Syntax Trees#

An important consequence of the definition for constructing formulas is that every formula has only one reading. That is, unlike in natural language, there is no (structural) ambiguity associated with a formula. Note that parentheses are needed to achieve a single reading for each formula. For instance, consider the following two formulas:

  1. (¬P∨Q)(\neg P\vee Q)
  2. ¬(P∨Q)\neg(P\vee Q)

The reading of formula 1 is "either not PP or QQ"; and the reading of formula 2 is "it is not the case that either PP or QQ". Without parentheses, the string

¬P∨Q\neg P \vee Q

would be ambiguous between these two readings.

An important tool that helps visualize the readings of different formulas is a syntax tree (also called a parse tree). The main idea is that each formula can be turned into a diagram using the following rules:

  1. Identify the main connective of the formula.

  2. If the main connective is a unary connective, write the formula without the unary connective below the formula. If the main connective is a binary connective, then below the formula, write the left disjunct/left conjunct/antecedent to the left of the right disjunct/right conjunct/consequent. Draw a line connecting the formula to the formula(s) below it.

  3. Repeat the above process until all formulas at the bottom of the diagram are atomic propositions.

For example, the syntax trees for formulas 1 and 2 are:

syntax trees

Example

What is the syntax tree of ((P∨Q)→R)((P\vee Q)\rightarrow R)?

Example

What is the syntax tree of (¬P→(Q∧R))(\neg P\rightarrow (Q\wedge R))?

Other Connectives#

We used only four connectives when defining formulas. A natural question is: Why focus only on these four connectives? What about other binary connectives that are found in everyday reasoning and mathematical writing? We will return to these questions later in the text. A very useful connective that is not part of the definition of a formula is the biconditional. The biconditional is a binary connective, expressed with the symbol "↔\leftrightarrow", that means "...if, and only if,...". (Some texts use the "≡\equiv" symbol.) We can add this connective to the definition of a formula by adding the following clause to item 3 of the rules to construct formulas:

  • If XX and YY are formulas, then (X↔Y)(X\leftrightarrow Y) is a formula.

However, for simplicity, it is more convenient to treat the biconditional as shorthand for a longer formula. We will say that "(X↔Y)(X\leftrightarrow Y)" is short for "((X→Y)∧(Y→X))((X\rightarrow Y)\wedge(Y\rightarrow X))". For example, the formula

(P∧Q)↔(R↔¬S)(P\wedge Q)\leftrightarrow (R\leftrightarrow\neg S)

is short for the formula

(((P∧Q)→((R→¬S)∧(¬S→R)))∧(((R→¬S)∧(¬S→R))→(P∧Q))).(((P\wedge Q)\rightarrow ((R\rightarrow\neg S)\wedge (\neg S\rightarrow R))) \wedge \\ (((R\rightarrow\neg S)\wedge (\neg S\rightarrow R))\rightarrow (P\wedge Q))).

Simplifying Notation#

The use of parentheses in formulas ensures that every formula can be read in one way. The downside is that having too many parentheses in a formula can make the formula difficult to read. In order to simplify the notation, we will follow some conventions to allow some parentheses to be dropped from a formula. You are already familiar with this from algebra: 3∗2+13*2 + 1 is evaluated as (3∗2)+1=7(3*2) + 1 = 7 rather than 3∗(2+1)=93*(2+1) = 9. We will adopt the following conventions to simplify the reading of formulas. (Other conventions are used in some logic texts, but we will only need the following three.)

  1. The outermost parentheses can be removed. For example, ((P∧R)→Q)((P\wedge R)\rightarrow Q) can be replaced with (P∧R)→Q(P\wedge R)\rightarrow Q.
  2. Group conjunctions and disjunctions before conditionals (including the biconditional). For example,
    • (P∧Q)→R(P\wedge Q) \rightarrow R is the same as P∧Q→RP\wedge Q \rightarrow R.
    • (P∧Q)→(R∨S)(P\wedge Q) \rightarrow (R\vee S) is the same as P∧Q→R∨SP\wedge Q \rightarrow R\vee S.
    • P↔(R∨S)P \leftrightarrow (R\vee S) is the same as P↔R∨SP \leftrightarrow R\vee S.
  3. Group conjunctions and disjunctions to the left before the ones on the right. For example,
    • (P∧Q)∧R(P\wedge Q) \wedge R is the same as P∧Q∧RP\wedge Q \wedge R.
    • ((P→Q)∨R)∨S((P\rightarrow Q) \vee R)\vee S is the same as (P→Q)∨R∨S(P\rightarrow Q) \vee R \vee S.
    • ((P∨Q)∨R)∨S((P\vee Q) \vee R)\vee S is the same as P∨Q∨R∨SP\vee Q\vee R \vee S.

Practice Questions#

A. Identify the main connective of the following formulas.

  1. ((P∨Q)→¬R)∨S)((P\vee Q)\rightarrow \neg R) \vee S)
  1. ¬¬¬(P∨Q)\neg\neg \neg (P\vee Q)
  1. ¬P∧¬Q\neg P\wedge \neg Q
  1. (P∨Q)∧¬(¬P∧¬Q)(P\vee Q) \wedge \neg (\neg P\wedge \neg Q)
  1. ((P∨Q)∨R)∨Q((P\vee Q) \vee R)\vee Q

B. For each of the following formulas, identify the left and right disjuncts.

  1. (P∨Q)(P\vee Q)
  1. ((P∨Q)∨R)((P\vee Q) \vee R)
  1. (¬P∨(Q∨R))(\neg P \vee (Q\vee R))

C. For each of the following formulas, identify the left conjunct and the right conjunct.

  1. (¬P∧Q)(\neg P\wedge Q)
  1. ((P∧Q)∧¬(P∧R)((P\wedge Q) \wedge\neg (P\wedge R)
  1. (((Q∧R)∧S)∧Q)(((Q\wedge R) \wedge S)\wedge Q)

D. For each of the following formulas, identify the antecedent and consequent.

  1. (¬P→Q)(\neg P\rightarrow Q)
  1. ((P∨Q)→¬R)((P\vee Q) \rightarrow\neg R)
  1. ((Q→R)→(R→Q))((Q\rightarrow R) \rightarrow (R\rightarrow Q))

E. Using the conventions defined in the section Simplifying Notation, add parentheses to rewrite the following formulas in official notation:

  1. ¬P→Q∨¬R\neg P\rightarrow Q \vee \neg R
  1. P∧Q→¬R∨SP\wedge Q\rightarrow \neg R \vee S
  1. ¬(P∨Q∨R)→Q∧R\neg(P\vee Q\vee R)\rightarrow Q\wedge R
  1. P∧(Q→R)∧¬SP\wedge (Q\rightarrow R) \wedge \neg S
  1. ¬P∨¬¬Q∨R→S∧¬S\neg P\vee \neg\neg Q \vee R\rightarrow S\wedge \neg S

F. For each of the following questions, select the formula with variables such that the given formula is an instance of that formula.

  1. ¬P∨(Q∧R)\neg P \vee (Q \wedge R)

  2. P→P∨QP\rightarrow P \vee Q

  3. ¬¬P→P\neg \neg P \rightarrow P

  4. ¬((P→Q)∧(R∨S))→(¬(P→Q)∨¬(R∨S))\neg((P\rightarrow Q) \wedge (R\vee S)) \rightarrow (\neg (P\rightarrow Q) \vee \neg(R\vee S))

  5. (P→(¬Q∧R))→(¬P∨(¬Q∧R))(P\rightarrow (\neg Q\wedge R)) \rightarrow (\neg P \vee (\neg Q\wedge R))

G. Find the syntax trees for each of the following formulas:

  1. (A∨¬B)∧¬(C∨D)(A\vee \neg B)\wedge \neg (C\vee D)
  2. A∨B→¬C∨DA\vee B \rightarrow \neg C\vee D
  3. ¬(A∨((B→¬C)∧D))\neg (A\vee ((B \rightarrow \neg C)\wedge D))
  4. ¬(A∨B)→(¬A∧¬B)\neg (A\vee B) \rightarrow (\neg A\wedge \neg B)
  5. ¬¬P∨¬P→Q\neg\neg P\vee\neg P \rightarrow Q