Chapter 01 - The Foundations - Logic and Proofs

The Foundations : Logic and Proofs

Propositional Logic

A proposition is a declarative sentence (that is, a sentence that declares a fact) that is either true or false, but not both. We use letters to denote propositional variables (or sentential variables), that is, variables that represent propositions, just as letters are used to denote numerical variables. The conventional letters used for propositional variables are p, q, r, s, .

The truth value of a proposition is true, denoted by T, if it is a true proposition, and the truth value of a proposition is false, denoted by F, if it is a false proposition. Propositions that cannot be expressed in terms of simpler propositions are called atomic propositions. The area of logic that deals with propositions is called the propositional calculus or propositional logic.

Logical Operators

• Negation (p) : Let p be a proposition. The negation of p, denoted by p (also denoted by p), is the statement “It is not the case that p.” The proposition p is read “not p.” The truth value of the negation of p, p, is the opposite of the truth value of p.

• Conjunction (p q) : Let p and q be propositions. The conjunction of p and q, denoted by p q, is the proposition “p and q.” The conjunction p q is true when both p and q are true and is false otherwise.

• Disjunction (p q) : Let p and q be propositions. The disjunction of p and q, denoted by p q, is the proposition “p or q.” The disjunction p q is false when both p and q are false and is true otherwise.

• XOR (p q) : Let p and q be propositions. The exclusive or of p and q, denoted by p q (or p XOR q), is the proposition that is true when exactly one of p and q is true and is false otherwise.

• NAND & NOR (p ∣ q & p q) : The proposition p NOR q is true when both p and q are false, and it is false otherwise. The propositions p NAND q and p NOR q are denoted by p ∣ q and p q, respectively. (The operators | and are called The Sheffer Stroke and The Peirce Arrow.)

Conditional Statements

• Implication (p q) : Let p and q be propositions. The conditional statement p q is the proposition “if p, then q.” The conditional statement p q is false when p is true and q is false, and true otherwise. In the conditional statement p q, p is called the hypothesis (or antecedent or premise) and q is called the conclusion (or consequence).

• Biconditional (p q) : Let p and q be propositions. The bi-conditional statement p q is the proposition “p if and only if q”. The bi-conditional statement p q is true when p and q have the same truth values, and is false otherwise. Biconditional statements are also called bi-implications.

Truth Tables

p	q	p	q	p q	p q	p q	p q	p q
T	T	F	F	T	T	F	T	T
T	F	F	T	F	T	T	F	F
F	T	T	F	F	T	T	T	F
F	F	T	T	F	F	F	T	T

Converse, Contrapositive, AND Inverse

The proposition q p is called the converse of p q. The contrapositive of p q is the proposition q p. The proposition p q is called the inverse of p q.

p	q	p	q	p q	q p	q p	p q
T	T	F	F	T	T	T	T
T	F	F	T	F	F	T	T
F	T	T	F	T	T	F	F
F	F	T	T	T	T	T	T
So p q is equivalent to its contrapositive q p and q p is equivalent to its contrapositive p q.

Propositional Equivalences

• A compound proposition that is always true, no matter what the truth values of the propositional variables that occur in it, is called a tautology.
• A compound proposition that is always false is called a contradiction.
• A compound proposition that is neither a tautology nor a contradiction is called a contingency.

The compound propositions p and q are called logically equivalent if p q is a tautology. The notation p q denotes that p and q are logically equivalent.

De Morgan’s Laws : (p q) p q (p q) p q

Logical Equivalences

Name	Equivalences
Identity Laws	p T p p F p
Domination Laws	p T T p F F
Idempotent Laws	p p p p p p
Double Negation Law	(p) p
Commutative laws	p q q p p q q p
Associative laws	(p q) r p (q r) (p q) r p (q r)
Distributive laws	p (q r) (p q) (p r) p (q r) (p q) (p r)
De Morgan’s laws	(p q) p q (p q) p q
Absorption laws	p (p q) p p (p q) p
Negation laws	p p T p p F

Logical Equivalences Involving Biconditional Statements.

• p q (p q) (q p)
• p q p q
• p q (p q) (p q)
• (p q) p q
• (p q) (p q) (The Conditional-Disjunction Equivalence)

We will sometimes use the notation : p for p p p and p for p p p. Using this notation, the extended version of De Morgan’s laws can be written concisely as : ( p) p.

