Mathematical Expression and
Reasoning for Computer Sci- ence
Lecture Notes for CSC165 (Version 0.5)
Department of Computer Science University of Toronto
Copyright By PowCoder代写 加微信 powcoder
Many thanks to , , and François Pitt for helpful comments and edits to earlier versions of these notes.
mathematical expression and reasoning for computer science 3
Prologue: what is this course about, and why should I care? Why mathematical expression and reasoning in computer science? Course overview 11
1 Mathematical Expression 13 Sets 13
Functions 15
Summation and product notation Inequalities 18
Propositional logic 19
Predicate logic 22
Writing sentences in predicate logic Defining predicates 28
Our conventions for writing formulas
2 Introduction to Proofs Some basic examples
What goes into a proof?
6 david liu and toniann pitassi
A new domain: number theory Alternating quantifiers revisited False statements and disproofs Proof by cases 51 Generalizing statements
Proof by contrapositive Characterizations 57 Greatest common divisor Modular arithmetic 62 Proof by contradiction
3 Induction 67
The principle of induction
Examples from number theory
Combinatorics 73
Incorrect proofs by induction
Looking ahead: strong induction (optional) 77
4 Representations of Natural Numbers 79 Decimal representation of natural numbers 79
Binary representation of natural numbers 79 Properties of binary representation 80
5 Analyzing Algorithm Running Time A motivating example 85
Asymptotic growth 87
One special case of Big-O: O(1) 91
Omega and Theta 91
Properties of Big-O, Omega, and Theta 92 Back to algorithms 95
Worst-case and best-case running times 104 Don’t assume bounds are tight! 108
Average-case analysis
6 Graphs and Trees 115 Initial definitions 115
Paths and connectedness A limit for connectedness
Cycles and trees Rooted trees
7 Looking Ahead
Turing’s legacy: the limitations of computation 135
Gödel’s legacy: the limitations of proofs 138 P versus NP 139
Other cool applications: Cryptography 139
mathematical expression and reasoning for computer science 7
Prologue: what is this course about, and why should I care?
In CSC165, we will be talking about how to express statements precisely using the language of mathematical logic. This gives a way to communicate ideas without any ambiguity, which is an essential skill for any discipline. For ex- ample, the English statement “Some people like David” can be interpreted as saying that at least one person likes David, or that few, many, or even all people like David. What about “You can get cake or ice cream”? Does this mean that you may enjoy both cake and ice cream, or that you must choose between the two? Another example is the English expression “If you are a Pittsburgh Pens fan, then you are not a Philadelphia Flyers fan.” Its meaning is clear enough if you meet a Pens fan, but what does this mean, if anything, for someone who isn’t a Pittsburgh Pens fan? Does the same reasoning apply to the statement “If you can solve any problem in this course, then you will get an A”? Mathematical expressions in formal logic, on the other hand, have only one meaning. They remove all ambiguity so that only one interpretation is possible.
The second major theme of the course is developing methods to give rigorous mathematical proofs or disproofs of mathematical statements. We don’t just want to be able to express ideas, we want to be able to argue—to both our- selves and others—that these ideas are correct. Mathematical proofs are a way to convince someone of something in an absolute sense, without worrying about biases, rhetoric, feelings, or alternate interpretations. The beauty of mathematics is that unlike other vast areas of human knowledge, it is possible to prove that a mathematical statement is true with one-hundred percent certainty. Without a rigorous mathematical proof, we can be easily fooled by our intuition and pre- conceptions. We will see throughout the course that some statements that seem perfectly reasonable turn out to be wrong, and others turn out to be true in sur- prising ways. Sometimes our intuition is valid and a proof seems like a mere formality; but often our intuition is incorrect, and going through the process of a rigorous mathematic proof is the only way that we discover the truth!
Why mathematical expression and reasoning in computer science?
So many reasons! Perhaps the most basic one is program correctness. Say your friend has written a complicated program that she says does something truly remarkable. How do you know it is correct?1 You can test it on some inputs, but how do you know that your tests are thorough enough? Programmers often rely on a combination of tests and their own intuition to convince themselves that
1 What does it mean for a program to “be correct?” How can you prove that a program is correct?
10 david liu and toniann pitassi
their programs are correct, but neither of these are guarantees. A correctness proof will convince you that without a shadow of a doubt, the algorithm is correct on all possible inputs. Not only that, but the practice of proving the correctness of algorithms will refine your own intuitions, making you a better programmer overall.
But wait. Maybe her program does what she claims, but what if on some inputs it takes an extremely long time to run?2 A worst-case complexity analysis is a formal way to convince you that no matter what the input is, her program will run in some guaranteed number of time steps, independent of which computer or programming language is used to write and run this program.
These are two fundamental computer science areas where formal mathematical expression is required to precisely define concepts, and mathematical reasoning is required to prove statements about those concepts. Throughout this course we will follow this two-step process of defining and then proving things very explicitly, and we will practice on many examples. There are many other appli- cations of mathematical expression and reasoning in computer science, some of which we list below. In all cases, mathematical expression allows us to precisely define our claims about the system in question, and mathematical proofs give us a mechanism to convince others with certainty that our system is working as we specified.
• Program verification. This is essentially program correctness mentioned above, and is in fact an entire subarea of computer science. Formal verification is the use of mathematical expression and reasoning in order to argue that a given software or hardware system is correct. Again, you need mathematical expression in order to specify without ambiguity both what the system is and what it means for the system to be correct. Then you need proofs in order to prove or disprove the correctness of the system.
• Cryptography. Cryptography is the science of developing techniques to com- municate information in a way that is secure even in the presence of adver- saries. The most basic cryptographic task is to send an encrypted message across the Internet to a particular person so that the intended receiver is able to decrypt the message, while ensuring that other agents, for whom the mes- sage is not intended, are not able to modify the message or to decrypt it. The area of cryptography is now quite sophisticated, and there are extremely clever protocols that allow us to perform many tasks, such as public-key cryp- tography, digital signatures, and data authentication. Mathematical expres- sion is required in order to even define precisely what we mean by “secure.”3 Then proofs are needed in order to show that our cryptographic techniques are indeed secure.
• Privacy. Issues of privacy are abundant. How do we manage the massive amount of data that is available through the web, while at the same time keep sensitive information private? In order to study this question, one first needs a formal definition of what is even meant by privacy.4 Intuitively, we want such a definition to capture the idea that data can be used for the bene- fit of society—such as to discover correlations between behaviour, symptoms and diseases—but so that the privacy of any particular person is not com-
2 What does it mean for a program to “take a long time to run?” How can you prove that a program takes a long (or short) time to run?
3 You can think about it, but it is not at all obvious what such a definition should say. In fact, there are many definitions of security and other cryp- tographic notions used in theory and practice, depending on the context.
4 As with “security,” there are many definitions out there for what is meant by “privacy,” including the notion of differential privacy that has lately been in the news.
mathematical expression and reasoning for computer science 11
promised. Once the definition is in place, the job then becomes to develop protocols and mechanisms that do useful things while maintaining a privacy guarantee. Again, one needs mathematical expression in order to state the definition of privacy, and proofs in order to show that the mechanisms satisfy the privacy definition.
• Artificial intelligence. Many problems in artificial intelligence and machine learning involve logic. For example, in order to navigate a robot through a room, it helps to have a precise description of the room, as well as a plan for how to move through the room. Practically all problems in artificial in- telligence involve mathematical expression and reasoning, including: natural language processing, image recognition, learning and planning.
• Complexity theory. Complexity theory is about whether important problems that we want solve can be carried out efficiently with respect to costly re- sources. Common resources considered are time, computer memory, and randomness.5 This study requires formal definitions of what we mean by efficient; research in this area aims to invent proofs that certain problems can or cannot be solved efficiently.
Course overview
In our first few weeks of this course, we will discuss mathematical expressions. That is, you will learn a new language and how to express precise statements in this language. It may seem daunting to pick up a new language in a few short weeks, but in fact you probably have been using this language since you were born. What we will do is formalize your intuitive understanding of logic so that it is as clear as possible what constitutes a legal mathematical statement and what doesn’t.
After learning how to express our statements in this language of mathematical logic, we will discuss ways of reasoning about the truth (or falsehood) of these statements. You will both read and write proofs, learning how to construct airtight arguments and communicate them to others, and how to poke holes in flawed proofs. To practice the dual skills of expression and reasoning in computer science domains, we will introduce several new domains to serve as the foundations for our mathematical statements: number theory, combinations and permutations, program runtime, and graphs.6
5 The idea of “randomness” as a re- source may be a surprising one, but is in fact the heart of one of the biggest open questions in complexity theory: If a problem can be solved by an efficient randomized algorithm, can it be solved by an efficient algorithm which has no randomness?
6 Of course, we are not introducing these domains just for the sake of having a few new definitions to play around with. Each of the domains we will study in this course serve a vital role in many areas of computer science, which we will only scratch the surface of in this course.
1 Mathematical Expression
As a starting point for formalizing our intuition of logic, we will define two mathematical notions that we will use repeatedly throughout the course: sets and functions. Much of the terminology here may be review for you (or at least appear vaguely familiar), but please pay careful attention to the bolded terms, as we will make heavy use of each of them throughout the course. Each of these terms has a specific technical meaning (given by our definition) that may be subtly different from your intuitive understanding. As we will stress again and again, definitions are precise statements about the meaning of a term or sym- bol; whenever we define something, it will be your responsibility to understand that definition so that you can understand—and later, reason about—statements using these terms at any point in the rest of this course and beyond.
Definition 1.1. A set is a collection of distinct objects, which we call elements of the set. A set can have a finite number of elements, or infinitely many elements. The size of a finite set A is the number of elements in the set, and is denoted by |A|. The empty set (the set consisting of zero elements) is denoted by ∅.
Before moving on, let us see some concrete examples of sets. These examples illustrate not just the versatility of what sets can represent, but also illustrate various ways of defining sets.
Example 1.1. A finite set can be described by explicitly listing all its elements between curly brackets, such as {a, b, c, d} or {2, 4, −10, 3000}.
Example 1.2. A set of records of all people that work for a small company. Each record contains the person’s name, salary, and age. For example:
( , $70000, 53), ( , $67000, 30), ( , $65000, 25), ( , $70000, 40). Example 1.3. Here are some familiar infinite sets of numbers. Note that we use
the . . . to indicate the continuation of a pattern of numbers.
• The set of natural numbers, N = {0,1,2,…}.1 • The set of integers, Z = {…,−2,−1,0,1,2,…}. • Thesetofpositiveintegers,Z+={1,2,…}.
• The set of rational numbers, Q.
1 By convention in computer science, 0 is a natural number.
14 david liu and toniann pitassi
• The set of real numbers, R.
• The set of non-negative real numbers, R≥0.
Example 1.4. The set of all finite strings over {0, 1}. A finite string over {0, 1} is a finite sequence b0b1b2 . . . bk−1, where k is a natural number (called the length of the string)2 and each of b0, b1, etc. is either 0 or 1. The string of length 0 is called the empty string, and is typically denoted by the symbol ε.
Note that we have defined this set without explicitly listing all of its elements, but instead by describing exactly what properties its elements have. For exam- ple, using our definition, we can say that this set contains the element 01101000, but does not contain the element 012345.3
Example 1.5. A set can also be described as in this example: {x | x ∈ N and x ≥ 5}.
This is the set of all natural numbers which are greater than or equal to 5. The left part (before the vertical bar |) describes the elements in the set in terms of a variable x, and right part states the condition(s) on this variable that must be satisfied.4
As a more complex example, we can define the set of rational numbers as:
p Q= qp,q∈Zandq̸=0 .
We have only scratched the surface of the kinds of objects we can represent using sets. Later on in the course, we will enrich our set of examples by studying sets of computer programs, sequences of numbers, and graphs.
Operations on sets
We have already seen one set operation: the size operator, |A|. In this subsection,
we’ll list other common set operations that we will use in this course.
The following boolean set operations return either True or False. We only describe when these operations return True; they return False in all other cases.
• x∈A: returns True when x is an element of A; y∈/A returns True when y is not an element of A.
• A⊆B:returnsTruewheneveryelementofAisalsoinB.Wesayinthiscase that A is a subset of B.
Every set is a subset of itself, and the empty set is a subset of every set: A ⊆ A and ∅ ⊆ A are always True.
• A=B:returnsTruewhenA⊆BandB⊆A.Inthiscase,AandBcontain the exact same elements.
2 For example, the length of the string 10100101 is eight.
3 Food for thought: how would you generate a list of all finite strings over 0, 1?
4 Tip: The | can be read as “where”.
The following operations return sets:
mathematical expression and reasoning for computer science 15
• A ∪ B, the union of A and B. Returns the set consisting of all elements that occur in A, in B, or in both.
A ∪ B = {x | x ∈ A or x ∈ B}.
• A ∩ B, the intersection of A and B. Returns the set consisting of all elements
that occur in both A and B.
A ∩ B = {x | x ∈ A and x ∈ B}.
• A \ B, the difference of A and B. Returns the set consisting of all elements
that are in A but that are not in B.
A \ B = {x | x ∈ A and x ∈/ B}.
• A × B, the (Cartesian) product of A and B. Returns the set consisting of all
pairs (a, b) where a is an element of A and b is an element of B.
A × B = {(x, y) | x ∈ A and y ∈ B}.
• P(A), the power set of A, returns the set consisting of all subsets of A.5 For
example, if A = {1, 2, 3}, then
P(A) = ∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}.
P(A) = {S | S ⊆ A}. Functions
Definition 1.2. Let A and B be sets. A function f : A → B is a mapping from elements in A to elements in B. A is called the domain of the function, and B is called the codomain of the function.
For example, if A and B are both the set of integers, then the (predecessor) func- tion Pred : Z → Z, defined by Pred(x) = x − 1, is the function that maps each in- teger x to the integer before it. Given this definition, we know that Pred(10) = 9 and Pred(−3) = −4.
A more formal definition of the term “mapping” above is a subset of the Carte- sian product A × B, where every element of A appears exactly once. For exam- ple, we can define the Pred function as the following set:
{…,(−2,−3),(−1,−2),(0,−1),(1,0),(2,1),…}.
One important distinction between the domain and codomain of a function is in what they require of that function. For a function f : A → B, its domain A is the set of possible inputs for the function, and f must have a valid value for every single one of those inputs. So for example, the function g(x) = 1x cannot have domain R, since g(0) is not defined.6 However, the codomain B only has to contain the possible outputs of f —not every element of B needs to be a possible output. Continuing our example, the function g(x) = 1x can have codomain R, since 1x is always a real number, even though g(x) never outputs 0.
Sometimes it is useful to discuss the exact of possible outputs of a function. For this, we have one more definition.
5 Food for thought: what is the relation- ship between |A| and |P(A)|?
6 We could choose R \ {0} as g’s do- main.
16 david liu and toniann pitassi
Definition 1.3. Let f : A → B be a function. We define the range of f to be the set consisting of its possible outputs. Formally, this is the set { f (x) | x ∈ A}.
Note that the range of f is always a subset of its codomain B, but does not necessarily equal B.
You might wonder: why bother having separate definitions for codomain and range, why not just always define functions with their exact range? There are two reasons why this isn’t always feasible:
• Functions don’t always have a range that is easy to describe or compute. For example, the function f (x) = (1 + sin(x))cos(x) over the domain R always outputs a non-negative real number, so we can pick its codomain to be R≥0, but finding its precise range requires more work.
• Later on, we’ll be analysing properties of arbitrary functions with a given domain and codomain, for example, an arbitrary function f : R → R. In these cases, we’ll want to include functions whose range is potentially much smaller than R in our analysis.
For these reasons, we’ll generally define function codomains using standard numeric sets like N and R, and leave the range of a function unstated unless it is required by the particular problem at hand.
Function arity
Functions can have more than one input. For sets A1, A2, . . . , Ak a
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com