Chapter 3: Propositional Logic

Definition

A proposition is any sentence that is either true or false.

It is easy to think of example propositions. For example, “Japan is east of China” is a true proposition, while “3 is less than 2” is a false proposition.

You can have a proposition like “The ball is red” which is true when pointing to a red ball. That same proposition is false when pointing to a white ball.

It might even seem hard to think of sentences that are not propositions, until you see a few examples!

• Pick up milk when you go to the store.
• What time is it?
• Hooray!

None of the above sentences are either true or false, so these are sentences which are not propositions.

Out of a desire for abstraction, we will represent propositions by a single letter, like P. This is called a “propositional variable”.

This is just like how a mathematical variable is allowed to take a bunch of different numeric values. A propositional variable is allowed to be or “take on” a bunch of different propositions.

Therefore when we write P, we don’t necessarily know which proposition it refers to. For the purposes of logic, there are really just two interesting possibilities: P may be true or false.

This is our first introduction to syntax and semantics: The symbol P is the syntax of an expression.

The semantics are the truth-values assigned to variables. When choosing to give P the value "true", we imagine that P is some true sentence. If we choose to give P the value "false", then we imagine that P is some false sentence.

Because it is valuable to keep straight, which things are syntax and which are semantics, it is helpful to write each in a distinctive script. It is traditional to write syntax in standard italic letters. There is less standardization for the symbols used for semantics. To make them very visibly different from syntax, I'm going to write them in Devanagari.

We will use $ट$ for “true”, which is a Devanagari letter, pronounced similar to an English 'T'. So when you think of this, imagine the letter 'T' for "true".

We will use फ for "false", which is a Devanagari letter, pronounced like an English 'F'. So when you think of फ, imagine the letter 'F' for "false".

Notes on the use of Devanagari.

1. Placing a dot below the letter फ, to make फ, produces a sound in Devanagari which is closer to the English 'F' sound. But I figure, why bother? For our purposes I just want a distinct symbol, which somehow gestures at the idea of "false". The simpler letter फ is good enough!
2. I know that many English-speaking readers may be intimidated by letters from a language as different as Hindi. However, I promise that the number of Devanagari letters will be kept small. You will, in fact, learn many more new symbols which are standard logical symbols, than you will learn Devanagari letters.
3. In the definition below, we will write a sentence like $P^म=ट$. I recommend pronouncing this as "P in M is true."

Definition

Syntatic

A propositional variable is a variable (a symbol) which could denote any proposition.

Semantic

If $P_1,P_2,\dots$ are propositional variables, then a truth model (or just model for short, also sometimes called a truth-assignment or a truth-function) is an assignment of truth-values to the variables. The truth-values are true and false, represented by ट and फ.

We will denote a truth model by the symbol म (A Devanagari letter similar to 'M'.).

If म assigns ट to P, we write

$$P^{म}= ट$$

and if म assigns फ to P we write

$$P^{म} = फ$$

A model is a function.

The above establishes that a model assigns truth-value to propositional variables. Picking a model is basically just deciding which propositions get interpreted as true or false.

If we intend for the variable P to express “1 + 1 = 2” then we would pick a model, $म$, in which $P^{म}=ट$. If we use P to stand for “1 + 1 = 0” then we would pick our model such that $P^{म}=फ$.

But one might reasonably wonder “Ok, I think I get that. But like … what is a model?"

Technically, a model is a function. The inputs are the propositional variables and the outputs are truth-values.

Let’s see an example. Suppose that we begin from the proposition "This triangle is obtuse and isosceles". We might use P to reprensent "this triangle is obtuse" and Q to represent "this triangle is isosceles".

If the triangle that we are discussing is this one:

then this triangle is obtuse, therefore we should choose a model, $म_1$, such that $P^{म_1}=ट$.

Since the triangle is also isosceles, then we should also decide that our model assigns $Q^{म_1}=ट$.

On the other hand, if the triangle were

then this is not obtuse but it is isosceles. Therefore we should use the model

$$\begin{aligned} P^{म_2} =फ\\ Q^{म_2} = ट \end{aligned}$$

Exercise

Use the same P and Q above. That is to say, P is our symbol for "This triangle is obtuse," and Q is our symbol for "This triangle is isosceles."

What is the appropriate model for the following triangle?

Exercise

Consider two variables, P and Q, not necessarily as above.

List every possible model for these two variables.

(Here is one: $म_1$ is the model given by $P^{म_1} = ट$ and $Q^{म_2}=ट$.)

Exercise

Suppose that you have three propositional variables, P, Q, and R.

