Chapter
Chapter 1
From Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk by Sambif
Concepts
- What topics and chapters are included in this book?
"Contents at a glance Contents at a glance i Preface iii Acknowledgements v 1 Meetup at the trailhead 1 2 Sets 7 3 Relations 33 4 Probability 57 5 Structures 83 6 Counting 139 7 Numbers 161 8 Logic 19
- Why does this book take a practical approach to discrete mathematics?
"Preface Discrete math is a popular book topic — start Googling around and you’ll find a zillion different textbooks about it. Take a closer look, and you’ll discover that most of these are pretty thi
- What level of mastery does the book recommend for computer science students?
"iv PREFACE this material, what it means, and how it impacts their discipline. Becoming an expert theorem prover is not required, nor is deriving closed-form expressions for the sizes of trees with es
- What learning experience does this book aim to provide?
"To this end, the book in your hands is a quick guided tour of introductory-level discrete mathematics. It’s like a cool, brisk walk through a pretty forest. I point out the notable features of the la
- Who contributed suggestions and corrections to improve this text?
"Acknowledgements A hearty thanks to Karen Anewalt, Crystal Burson, Prafulla Giri, Tayyar Hussain, Jennifer Magee, Veena Ravishankar, Jacob Shtab- noy, and a decade’s worth of awesome UMW Computer Sci
- How should you use an index card to check your exercise answers?
"Use an index card or a piece of paper folded lengthwise, and cover up the right-hand column of the exercises below. Read each exercise in the left-hand column, answer it in your mind, then slide the
- What is the opposite of concrete?
"the opposite of concrete? Abstract."
- What is the opposite of discrete?
"What’s the opposite of discrete? Continuous."
- Is a quantity of water abstract or concrete, and discrete or continuous?
"A quantity of water in a glass. Would you call it abstract, or concrete? Discrete, or continuous? Concrete, since it’s a real entity you can experience with the senses. Continuous, since it could be
- Would you call “twenty-seven” abstract and discrete?
"Abstract, or concrete? Discrete, or continuous? Abstract, since you can’t see or touch or smell “twenty-seven.” Probably discrete, since it’s an integer, and when we think of whole numbers we think “
- Is a bit abstract or concrete, and discrete or continuous?
"A bit in a computer’s memory. Would you call it abstract, or concrete? Discrete, or continuous? Clearly it’s discrete. Abstract vs. concrete, though, is a little tricky. If we’re talking about the ac
- If math isn’t just about numbers, what else is it about?
"If math isn’t just about numbers, what else is it about? Any kind of abstract object that has properties we can reason about."
- What is a set, and how does it identify its members?
"A set is a selection of certain things out of a (normally larger) group. When we talk about a set, we’re declaring that certain specific items from that group are in the set, and certain items are no
- How are sets written, and what are empty and domain sets?
"As with most of math, it turns out to be useful to define symbols for these concepts, because then we can talk about them more precisely and concisely. We normally list the members of a set using cur
- How do membership symbols and fuzzy sets change the idea of belonging?
"Another symbol we’ll use a lot is “ ∈ ”, which means “is a member of.” Since Lizzy is a female, we can write: Lizzy ∈ F to show that Lizzy is a member of the F set. Conversely, we write: T.J. / ∈ F t
- What are the extensional and intensional ways to define a set?
"There are two ways to define a set: extensionally and intensionally. I’m not saying there are two kinds of sets: rather, there are simply two ways to specify a set. To define a set extensionally is t
- Can two sets with different meanings still be equal?
"Note that two sets with different intensions might nevertheless have the same extension. Suppose O is “the set of all people over 25 years old” and R is “the set of all people who wear wedding rings.
- How does adding conditions to a set definition change its extension?
"We sometimes use curly brace notation in combination with a colon to define a set intensionally. Consider this: M = {k : k is between 1 and 20, and a multiple of 3}. When you reach a colon, pronounce
- What is an infinite set?
"Sets can have an infinite number of members. That doesn’t make sense for the Davies family example, but for other things it does, of course, like: I = { k : k is a multiple of 3 } . Obviously there a
- Can an infinite set be defined extensionally?
"You might think, by the way, that there’s no way to define an infinite set extensionally, since that would require infinite paper. This isn’t true, though, if we creatively use an ellipsis: I = { 3 ,
- How do sets differ from arrays and linked lists in order and duplication?
"If you’ve done some computer programming, you might see a resemblance between sets and the collections of items often used in a program: arrays, perhaps, or linked lists. To be sure, there are some s
- How are sets different from computer collections in size and type?
"Infinite sets. ’Nuff said. I’ve never seen an array with infinitely many elements, and neither will you. Untyped. Most of the time, an array or other collection in a computer program contains element
- Why is a set an abstract concept rather than an explicit list?
"Perhaps the biggest thing to remember here is that a set is a purely abstract concept, whereas an array is a concrete, tangible, explicit list. When we talk about sets, we’re reasoning in general abo
- Why are ordered pairs different from sets?
"You’ll remember from high school algebra the notion of an ordered pair (x, y). We dealt with those when we wanted to specify a point to plot on a graph: the first coordinate gave the distance from th
- What is an n-tuple?
"Three-dimensional points need ordered triples (x, y, z), and it doesn’t take a rocket scientist to deduce that we could extend this to any number of elements. The question is what to call them, and y
- Why can sets of sets lead to Russell’s Paradox?
"Sets are heterogeneous — a single set can contain four universities, seven integers, and an ahi tuna — and so it might occur to you that they can contain other sets as well. This is indeed true, but
- How many members does the set V contain?
"Consider this set: V = { 3 , 5 , { 5 , 4 } , 2 } . This set has four (not five) members. Three of V ’s members are integers: 2, 3, and 5. The other one is a set (with no name given). That other set,
- What is the difference between ∅ and {∅}?
"As a corollary to this, there’s a difference between ∅ and { ∅ } . The former is a set with no elements. The latter is a set with one element: and that element just happens to be a set with nothing i
- What is the cardinality of a set?
"When we talk about the number of elements in a set, we use the word cardinality. You’d think we could just call it the “size” of the set, but mathematicians sometimes like words that sound cool. The
- How is cardinality written using mathematical notation?
"The notation we use for cardinality is vertical bars, like with absolute value. So we write: | M | = 3. To restate the example immediately above, | ∅ | = 0, but |{ ∅ }| ="
- How can a set be a member of another set?
"For instance, the set Z of all zebras is a member of R, since Z itself is a set (not a zebra) and so Z / ∈ Z. The set S, on the other hand, defined as “the set of all sets mentioned in this book,” is
- What symbols represent common number sets?
"In addition to the empty set, there are symbols for some other common sets, including: • Z — the integers (positive, negative, and zero) • N — the natural numbers (positive integers and zero) • Q — t
- How do the cardinalities of the natural and real numbers differ?
"The cardinality of all these sets is infinity, although as I alluded to previously, | R | is in some sense “greater than” | N | . For the curious, we say that N is a countably infinite set, whereas |
- Why is the cardinality of the rational numbers equal to that of the natural numbers?
"Once you’ve digested this, I’ll spring another shocking truth on you: | Q | is actually equal to | N | , not greater than it as | R | is. Cantor came up with an ingenious numbering scheme whereby all
- What operations can be used to combine sets?
"Okay, so we have sets. Now what can we do with them? When you first learn about numbers back before kindergarten, the next thing you learn is how to combine numbers using various operations to produc
- What laws describe how union and intersection combine sets?
"Laws of combining sets There are a bunch of handy facts that arise when combining sets using the above operators. The important thing is that these are all easily seen just by thinking about them for
- How do De Morgan’s laws relate complements to unions and intersections?
"• De Morgan’s laws. Now these are worth memorizing, if only because (1) they’re incredibly important, and (2) they may not slip right off the tongue the way the previous properties do. The first one
- What is the difference between set membership and being a subset?
"We learned that the “∈” symbol is used to indicate set membership: the element on the left is a member of the set on the right. A related but distinct notion is the idea of a subset. When we say X ⊆
- How can a set be an element of another set without being its subset?
"Let’s give some examples. Suppose that Q is the set {4, {9, 4}, 2}. Q has three elements here, one of which is itself a set. Now suppose that we let P be the set {4, 9}. Question: is P ∈ Q? The answe
- What are proper subsets and why is the empty set a subset of every set?
"Notice that by the definition, every set is a subset of itself. Sometimes, though, it’s useful to talk about whether a set is really a subset of another, and you don’t want it to “count” if the two s
- How should expressions involving set membership be read in mathematical statements?
"One note about reading this notation that I found confusing at first. Sometimes the expression “a ∈ X” is pronounced “a is an element of X,” but other times it is read “a, which is an element of X”.
- What is a power set?
"Power set is a curious name for a simple concept. We talk about the power set “of” another set, which is the set of all subsets of that other set. Example: suppose A = { Dad, Lizzy }. Then the power
- How are all the subsets of a set formed?
"It might seem strange to talk about “all of the possible subsets” — when I first learned this stuff, I remember thinking at first that there would be no limit to the number of subsets you could make
- What is the cardinality of a power set?
"Now what’s the cardinality of P(X) for some set X? That’s an interesting question, and one well worth pondering. The answer ripples through the heart of a lot of combinatorics and the binary number s
- What is a partition of a set?
"A partition is a group of subsets of another set that together are both collectively exhaustive and mutually exclusive. This means that every element of the original set is in one and only one of the
- Why do a set and its complement form a partition?
"Every set (S) together with its (total) complement (S) forms a partition of the entire domain of discourse Ω. This is because every element either is, or is not, in any given set. The set of males an
- How do partitions simplify counting?
"Partitions come up quite a bit, and when they do, we can make some important simplifications. Take S, the set of all students at UMW. We can partition it in several different ways. If we divide S int
- Are sets with Smith and Will in different orders the same?
"Smith } the same as the set { Smith, Will }? Yes indeed."
- Does the order matter in an ordered pair?
"2. Is the ordered pair (Will, Smith) the same as (Smith, Will)? No. Order matters with ordered pairs (hence the name), and with any size tuple for that matter."
- Can a set containing Han be the same as a set containing another set that includes Han?
"Han } the same as the set { Luke, { Leia, Han } }? No. For instance, the first set has Han as a member but the second set does not. (Instead, it has another set as a member, and that inner set happen
- Does a set have a first element?
"the set { Cowboys, Redskins, Steelers }? The question doesn’t make sense. There is no “first element” of a set. All three teams are equally members of the set, and could be listed in any order."
- Is J a subset of G or S?
"G be { Matthew, Mark, Luke, John }, J be { Luke, Obi-wan, Yoda }, S be the set of all Star Wars characters, and F be the four gospels from the New Testament. Now then. Is J ⊆ G ? No. 6. Is J ⊆ S ? Ye
- Is the set containing only Yoda a subset of J?
"⊆ J? Yes. The (unnamed) set that contains only Yoda is in fact a subset of J."
- Is { Yoda } ∈ J ?
"∈ J ? No. Yoda is one of the elements of J , but { Yoda } is not. In other words, J contains Yoda, but J does not con- tain a set which contains Yoda (nor does it contain any sets at all, in fact)."
- What subset relations are stated for S, J, G, and F?
"11. Is S ⊆ J ? No. 12. Is G ⊆ F ? Yes, since the two sets are equal. 13. Is G ⊂ F ? No, since the two sets are equal, so neither is a proper subset of the other."
- What subset relations involve ∅ and Ω?
"14. Is ∅ ⊆ S ? Yes, since the empty set is a subset of every set. 15. Is ∅ ⊆ ∅ ? Yes, since the empty set is a subset of every set. 16. Is F ⊆ Ω ? Yes, since every set is a subset of Ω . 17. Is F ⊂ Ω
- Is the empty set both an element and a subset of X?
"X = { Q, ∅ , { Z } }. Is ∅ ∈ X ? Is ∅ ⊆ X ? Yes and yes. The empty set is an element of X because it’s one of the elements, and it’s also a subset of X because it’s a subset of every set. Hmmm."
- What elements are contained in the sets A, B, and T?
"A be { Macbeth, Hamlet, Othello }, B be { Scrabble, Monopoly, Othello }, and T be { Hamlet, Village, Town }."
- What is A ∪ B?
"A ∪ B ? { Macbeth, Hamlet, Othello, Scrab- ble, Monopoly }. (The elements can be listed in any order.)"
- What is (A ∪ B) ∩ T?
"( A ∪ B ) ∩ T ? { Hamlet }. (Note: not the same answer as in item 24 now that the parens are placed differently.)"
- What is T × A?
"T × A ? { (Hamlet, Macbeth), (Hamlet, Hamlet), (Hamlet, Othello), (Vil- lage, Macbeth), (Village, Hamlet), (Village, Othello), (Town, Macbeth), (Town, Hamlet), (Town, Othello) }. The order of the ord
- What is (B ∩ B) × (A ∩ T)?
"29. What’s ( B ∩ B ) × ( A ∩ T ) ? { (Scrabble, Hamlet), (Monopoly, Hamlet), (Othello, Hamlet) }."
- What are the cardinalities of the unions, intersections, and Cartesian product?
"30. What’s | A ∪ B ∪ T | ? 7. 31. What’s | A ∩ B ∩ T | ? 0. 32. What’s | ( A ∪ B ∪ T ) × ( B ∪ B ∪ B ) | ? 21. (The first parenthesized expres- sion gives rise to a set with 7 ele- ments, and the sec
- Can a set be extensional or intensional?
"33. Is A an extensional set, or an intensional set? The question doesn’t make sense. Sets aren’t “extensional” or “inten- sional”; rather, a given set can be described extensionally or intensionally.
- Are the sets {Luke, Matthew} and {John} collectively exhaustive?
"No, because the sets are not collectively exhaustive; Mark is missing."
- Are {Mark, Luke} and {Matthew, Luke} a partition of G?
"G ? • { Mark, Luke } • { Matthew, Luke } No, because the sets are neither collectively exhaustive (John is missing) nor mutually exclusive (Luke appears in two of them)."
- Do { Matthew, Mark, Luke } and { John } form a partition of G?
"G ? • { Matthew, Mark, Luke } • { John } Yes. (Trivia: this partitions the elements into the synoptic gospels and the non-synoptic gospels)."
- Is this a partition of G into gospels with and without a Christmas story?
"Is this a partition of G? • { Matthew, Luke } • { John, Mark } Yes. (This partitions the elements into the gospels which feature a Christmas story and those that don’t)."
- Is this a partition of G into groups based on the writers’ nationalities?
"38. Is this a partition of G? • { Matthew, John } • { Luke } • { Mark } • ∅ Yes. (This partitions the elements into the gospels that were written by Jews, those that were written by Greeks, those tha
- Is { peanut, jelly } an element of the power set of { peanut, butter, jelly }?
"hanna }? { { Rihanna }, ∅ }. 40. Is { peanut, jelly } ∈ P ({ peanut, butter, jelly }? Yes, since { peanut, jelly } is one of the eight subsets of { peanut, but- ter, jelly }. (Can you name the other
- What is a relation between two sets?
"A relation between a set X and Y is a subset of the Cartesian product X × Y. Recall that X × Y yields a set of ordered pairs, one for each combination of an element from X and an element from Y. If X
- How many different relations can exist between two sets?
"Now if I define a relation between X and Y, I’m simply specifying that certain of these ordered pairs are in the relation, and certain ones are not. For example, I could define a relation R that cont
- How is membership in a relation written?
"I find the notation for expressing relations somewhat awkward. But here it is. When we defined the relation S above, we had the ordered pair (Harry, Dr. Pepper) in it. To explicitly state this fact,
- How can a relation be defined extensionally or intensionally?
"Just as with sets, we can define a relation extensionally or intensionally. To do it extensionally, it’s just like the examples above — we simply list the ordered pairs: { (Hermione, Mt. Dew), (Hermi
- What are examples of different relations on the same two sets?
"We can of course define other relations on the same two sets. Let’s define a relation “likes” to contain { (Harry, Dr. Pepper), (Ron, Dr. Pepper), (Hermione, Dr. Pepper), (Hermione, Mt. Dew) }. This
- What does it mean for elements to be associated in a relation?
"Bottom line is: when we talk about a relation, we’re simply designating certain elements of one set to “go with” or “be associated with” certain elements of another set. Normally this corresponds to
- What is an endorelation?
"In the above example, the two sets contained different kinds of things: people, and drinks. But many relations are defined in which the left and right elements are actually drawn from the same set. S
- Does a relation between a set and itself require the two elements of each pair to be the same?
"Note that just because a relation’s two sets are the same, that doesn’t necessarily imply that the two elements are the same for any of its ordered pairs. Harry clearly doesn’t have a crush on himsel
- What is an infinite relation and how can it be specified?
"Sets can be infinite, and relations can be too. An infinite relation is simply a relation with infinitely many ordered pairs in it. This might seem strange at first, since how could we ever hope to s
- How can an infinite relation be specified extensionally?
"As an example of the second, consider the relation “isLuckierThan” between N and N. (The “N” means “the natural numbers.”) We specify it extensionally as follows: { (1, 13), (2, 13), (3, 13), …(12, 1
- What do reflexivity, symmetry, and antisymmetry mean for endorelations?
"Lots of the relations we care about are endorelations, or relations between a set and itself. Throughout this section, assume that R is the relation in question, and that it is defined from set A to
- How are asymmetric, symmetric, and antisymmetric relations different?
"Antisymmetric is very different from asymmetric. An asymmetric relation is simply one that is not symmetric: in other words, there is some (x, y) in it without a matching (y, x). An antisymmetric rel
- What is transitivity, and how can it be tested in an explicit relation?
"A relation is transitive if whenever xRy and yRz, then it is guaranteed that xRz. The “isTallerThan” relation is transitive: if Bob is taller than Jane, and Jane is taller than Sue, then Bob must be
- What are partial orders and partially ordered sets?
"An endorelation that is (1) reflexive, (2) antisymmetric, and (3) transitive is called a partial order. A set together with a partial order is called a partially ordered set, or “poset” for short. Th
- What is a function?
"One very, very important type of relation is called a function. Some mathematicians treat functions totally separately from relations, but I think it’s more useful to think of a function as a special
- How do functions provide a well-defined answer?
"One of the things that makes functions useful is that we can ask “which element of Y goes with X?” and we will always get back a well-defined answer. We can’t really do that with relations in general
- How does the vertical line test identify a function?
"You might also remember discussing functions in high school math, and the so-called “vertical line test.” When you plotted the values of a numerical function on a graph, and there was no vertical (up
- What are a function’s meaning, definition, and range?
"Now as with relations, functions normally have “meaning.” We could define a function called “firstTasted” that associates each wizard with the soft drink he or she first sampled as a child. We could
- What is an injective function?
"An injective function is not only a function, but also kind of a “function in reverse”: not only does no x map to two different y’s, which is the case for all functions, but no two x’s map to the sam
- What is a surjective function?
"A surjective function is one that reaches all the elements of its codomain: some x does in fact reach every y. Another way of saying this is: for a surjective function, the range equals the entire co
- What is a bijective function?
"A bijective function is simply one that is both injective and surjective. With an injective function, every y is mapped to by at most one x; with a surjective function, every y is mapped to by at lea
- How do the examples f₁ through f₆ illustrate function properties?
"With X = {Harry, Ron, Hermione} and Y = {Dr. Pepper, Mt. Dew}, consider the function f₁: f₁(Harry) = Mt. Dew, f₁(Ron) = Mt. Dew, and f₁(Hermione) = Mt. Dew. This function is not injective, since more
- Is the given set of ordered pairs a relation between A and S?
"A be the set { Chuck, Julie, Sam } and S be the set { basketball, volleyball }. Is { (Julie, basketball), (Sam, basketball), (Julie, volley- ball) } a relation between A and S ? Yes it is, since it i
- Is the relation an endorelation?
"No, because an endorelation involves one set with itself, not two different sets (like A and S are.)"
- Is {(Chuck, basketball), (basketball, volleyball)} a relation between A and S?
"No, since the first element of one of the ordered pairs is not from the set A."
- Is the empty set a relation between A and S?
"Yes it is, since it is a subset of A × S."
- What is the maximum cardinality between A and S?
"tween A and S be? The maximum cardinality is 6, if all three athletes played all three sports. (I’m assuming that the meaning of the relation is “ plays ” instead of “ isAFanOf ” or “ knowsTheRulesFo
- What are the reflexive, symmetric, antisymmetric, and transitive properties of the endorelation T?
"O be an endorelation on T , defined as follows: { (Kirk, Scotty), (Spock, Scotty), (Kirk, Spock), (Scotty, Spock) }. Is T reflexive? No, since it doesn’t have any of the elements of T appearing with
- Is H reflexive?
"H is an endorelation on T, defined as follows: { (Kirk, Kirk), (Spock, Spock), (Uhura, Scotty), (Scotty, Uhura), (Spock, McCoy), (McCoy, Spock), (Scotty, Scotty), (Uhura, Uhura) }. H is not reflexive
- Is H symmetric?
"H is an endorelation on T, defined as follows: { (Kirk, Kirk), (Spock, Spock), (Uhura, Scotty), (Scotty, Uhura), (Spock, McCoy), (McCoy, Spock), (Scotty, Scotty), (Uhura, Uhura) }. H is symmetric bec
- Is H antisymmetric?
"H is an endorelation on T, defined as follows: { (Kirk, Kirk), (Spock, Spock), (Uhura, Scotty), (Scotty, Uhura), (Spock, McCoy), (McCoy, Spock), (Scotty, Scotty), (Uhura, Uhura) }. H is not antisymme
- Is H transitive?
"H is an endorelation on T, defined as follows: { (Kirk, Kirk), (Spock, Spock), (Uhura, Scotty), (Scotty, Uhura), (Spock, McCoy), (McCoy, Spock), (Scotty, Scotty), (Uhura, Uhura) }. H is transitive be
- What properties does the outranks relation have?
"outranks is an endorelation on the set of all crew members of the Enterprise, where (x, y) ∈ outranks if character x has a higher Star Fleet rank than y. Is outranks reflexive? No, since no officer o
- What properties does the sameShirtColor relation have?
"Let sameShirtColor be an endorelation on the set of all crew members of the Enterprise, where (x, y) ∈ sameShirtColor if character x ordinarily wears the same shirt color as character y. Is sameShirt
- Why is the relation not a function?
"A as the set { Chuck, Julie, Sam } and S as the set { basketball, volleyball }. Then we defined the relation { (Julie, basketball), (Sam, basketball), (Julie, volleyball) }. Is this relation a functi
- Is the relation still a function after removing (Julie, volleyball)?
"Suppose we then re- move (Julie, volleyball). We now have { (Julie, bas- ketball), (Sam, basketball), (Chuck, basketball) }. Is this a function? Yes. Congratulations."
- What does the function “faveSport” indicate?
"Call this function “faveSport,” which suggests that its meaning is to indicate which sport is each athlete’s favorite."
- What is the domain of faveSport?
"The domain of faveSport? { Julie, Chuck, Sam }."
- What is the codomain of faveSport?
"What’s the codomain of faveSport? { basketball, volleyball }."
- Why is faveSport not injective?
"No, because Julie and Sam (and Chuck) all map to the same value (basketball). For a function to be injective, there must be no two do- main elements that map to the same codomain element."
- Can the function be injective?
"injective? Not without altering the underlying sets. There are three athletes and two sports, so we can’t help but map multiple athletes to the same sport."
- How can a function be made surjective?
"surjective? Sure, for instance change Sam from basketball to volleyball. Now both of the codomain elements are “reach- able” by some domain element, so it’s surjective."
- How can we make a mapping bijective?
"that it’s bijective? One way is to add a third sport — say, kickboxing — and move either Julie or Chuck over to kickboxing. If we have Julie map to kickboxing, Sam map to volleyball, and Chuck map to
- How do we write the fact that Julie maps to kickboxing?
"Do we normally write the fact that “Julie maps to kickboxing”? faveSport(Julie) = kickboxing."
- What are outcomes and sample spaces?
"Since life is uncertain, we don’t know for sure what is going to happen. But let’s start by assuming we know what things might happen. Something that might happen is called an outcome. You can think
- What is an event in probability?
"In probability, we define an event as a subset of the sample space. In other words, an event is a group of related outcomes (though an event might contain just one outcome, or even zero). I always th
- What is the set of all events?
"By the way, “the set of all outcomes” is simply Ω, since an outcome is an element of Ω. But an event is a subset of Ω, not a single element. What, then, is “the set of all events?” If you think it th
- What is a probability measure and what do its values mean?
"A probability measure is simply a function from the domain of events to the codomain of real numbers. We’ll normally use the letters “Pr” for our probability measure. In symbols, Pr : P(Ω) → R, since
- How are event probabilities computed from outcome probabilities?
"The easiest way to think about probability measures is to start with the probabilities of the outcomes, not events. Each outcome has a specific probability of occurring. The probabilities of events l
- What rules must a valid probability measure satisfy?
"In order for a function to be a valid probability measure, it must satisfy several rules: 1. Pr(Ω) = 1. 2. Pr(A) ≥ 0 for all A ⊆ Ω. 3. Pr(A ∪ B) = Pr(A) + Pr(B) − Pr(A ∩ B). Rule 1 means that somethi
- How is probability calculated when all outcomes are equally likely?
"A common special case occurs when all outcomes are equally likely. This usually happens when we roll dice, flip coins, or deal cards, since the probability of rolling a 3 is normally the same as roll
- How do frequentists define probability?
"Which brings me to an important question. How do we get these probability numbers, anyway? Everything so far has assumed that the numbers have been dropped into our lap. The answer depends somewhat o
- How do Bayesians interpret probability?
"If frequentism is thus on a quest for experimental objectivity, Bayesianism might be called “subjective.” This isn’t to say it’s arbitrary or sloppy. It simply has a different notion of what probabil
- How does conditional probability revise an estimate using background knowledge?
"I mentioned that Bayesians are especially concerned with the idea of revising estimates about probability based on new information that may come to light. This notion can be crystallized in the idea
- How can background knowledge drive a conditional probability to zero or one?
"Background knowledge can even peg our probability estimate to an extreme: all the way to 0, or to 1. What’s Pr(U | C), the probability of an underage winner, given that he/she is a country singer? Th
- Why is conditional probability not commutative?
"Keep in mind, by the way, that unlike union and intersection, conditional probability is not commutative. In other words, Pr(X | Y) ≠ Pr(Y | X) in general. To take just one example, look again at the
- How do partitions divide an event into mutually exclusive and exhaustive pieces?
"There’s a very useful fact that goes by the grandiose name “The Law of Total Probability.” It goes like this. If there’s an event whose probability we’d like to know, we can split it up into pieces a
- What is the formula for the Law of Total Probability?
"In the two-set case, no matter what the event A is, we can divide up its probability like this: Pr(A) = Pr(A ∩ B) + Pr(A ∩ Bᶜ) = Pr(A | B) Pr(B) + Pr(A | Bᶜ) Pr(Bᶜ), where B is any other event. The l
- How can the Law of Total Probability find the chance that a randomly selected moviegoer is a minor?
"Suppose that as part of a promotion for Muvico Cinemas movie theatre, we’re planning to give a door prize to the 1000th customer this Saturday afternoon. We want to know the probability that this per
- How does Bayes’ Theorem make difficult probabilities easier to estimate?
"Another trick that helps compute probabilities in practice is Bayes’ Theorem. We’ve defined Pr( A | K ) as Pr ( A ∩ K ) Pr ( K ) , and by swapping the letters we get Pr( K | A ) = Pr ( K ∩ A ) Pr ( A
- Why can a positive medical test still mean a low probability of having a disease?
"A simple and commonly cited example is that of interpreting medical exam results for the presence of a disease. If your doctor recommends that you undergo a blood test to see if you have some rare co
- How can Bayes’ Theorem identify the likely author of a document?
"Anyway, all the stuff about diseases and tests is a side note. The main point is that Bayes’ Theorem allows us to recast a search for Pr( X | Y ) into a search for Pr( Y | X ), which is often far eas
- What does it mean for two events to be independent?
"We’ve seen that a particular problem can involve multiple different events. In the All-time Idol example, we considered the probability of a female winner, a country singer winner, and an underage wi
- How can a contingency table show that two events are independent?
"Suppose we have the following contingency table that shows the results of a survey we conducted at UMW on dominant handedness:\n\nMale Female\n\nLeft-handed 20 26\n\nRight-handed 160 208\n\nThe data
- Why should independence be supported by evidence rather than assumed?
"The shrewd reader may object that this was a startling coincidence: the numbers worked out exactly perfectly to produce this result. The proportion of left-handed females was precisely the same as th
- Why are mutually exclusive events not independent?
"Whoops! One last point on the topic of independence: please don’t make the mistake of thinking that mutually exclusive events are independent! This is by no means the case, and in fact, the opposite
- Who belongs to the sample space for the 100-m freestyle heat?
"in the 100-m freestyle are Ben, Chad, Grover, and Tim. These four swimmers make up our sample space Ω for the winner of this heat. Is Chad ∈ Ω ? Yes. 2. Is Tim an outcome? Yes."
- Why is Ben not an event?
"No, since outcomes are elements of the sample space, while events are subsets of the sample space."
- Why is this not a valid probability measure?
"I told you that Pr({Ben})=.1, Pr({Chad})=.2, Pr({Grover})=.3, and Pr({Tim})=.3. Would you believe me? Better not. This is not a valid probability measure, since the sum of the probabilities of all th
- How can you determine the probability that Ben wins the heat?
"Chad})=.3, and Pr({Ben, Tim})=.4, and Pr({Grover})=.4. Could you tell me the probability that Ben wins the heat? Yes. If Pr({Ben, Chad})=.3 and Pr({Grover})=.4, that leaves .3 probability left over f
- How do you calculate the probability that someone besides Chad wins?
"Pr({Chad}) = 1 − Pr({Chad}), so we just need to figure out the probability that Chad wins, and take one minus that. Clearly if Pr({Ben, Chad}) = .3 (as we were told), and Pr({Ben}) = .1 (as we comput
- What swimmer probabilities and groupings are given in this example?
"ities of our four swimmers Ben, Chad, Grover, and Tim each win- ning the heat at .1, .2, .4, and .3, respectively.\n\n4.7. INDEPENDENCE 81 Now suppose Ben, Chad, and Grover are UMW athletes, Tim is f
- Are all competitors represented in the sets J and S?
"J ∪ S )? Exactly 1. All of the outcomes are represented in the two sets J and S . (Put another way, all competitors are juniors or seniors.)"
- Why is Pr( J ∩ S ) equal to zero?
"Pr( J ∩ S )? Zero. Sets J and S have no elements in common, therefore their intersection is a set with no outcomes, and the probability of a non-existent outcome happening is 0. (Put another way, nob
- What’s the probability of a UMW junior winning the heat?
"14. What’s the probability of a UMW junior winning the heat? This is Pr( U ∩ J ), which is the probability that the winner is a junior and a UMW student. Since U ∩ J = { Ben }, the answer is .1."
- How do you calculate the probability that a winner is a UMW student or a junior?
"winner is from UMW or a junior (or both)? This is Pr( U ∪ J ), which is the probability that the winner is a junior or a UMW student (or both). This calls for computing Pr( U ) plus Pr( J ), but don’
- How does learning that the winner was a UMW student change the probability of a junior winner?
"By the definition of conditional probability, Pr(J | U) = Pr(J ∩ U) / Pr(U) = .1 / .7 = 1/7 ≈ .143. This is quite a bit lower than the .4 we computed for Pr(J) in item 10. So if you knew nothing abou
- How does learning that the swimmer is a junior change the probability of a non-UMW winner?
"U | J )? Pr ( U | J ) = Pr ( U ∩ J ) Pr ( J ) or . 3 . 4 = 3 4 = .75 , way higher than the .3 from item 11. Learning that the swimmer is a ju- nior makes the likelihood of a non- UMW winner leap sky
- What is the probability that someone coming out of a voting booth has a Twitter account?
"75% of Twitter users vote, whereas only about half of people in general vote. Now say that about one out of every three people are on Twitter. If you see someone emerge from a voting booth, what’s th
- What is a graph and why is it a powerful way to represent knowledge?
"In many ways, the most elegant, simple, and powerful way of representing knowledge is by means of a graph. A graph is composed of a bunch of little bits of data, each of which may (or may not) be att
- What are the fundamental terms used to describe graphs?
"The study of graphs brings with it a whole bevy of new terms which are important to use precisely:\n\nvertex. Every graph contains zero or more vertices. (These are also sometimes called nodes, conce
- What is a directed acyclic graph, or DAG?
"DAG (directed, acyclic graph). One common use of graphs is to represent flows of dependencies, for instance the prerequisites that different college courses have for one another. Another example is p
- Why does the spatial positioning of vertices not change a graph?
"One important thing to understand about graphs is which aspects of a diagram are relevant. Specifically, the spatial positioning of the vertices doesn’t matter. In Figure 5.2 we drew Muhammad Ali in
- How are graphs related to sets?
"We seem to have strayed far afield from sets with all this graph stuff. But actually, there are some important connections to be made to those original concepts. Recall the wizards set A from chapter
- What is a free tree?
"A tree is really nothing but a simplification of a graph. There are two kinds of trees in the world: free trees, and rooted trees. A free tree is just a connected graph with no cycles. Every node is
- What properties does a free tree have?
"If you have a free tree, the following interesting facts are true: 1. There’s exactly one path between any two nodes. (Check it!) 2. If you remove any edge, the graph becomes disconnected. (Try it!)
- What is a free tree and how does it relate to a spanning tree?
"n nodes, there are n − 1 edges. (Think about it!) 4 There appears to be no consensus as to which of these concepts is the most basic. Some authors refer to a free tree simply as a “tree” — as though
- What makes a rooted tree different from a free tree?
"Rooted trees\n\nNow a rooted tree is the same thing as a free tree, except that we elevate one node to become the root. It turns out this makes all the difference. Suppose we chose A as the root of F
- What are the main terms used to describe rooted trees?
"Rooted tree terminology\n\nRooted trees carry with them a number of terms. I’ll use the tree on the left side of Figure 5.16 as an illustration of each:\n\nroot. The node at the top of the tree, whic
- What does it mean for nodes to be on the same level?
"All the nodes with the same depth are considered on the same “level.” B and F are on level 1, and D and E are on level 3. Nodes on the same level are not necessarily siblings. If F had a child named
- How do subtrees demonstrate the recursive nature of trees?
"Finally, much of what gives trees their expressive power is their recursive nature. This means that a tree is made up of other (smaller) trees. Consider our example. It is a tree with a root of A. Bu
- What makes a rooted tree a binary tree?
"The nodes in a rooted tree can have any number of children. There’s a special type of rooted tree, though, called a binary tree which we restrict by simply saying that each node can have at most two
- What are the three ways to traverse a binary tree?
"There were two ways of traversing a graph: breadth-first, and depth-first. Curiously, there are three ways of traversing a tree: pre-order , post-order , and in-order . All three begin at the root, a
- How is a tree traversed in pre-order?
"and traverse it in its entirety. 3. Do the same with the right child. It’s tricky because you have to remember that each time you “treat a child as a subtree” you do the whole traversal process on th
- How do you begin a post-order traversal of a tree?
"To traverse a tree post-order , we: 1. Treat the left child and all its descendants as a subtree, and traverse it in its entirety. 2. Do the same with the right child."
- How does post-order traversal visit the nodes of a tree?
"It’s the same as pre-order, except that we visit the root after the children instead of before. Still, despite its similarity, this has always been the trickiest one for me. Everything seems postpone
- How does in-order traversal position the root between its subtrees?
"Finally, to traverse a tree in-order, we: 1. Treat the left child and all its descendants as a subtree, and traverse it in its entirety. 2. Visit the root. 3. Traverse the right subtree in its entire
- How does recursion support tree traversal?
"Finally, it’s worth mentioning that all of these traversal methods make elegant use of recursion. Recursion is a way of taking a large problem and breaking it up into similar, but smaller, sub-proble
- What are the defining properties of binary tree shapes and binary search trees?
"Binary trees can be any ragged old shape, like our Figure 5.17 example. Sometimes, though, we want to talk about binary trees with a more regular shape, that satisfy certain conditions. In particular
- How are binary search trees, binary trees, rooted trees, trees, connected graphs, and graphs related?
"Whew, that was a lot of information about structures. Before we continue our walk in the next chapter with a completely different topic, I’ll leave you with this summary thought. Let BST be the set o
- How many vertices and edges are in the graph?
"D C A F E B. How many vertices are there in the graph below? 6. How many edges are there?"
- What is the degree of vertex B?
"What’s the degree of vertex B?"
- Is the graph directed?
"Is this graph directed? No. (No arrowheads on the lines.)"
- Why is this graph not a tree?
"No. (A tree must be connected, and must also have no cycles, which this graph clearly does: e.g. , B –to– A –to– E –to– B .)"
- How many ordered pairs does the relation represented by this graph have?
"dorelation, how many ordered pairs would it have? 14. (If you said 7, remember that since there are no arrowheads on the lines, this is an undirected graph, which corresponds to a symmetric relation,
- What are the two notions of connectedness for directed graphs?
"Depends on what we mean. There are two different notions of “connectedness” for directed graphs. One is strongly connected, which means every vertex is reachable from any other by following the arrow
- Why can’t a tree have extra edges?
"No. For one thing, a tree can’t have any “extra” edges beyond what’s necessary to make it connected, and there’s redundancy galore here."
- Does the graph contain a cycle that prevents completion?
"Allllmost. If you look very carefully, you’ll see that there is indeed a cycle: I –to– G –to– L . So if this graph were to rep- resent a recipe or project workflow, it would be impossible to complete
- Would the graph be a DAG after reversing the direction of the I-to-G edge?
"the I –to– G edge, would it be a DAG? Yes. The steps could now be completed in this order: H , G , L , I , M , K , and finally J ."
- How many ordered pairs would the endorelation have?
"endorelation, how many ordered pairs would it have?"
- In what order would a depth-first traversal visit the nodes?
"Suppose we traversed the graph below in depth-first fashion, starting with node P. In what order would we visit the nodes? N O P Q R S T There are two possible answers: P, Q, R, S, T, N, O, or else P
- In what order can we visit the nodes in a breadth-first traversal starting with node P?
"breadth-first fashion, starting with node P . Now in what order would we visit the nodes? Again, two possible answers: P , O , Q , N , R , T , S , or else P , Q , O , R , N , S , T . Note in particul
- In what order would we visit the nodes in pre-order fashion?
"pre-order fashion, in what order would we visit the nodes? G S Y H E W D P U A G , S , Y , H , E , W , D , P , U , A ."
- What sequence is given in order fashion?
"order fashion? H , E , Y , S , U , P , D , A , W , G ."
- Is the graph below a tree?
"Mal Jayne Inara Kaylee Wash River Simon Zoe Yes. (Every node has one and only one path to the root, and to every other node for that matter.)"
- What makes a tree binary?
"Yes. (Every node has at most two children, and they are clearly pictured as being a “left” child and/or a “right” child.)"
- Why is this not a binary search tree?
"No. Although nearly every node does satisfy the BST property (all the nodes in its left subtree come before it alphabetically, and all the nodes in its right subtree come after it), there is a single
- How can swapping Zoe and Wash fix the tree?
"Many ways; one would be to swap Zoe ’s and Wash ’s positions. If we do that, the fixed tree would be: Mal Jayne Inara Kaylee Zoe River Simon Wash Take a moment and convince your- self that every node
- Why does the tree have one level too many?
"It’s not too bad, but it does have one too many levels in it (it has a height of 4, whereas all its nodes would fit in a tree of height 3)."
- How could the River–Simon–Wash threesome be rearranged?
"anced? Many ways; one would be to rotate the River – Simon – Wash threesome so that Simon becomes Zoe ’s left child. Simon would then be the parent of River (on his left) and Wash (on his right)."
- Where would a node called “Shepherd” be added to the tree?
"called “ Shepherd ” to this tree, where would he go? To Simon ’s left."
- How can we remove the Mal node while preserving the BST property?
"Mal ” node from this tree, how would we do that? We can put the left-most node of Mal ’s right subtree (that would be River ) in Mal ’s place, and then make Simon (and everything under him) become Wa
- How does the Fundamental Theorem of Counting determine the number of independent choices?
"We start with a basic rule that goes by the audacious name of The Fundamental Theorem of Counting. It goes like this: If a whole can be divided into k parts, and there’s nᵢ choices for the iᵗʰ part,
- How does counting mutually exclusive license-plate lengths illustrate addition and exponential growth?
"Every car in the state of Virginia must be issued its own license plate number. This one requires a bit more thought, since not all license numbers have the same number of characters. In addition to
- How can the counting rule handle positions with different numbers of choices?
"Suppose Virginia outlawed personalized plates and gave everyone a randomly generated 7-character plate. Furthermore, the last four characters of the plate had to be digits instead of letters, so that
- How does counting the complement simplify an “at least one” condition?
"Sometimes we have something difficult to count, but we can turn it around in terms of something much easier. Often this involves counting the complement of something, then subtracting from the total.
- What is a permutation, and how is the factorial used to count permutations?
"When we’re counting things, we often run into permutations. A permutation of n distinct objects is an arrangement of them in a sequence. For instance, suppose all three Davies kids need to brush thei
- How can permutations be systematically enumerated?
"We’ve discovered that there are 120 permutations of BRISK, but how would we go about listing them all? You can play around with the Davies kids and stumble upon all 6 permutations, but for larger num
- How are partial permutations counted when only some items are selected?
"Sometimes we want to count the permutations of a set, but only want to choose some of the items each time, not all of them. For example, consider a golf tournament in which the top ten finishers (out
- What is a combination, and how is it different from a permutation?
"All the stuff with permutations has emphasized order. Somebody gets first place in the golf tournament, and somebody else gets second, and you bet your bottom dollar that it matters which is which. W
- How can overcounting permutations help us count combinations?
"To see how to count these in general, let’s return to the golf tournament example. Suppose that in addition to winning money, the top three finishers of our local tournament will also advance to the
- What is the formula for combinations, and why are they called binomial coefficients?
"And in general, that’s all we have to do. To find the number of combinations of k things taken from a total of n things we have: n choose k = n! / ((n − k)! k!) combinations. This pattern, too, comes
- Why are the binomial coefficients symmetric?
"Now in some ways we’re on a bit of a tangent, since the fact that the “n-choose-k” values happen to work out to be the same as the binomial coefficients is mostly just an interesting coincidence. But
- How can choosing players be equivalent to choosing non-players?
"And in the above example, we see that ( 4 0 ) is equal to ( 4 4 ) , and that ( 4 1 ) is equal to ( 4 3 ) . Why is this? Well, you can look back at the formula for ( n k ) and see how it works out alg
- When are the numbers of combinations greatest and smallest?
"Also notice that the way to get the greatest number of combinations of n items is for k to be half of n . If we have 100 books in our library, there are a lot more ways to check out 50 of them then t
- What are the three basic situations behind most counting problems?
"Most of the time, counting problems all boil down to a variation of one of the following three basic situations: • n^k — this is when we have k different things, each of which is free to take on one
- How does the definition of a workout routine change the counting answer?
"As an example, suppose my friend and I work out at the same gym. This gym has 18 different weight machines to choose from, each of which exercises a different muscle group. Each morning, we each do a
- How does the multiplication principle count costume choices with optional or unlimited accessories?
"Inside a dusty chest marked “Halloween costumes” in the family attic, there are four different outfits (a wizard’s cape, army fatigues, and two others), five different headgears (a batman helmet, a h
- How many costume choices are possible when a child can select up to three accessories?
"Okay, that’s overkill. A kid only has two hands, after all, so handling nine accessories would be a dextrous challenge. Let’s say instead that a child can choose up to three accessories (but must hav
- How many groups of three to five people contain at least one child and one adult?
"When it’s finally time to go trick-or-treating, we join up with our next-door neighbors and split up the families into somewhat haphazard groups. There are eleven total children, and six adults. Now
- How many ordered outcomes are possible for first, second, and third place?
"To encourage rivalry and gluttony, we’re going to give a special certificate to the child who collects the most candy at the end of the night. And while we’re at it, we’ll give 2nd-place and 3rd-plac
- How many possible orders of finish are there when 11 kids each receive a certificate?
"every kid to get a certificate with their name and place-of-finish on it. How many possibilities? (Assume no ties.) This is now a full-blown permutation: 11! . It comes to 39,916,800 different orders
- Why should a number be separated from its base-10 representation?
"Before we do anything with bases, let’s talk about the concept of number, generally. The question “what is a number?” sounds like the dumbest question I could possibly ask you. Yet I predict that unl
- What is a number when it is viewed as a quantity?
"When you think of a number, I want you to try to erase the sequence of digits from your mind. Think of a number as what is is: a quantity. Here’s what the number seventeen really looks like: It’s jus
- Why are digit changes at base-10 boundaries only an illusion of significance?
"But if you had been writing these numbers out as base-10 representations, like you’re used to doing, you might have thought differently. You’d have gone from: (A) 8 to (B) 9 to (C) 10 When going from
- How does a base determine the symbols and place values used to represent numbers?
"As I mentioned, a base is simply a number that’s an anchor for our place value system. It represents how many distinct symbols we will use to represent numbers. This implicitly sets the value of the
- What do the most significant and least significant digits represent?
"By the way, we will often use the term least significant digit to refer to the right-most digit (2, in the above example), and most significant digit to refer to the left-most (5). “Significant” simp
- How are numbers interpreted in a base 7 system?
"All of this probably seems pretty obvious to you. All right then. Let’s use a base other than ten and see how you do. Let’s write out a number in base 7. We have seven symbols at our disposal: 0, 1,
- Why is hexadecimal used in computer science, and what do its digits represent?
"Now objectively speaking, it turns out that ten is a pretty weird base too. I know it doesn’t seem like it, but that’s only because we’re so used to it. Really, if you’re repeatedly adding little cir
- How can you convert a decimal number to hexadecimal using modulo and floor?
"So we know how to take a hexadecimal number (like 72E3_16) and find its decimal equivalent: we just interpret each place’s value as 1, 16, 256, 4096, and so on. What about going the other way? If we
- How do you add hexadecimal numbers directly?
"Suppose we have two hexadecimal numbers, and we want to add them together to get a hexadecimal result. How do we do it? One way is to first convert them both to decimal, then add them like you learne
- Why is binary, or base 2, used in computer science?
"The other base we commonly use in computer science is base 2, or binary. This is because the basic unit of information in a computer is called a bit, which has only two values, conventionally called
- How do place values and counting work in binary?
"The rules for interpreting place value are the same: 110101₂ = 1 × 2⁵ + 1 × 2⁴ + 0 × 2³ + 1 × 2² + 0 × 2¹ + 1 × 2⁰ = 1 × 32 + 1 × 16 + 0 × 8 + 1 × 4 + 0 × 2 + 1 × 1 = 53₁₀. So in binary we have a one
- How do you convert between binary and decimal?
"Converting from binary to decimal was demonstrated above, with 110101₂ = 53₁₀. To go the other way, we follow the algorithm from page 170. Let’s try it for the decimal number 49: 1. (Step 1) We first
- What happens after taking the floor of 24 divided by 2?
"b 24 ÷ 2 c = 12 . Make 12 our new value, move our pencil to the left of the 0, and go back to step 1."
- What value results from taking the floor of 12 divided by 2?
"b 12 ÷ 2 c = 6 . Make 6 our new value, move our pencil to the left of the 0, and go back to step 1."
- What do you do after taking the floor of 6 divided by 2?
"b 6 ÷ 2 c = 3 . Make 3 our new value, move our pencil to the left of the 0, and go back to step 1."
- What happens after dividing 3 by 2 and taking the floor?
"b 3 ÷ 2 c = 1 . This still isn’t zero, so make 1 our new value, move our pencil to the left of the 0, and go back to step 1."
- How do you convert between binary and hexadecimal using nibbles?
"b 1 ÷ 2 c = 0 . We’re done. The final answer is 110001 2 . Double-checking our work, we verify that indeed one 32 plus one 16 plus one 1 gives 49, which is what we started with. Converting to and fro
- How do you add binary numbers?
", hexadecimal, or any other base: you just have to know when to “roll over the odometer,” which in this case is almost instantly, since the highest value a bit can hold is 1! Let’s give it a shot: 11
- How much information can one or more bytes store?
"Capacity How large a value can a byte store? There are 8 bits, and each one can independently have either of two values (0 or 1), so by the Fundamental Theorem of Counting, there are 2 8 different co
- How are negative numbers represented in binary?
"7.4. BINARY (BASE 2) 179 Binary representation schemes That’s mostly all there is to it. But there’s one thing we haven’t discussed yet, and that’s negative numbers. We know how to represent any posi
- Why does sign-magnitude representation lose one value of expressive power?
"− 127. If you have sharp eyes, you may have noticed a discrepancy in the counting. With the sign-magnitude approach, we can hold numbers in the range − 127 to 127. But wait: that’s only 255 different
- How does the two’s-complement scheme address the shortcomings of sign-magnitude representation?
"Two’s-complement This shortcoming in the sign-magnitude scheme is remedied with the two’s-complement scheme, which is the one actually used most often in practice. It’ll seem weird at first — certain
- What does a 0 or 1 indicate?
"If it’s a 0, you have a positive number. If it’s a 1, you have a negative number."
- How do you determine the value of a positive or negative number in two’s-complement notation?
"If, however, it’s a negative number, then to discover the magnitude of that negative number you must flip all the bits and add one. This will give you a positive number which is the absolute value of
- How does two’s-complement representation let computers perform subtraction through addition?
"Strange as it sounds, a two’s-complement representation scheme allows us to perform addition and subtraction with a single operation. In first grade (or so), you learned the procedure for adding mult
- What are the representable range and overflow rules for two’s-complement numbers?
"One last word on two’s-complement: what is the range of numbers we can represent? It turns out to be -128 to 127. The highest value is 01111111, which is 127. You might think the lowest value would b
- Why does the same binary bit pattern have different values under different representation schemes?
"Finally, if we come up for air out of all this mass of details, it’s worth emphasizing that there is no intrinsically “right” way to interpret a binary number. If I show you a bit pattern — say, 1100
- How can you quickly judge whether a base-conversion claim is impossible?
"1. If I told you that the decimal number (i.e., base-10 number) 2022 was equal to 13621₆, would you call me a liar without even having to think too hard? Yes, you should. A number in base-6 can’t hav
- Which base-conversion claims require calculating the exact value?
"4. If I told you that the decimal number 2022 was equal to 1231₆, would you call me a liar without even having to think too hard? No, you shouldn’t, because you do have to think hard for this one. As
- How can you recognize impossible claims about modular remainders?
"6. If I told you that 98,243,917,215 mod 7 was equal to 1, would you call me a liar without even having to think too hard? No, you shouldn’t. It turns out that the answer is 3, not 1, but how would y
- Are the numbers 18 and 25 congruent modulo 7?
"the numbers 18 and 25 con- gruent mod 7? Yes. If we take groups of 7 out of 18 stones, we’ll get two such groups (a total of 14 stones) and have 4 left over. And then, if we do that same with 25 ston
- Are the numbers 18 and 25 congruent mod 6?
"the numbers 18 and 25 con- gruent mod 6? No. If we take groups of 6 out of 18 stones, we’ll get three such groups with nothing left over. But if we start with 25 stones, we’ll take out 4 such groups
- Are the numbers 617,418 and 617,424 equal?
"11. Are the numbers 617,418 and 617,424 equal? Of course not. Don’t waste my time."
- Are the numbers 617,418 and 617,424 congruent mod 3?
"12. Are the numbers 617,418 and 617,424 congruent mod 3? Yes. The number 617,418 is exactly 6 less than 617,424. Let’s say there are k stones left over after remov- ing groups of three from 617,418.
- Are the numbers 617,418 and 617,424 congruent modulo 2, 5, and 6?
"13. Are the numbers 617,418 and 617,424 congruent mod 2? Yes. The number 617,418 is ex- actly 6 less than 617,424. If there are k stones left over after removing pairs of stones from 617,418, we’d ge
- What is the binary number 1011001110101010₂ in hexadecimal?
"The binary number 1011001110101010₂ in hexadecimal is B3AA₁₆, since each of the four 4-bit nibbles goes one-for-one with a hex digit. You can look up nibble values on p. 177 if you want, but again it
- What is the binary number 1011001110101010₂ in decimal?
"What’s the binary number 1011001110101010₂ in decimal? Or is that too hard a question to eyeball? Ugh. Ain’t nobody got time for that."
- What is 16 in binary?
"16 in binary? Or is that too hard a question to eyeball? Simple: 1111001011001110 2 . Read it right off the chart (p. 177)."
- What value does the binary number 1010 represent as an unsigned number?
"tern 1010 was meant to represent an unsigned number, what value would it represent? Ten. ( 8 + 2 = 10 )."
- What value would 1010 represent as a sign-magnitude number?
"tern 1010 was meant to represent a sign-magnitude number, what value would it represent? Negative two. The left-most bit is 1, so it’s negative; and the remaining bits are 010 , which when interprete
- What value does the two’s-complement bit pattern 1010 represent?
"1010 was meant to represent a two’s-complement number, what value would it represent? Negative six. The left-most bit is 1, so it’s negative. This means in order to figure out the value, we have to f
- What is a proposition in propositional logic?
"The simpler — but less powerful — of the two logic systems we’ll study is called propositional logic. It has this name because the core building block is the proposition. A proposition is simply a st
- How do logical connectives combine propositions?
"So things are pretty boring so far. We can define and label propositions, but none of them have any connections to the others. We change that by introducing logical operators (also called logical con
- How do implication and equivalence work in propositional logic?
"⇒ (“implies”)\n\nOkay, now for the toughest one. We’re going to spend significant time thinking through this one carefully, because it’s both important (in some ways, the most important of the operat
- How do truth tables represent logical connectives?
"Several times in this book, we’ve drawn the distinction between intension — the inner, conceptual meaning — and extension — the exhaustive list of examples. A set can have both an intension like “the
- Why are predicates more useful than individual propositions?
"Propositional logic can represent a lot of things, but it turns out to be too limiting to be practically useful. Every proposition is its own opaque chunk of truthhood or falsity, with no way to brea
- How can predicates represent relationships among multiple objects?
"Every sentence has a subject and a predicate. In “Billy jumps,” “Billy” is the subject, and “jumps” the predicate. Basically, a predicate is anything that can describe or affirm something about a sub
- How do universal and existential quantifiers express claims about many objects?
"One powerful feature of predicate logic is the ability to make grandiose statements about many things at once. There are two kinds of quantifiers in predicate logic, the first of which is called the
- How can quantifiers be negated, interchanged, and ordered?
"It’s common practice to negate quantifiers, both universal and existential. For example, ¬∃p President(p) ∧ Female(p) conveys that there does not exist a female president. Similarly, ¬∀x HasGovernor(
- What propositions are represented by B, C, and R?
"Let B be the proposition that Joe Biden was elected president in 2020, C be the proposition that Covid-19 was completely and permanently eradicated from the earth in 2021, and R be the proposition th
- What must be true for B ⇒ C to be true?
"B ⇒ C ? False. (The premise is true, so the conclusion must also be true for this sentence to be true.)"
- Why is C ⇒ B true?
"C ⇒ B ? True . (The premise is false, so all bets are off and the sentence is true.)"
- Is C ⇒ ¬ R true when the premise is false?
"C ⇒ ¬ R ? True . (The premise is false, so all bets are off and the sentence is true.)"
- Is C ⇔ ¬ B true?
"C ⇔ ¬ B ? True. (The truth values of the left and right sides are the same.)"
- How can the unique values of X, Y, Z, and Q be determined from the assertion?
"“ X ∧ ¬ Y ∧ ¬ ( Z ⇒ Q ) .” And since I’m the professor, you can assume I’m correct about this. From this information alone, can you determine a unique set of values for the four variables? Or is ther
- Why is the assertion X ∧ ¬ Y ∧ ¬ ( Z ⇒ X ) impossible?
"Q and replace it with X , thus making my asser- tion: “ X ∧ ¬ Y ∧ ¬ ( Z ⇒ X ) .” Now what is/are the solutions? Now it’s impossible, and if you study the previous item, you’ll see why. The only way t
- What does ∀ x Professor(x) . False mean?
"∀ x Professor ( x ) . False. This says “everyone and ev- erything is a professor,” which is clearly not true. (Consider what you ate for lunch as a counterexample.)"
- What does the statement ∀ x Human(x) . False mean?
"∀ x Human ( x ) . False. This says “everyone and ev- erything is human,” which is clearly not true. (Consider the book in front of you as a counterexample.)"
- What does ¬∀ x Human ( x ) . True mean?
"¬∀ x Human ( x ) . True. This says “it’s not the case that everyone and everything is hu- man.” And that certainly is not the case."
- Why is the statement “nothing is human” false?
"∀ x ¬ Human ( x ) . False. This says “nothing is human,” which is clearly not true. (Consider yourself as a counterexample.)"
- What does ¬∃ x Human(x) mean?
"¬∃ x Human ( x ) . False. This says “nothing is human,” just like item 29 did."
- Why are ∀ x Human(x) ∧ Professor(x) and ∀ x Human(x) ⇒ Professor(x) different?
"32. True or false: ∀ x Human ( x ) ∧ Professor ( x ) . Not even close. This says “everything in the universe is a human professor.” (Even though I would exist in such a world, what a sad, limited pla
- Why does ∃ x Professor(x) ⇒ Human(x) produce a misleadingly true statement?
"34. True or false: ∃ x Professor ( x ) ⇒ Human ( x ) . This is technically true, but for a stupid reason, and whoever wrote it almost certainly didn’t intend what they wrote. It says, “there’s at lea
- How can every professor being human be expressed correctly?
"35. True or false: ∀ x Professor ( x ) ⇒ Human ( x ) . True at last! This is what we were try- ing to say all along. Every professor is a person. 36. True or false: ¬∃ x Professor ( x ) ⇒ ¬ Human ( x
- What is a proof?
"A proof is essentially a chain of reasoning, in which each step can be logically deduced from the ones that preceded it. It’s a way of putting your thought process on display so it can be scrutinized
- How can a knowledge base support a proof?
"Knowledge bases in artificial intelligence systems are designed to support these chains of reasoning. They contain statements expressed in formal logic that can be examined to deduce only the new fac
- What are axioms and theorems?
"Not all proofs are performed in formal logic like this; some use algebra, set theory, or just plain English. But the idea is the same: start with what you know, proceed to derive new knowledge using
- What is a direct proof?
"There are a number of accepted “styles” of doing proofs. Here are some important ones: Direct proof. The examples we’ve used up to now have been direct proofs. This is where you start from what’s kno
- How does an indirect proof work?
"Indirect proof, also known as a proof by contradiction or reductio ad absurdum, starts in a completely opposite way. It says, “okay, I’m trying to prove X. Well, suppose for the sake of argument I as
- How does the proof that the square root of 2 is irrational use contradiction?
"One of the most famous indirect proofs dates from Euclid’s Elements in 300 B.C. It proves that the square root of 2 is an irrational number, a great surprise to mathematicians at the time, most of wh
- Why can mathematical induction be understood as proof by recursion?
"One of the most powerful methods of proof — and one of the most difficult to wrap your head around — is called mathematical induction, or just “induction” for short. I like to call it “proof by recur
- How do you express a claim so it can be proved by induction?
"The first thing you have to be able to do is express the thing you’re trying to prove as a predicate about natural numbers. In other words, you need to form a predicate that has one input, which is a
- How does the weak form of mathematical induction work?
"There are actually two forms of induction, the weak form and the strong form. Let’s look at the weak form first. It says: 1. If a predicate is true for a certain number, 2. and its being true for som
- What would a 23-year-old being able to vote prove?
"Well, if a 23-year-old can vote, then that would sure prove it (by the inductive step)."
- Can a 22-year-old voting prove the claim by the inductive step?
"Can he? Well, if a 22-year-old can vote, then that would sure prove it (by the inductive step)."
- What would an inductive step involving a 21-year-old prove?
"Well, if a 21-year-old can vote, then that would sure prove it (by the inductive step)."
- How can mathematical induction prove Gauss’s formula for the sum of the first n integers?
"A famous story tells of Carl Friedrich Gauss, perhaps the most brilliant mathematician of all time, getting in trouble one day as a schoolboy. As punishment, he was sentenced to tedious work: adding
- How can induction prove that (ab)ⁿ equals aⁿbⁿ?
"You learned in middle school that (ab)ⁿ = aⁿbⁿ. Prove this by mathematical induction. Solution: Let P(n) be the proposition that (ab)ⁿ = aⁿbⁿ.\n\n1. base case. We prove that P(1) is true simply by pl
- How can induction prove that a perfect binary tree has one more leaf than internal node?
"Let P(n) be the proposition that a perfect binary tree of height n has one more leaf than internal node. That is, if lₖ is the number of leaves in a tree of height k, and iₖ is the number of internal
- When is the strong form of mathematical induction useful?
"Now sometimes we actually need to make a stronger assumption than just the single proposition P(k) is true in order to prove that P(k + 1) is true. In all the examples above, the k + 1 case flowed di
- Why is constructing mathematical proofs an essential skill?
"Finding proofs is an art. In some ways, it’s like programming: you have a set of building blocks, each one defined very precisely, and your goal is to figure out how to assemble those blocks into a s