Graph theory and combinatorics dr dsc pdf free download

Since Spring , the book has been used as the primary textbook or a supplemental resource at more than 75 colleges and universities around the world see the partial adoptions list. This 3rd edition brings many improvements, including nearly new exercises, a new section on trees in the graph theory chapter, and improved exposition throughout.

Previous editions will continue to be available indefinitely. A few times a year, the text is updated with a new "printing" to correct errors. See the errata list for more information. This free book focuses on the interplay between random walks on planar maps and Koebe's circle packing theorem. Further topics covered include electric networks, the He—Schramm theorem on infinite circle packings, uniform spanning trees of planar maps, local limits of finite planar maps and the almost sure recurrence of simple random walks on the Applied Discrete Structures.

Applied Discrete Structures, is a two semester undergraduate text in discrete mathematics, focusing on the structural properties of mathematical objects.

These include matrices, functions, graphs, trees, lattices and algebraic structures. Therefore Jones is the murderer. Can none of them be guilty?

If so, then they are all telling the truth, but this is impossible, because as we just saw, some of the statements are contradictory. Can more than one of them be guilty?

If, for example, they are all guilty, then their statements give us no information. So that is certainly possible. This information is enough to determine the entire system. Let each letter stand for the statement that the person whose name begins with that letter is chatting.

Note that we were able to convert all of these statements into conditional statements. In what follows we will sometimes make use of the contrapositives of these conditional statements as well. First suppose that H is true. Then it follows that A and K are true, whence it follows that R and V are true. But R implies that V is false, so we get a contradiction. Therefore H must be false. From this it follows that K is true; whence V is true, and therefore R is false, as is A.

We can now check that this assignment leads to a true value for each conditional statement. There are four cases to consider. If Alice is the sole truth-teller, then Carlos did it; but this means that John is telling the truth, a contradiction.

If John is the sole truth-teller, then Diana must be lying, so she did it, but then Carlos is telling the truth, a contradiction. If Carlos is the sole truth-teller, then Diana did it, but that makes John truthful, again a contradiction. So the only possibility is that Diana is the sole truth-teller. This means that John is lying when he denied it, so he did it. Note that in this case both Alice and Carlos are indeed lying. Since Carlos and Diana are making contradictory statements, the liar must be one of them we could have used this approach in part a as well.

Therefore Alice is telling the truth, so Carlos did it. Note that John and Diana are telling the truth as well here, and it is Carlos who is lying. There are two cases. Therefore the two propositions are logically equivalent. We see that the fourth and seventh columns are identical. For part a we have the following table. We argue directly by showing that if the hypothesis is true, then so is the conclusion. An alternative approach, which we show only for part a , is to use the equivalences listed in the section and work symbolically.

Then p is false. To do this, we need only show that if p is true, then r is true. Suppose p is true. It now follows from the second part of the hypothesis that r is true, as desired.

Then p is true, and since the second part of the hypothesis is true, we conclude that q is also true, as desired. If p is true, then the second part of the hypothesis tells us that r is true; similarly, if q is true, then the third part of the hypothesis tells us that r is true. Thus in either case we conclude that r is true. This is not a tautology. It is saying that knowing that the hypothesis of an conditional statement is false allows us to conclude that the conclusion is also false, and we know that this is not valid reasoning.

Since this is possible only if the conclusion if false, we want to let q be true; and since we want the hypothesis to be true, we must also let p be false.

It is easy to check that if, indeed, p is false and q is true, then the conditional statement is false. Therefore it is not a tautology. The second is true if and only if either p and q are both true, or p and q are both false. Clearly these two conditions are saying the same thing. We determine exactly which rows of the truth table will have T as their entries. The conditional statement will be true if p is false, or if q in one case or r in the other case is true, i. Since the two propositions are true in exactly the same situations, they are logically equivalent.

But these are equivalent by the commutative and associative laws. An conditional statement in which the conclusion is true or the hypothesis is false is true, and that completes the argument.

