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.
)→q. 8.5.3 Eliminating Redundant Letters A formula of propositional logic may contain redundant letters. We have already seen an example in the table of important equivalences: absorption tells us that p∧(p∨q) ⊣⊢ p ⊣⊢ p∨(p∧q); the letter q is thus redundant in each of the two outlying formulae. The expansion equivalences in the same table give another example. So does the equivalence (p→q)∧( p→q) ⊣⊢ q, not in the table. Suppose we expand our language a little to admit a zero-ary connective ⊥
functions on N × N into N with f((x,y)) = x + y and g((x,y)) = x⋅y. So there will be no real loss in generality when, to keep notation simple, we formulate principles in terms of one-place functions. There are many occasions like this in mathematics, where a concept or construction may be seen in either of two ways, each with its costs and benefits. One perspective can be taken as more general or basic than another, but also vice versa. We have just seen this for the specific concepts of
axis) and the values of each of P(6,k) and C(6,k) on the ordinate (vertical axis). (c)Your investment advisor has given you a list of eight stocks attractive for investment. You decide to invest in three of them. How many different selections are possible? (d)Same scenario, except that you decide to invest $1,000 in one, double that in another, and double that again in a third. How many different selections are possible? Solutions to (c) and (d) These two questions illustrate how important it
Alice: OK, but aren’t we doing some logic here? I see words like ‘if’, ‘only if’, ‘every’, ‘not’ and perhaps more. Shouldn’t we begin by explaining what they mean? Hatter: Hatter: We are, and we could, but life will be easier if for the moment we just use these particles intuitively. We will get back to their exact logical analysis later. 1.2.3 Identity and Proper Inclusion The notion of inclusion leads us to the concept of identity (alias equality) between sets. Clearly, if both and B ⊆ A,
as − +5*2x + − y3 + 2x. To decipher this last sequence, construct its (unique!) decomposition tree from the leaves to the root. The leaves will be labelled by the constants and variables. +2x will label the parent of nodes labelled by 2 and x; −y3 will label the parent of nodes labelled by 3 and y, etc. This is known as Polish notation, after the nationality of its inventor. There is also reverse Polish notation, where the operation is written after its arguments, and which likewise makes