Sets, Logic and Maths for Computing (Undergraduate Topics in Computer Science)
David Makinson
Language: English
Pages: 283
ISBN: 1447124995
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.
Linux 3-D Graphics Programming
Cybersex: The Dark Side of the Force: A Special Issue of the Journal Sexual Addiction and Compulsion
Linux Server Hacks: 100 Industrial-Strength Tips and Tools
Sets, Logic and Maths for Computing (2nd Edition) (Undergraduate Topics in Computer Science)
formulae, we can easily show that for each assignment v: E→{1,0}, there is a unique function v +: L→{1,0}, where L is the set of all formulae, that satisfies the following two conditions:(1)It agrees with v on E, that is, v +(p) = v(p) for every elementary letter p. (2)It satisfies the truth-table conditions; that is, v +(α) = 1 iff v +(α) = 0, v +(α∧β) = 1 iff v +(α) = v +(β) = 1, and v +(α∨β) = 0 iff v +(α) = v +(β) = 0. Such a v + is called a valuation of formulae – the valuation determined
question that we posed at the end of Sect. 8.2 about the connectives needed to be able to express all truth functions. They may all be represented using just the two connectives , ∧, since from them we can get ∨ by the last of the four de Morgan equivalences, and we already know that with that trio, we may obtain all the others. Likewise, the pair , ∨ suffices to express all possible truth functions via the third de Morgan equivalence. We now give a table listing important equivalences that
exactly one successor. (j) My mother’s father is older than my father’s mother. Some solutions, hints and comments(a)Can be ∀x(Lx → Dx)∧∀x(Tx → Dx) or ∀x((Lx∨Tx) → Dx). It cannot be expressed as ∀x((Lx∧Tx) → Dx) – try to understand why! Note that the universal quantifier is not explicit in the English, but it evidently part of the meaning. (b)∀x((Tx∧Rx) → Ex). Here we are using T for ‘is a triangle’. You can also simplify life by declaring the set of all triangles as your domain (also called
equivalence mentioned in Sect. 4.7.2. Selected Reading Induction and recursion on the positive integers. There are plenty of texts, although most tend to neglect recursive definition in favour of inductive proof. Here are three among them: Hein JL (2005) Discrete structures, logic and computability, 2nd edn. Jones and Bartlett, New York, chapter 4.4 Schumacher C (2001) Chapter zero: fundamental notions of abstract mathematics. Pearson, Boston, chapter 3 Velleman DJ (2006) How to prove it: a
probabilities of winning p(a) = 0.1, p(b) = 0.3, p(c) = 0.6. Suppose the payoff function puts f(a) = 12, f(b) = −1, f(c) = −1. Then the expectation of f given p is the sum f(a)·p(a) + f(b)·p(b) + f(c)·p(c) = 12·(0.1) − 1·(0.3) − 1·(0.6) = 0.3. In general terms, given a payoff function f: S → R and a probability distribution p: S → [0,1] we define the expectation of f given p, written μ(f, p) or just μ, by the equation μ = μ(f, p) = Σ s∈S {f(s)·p(s)}. Equivalently, in a form that can be useful
