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, \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., $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 ($X$, $Y$, and $Z$), possibly with subscripts (e.g., $X_1$, $X_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, \ldots, P, Q, R, \ldots, U, V, W$, $P_1, P_2, \ldots$ is a formula.
2. If $X$ is a formula, then $\neg X$ is a formula.
3. If $X$ and $Y$ are formulas, then so is $(X\vee Y)$, $(X\wedge Y)$, and $(X\rightarrow Y)$.
4. Nothing else is a formula.

Examples of formulas constructed using these rules include:

• $(P\vee\neg P)$,
• $\neg (P\rightarrow Q)$,
• $((P\vee Q)\wedge \neg R)$, and
• $\neg\neg(P\vee R)$.

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

Example

$(P\vee \neg P)$ is a formula:

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

Example

$\neg(P\rightarrow Q)$ is a formula:

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

Example

$((P\vee Q)\wedge \neg R)$ is a formula:

1. Since $P$, $Q$ and $R$ are atomic propositions, they are formulas according to rule 1.
2. Since $R$ is a formula, $\neg R$ is a formula according to rule 2.
3. Since $P$ and $Q$ are formulas, $(P\vee Q)$ is a formula according to rule 3.
4. Since $(P\vee Q)$ and $\neg R$ are formulas, $((P\vee Q)\wedge \neg R)$ is a formula according to rule 3.

Example

$\neg\neg(P\vee R)$ is a formula:

1. Since $P$ and $R$ are atomic propositions, they are formulas according to rule 1.
   
2. Since $P$ and $R$ are formulas, $(P\vee R)$ is a formula according to rule 3.
   
3. Since $(P\vee R)$ is a formula, $\neg(P\vee R)$ is a formula according to rule 2.
   
4. Since $\neg(P\vee R)$ is a formula, $\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\vee\wedge\ Q)$: Rule 3 requires that a single connective is written between two formulas.
• $\vee P$: Rule 3 requires that a connectives is written between two formulas.
• $\neg (P)$ or $(\neg P)$: Rule 2 does not use parentheses when constructing a formula.
• $P\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\vee Q$ will be a formula.
• $(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 $X$ and $Y$ and the one on the right is constructed using atomic propositions $P$ and $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 $P$ and the formula $\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\vee \neg Q)$: Let $X$ be $P$ and $Y$ be $Q$.
2. $((P\wedge Q) \vee \neg \neg R)$: Let $X$ be $(P\wedge Q)$ and $Y$ be $\neg R$.
3. $((P\vee \neg Q) \vee \neg (P\vee \neg Q))$: Let $X$ be $(P\vee \neg Q)$ and $Y$ be $(P\vee \neg Q)$

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

$$(X\vee P)$$

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

1. $(Q\vee P)$: Let $X$ be $Q$.
2. $(P\vee P)$: Let $X$ be $P$.
3. $(((A\vee B) \wedge \neg C)\vee P)$: Let $X$ be $((A\vee B) \wedge \neg C)$.

Terminology

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

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 $(\neg P\vee Q)$ is $\vee$, and the main connective of $\neg(P\vee Q)$ is $\neg$.

Lecture

Slides

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. $(\neg P\vee Q)$
2. $\neg(P\vee Q)$

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

$$\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:

Example

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

Lecture

Slides

Example

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

Lecture

Slides

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 $X$ and $Y$ are formulas, then $(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\leftrightarrow Y)$" is short for "$((X\rightarrow Y)\wedge(Y\rightarrow X))$". For example, the formula

$$(P\wedge Q)\leftrightarrow (R\leftrightarrow\neg S)$$

is short for the formula