Predicates and Quantifiers

Predicates

The statement “x is greater than 3” has two parts. The first part, the variable x, is the subject of the statement. The second part—the predicate, “is greater than 3”—refers to a property that the subject of the statement can have. We can denote the statement “x is greater than 3” by P(x), where P denotes the predicate “is greater than 3” and x is the variable. The statement P(x) is also said to be the value of the propositional function P at x. Once a value has been assigned to the variable x, the statement P(x) becomes a proposition and has a truth value.

In general, a statement involving the n variables x, x, , x can be denoted by P(x, x, , x). A statement of the form P(x, x, , x) is the value of the propositional function P at the n-tuple (x, x, , x), and P is also called an n-place predicate or an n-ary predicate.

Preconditions AND Postconditions

The statements that describe valid input are known as preconditions and the conditions that the output should satisfy when the program has run are known as postconditions.

Quantifiers

The Universal Quantification

The universal quantification of P(x) is the statement “P(x) for all values of x in the domain.” The notation xP(x) denotes the universal quantification of P(x). Here is called the universal quantifier. We read xP(x) as “for all xP(x)“. An element for which P(x) is false is called a counterexample to xP(x).

The Existential Quantification

The existential quantification of P(x) is the proposition : “There exists an element x in the domain such that P(x).” We use the notation xP(x) for the existential quantification of P(x). Here is called the existential quantifier.

The Uniqueness Quantifier

The uniqueness quantifier is denoted by The notation xP(x) stating “There exists a unique x such that P(x) is true”.

Quantifiers over finite domain

When the domain of a quantifier is finite, that is, when all its elements can be listed, quantified statements can be expressed using propositional logic. In particular, when the elements of the domain are x, x, , x, the universal quantification xP(x) is the same as the conjunction P(x) P(x) P(x), because this conjunction is true if and only if P(x), P(x), , P(x) are all true.

Binding Variables

Statements involving predicates and quantifiers are logically equivalent if and only if they have the same truth value no matter which predicates are substituted into these statements and which domain of discourse is used for the variables in these propositional functions. We use the notation S T to indicate that two statements S and T involving predicates and quantifiers are logically equivalent.

• x(P(x) Q(x)) xP(x) xQ(x).
• x(P(x) Q(x)) xP(x) xQ(x)
• xP(x) x P(x)
• xQ(x) x Q(x)

A statement is in Prenex Normal Form (PNF) if and only if it is of the form : QxQx P(x, x, , x), where each Q, i 1, 2, , k, is either the existential quantifier or the universal quantifier, and P(x, x, , x) is a predicate involving no quantifiers. For example, xy(P(x, y) Q(y)) is in prenex normal form, whereas xP(x) xQ(x) is not (because the quantifiers do not all occur first). Every statement formed from propositional variables, predicates, T, and F using logical connectives and quantifiers is equivalent to a statement in prenex normal form.

Rules of Inference

Everything within the scope of a quantifier can be thought of as a propositional function. For example, xy(x + y 0) is the same thing as xQ(x), where Q(x) is yP(x, y), where P(x, y) is x + y 0.

By an argument, we mean a sequence of statements that end with a conclusion. By valid, we mean that the conclusion, or final statement of the argument, must follow from the truth of the preceding statements, or premises, of the argument.

Valid Arguments in Propositional Logic

An argument in propositional logic is a sequence of propositions. All but the final proposition in the argument are called premises and the final proposition is called the conclusion. An argument is valid if the truth of all its premises implies that the conclusion is true. An argument form in propositional logic is a sequence of compound propositions involving propositional variables. An argument form is valid if no matter which particular propositions are substituted for the propositional variables in its premises, the conclusion is true if the premises are all true.

For large number of propositional variables, we do not have to resort to truth tables. Instead, we can first establish the validity of some relatively simple argument forms, called rules of inference. These rules of inference can be used as building blocks to construct more complicated valid argument forms. We will now introduce the most important rules of inference in propositional logic. The tautology (p (p q)) q is the basis of the rule of inference called Modus ponens, or the law of detachment. (Modus ponens is Latin for mode that affirms.)

Rules of Inference