How many models are possible?

Consider the sentence

2 is prime and even.

This is a "conjunction" of two propositions,

• 2 is prime, and
• 2 is even.

We could represent the proposition “2 is prime” as the variable P.

We could represent “2 is even” as the variable Q.

Then we would represent the conjunction of P and Q as

$$P\land Q$$

That is to say, we will use the “up wedge” symbol to represent conjunction.

---

Recall that we are trying to develop the language of propositional logic, which is a set of "signifiers". The signifiers are the meaningful sequences of symbols. We've already see that an individual propositional variable is a signifier, because we gave it a semantic interpretation (in this context, that means that we assign it truth-value).

In propositional logic we will call the signifiers "formulas". So each propositional variable is a formula.

But moreover, every conjunction is also a formula, like $P\land Q$.

But moreover still, we can also form conjunctions of conjunctions, like

$$(P\land Q)\land R$$

We are also able to form more complex conjunctions, like

$$(P\land Q)\land (R\land S)$$

Definition

Let $\phi$ and $\psi$ be propositional formulas.

Then their syntactic conjunction (or just conjunction) is the formula $(\phi\land\psi)$. The conjunction of two formulas is also a propositional formula.

Note that when the parentheses are not needed, we may omit them. So for example, instead of writing $(P\land Q)$ we merely write $P\land Q$.

On the other hand, in $P\land (Q\land R)$, the parentheses around $(Q\land R)$ tells us which order the formulas are conjoined. If we dropped all parentheses and wrote $P\land Q\land R$, we would not know whether this means $(P\land Q)\land R$ or $P\land (Q\land R)$.

Therefore we are free to drop the outer-most parentheses for convenience, but only the outer-most.

---

Let’s see how the above definition implies that $P\land(Q\land R)$ is a propositional formula. First we note that Q and R are each variables, and therefore they are formulas.

Because Q and R are formulas, therefore $Q\land R$ is a formula.

P is a formula because it is a variable. Because P and $Q\land R$ are formulas, therefore $P\land(Q\land R)$ is a formula.

Exercise

The section above demonstrated how to show that $P\land (Q\land R)$ is a formula. In a similar style, show that $(P\land Q)\land (Q\land R)$ is a formula.

Explain why you cannot prove that $P\land$ is a formula.

Is $P\land\land P$ a formula?

Is $P\land P$ a formula?

Although the definition of conjunction above is correct, notice that it doesn’t actually tell you what conjunction is supposed to represent or what it’s supposed to do. It tells us the syntax, but not the semantics.

Recall that the semantics of propositional logic is concerned with truth-value.

In the following definition, we will state the rule that "true and true is true". For example, the sentence "3 is more than 2 and 3 is odd" is true, because it conjoins two true propositions. This rule is formally expressed by the equation

$$ट \land ट = ट$$

Definition

Semantic conjunction is the following operation, denoted by $\curlywedge$.

$$\begin{aligned} ट\curlywedge ट = ट\\\\ ट\curlywedge फ = फ\\\\ फ\curlywedge ट = फ\\\\ फ\curlywedge फ = फ \end{aligned}$$

Let $\phi$ and $\psi$ be formulas, and let $म$ be a model defined for $\phi$ and $\psi$.

Then $(\phi\land \psi)^{म}$ is defined to be equal to $\phi^{म}\curlywedge \psi^{म}$. Whatever this value is, we call it the (truth-)value of $\phi\land \psi$ in $म$. We may also refer to this as the evaluation of $\phi\land\psi$ in $म$.

Exercise

In the same way that one can read "$ट\curlywedge ट = ट$" as saying

True and true is true.

likewise interpret the other equations that define $\curlywedge$.

Note

Semantic conjunction is an example of a "boolean algebra operation". The values $ट$ and $फ$ are often called "boolean values".

A function is then called a "boolean algebra operation" if its inputs and outputs are boolean values.

Hence semantic conjunction, as well as several of the other operations below, are all boolean algebra operations.

Let’s see an example. Assume that we have a model, $म$, such that $P^{म} = ट$ and $Q^{म}= ट$. Let’s see how the definition above assigns a value to $P\land Q$.

$$\begin{aligned} (P\land Q)^{म} &= P^{म}\curlywedge Q^{म} \\ &= ट\curlywedge ट\\ &= ट \end{aligned}$$

The above calculation demonstrates that, in this model, we have $(P\land Q)^म = ट$.

---

Let’s do another. Let’s show that if P is false, Q is true, and R is true, then $((P\land Q)\land R)^{म}= फ$. The equations are numbered so that I can refer to and explain each of them later.