$$(((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 + 1$ is evaluated as $(3*2) + 1 = 7$ rather than $3*(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\wedge R)\rightarrow Q)$ can be replaced with $(P\wedge R)\rightarrow Q$.
2. Group conjunctions and disjunctions before conditionals (including the biconditional). For example,
   • $(P\wedge Q) \rightarrow R$ is the same as $P\wedge Q \rightarrow R$.
   • $(P\wedge Q) \rightarrow (R\vee S)$ is the same as $P\wedge Q \rightarrow R\vee S$.
   • $P \leftrightarrow (R\vee S)$ is the same as $P \leftrightarrow R\vee S$.
3. Group conjunctions and disjunctions to the left before the ones on the right. For example,
   • $(P\wedge Q) \wedge R$ is the same as $P\wedge Q \wedge R$.
   • $((P\rightarrow Q) \vee R)\vee S$ is the same as $(P\rightarrow Q) \vee R \vee S$.
   • $((P\vee Q) \vee R)\vee S$ is the same as $P\vee Q\vee R \vee S$.

Practice Questions

A. Identify the main connective of the following formulas.

1. $((P\vee Q)\rightarrow \neg R) \vee S)$

2. $\neg\neg \neg (P\vee Q)$

3. $\neg P\wedge \neg Q$

4. $(P\vee Q) \wedge \neg (\neg P\wedge \neg Q)$

5. $((P\vee Q) \vee R)\vee Q$

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

1. $(P\vee Q)$

2. $((P\vee Q) \vee R)$

3. $(\neg P \vee (Q\vee R))$

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

1. $(\neg P\wedge Q)$

2. $((P\wedge Q) \wedge\neg (P\wedge R)$

3. $(((Q\wedge R) \wedge S)\wedge Q)$

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

1. $(\neg P\rightarrow Q)$

2. $((P\vee Q) \rightarrow\neg R)$

3. $((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. $\neg P\rightarrow Q \vee \neg R$

2. $P\wedge Q\rightarrow \neg R \vee S$

3. $\neg(P\vee Q\vee R)\rightarrow Q\wedge R$

4. $P\wedge (Q\rightarrow R) \wedge \neg S$

5. $\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. $\neg P \vee (Q \wedge R)$

   $\neg X \vee Y$

   $(\neg X \vee Y) \wedge Z$

   $(\neg X \wedge Y)$

   ​

   Let $X$ be $P$ and $Y$ be $(Q\wedge R)$.

2. $P\rightarrow P \vee Q$

   $(X \rightarrow X) \vee Y$

   $X \rightarrow (X\vee Y)$

   $X\vee Y$

   ​

   First add parentheses: $P\rightarrow (P \vee Q)$.
   Let $X$ be $P$ and $Y$ be $Q$.

3. $\neg \neg P \rightarrow P$

   $\neg X \rightarrow X$

   $X \rightarrow X$

   $\neg\neg X \rightarrow X$

   ​

   Let $X$ be $P$.

4. $\neg((P\rightarrow Q) \wedge (R\vee S)) \rightarrow (\neg (P\rightarrow Q) \vee \neg(R\vee S))$

   $\neg (X \wedge Y) \rightarrow (\neg X\vee \neg Y)$

   $\neg (X \wedge Y) \rightarrow (\neg X\wedge \neg Y)$

   $\neg (X \vee Y) \rightarrow (\neg X\wedge \neg Y)$

   ​

   Let $X$ be $(P\rightarrow Q)$ and $Y$ be $(R\vee S)$.

5. $(P\rightarrow (\neg Q\wedge R)) \rightarrow (\neg P \vee (\neg Q\wedge R))$

   $X\rightarrow (\neg X \vee Y)$

   $(X\rightarrow Y) \rightarrow (\neg X\vee Y)$

   $(X \rightarrow (Y\wedge Z)) \rightarrow (X\vee \neg (Y\wedge Z))$

   ​

   Let $X$ be $P$ and $Y$ be $(\neg Q\wedge R)$.

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

1. $(A\vee \neg B)\wedge \neg (C\vee D)$
2. $A\vee B \rightarrow \neg C\vee D$
3. $\neg (A\vee ((B \rightarrow \neg C)\wedge D))$
4. $\neg (A\vee B) \rightarrow (\neg A\wedge \neg B)$
5. $\neg\neg P\vee\neg P \rightarrow Q$