1.1
Sentential Logic

Purpose of Section

To introduce sentential (sen-TEN-shuhl) or propositional logic and the fundamental idea of a sentence (or proposition) and show how simple sentences can be combined using the logical connectives "and," "or," and "not" to form compound sentences. We then analyze the meaning of these connectives by means of truth tables and then introduce the concepts of logical equivalence, tautologies, and contradictions. We close by introducing conjunctive and disjunctive normal forms of logical expressions.

1.1.1 Introduction

So what is mathematics? The word itself is derived from the Greek word mathematike, meaning "knowledge" or "learning." To both the practitioners of mathematics as well as the general public, the definition of the Queen of the Sciences varies widely.

• One of the greatest mathematician of Greek antiquity, Aristotle (384-322 BCE) defined mathematics as follows:

Mathematics is the science of quantity.

• Later, the Italian physicist Galileo (1564-1642), who was more interested in how it was applied, wrote:

"Mathematics is the language of the Universe and its characters are triangles, circles, and other geometric figures, without which it is impossible to understand a single word of it."

• A more generic definition is given by the encyclopedia Britannica, which defines mathematics as follows:

Mathematics is the science of numbers and shapes and the relations between them.

• Then there is the beauty in mathematics as observed by the physicist Albert Einstein, who wrote

Pure mathematics is, in its way, the poetry of logical ideas.

• Iranian mathematician Maryam Mirzakhani once shared her thoughts about mathematics.

There are times when I feel like I'm in a big forest and don't know where I'm going, but then I come to the top of a hill and can see everything more clearly.

1.1.2 Getting into Sentential Logic

Although mathematics uses symbolic notation, its logical arguments are formulated in natural languages and so it becomes necessary to examine the truth value of natural language sentences. We begin by introducing the logical system behind reasoning called sentential (or propositional) logic, which is the most basic formal system of logic1 and uses symbols and rules of inference such as

if P is true and P implies Q, then Q is true2

Sentential logic is generally the first topic introduced in a formal study of logic, followed by more involved systems of logic, like predicate logic and modal logic.

Important Note

The study of logic had its origins in many ancient cultures, but it was the writings of the Greek logician Aristotle (384-322 BCE) who most influenced Western culture in a collection of works known collectively as the Oranon.

English, as do all natural languages, contains various types of sentences, such as declarative, interrogative, exclamatory, and so on, which allow for the effective communication of thoughts and ideas. Some sentences are short and to the point, whereas others are long and rambling.

Some sentences can be classified as being either true or false, such as the sentence, "It will rain tomorrow." Although we may not know if it will rain or not rain, the sentence is nevertheless either true or false.

Other sentences, like the interrogatory sentence, "Why doesn't Burger King sell hotdogs?" or the exclamatory sentence, "Don't go there!" express thoughts, but have no truth or false value. Although statements like these are useful for effective communication, they are no concern in our study of logic. The sentences we study in this book are declarative and are intended to convey information. In formal logic, the word "sentence" is used in a technical sense as described in the following definition.

Definition

A sentence (or proposition) is a statement which is either true or false. If the sentence is true, we denote its truth value by the letter T and by F if it is false. In computer science they are often denoted by 1 and 0, respectively.

Example 1 Are the Following Statements Sentences?

1. Love is sharing your popcorn.
2. Come here!
3. N is an even integer.
4. Who first proved that p is a transcendental number?
5. Who was the greatest mathematician of the twentieth century?
6. This sentence is false.

1. a)-d)The statements are sentences. The reader can decide whether they are true or false.
2. e)The statement has no truth value so it is not a sentence.
3. f)Granted the statement is true or false, its truth value depends on the value of an unknown number N, so it is not considered a sentence. In Section 1.3, we will introduce quantifiers that will turn this statement into a sentence.
4. g)This is an interesting question, but questions are not sentences. The person who first proved p is a transcendental number was the German mathematician Ferdinand von Lindemann, who proved it in 1882. The number p is also irrational, which was proved by another German mathematician Johann Lambert in 1768.
5. h)This statement is not a sentence, but you can find candidates for the greatest mathematician by googling "famous mathematicians of the 20th century."
6. i)If you say the statement is true, then according to what the statement says, it is false. But on the other hand, if you say the statement is false, then the statement says it is true. In either case, we reach a contradiction. Hence, we conclude the statement is neither true nor false, and hence, it is not a sentence. This logical paradox that arises when a statement refers to itself in a negative way is one of the many forms of what is called the Russell paradox.

Liar Paradox

Consider the following statement

This sentence is not true.

This statement is paradoxical since if we say the sentence is true, the sentence itself says it is false, which yields a contradiction. On the other hand, if we say the sentence is false, the sentence itself says it is false, hence, it must be true. In either case, one is led to a contradiction, so one cannot say the sentence is true or false, and thus not what we call a sentence.

Russell's Barber Paradox

The Russell Barber Paradox is an example of a self-referential statement that refer to itself in a negative way. The paradox considers a barber in a small town that shaves all men in the town, but only those men, who do not shave themselves. The prophetic question then arises, does the barber shave himself? If you say the barber shaves himself, then barber does not shave himself since he only shaves those who do not shave themselves. On the other hand, if you say the barber does not shave himself, then he shaves himself since he shaves those who do not shave themselves. This paradox was formulated by the English logician Bertrand Russell (1872-1970) in 1901, and played a major role in the modern development set theory.

1.1.3 Compound Sentences ("AND," "OR," and "NOT")

In arithmetic, we combine numbers with operations +, × , -, and so on. In logic, we combine sentences with logical expressions. The sentences discussed thus far are examples of simple (or atomic) sentences since they are made up of a single thought or idea. It is possible to combine these sentences to form compound sentences using logical connectives.3

Important Note

It has been said that love and the ability to reason are the two most important human traits. Readers interested in the former must go elsewhere for advice, but if the reader is interested in the human trait of reasoning, you are in the right place.

Definition

Logical Connectives

Given the sentences P and Q, we define:

• Logical AND: The conjunction of P and Q, denoted P ? Q, is the sentence "P and Q" which is true when both P and Q are true, otherwise false.
• Logical OR: The disjunction of P and Q, denoted P ? Q, is the sentence "P or Q" which is true when at least one of P or Q are both true, otherwise false.
• NOT operator: The negation of P, denoted ~P, is the sentence "not P" and ~P is true when P is false, and ~P is false when P is true.

Example 2 Logical Conjunction

Let P and Q be the sentences

• P: "Jack went up the hill."
• Q:...