Beginning Rigorous Mathematics/Basic Logic

From Wikibooks, open books for an open world
Jump to: navigation, search

In the previous chapter we made clear what a logical statement is. In this chapter we will define and derive rules for working with compound logical statements. The symbols used to combining statements are called "logical operators".

In this section the symbols and denote any logical statements.

Logical operators and Truth Tables[edit]

Truth tables are used in two ways. Firstly to define exactly what a certain compounded statement means, and secondly to derive the properties of more complicated compounded statements. Truth tables exhaust all possible combinations of the truth of falsehood of the constituent statements in the compounded statement to yield exactly under what combinations of truth and falsehood of the constituent statements, the compound statement is true or false.

Definitions[edit]

Not, Negation[edit]

We define the symbol "" to mean "not". If is a statement then is also a statement. It inverts the truth or falsehood of logical statements. In other words, if the statement is true, then the statement is false and if is false, then is true. We call the negation of .

We rigorously define the symbol "" by the following truth table

T F
F T

Even though "not" simplest logical operator, the negation of statements is important when trying to prove that certain objects have or do not have certain properties. It makes the skill of being able to correctly negate statements an important one.

And, Conjunction[edit]

We define the symbol "" to mean "and". If and are statements then is also a statement, is called the conjunction of and , and it reads " AND ". The compound statement is true only when both statements and are true.

We rigorously define the symbol "" by the following truth table

T T T
T F F
F T F
F F F


Or, Disjunction[edit]

We define the symbol "" to mean "or". If and are statements then is also a statement, is called the disjunction of and , and it reads " OR ". The compound statement is true only when either or or both statements and are true.

We rigorously define the symbol "" by the following truth table

T T T
T F T
F T T
F F F

If ... then, Implication[edit]

We define the symbol "" to mean "implies". If and are statements then is also a statement and it reads " IMPLIES " or also "IF THEN ". The compound statement is false only when is true and is false. We call the hypothesis and the Conclusion of the implication.

We rigorously define the symbol "" by the following truth table

T T T
T F F
F T T
F F T

We call the statement "" the converse of "".

Logical implication plays an important role since most theorems take on the form of an implication.

If and only if, Equivalence[edit]

We define the symbol "" to mean "if and only if". If and are statements then is also a statement and it reads " is true if and only if is true".

We rigorously define the symbol "" by the following truth table

T T T
T F F
F T F
F F T


Basic results[edit]

In this section we will prove some basic equivalences for compounded logical statements. We say that two (compound) statements are logically equivalent when written in the same truth table, their columns are identical. Knowing how to write statements into logically equivalent statements is very useful in the sense that a statement might be difficult to prove, yet a logically equivalent statement might be easier to prove.

Lemma 1 (DeMorgan's law, part 1)[edit]

is logically equivalent to

Proof

T T T F F F F
T F F T F T T
F T F T T F T
F F F T T T T

Since the columns for the compound statements are identical, they are logically equivalent. QED

Proving the following theorems are left as exercises.

Lemma 2 (DeMorgan's law, part 2)[edit]

is logically equivalent to

Lemma 3[edit]

is logically equivalent to

Lemma 4[edit]

is logically equivalent to

Lemma 5[edit]

is logically equivalent to

Lemma 6 (Contrapositive)[edit]

is logically equivalent to

Lemma 7[edit]

is logically equivalent to


Predicates and Quantifiers[edit]

A predicate is defined to be a function mapping any set into the set where the symbols and mean 'true' and 'false' respectively. A predicate can be thought of a collection of statements, one for each element of the domain of the predicate.

For example, we may define the predicate by "x is an even integer". Instead of writing "" and "" we will say and write " is false" and " is true".

If is a predicate, then the predicate defined to be such that is true exactly when is false and is false exactly when is true, is called the negation of .

There are two quantifiers denoted by the symbols "" and "" which read "for all" and "there exists" respectively.

Let be a predicate and let be any subset of (subsets are discussed in the next section). Then which reads "For all elements contained in , P(x) is true." is a statement, and is defined to be true exactly when is true for every element contained in .

Similarly, which reads "There exists an element contained in such that P(x) is true." is a statement, and is defined to be true exactly when is true for at least one element contained in .

We define the negation of statements involving quantifiers as follows and

Logical rules of inferrence[edit]

Proving the truth of statements require knowledge of standard valid logical rules of inference, the most important of which are:

Adjunction[edit]

If and are both true then so is

Simplification[edit]

If is true then is true.

If is true then is true.

Addition[edit]

If is true then is true (regardless of the truth or falsehood of ).

Disjunctive syllogism[edit]

If is true, and is false then is true.

If is true, and is false then is true.

Modus Ponens[edit]

If is true, and is true, then is true.

Modus Tollens[edit]

If is true, and is false, then is false.


In a mathematical proof, these rules are usually not explicitly mentioned as they have become second nature to mature students and authors of mathematics. We will be very explicit and pedantic in the proofs of some results in the following chapters, so will mention them.