$$\begin{aligned} ((P\land Q)\land R)^{म} &\stackrel{1}{=} (P\land Q)^{म} \curlywedge R^{म} \\ &\stackrel2= (P^{म}\curlywedge Q^{म})\curlywedge ट \\ &\stackrel3= (फ \curlywedge ट)\curlywedge ट \\ &\stackrel4= फ \curlywedge ट\\ &\stackrel5= फ \end{aligned}$$

Here is an explanation of each equation above.

1. Definition of evaluation, applied $P\land Q$ and R.
2. Definition of evaluation, applied to P and Q. Also, the assumption that R is true.
3. The assumption that P is false and Q true.
4. The resulting value is $फ$.
5. The resulting value is $फ$.

Exercise

Let P represent a false proposition, Q and R represent true propositions.

Find $((P\land Q)\land (Q\land R))^{म}$.

Note that the semantics here are defined recursively.

• Base case: If $\phi$ is a propositional variable, then $\phi^{म}$ is defined by $म$. That is to say, the very definition of $म$ will tell us what $\phi^{म}$ is.
• Recursive case: If $\phi$ is a conjunction of two other formulas, $\phi=(\chi\land\psi)$, then

$$\begin{aligned} \phi^{म} &= \chi^{म}\curlywedge \psi^{म} \end{aligned}$$

The recursive case, is “recursive” because it computes the value from simpler cases. Those simpler values are the values $\chi^{म}$ and $\psi^{म}$.

It can help to display how the conjunction acts on truth-values, by putting this information into a table. It’s just a nice, dense summary of all the same information that we discussed above.

$$\begin{array}{|c|c||c|c|c|} \hline P & Q & P & \land & Q \\\hline \color{red} ट & \color{red}ट & & \color{red}ट & \\ ट &फ & &फ & \\ \color{red}फ & \color{red}ट & & \color{red}फ & \\ फ &फ & &फ & \\\hline \end{array}$$

The rows are in alternating colors just for readability—the colors don’t mean anything.

Each row corresponds to a model. For example, if $म$ is the model which assigns $P^{म}=फ$ and $Q^{म}=फ$, then this is represented in the last row of the table.

In this last row, under $\land$, it holds the value of the proposition $P\land Q$. This is the black $फ$. This comes from computing

$$\begin{aligned} (P\land Q)^{म} &= P^{म}\curlywedge Q^{म}\\ &=फ\curlywedgeफ\\ &=फ \end{aligned}$$

Consider the proposition "3 is even or prime". This is called a "disjunction" of the propositions

• 3 is even.
• 3 is prime. If we represent "3 is even" by the variable P, and "3 is prime" by the variable Q, then we will represent their disjunction "3 is even or prime" by

$$P\lor Q$$

All of this is very similar to the conversation for conjunction.

Definition

Let $\phi$ and $\psi$ be propositional formulas.

We define their **syntactic disjunction to be the expression

$$(\phi\lor\psi)$$

We define the boolean operator, semantic disjunction, by

$$\begin{aligned} ट\curlyvee ट = ट\\\\ ट\curlyvee फ = ट\\\\ फ\curlyvee ट = ट\\\\ फ\curlyvee फ = फ \end{aligned}$$

If $म$ is a model defined for $\phi$ and $\psi$, then we define

$$(\phi\lor\psi)^{म}= \phi^{म}\curlyvee \psi^{म}$$

Here is the truth-table for disjunction:

$$\begin{array}{|c|c||c|c|c|} \hline P & Q & P & \lor & Q \\\hline \color{red}ट & \color{red}ट & & \color{red}ट & \\ ट & फ & & ट & \\ \color{red}फ & \color{red}ट & & \color{red}ट & \\ फ & फ & & फ & \\\hline \end{array}$$

Exercise

In the same way that $ट\curlyvee ट = ट$ means

True or true is true.

likewise explain the other equations which define $\curlyvee$.

Exercise

Suppose that P and Q are true while R is false.

Find $(P\lor (Q\land R))^{म}$.

Recall the definition of a composite number: An integer $n\ge 2$ is composite if it is not prime.

We say that the definition of "composite" is the negation of the definition of prime.

If we represent the proposition “8 is prime” by P, then its negation is represented by

$$\neg P$$

Definition

Let $\phi$ be a propositional formula.

Its syntactic negation is the formula $\neg \phi$. Any negation of a formula is a formula.

We define the boolean operation of semantic negation by