Name	Tautology	Rule of Inference
Modus Ponens	(p (p q)) q	p p q - - - - - - q
Modus Tollens	(q (p q)) p	q p q - - - - - - p
Hypothetical Syllogism	((p q) (q r)) (p r)	p q q r - - - - - - p r
Disjunctive Syllogism	((p q) p) q	p q p - - - - - - q
Addition	p (p q)	p - - - - - - p q
Simplification	(p q) p	p q - - - - - - p
Conjunction	((p) (q)) (p q)	p q - - - - - - p q
Resolution	((p q) (p r)) (q r)	p q p r - - - - - - q r

Resolution

Computer programs have been developed to automate the task of reasoning and proving theorems. Many of these programs make use of a rule of inference known as resolution. This rule of inference is based on the tautology ((p q) (p r)) (q r).

Fallacies

The proposition ((p q) q) p is not a tautology, because it is false when p is false and q is true. However, there are many incorrect arguments that treat this as a tautology. In other words, they treat the argument with premises p q and q and conclusion p as a valid argument form, which it is not. This type of incorrect reasoning is called the fallacy of affirming the conclusion.

The proposition ((p q) p) q is not a tautology, because it is false when p is false and q is true. Many incorrect arguments use this incorrectly as a rule of inference. This type of incorrect reasoning is called the fallacy of denying the hypothesis.

Rules of Inference for Quantified Statements

Universal instantiation is the rule of inference used to conclude that P(c) is true, where c is a particular member of the domain, given the premise xP(x). Universal instantiation is used when we conclude from the statement “All women are wise” that “Lisa is wise,” where Lisa is a member of the domain of all women.

Universal generalization is the rule of inference that states that xP(x) is true, given the premise that P(c) is true for all elements c in the domain. Universal generalization is used when we show that xP(x) is true by taking an arbitrary element c from the domain and showing that P(c) is true. The element c that we select must be an arbitrary, and not a specific, element of the domain. That is, when we assert from xP(x) the existence of an element c in the domain, we have no control over c and cannot make any other assumptions about c other than it comes from the domain. Universal generalization is used implicitly in many proofs in mathematics and is seldom mentioned explicitly. However, the error of adding unwarranted assumptions about the arbitrary element c when universal generalization is used is all too common in incorrect reasoning.

Existential instantiation is the rule that allows us to conclude that there is an element c in the domain for which P(c) is true if we know that xP(x) is true. We cannot select an arbitrary value of c here, but rather it must be a c for which P(c) is true. Usually we have no knowledge of what c is, only that it exists. Because it exists, we may give it a name (c) and continue our argument.

Existential generalization is the rule of inference that is used to conclude that xP(x) is true when a particular element c with P(c) true is known. That is, if we know one element c in the domain for which P(c) is true, then we know that xP(x) is true.

Name	Rule Of Inference
Universal instantiation	xP(x) - - - - - - - - - - - - - - - - - - - P(c)
Universal generalization	P(c) for an arbitrary c - - - - - - - - - - - - - - - - - - - xP(x)
Existential instantiation	xP(x) - - - - - - - - - - - - - - - - - - - P(c) for some element c
Existential generalization	P(c) for some element c - - - - - - - - - - - - - - - - - - - xP(x)
Universal Modus Ponens	x(P(x) Q(x)) P(a), where a is a particular element in the domain - - - - - - - - - - - - - - - - - - — - - - - - - - - - - - - - - - - - - Q(a)
Universal Modus Tollens	x(P(x) Q(x)) Q(a), where a is a particular element in the domain - - - - - - - - - - - - - - - - - - — - - - - - - - - - - - - - - - - - - P(a)

Introduction to Proofs

Formally, a theorem is a statement that can be shown to be true. In mathematical writing, the term theorem is usually reserved for a statement that is considered at least somewhat important. Less important theorems sometimes are called propositions. (Theorems can also be referred to as facts or results.) A theorem may be the universal quantification of a conditional statement with one or more premises and a conclusion. A proof is a valid argument that establishes the truth of a theorem. The statements used in a proof can include axioms (or postulates), which are statements we assume to be true. Axioms may be stated using primitive terms that do not require definition, but all other terms used in theorems and their proofs must be defined. Rules of inference, together with definitions of terms, are used to draw conclusions from other assertions, tying together the steps of a proof. In practice, the final step of a proof is usually just the conclusion of the theorem.

