This is basically a course on Propositional Logic. Perhaps such a course is obviously useful to Computation students but it is also useful for Mathematics students to learn about logic. Mathematical proofs are excercises in logic, but complicated by the mathematics! Propositional Logic removes the Mathematics, leaving the logical stucture of the proofs. These structures can be studied to see if a given proof is valid or not.
| Notes | Contents |
|---|---|
| Propositional Logic | Propositions, Connectives (and, or, not), Truth Tables, The Boolean Laws of Logics. Equivalence of forms, tautology and contradiction. |
| More Connectives | Conditional and Biconditional, contrapositive, converse. |
| Arguments | Definition of a valid argument. Two ways to use a truth table to show an argument is Valid. |
| Inference Rules I | Natural Deduction: A Rule of Assumption, MPP, MTT, DN. |
| Inference Rules II | Natural Deduction: Eliminating the "and", Eliminating the "or", Introducing "or", Introducing "and". |
| Inference Rules III | Natural Deduction: Conditional Proof, Proof by Contradiction. |
| Sets | Subset, equality, denoting a set. Formal languages. |
| Set Operations | Complement, union, intersection, difference, symmetric difference. The Boolean Laws for Sets. |
| Quantifiers | Universal and existential quantifiers. Symbolising English sentences. Negating quantified sentences. Proving validity of quantified arguments. |
| Further Set Operations | Cartesian product, Power set. Cardinalities of a union of sets, of a produxt of sets and of a power set. |
| Relations | Relations. Digraphs. Reflexive, symmetric, transitive relations. Equivalence Relations. |
| Functions I | Describing a function. Onto and one-to-one functions. |
| Functions II | Composition and inverses. |
| Matrices | Defintion, addition and multiplication. Identity and inverses. Solving systems of linear equations. Gaussian Elimination. |
Unfortunately there are no typed answers for these questions.
Additional examples of arguments for you to practice on are available here:
Additional examples of both valid and invalid arguments containing quantifiers and predicates are available here:
Logic, by Nolt, Rohatyn and Varzi.
Pub. Schaum's Outline series, 2nd edition. ISBN 0-07-046649-1.
This book is a bit wordy but follows the logic part of the course
very closely and is packed full of worked
examples.
The Essence of Logic, by Kelly, J.
Pub. Prentice Hall, 0-13-396375-6.
This book goes far further than we will in the course though Chapters 3 and
6 contain material similar to that in this course.
Foundation Discrete Mathematics for Computing, by Dexter J. Booth,
Pub. International Thompson, ISBN 1-85032-276-7.
This book has a little on logic, though what it has follows our material
fairly well. This book does have a lot of material on sets and functions.