$$\begin{aligned} \sim ट =फ\\\simफ =ट \end{aligned}$$

For a model $म$ defined for $\phi$, we define

$$(\neg \phi)^{म} = \ \ \sim \phi^{म}$$

The truth-table for negation is

$$\begin{array}{|c||c|c|}\hline P & \neg & P \\\hline \color{red}ट & \color{red}फ & \\ फ &ट & \\\hline \end{array}$$

Notice that since the table has only two rows. This is due to the fact that negation only operates on a single proposition. That proposition has only two possible values, true or false, and therefore requires only two rows of a table.

Exercise

Show that $\sim(\sim ट) = ट$ and $\sim(\sim फ) = फ$.

After you have done this, we now know that $\sim(\sim x) = x$ for each $x\in \{ट,फ\}$.

Let $म$ be a model defined for P.

Explain why $(\neg(\neg P))^{म} = P^{म}$, no matter which model is used.

Arguably, the conditional the most important operator, because it plays a role in nearly every mathematical theorem.

Let’s take for example the conditional sentence,

If $X\subseteq \Bbb Z$ is a set of integers which is bounded below, then X has a minimum.

“If” usually indicates which part of the conditional we call the “antecedent”. This is the part which you are meant to "imagine" or "assume" is true. So for this theorem you are supposed to assume that X is a set of integers bounded below.

"Then" indicates the "consequent" of the conditional. This is the part of the sentence which is claimed to be true, as long as we assume the antecedent. The consequent of the example sentence is "X has a minimum".

If P and Q are propositional variables, then $P\to Q$ represents "if P then Q".

Most people would guess that $P\to Q$ is true when both P and Q are true. Hence we have the first row of the truth-table.

$$\begin{array}{|c|c||c|c|c|}\hline P&Q&P&\to &Q\\\hline \color{red}ट & \color{red}ट & & \color{red}ट & \\ \end{array}$$

Now what if P is true and Q false? For example what if we state “If 2 is prime then 2 is odd”? Here P is “2 is prime” and Q is “2 is odd”. I think we easily understand that this statement is false because 2 is prime, but 2 is not odd.

Therefore the next row of the table is:

$$\begin{array}{|c|c||c|c|c|}\hline P&Q&P&\to &Q\\\hline \color{red}ट & \color{red}ट & & \color{red}ट & \\ ट & फ & & फ & \\ \end{array}$$

The part that many people struggle to understand comes next.

What are we supposed to say, when P is false? Consider some example “if-then” propositions, in which the antecedent is false.

• If 2 is bigger than 3, then triangles have three sides.
• If 2 is bigger than 3, then triangles are round.

In the first example, P is false, and Q is true. In the second example, P is false and Q is false. What should the truth-table contain for these rows?

Note

It is traditional for mathematicians to regard both of these as true statements.

Here is an argument for why that’s a good idea:

It is clearly a true principle that “if x is a natural number divisible by 4, then x is even”. As such, if we “plug in” any natural number x, we should get a true proposition.

Therefore if we plug in $x=5$, the result must be a true proposition. When we do, we have the proposition “if 5 is a natural number divisible by 4, then 5 is even”. The antecedent is false, and the consequent is false.

Therefore when the antecedent and consequent are false, the conditional must be true. One can find a similar argument for the case when the antecedent is false and the consequent true.

The conditional truth-table is

$$\begin{array}{|c|c||c|c|c|}\hline P&Q&P&\to &Q\\\hline \color{red}ट & \color{red}ट & & \color{red}ट & \\ ट & फ & & फ & \\ \color{red} फ & \color{red} ट & & \color{red} ट & \\ फ & फ & & ट & \\\hline \end{array}$$

Note

Note: This is called the “material conditional”.

The understanding of “if-then” presented above, is the one that is used throughout mathematics.

However, it is not a good model for how most English language uses the “if-then” construction.

Consider "if you had stood two inches to the left then you would have been crushed".

We cannot analyze this with propositional logic, because the antecedent "you had stood two inches to the left" does not have truth-value! If we say this about Buster Keaton (pictured above) then he was not two inches to the left. So what does "you had stood two inches to the left" even mean here? Said outside the context of the if-then structure, this is just grammatically ill-formed.

But the entire idea of propositional logic, is to determine the meaning of the whole sentence (here, the conditional) by understanding each component in isolation, and then composing those components. This simply does not work with counter-factual conditionals like the one above.

Just as the material conditional is inadequate for analyzing counterfactuals, it is also unable to adequately express causal conditionals.

The interested reader is welcome to research the topic of the material conditional, and related ideas.