A less important theorem that is helpful in the proof of other results is called a lemma (plural lemmas). Complicated proofs are usually easier to understand when they are proved using a series of lemmas, where each lemma is proved individually. A corollary is a theorem that can be established directly from a theorem that has been proved. A conjecture is a statement that is being proposed to be a true statement, usually on the basis of some partial evidence, a heuristic argument, or the intuition of an expert. When a proof of a conjecture is found, the conjecture becomes a theorem. Many times conjectures are shown to be false, so they are not theorems.

A direct proof of a conditional statement p q is constructed when the first step is the assumption that p is true; subsequent steps are constructed using rules of inference, with the final step showing that q must also be true. A direct proof shows that a conditional statement p q is true by showing that if p is true, then q must also be true, so that the combination p true and q false never occurs. In a direct proof, we assume that p is true and use axioms, definitions, and previously proven theorems, together with rules of inference, to show that q must also be true.

We need other methods of proving theorems of the form x(P(x) Q(x)). Proofs of theorems of this type that are not direct proofs, that is, that do not start with the premises and end with the conclusion, are called indirect proofs. An extremely useful type of indirect proof is known as proof by contraposition. Proofs by contraposition make use of the fact that the conditional statement p q is equivalent to its contrapositive, q p. This means that the conditional statement p q can be proved by showing that its contrapositive, q p, is true. In a proof by contraposition of p q, we take q as premise, and using axioms, definitions, and previously proven theorems, together with rules of inference, we show that p must follow.

Suppose we want to prove that a statement p is true. Furthermore, suppose that we can find a contradiction q such that p q is true. Because q is false, but p q is true, we can conclude that p is false, which means that p is true. Because the statement r r is a contradiction whenever r is a proposition, we can prove that p is true if we can show that p (r r) is true for some proposition r. Proofs of this type are called proofs by contradiction. Because a proof by contradiction does not prove a result directly, it is another type of indirect proof.

Proof Methods and Strategy

Exhaustive Proof and Proof by Cases

To prove a conditional statement of the form (p p p) q the tautology [(p p p) q] [(p q) (p q) (p q)] can be used as a rule of inference. This shows that the original conditional statement with a hypothesis made up of a disjunction of the propositions p p p can be proved by proving each of the n conditional statements p q, i 1, 2, , n, individually. Such an argument is called a proof by cases. Sometimes to prove that a conditional statement p q is true, it is convenient to use a disjunction p p p instead of p as the hypothesis of the conditional statement, where p and p p p are equivalent.

In general, when the phrase “without loss of generality” is used in a proof (often abbreviated as WLOG), we assert that by proving one case of a theorem, no additional argument is required to prove other specified cases. That is, other cases follow by making straightforward changes to the argument, or by filling in some straightforward initial step. Proofs by cases can often be made much more efficient when the notion of without loss of generality is employed. Incorrect use of this principle, however, can lead to unfortunate errors. Sometimes assumptions are made that lead to a loss in generality. Such assumptions can be made that do not take into account that one case may be substantially different from others. This can lead to an incomplete, and possibly unsalvageable, proof. In fact, many incorrect proofs of famous theorems turned out to rely on arguments that used the idea of “without loss of generality” to establish cases that could not be quickly proved from simpler cases.

Existence Proofs

Many theorems are assertions that objects of a particular type exist. A theorem of this type is a proposition of the form xP(x), where P is a predicate. A proof of a proposition of the form xP(x) is called an existence proof. There are several ways to prove a theorem of this type. Sometimes an existence proof of xP(x) can be given by finding an element a, called a witness, such that P(a) is true. This type of existence proof is called constructive. It is also possible to give an existence proof that is nonconstructive; that is, we do not find an element a such that P(a) is true, but rather prove that xP(x) is true in some other way. One common method of giving a nonconstructive existence proof is to use proof by contradiction and show that the negation of the existential quantification implies a contradiction.

Some theorems assert the existence of a unique element with a particular property. In other words, these theorems assert that there is exactly one element with this property. To prove a statement of this type we need to show that an element with this property exists and that no other element has this property. The two parts of a uniqueness proof are: Existence: We show that an element x with the desired property exists. Uniqueness: We show that if x and y both have the desired property, then x y.

Showing that there is a unique element x such that P(x) is the same as proving the statement x(P(x) y(y x P(y))).