# 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.

Absolute C++ (5th Edition)

CMS Security Handbook

Linux Server Hacks: 100 Industrial-Strength Tips and Tools

Windows 8 Secrets

Fundamentals of Web Development

Alongside intersection we have another operation called union. The two operations are known as duals of each other, in the sense that each is like the other ‘upside down’. For any sets A and B, we define their union A∪B by the following rule. For all x: where this is understood in the sense: in other words: The contrast with intersection may be illustrated by Venn diagrams, but they differ a little from those used earlier. Now that we are representing operations rather than statements, we no

about (5)? In the annotations, we noted that it is tautologically implied by {1,4}, so monotony tells us that it implied by {1,2,3,4}. But again we need to show that it is tautologically implied by {1,2,3}, so we need to ‘get rid of’ (4). We are in effect using the following principle, called cumulative transitivity, where, in our example, A = {1,2,3}, B = {4} and γ = (5). All three of these principles – strong reflexivity, monotony and cumulative transitivity – are needed to ensure that when

example to show that the union of two transitive relations need not be transitive. (e)Is the composition of two transitive relations always transitive? Give a verification or a counterexample. 2.5 Equivalence Relations and Partitions We now look at properties that are of particular interest when we want to express a notion of equivalence or similarity between items. 2.5.1 Symmetry We say that R is symmetric iff whenever (a,b) ∈ R, then (b,a) ∈ R. For example, the relation of identity (alias

class of functions, they were thought to exhaust all the computable functions, until the Ackermann function provided a counterexample. But what interests here us about the Ackermann function is the way in which the last clause of the definition makes the value of A(m,n) depend on the value of the same function for the first argument diminished by 1, but paired with a value of the second argument that might be larger than n. As the function picks up speed, to calculate the value of A(m,n) for a

times) = m⋅n = #(A)⋅#(B). The same reasoning gives us more generally: Multiplication rule for many sets. #(A 1×…×A n ) = #(A) ⋅…⋅#(B) for any finite sets A 1,…,A n . Exercise 5.1.1 (4) (with solution) The menu at our restaurant allows choice: For first course, one can choose either soup or salad, the second course can be either beef, duck or vegetarian, followed by a choice of fruit or cheese, ending with black tea, green tea or coffee. How many selections are possible? Solution