Sets, Logic and Maths for Computing (Undergraduate Topics in Computer Science)
Format: PDF / Kindle (mobi) / ePub
This easy-to-follow textbook introduces the mathematical language, knowledge and problem-solving skills that undergraduates need to study computing. The language is in part qualitative, with concepts such as set, relation, function and recursion/induction; but it is also partly quantitative, with principles of counting and finite probability. Entwined with both are the fundamental notions of logic and their use for representation and proof. Features: teaches finite math as a language for thinking, as much as knowledge and skills to be acquired; uses an intuitive approach with a focus on examples for all general concepts; brings out the interplay between the qualitative and the quantitative in all areas covered, particularly in the treatment of recursion and induction; balances carefully the abstract and concrete, principles and proofs, specific facts and general perspectives; includes highlight boxes that raise common queries and clear confusions; provides numerous exercises, with selected solutions.
interdependent. Application without understanding is blind and quickly leads to errors – often trivial, but sometimes ghastly. On the other hand, comprehension remains poor without the practice given by applications. In particular, you do not fully understand a definition until you have seen how it takes effect in specific situations: positive examples reveal its scope, negative ones show its limits. It also takes some experience to be able to recognize when you have really understood something,
just an annotated sequence of propositions. We now write it explicitly as a split-level proof, replacing the suppositions by subproofs. As a Split-Level Proof The split-level version consists of a main proof, a subproof and, within the latter, a sub-subproof that has no further subproofs and is thus an elementary derivation. Main Proof A A1. ∀x[Wx → Mx] premise A2. Insert subproof B A3. ∃x[Ax∧Gx∧ Mx] → ∀x[(Ax∧Gx) → Wx] conclusion: from A1,A2 by CP Subproof B B1. ∀x[Wx → Mx] premise
to f(1) to obtain in line 7 a numerical expression, not containing f. From that point, we simplify the numerical expression until, in another six steps, we emerge with a standard numeral. Which is the better way to calculate? In this example, it does not make a significant difference. Indeed, quite generally, when the function is defined using simple recursion of the kind described in this section, the two modes of calculation will be of essentially the same length. The second one looks longer,
discussing that any further would take us too far off our track. 4.6.3 Proof by Structural Induction We have seen that the procedure of defining a set by structural recursion, that is, as the closure of a set under given relations or functions, is pervasive in computer science, logic and abstract algebra. Piggybacking on this mode of definition is a mode of demonstration that we will now examine – proof by structural induction. Let A be a set of any items whatsoever, let A + be the closure of
how many useful properties of probability functions may be extracted from the definition. Some of the most important are covered in the following exercise. Try to do as much as possible before looking at the solution! Exercise 6.1.2 (1) (with solution) Let p +: (S) → [0,1], or more briefly p without the superscript, be a probability function over a finite sample space S. Show that p has the following properties (where A,B are arbitrary subsets of S):(a) p(∅) = 0. (b) p(S) = 1. (c)