abstractmath.org

help with abstract math

Produced by Charles Wells.  Home.   Website Contents     Website Index   Blog

Back to the top of Proofs chapter.

Posted 21 August 2009

Logical Constructions. 1

Methods of Deduction. 2

Translation problem.. 2

Mathematical Logic. 2

Universally true assertions

And, or, not

Conditional assertions

Forms of proof

Existence statements

Quantifiers

Acknowledgment and references. 3

MATHEMATICAL
REASONING

This chapter covers:

¨ The major types of logical constructions used in mathematical assertions.

¨ The ways they are expressed in mathematical English and in the symbolic language.

¨ The methods of deduction that may be used with each type of logical construction.

Logical Constructions

A logical construction is a way of making a compound assertion whose truth depends only on the truth value of the assertion(s) it is constructed from.

Easy examples

The assertion “P and Q” is a logical construction. It claims that both assertions are true. The assertion “P or Q” claims that at least one of them is true. You can determine the truth of these two compound assertions provided you know the truth of P and of Q. You don’t need to know anything else about P and Q except their truth value to determine the meaning of “P and Q” and “P or Q”.

Truth tables

The truth values for a logical construction are given unambiguously by truth tables, one for each connective such as “and” and “or”. For example, from the tables shown here you can see immediately that if P is true and Q is false, then “P and Q” is false but “P or Q” is true.

The truth value of a logical construction involving assertions P and Q

is determined ENTIRELY by the truth table for the connective

and the truth values of P and Q.

The truth tables control the meaning. The meaning and connotation of the English words describing the connectives (“and” and “or” in the example above) do not affect the truth of the construction. They usually suggest the truth but can be misleading. This is one aspect of the translation problem.

Methods of Deduction

Text Box: In logic texts, methods of deduction are called rules of inference. If you know that the assertion “P and Q” is true, then you know just from the form of the assertion that P is true. For example, “7 is odd and 7 is prime” is true, so you can deduce that the assertion “7 is odd” is true. This is an example of a method of deduction. Many methods of deduction, but not all, are as trivial and as obvious as this one. Methods of deduction are not usually mentioned in proofs they are used without comment.

Every proof step must deduce an assertion

from previously proved assertions

by a valid method of deduction.

Each part of the discussion of math reasoning on this website describes a type of logical construction and gives the methods of deduction appropriate for that type of logical construction.

Translation problem

The translation problem is the task of extracting the mathematical and logical structure hidden in mathematical prose. The discussions of logical constructions and methods of deductions in this part of the website describe the difficulties with the translation problem.

¨ Word problems: To “translate a word problem into math” is to find the equation(s) (or other symbolic assertions) that contain the information in a word problem, with the intent of solving them. Finding the equations may be easy or hard and solving them may independently easy or hard.

¨ Proofs: Finding the logical structure of a proof given in narrative format is an instance of the translation problem. See in particular the contrapositive method and proof by contradiction.

¨ Definitions: Unpacking a definition is a form of translation. See rewriting according to the definition.

Besides the links given above, the translation problem is discussed for particular constructions under and, or and not, universal assertions and conditional assertions.

Mathematical Logic

Mathematical logic (or proof theory) is a branch of mathematics that uses mathematical structures to model mathematical statements and proofs. Doing this requires:

¨ Defining a formal language for mathematical statements (see logical symbols).

¨ Giving a strict mathematical definition of theorem and proof.

Mathematical logic is quite technical but very powerful; it has put mathematical reasoning on a sound scientific basis and it has enabled logicians to prove certain impossibility theorems such as Gödel’s Incompleteness Theorem. The description of proofs given on this website is informal and does not include all the technicalities necessary to make logic a part of math.

Logical symbols

In mathematical logic, assertions, connectives, quantifiers and rules of deduction are typically represented using symbols, and the symbolic system developed this way is studied as a mathematical object.

Examples

Assertions containing a variable x might be represented as P(x) and Q(x). Then expressions built up out of these may be represented in one of these ways (this list is not exhaustive):

means “for all x, P(x)” (universal quantifier).

means “there is an x for which P(x) is true” (existential quantifier).

means that P(x) is false (also written as or ).

means “P(x) or Q(x)” (also written P(x) + Q(x)).

means “P(x) and Q(x)” (also written P(x)Q(x) or P(x) & Q(x)).

means “If P(x), then Q(x)” (also written or ). See conditional assertions.

References

These websites provide more complete descriptions of this symbolism and of the theory behind it.

¨ Wikipedia

¨ Suber

¨ Williams.

Usage

The mathematical structures used in mathematical logic that correspond to a mathematician’s proof are often called formal proofs. However, the phrase “formal proof” can also describe proofs written in narrative form in mathematical English.