We can let p be true and the other two variables be false. We apply the rules stated in the preamble. The table is in fact displayed so as to exhibit the duality. The two identity laws are duals of each other, the two domination laws are duals of each other, etc.

The statement of the problem is really the solution. Each line of the truth table corresponds to exactly one combination of truth values for the n atomic propositions involved.

We can write down a conjunction that is true precisely in this case, namely the conjunction of all the atomic propositions that are true and the negations of all the atomic propositions that are false. If we do this for each line of the truth table for which the value of the compound proposition is to be true, and take the disjunction of the resulting propositions, then we have the desired proposition in its disjunctive normal form.

This exercise is similar to Exercise One such assignment is T for p and F for q and r. To say that p and q are logically equivalent is to say that the truth tables for p and q are identical; similarly, to say that q and r are logically equivalent is to say that the truth tables for q and r are identical. Clearly if the truth tables for p and q are identical, and the truth tables for q and r are identical, then the truth tables for p and r are identical this is a fundamental axiom of the notion of equality.

Therefore p and r are logically equivalent. We are assuming—and there is no loss of generality in doing so—that the same atomic variables appear in all three propositions. If q is true, then the third and fourth expressions will be true, and if r is false, the last expression will be true. In each case we hunt for truth assignments that make all the disjunctions true.

The answers given here are not unique, but care must be taken not to confuse nonequivalent sentences. Parts c and f are equivalent; and parts d and e are equivalent. But these two pairs are not equivalent to each other. Alternatively, there exists a student in the school who has visited North Dakota. Alternatively, all students in the school have visited North Dakota. Alternatively, there does not exist a student in the school who has visited North Dakota. Alternatively, there exists a student in the school who has not visited North Dakota.

Alternatively, not all students in the school have visited North Dakota. This is technically the correct answer, although common English usage takes this sentence to mean—incorrectly—the answer to part e. To be perfectly clear, one could say that every student in this school has failed to visit North Dakota, or simply that no student has visited North Dakota.

Note that part b and part c are not the sorts of things one would normally say. Alternatively, every rabbit hops. Alternatively, some rabbits hop. Alternatively, some hopping animals are rabbits.

See Examples 11 and The other parts of this exercise are similar. Many answer are possible in each case. If the domain were all residents of the United States, then this is certainly false. If the domain consists of all United States Presidents, then the statement is false.

In all of these, we will let Y x be the propositional function that x is in your school or class, as appropriate. In each case we need to specify some propositional functions predicates and identify the domain of discourse. There are many ways to write these, depending on what we use for predicates. For example, we can take P x to mean that x is an even number a multiple of 2 and Q x to mean that x is a multiple of 3.

Thus both sides of the logical equivalence are true hence equivalent. Now suppose that A is false. If P x is true for all x , then the left-hand side is true. On the other hand, if P x is false for some x, then both sides are false.

Therefore again the two sides are logically equivalent. If P x is true for at least one x, then the left-hand side is true. On the other hand, if P x is false for all x , then both sides are false. If A is false, then both sides of the equivalence are true, because a conditional statement with a false hypothesis is true. If A is false, then both sides of the equivalence are true, because a conditional statement with a false hypothesis is true and we are assuming that the domain is nonempty.

It is saying that one of the two predicates, P or Q , is universally true; whereas the second proposition is simply saying that for every x either P x or Q x holds, but which it is may well depend on x. As a simple counterexample, let P x be the statement that x is odd, and let Q x be the statement that x is even. Let the domain of discourse be the positive integers.

The second proposition is true, since every positive integer is either odd or even. P x is true, so we form the disjunction of these three cases. So the response is no. So the response is yes. The unsatisfactory excuse guaranteed by part b cannot be a clear explanation by part a.

If x is one of my poultry, then he is a duck by part c , hence not willing to waltz part a. Or, more simply, a nonnegative number minus a negative number is positive which is true. The answers to this exercise are not unique; there are many ways of expressing the same propositions sym- bolically. Note that C x, y and C y, x say the same thing. Our domain of discourse for persons here consists of people in this class.

