This Global Edition has been adapted to meet the needs of courses outside of the United States and does not align with the instructor and student resources available with the US edition. This renowned best-selling text, which has been used at over institutions around the world, gives a focused introduction to the primary themes in a Discrete Mathematics course and demonstrates the relevance and practicality of Discrete Mathematics to a wide variety of real-world applications—from Computer Science to Data Networking, to Psychology, to Chemistry, to Engineering, to Linguistics, to Biology, to Business, and many other important fields.
McGraw-Hill Education's Connect, is also available as an optional, add on item. Connect is the only integrated learning system that empowers students by continuously adapting to deliver precisely what they need, when they need it, how they need it, so that class time is more effective. Connect allows the professor to assign homework, quizzes, and tests easily and automatically grades and records the scores of the student's work. Problems are randomized to prevent sharing of answers an may also have a "multi-step solution" which helps move the students' learning along if they experience difficulty.
Author : Kenneth H. Rosen has become a bestseller largely due to how effectively it addresses the main portion of the discrete market, which is typically characterized as the mid to upper level in rigor.
The strength of Rosen's approach has been the effective balance of theory with relevant applications, as well as the overall comprehensive nature of the topic coverage. All rights reserved. Graph polynomials have been developed for measuring combinatorial graph invariants and for characterizing graphs. Various problems in pure and applied graph theory or discrete mathematics can be treated and solved efficiently by using graph polynomials.
Graph polynomials have been proven useful areas such as discrete mathematics, engineering, information sciences, mathematical chemistry and related disciplines. The material is presented so that key information can be located and used quickly and easily. Each chapter includes a glossary. Individual topics are covered in sections and subsections within chapters, each of which is organized into clearly identifiable parts: definitions, facts, and examples.
Examples are provided to illustrate some of the key definitions, facts, and algorithms. Some curious and entertaining facts and puzzles are also included. Readers will also find an extensive collection of biographies. This second edition is a major revision. It includes extensive additions and updates. Since the first edition appeared in , many new discoveries have been made and new areas have grown in importance, which are covered in this edition.
True to the fourth edition, the text specific web site supplements the subject matter in meaningful ways, offering additional material for students and instructors. Discrete math is an active subject with new discoveries made every year. The continual growth and updates to the web site reflect the active nature of the topics being discussed. This text is designed for a one- or two-term introductory discrete mathematics course to be taken by students in a wide variety of majors, including computer science, mathematics, and engineering.
College Algebra is the only explicit prerequisite. We have the link to download WinRAR on the bottom of the site. Featured book. Wolfgang Bauer 0. Milo D. Koretsky 0. Randall D. Knight 0. George Odian 0. John Kenkel 0. Trott 0. Carl S. Warren 2. Warren 0. Abraham Silberschatz 1. Frederick S. Hillier 1. William Stallings 1. Morris Mano 1. David Irwin 0. Morris Mano 0.
Michael F. Inverse: If it does not snow tonight, then I will not stay home. Contrapositive: Whenever I do not go to the beach, it is not a sunny summer day. Inverse: Whenever it is not a sunny day, I do not go to the beach. Contrapositive: If I do not sleep until noon, then I did not stay up late. A truth table will need 2n rows if there are n variables.
To construct the truth table for a compound proposition, we work from the inside out. In each case, we will show the intermediate steps. For parts a and b we have the following table column three for part a , column four for part b. For parts a and b we have the following table column two for part a , column four for part b.
This time we have omitted the column explicitly showing the negation of q. It is irrelevant that the condition is now false. This cannot be a proposition, because it cannot have a truth value. Indeed, if it were true, then it would be truly asserting that it is false, a contradiction; on the other hand if it were false, then its assertion that it is false must be false, so that it would be true—again a contradiction.
Thus this string of letters, while appearing to be a proposition, is in fact meaningless. This is a classical paradox. We will use the male pronoun in what follows, assuming that we are talking about males shaving their beards here, and assuming that all men have facial hair.
If we restrict ourselves to beards and allow female barbers, then the barber could be female with no contradiction. If such a barber existed, who would shave the barber? If the barber shaved himself, then he would be violating the rule that he shaves only those people who do not shave themselves.
On the other hand, if he does not shave himself, then the rule says that he must shave himself. Neither is possible, so there can be no such barber. Note that we can make all the conclusion true by making a false, s true, and u false.
Thus the system is consistent. This system is consistent. This requires that both L and Q be true, by the two conditional statements that have B as their consequence. Note that there is just this one satisfying truth assignment. This is similar to Example 17, about universities in New Mexico.
If A is a knight, then his statement that both of them are knights is true, and both will be telling the truth. But that is impossible, because B is asserting otherwise that A is a knave. Thus we conclude that A is a knave and B is a knight. We can draw no conclusions. A knight will declare himself to be a knight, telling the truth. A knave will lie and assert that he is a knight. If Smith and Jones are innocent and therefore telling the truth , then we get an immediate contradiction, since Smith said that Jones was a friend of Cooper, but Jones said that he did not even know Cooper.
If Jones and Williams are the innocent truth-tellers, then we again get a contradiction, since Jones says that he did not know Cooper and was out of town, but Williams says he saw Jones with Cooper presumably in town, and presumably if we was with him, then he knew him. Therefore it must be the case that Smith and Williams are telling the truth. Their statements do not contradict each other. 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.
0コメント