Gries D., Schneider F.B. A Logical Approach to Discrete Math

Gries D., Schneider F.B. A Logical Approach to Discrete Math
Издательство Dover Publications, 1993, -520 pp.This text attempts to change the way we teach logic to beginning students. Instead of teaching logic as a subject in isolation, we regard it as a basic tool and show how to use it. We strive to give students a skill in the propositional and predicate calculi and then to exercise that skill thoroughly in applications that arise in computer science and discrete mathematics.
We are not logicians, but programming methodologists, and this text reflects that perspective. We are among the first generation of scientists who are more interested in using logic than in studying it. With this text, we hope to empower further generations of computer scientists and mathematicians to become serious users of logic.
Logic is the glue that binds together methods of reasoning, in all domains. The traditional proof methods —for example, proof by assumption, contradiction, mutual implication, and induction— have their basis in formal logic. Thus, whether proofs are to be presented formally or informally, a study of logic can provide understanding.
But we want to impart far more than the anatomy of the glue —proof theory and model theory. We want to impart a skill in its use. For this reason, we emphasize syntactic manipulation of formulas as a powerful tool for discovering and certifying truths. Of course, syntactic manipulation cannot completely replace thinking about meaning. However, the discomfort with and reluctance to do syntactic manipulation that accompanies unfamiliar- ity with the process unnecessarily forces all reasoning to be in terms of meaning. Our goal is to balance the tendency to reason semantically with the ability to perform syntactic reasoning. Students thereby acquire understanding of when syntactic reasoning is more suitable, as well as confidence in applying it.
When we teach the propositional and predicate calculi, students are put in a syntactic straightjacket. Proofs must be written rigorously. This is an advantage, not a disadvantage, because students learn what it means for a proof to be rigorous and that rigor is easily achieved. We also describe principles and strategies for developing proofs and go over several proofs for the same theorem, discussing their advantages and disadvantages. Gradually, students learn how the shape of formulas can help in discovering proof. The students themselves develop many proofs and, with time and practice, begin to feel at ease with the calculi. We also relate formal logic informal proofs and to various well-known proof methods. This allows students to put what they have learned in context with their past experience with proofs. In the end, students have a firmer understanding of the notion of proof and an appreciation for rigor, precision, brevity, and elegance arguments.
Teaching logic as a tool takes time. It is a terrible mistake to skim over logic in one or two weeks. Five to eight weeks are needed to digest and to master the material. Time spent on logic early in the game can be gained back many times over in later courses. By mastering this material earlier students will have an easier time with subsequent material in mathematics and computer science.
We need a style of logic that can be used as a tool in every-day work. In our experience, an equational logic, which is based on equality and Leibniz’s rule for substitution of equals for equals, is best suited for this purpose.
Equational logic can be used in class, almost from the first day, to solve in a simple fashion problems that otherwise seem hopelessly complex. Students see right from the beginning that logic is useful.
Proofs in an equational logic are a nice alternative to reasoning in English, because they rarely parrot informal English arguments in the formal way. Formal logic is more than just a language in which English arguments are to be couched. Moreover, equational proofs are frequently shorter, simpler, and easier to remember than their counterparts in English or in other formal styles (e.g. Hilbert or natural deduction).
The equational style is already familiar to students, because of their earlier experiences with high-school algebra.
The equational style has wide applicability. This text is evidence for this claim. We have used the equational style to reason about sets, sequences, relations, functions, the integers, combinatorics, recurrent relations, programs, and graphs.Using Mathematics
Textual Substitution, Equality, and Assignment
Boolean Expressions
Propositional Calculus
Relaxing the Proof
Applications of Propositional Calculus
Hilbert-style Proofs
Formal Logic
Quantification
Predicate Calculus
Predicates and Programming
A Theory of Sets
Mathematical Induction
A Theory of Sequences
Relations and Functions
A Theory of Integers
Combinatorial Analysis
Recurrence Relations
Modern Algebra
A Theory of Graphs
Infinite Sets