Skip to main content

Section 2.1 Introduction to Logic

Symbolic logic uses formal mathematics with symbols to represent statements in language. Everyday language includes factual statements, opinions, commands, and questions. Symbolic logic only deals with statements and opinions, but not commands or questions. Aristotle was one of the early pioneers of propositional logic.

In mathematics, there are three important kind of mathematical statements.

Definition 2.1.1.

  • Universal statements, of the form “All \(X\) have property \(Y\)”.

  • Conditional statements, of the form “If \(X\) is true, then \(Y\) is true.”

  • Existential statements, of the form “There is at least one \(X\) for which property \(Y\) is true”.

These kinds of statements can be combined to form more complex statements.

Subsection 2.1.1 Statements, Propositional Logic, and Symbolic Logic

Definition 2.1.2.

A statement (or proposition) is a declarative sentence (a sentence that declares a fact) that is either definitely true or definitely false, but not both or indeterminate.

Statements are typically are represented by the letters \(P, Q, R\text{,}\) and \(S\text{.}\) In applications, letters that represent the sentence are typically used. For example, for the statement “John is coming to the party” might be represented by \(J\) (for “John”).

Or, more generally, letters can represent arbitrary statements, called a propositional variable. This is analogous to that letters like \(x\) represent arbitrary numbers.

Examples of sentences which are not statements include:

  • Commands. For example, “Tie your shoes.”

  • Questions. For example, “Are you having fun?”

  • Paradoxes or contradictions. This most often occurs with sentences that refer to themselves (are self-referential). For example, “This sentence is false.” (called the liar paradox). This is a paradox because if the sentence is true, then the sentence itself tells us it is false, and the sentence cannot both be true and false. Similarly, if the sentence is false, then the sentence tells us it is not false (i.e. true), leading to another contradiction. Thus, no truth value can be assigned to the statement.

Roughly, logic and mathematics can only apply to statements.

Subsection 2.1.2 Simple and Compound Sentences

Roughly, a simple sentence is a sentence that does not “contain” another complete sentence as a component. Intuitively, a simple sentence only says “one thing”.

Simple sentences can be combined together in various ways to form a compound sentence, which is simply a sentence that contains multiple simple statements. These simple sentences are combined with words such as,

  • “not”, called a negation.

  • “and”, called a conjunction.

  • “or”, called a disjunction

  • “if..., then...”, called an implication, or conditional.

  • “if and only if”, called a biconditional.

These words are called logical connectives.

Subsection 2.1.3 Negation (Not)

Definition 2.1.3.

Let \(P\) be a statement. The negation of \(P\text{,}\) denoted by \(\neg P\text{,}\) is a statement which is true if \(P\) is false, and is false when \(P\) is true.

In other words, the negation of \(P\) has opposite truth values as \(P\text{.}\)

At a very basic level, to determine the negation of a statement, one can add “it is not true that” to the beginning of the statement. The negation often occurs in English as the connective “not”.

The negation of “It is raining today.” is “It is not true that is raining today” or more simply, “It is not raining today”.

The statement “I did not take your hat” is the negation of the statement “I did take your hat” or more simply, “I took your hat”.

The negation of a statement that is itself a negation is the original statement. For example, the negation of “The grass is not green”, is “It is not true that the grass is not green”, or, “The grass is green” (a double negative).

The fact that the negation of a statement is false when the statement is true, and true when the statement is false, can be summarized in a so-called truth table.

Definition 2.1.6.

A truth table is a table that includes all possible combinations of truth values for each simple statement, and the truth value of any compound statements in each case.

For the single statement \(P\text{,}\) there are two possible values of \(P\text{:}\) true and false. The truth table for negation is given by,

\begin{equation*} \begin{array}{c|c} P \amp \neg P \\ \hline T \amp F \\ \hline F \amp T \\ \end{array} \end{equation*}

Each row of a truth table can be thought of as one possible state of affairs in the world. Here, there are only two possibilities.

Subsection 2.1.4 Disjunction (Or)

In English, the connective ``or" can have an ambiguous meaning. For example, the sentence,

\begin{equation*} \text{} \end{equation*}

probably means you have to choose between cake and fruit, and you cannot have both of them. In logic, this is called the exclusive or. However, the sentence,

\begin{equation*} \text{} \end{equation*}

probably means that people can enter if they have a driver's license, a passport, or they have both. This is called the inclusive or. This is the main or default “or” that is used in logic.

Definition 2.1.7.

Let \(P, Q\) be statements. The disjunction (or, or), denoted by \(P \lor Q\text{,}\) is a statement that is true if at least one of \(P\) or \(Q\) is true, and is false if both \(P\) and \(Q\) are false.

For two statements, there are 4 possible combinations: \(TT\text{,}\) \(TF\text{,}\) \(FT\text{,}\) and \(FF\text{.}\) The truth table for disjunction is given by,

\begin{equation*} \begin{array}{c|c|c} P \amp Q \amp P \lor Q \\ \hline T \amp T \amp T \\ \hline T \amp F \amp T \\ \hline F \amp T \amp T \\ \hline F \amp F \amp F \end{array} \end{equation*}

The order of the combinations (\(TT\text{,}\) then \(TF\text{,}\) \(FT\text{,}\) and finally \(FF\)) is just a convention, however it is preferred because it makes things more organized.

Note that just because a statement uses a logical connector such as “or”, does not necessarily mean it is an “or” statement. For example, “They decided to play Truth or Dare.” contains an “or”, however, it is used in part of a name, and is not used to connect simple sentences.

Subsection 2.1.5 Conjunction (And)

Definition 2.1.8.

Let \(P, Q\) be statements. The conjunction of \(P\) and \(Q\text{,}\) denoted by \(P \land Q\text{,}\) is a statement that is true if both \(P\) and \(Q\) are true, and is false if at least one of \(P\) and \(Q\) are false.

The truth table for conjunction is given by,

\begin{equation*} \begin{array}{c|c|c} P \amp Q \amp P \land Q \\ \hline T \amp T \amp T \\ \hline T \amp F \amp F \\ \hline F \amp T \amp F \\ \hline F \amp F \amp F \end{array} \end{equation*}

Subsection 2.1.6 Exclusive Or

Definition 2.1.9.

Let \(P, Q\) be statements. The exclusive or of \(P\) and \(Q\text{,}\) denoted by \(P \oplus Q\text{,}\) is a statement that is true if exactly one of \(P\) or \(Q\) are true.

The truth table for exclusive or is given by,

\begin{equation*} \begin{array}{c|c|c} P \amp Q \amp P \oplus Q \\ \hline T \amp T \amp F \\ \hline T \amp F \amp T \\ \hline F \amp T \amp T \\ \hline F \amp F \amp F \end{array} \end{equation*}