## Syllabus

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.

• General topics in Logic including Propositions, truth tables, Boolean laws of Propositional Logic, logical arguments and deductive proof.
• General topics in Set Theory including notations, predicates, belonging, equality and the Boolean laws for sets.
• Further topics in Logic including quantifiers and predicate logic.
• Further topics in sets including Cartesian products and cardinality.
• General topics in the Theory of Functions including the composition of functions, one-to-one and onto functions, inverses, recurrence relations and equivalence relations.
• Matrices and determinants, the basic definitions, properties and operations, inverses and the solution of equations.
Mathematical induction.

## Lecture Notes

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.

## Question Sheets

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.