We need to make up a predicate in each case. We let P s, c, m be the statement that student s has class standing c and is majoring in m. The variable s ranges over students in the class, the variable c ranges over the four class standings, and the variable m ranges over all possible majors. It is true from the given information.

This is false, since there are some mathematics majors. This is true, since there is a sophomore majoring in computer science. This is false, since there is a freshman mathematics major. This is false. It cannot be that m is mathematics, since there is no senior mathematics major, and it cannot be that m is computer science, since there is no freshman computer science major.

Nor, of course, can m be any other major. The best explanation is to assert that a certain universal conditional statement is not true. We need to use the transformations shown in Table 2 of Section 1. The logical expression is asserting that the domain consists of at most two members. It is saying that whenever you have two unequal objects, any object has to be one of those two. Note that this is vacuously true for domains with one element.

Therefore any domain having one or two members will make it true such as the female members of the United States Supreme Court in , and any domain with more than two members will make it false such as all members of the United States Supreme Court in In each case we need to specify some predicates and identify the domain of discourse. In English, everybody in this class has either chatted with no one else or has chatted with two or more others.

In English, some student in this class has sent e-mail to exactly two other students in this class. In English, for every student in this class, there is some exercise that he or she has not solved. Word order in English sometimes makes for a little ambiguity. In English, some student has solved at least one exercise in every section of this book.

This x provides a counterexample. The domain here is all real numbers. This statement says that there is a number that is less than or equal to all squares.

We need to show that each of these propositions implies the other. By our hypothesis, one of two things must be true. Either P is universally true, or Q is universally true.

Next we need to prove the converse. Otherwise, P x0 must be false for some x0 in the domain of discourse. Since P x0 is false, it must be the case that Q y is true for each y.

This is modus tollens. Modus tollens is valid. This is, according to Table 1, disjunctive syllogism. See Table 1 for the other parts of this exercise as well. We want to conclude r. We set up the proof in two columns, with reasons, as in Example 6. Note that it is valid to replace subexpressions by other expressions logically equivalent to them. Step Reason 1. Alternatively, we could apply modus tollens. Another application of modus tollens then tells us that I did not play hockey.

We could say using existential generalization that, for example, there exists a non-six-legged creature that eats a six-legged creature, and that there exists a non-insect that eats an insect. Now modus tollens tells us that Homer is not a student. There are no conclusions to be drawn about Maggie.

Universal instantiation and modus ponens therefore tell us that tofu does not taste good. The third sentence says that if you eat x, then x tastes good. No conclusions can be drawn about cheeseburgers from these statements. Therefore by modus ponens we know that I see elephants running down the road. In each case we set up the proof in two columns, with reasons, as in Example 6. In what follows y represents an arbitrary person.

After applying universal instantiation, it contains the fallacy of denying the hypothesis. We know that some s exists that makes S s, Max true, but we cannot conclude that Max is one such s.

We will give an argument establishing the conclusion. We want to show that all hummingbirds are small. Let Tweety be an arbitrary hummingbird. We must show that Tweety is small. Therefore by universal modus ponens we can conclude that Tweety is richly colored. The third premise implies that if Tweety does not live on honey, then Tweety is not richly colored.

Therefore by universal modus tollens we can now conclude that Tweety does live on honey. Finally, the second premise implies that if Tweety is a large bird, then Tweety does not live on honey. Therefore again by universal modus tollens we can now conclude that Tweety is not a large bird, i. Notice that we invoke universal generalization as the last step.

Thus we want to show that if P a is true for a particu- lar a, then R a is also true. The right-hand side is equivalent to F. As we noted above, the answer is yes, this conclusion is valid. This conditional statement fails in the case in which s is true and e is false. If we take d to be true as well, then both of our assumptions are true.

Therefore this conclusion is not valid. This does not follow from our assumptions.