Discrete structures logic and computability 3rd edition pdf download

Hein presents material in a spiral medthod of learning, introducing basic information about a topic, allowing the. Discrete Structures. Extremely well organized and lucidly written book with an approach to explain the concepts in communicable languages. Suitable text book for the students of BCA, B. Each Chapter follows Objective type problems. Around objective type problems Multiple choice questions, Fill in the.

Discrete Structures introduces readers to the mathematical structures and methods that form the foundation of computer science and features multiple techniques that readers will turn to regularly throughout their careers in computer and information sciences. Over the course of five modules, students learn specific skills including binary and modular arithmetic,.

Discrete Structure, Logic, and Computability introduces the beginning computer science student to some of the fundamental ideas and techniques used by computer scientists today, focusing on discrete structures, logic, and computability.

The emphasis is on the computational aspects, so that the reader can see how the concepts are actually used. Discrete Structures and Their Interactions. Discover the Connections between Different Structures and FieldsDiscrete Structures and Their Interactions highlights the connections among various discrete structures, including graphs, directed graphs, hypergraphs, partial orders, finite topologies, and simplicial complexes.

It also explores their relationships to classical areas of mathematics,. Here are the bags, some of which are sets, fol- lowed by the number of permutations. Bag Permutations [1, 3, 6] 3! The expectation is the following sum of the products. Then we have the following solutions. The last answer is the first component of X.

So we have the answers 0. Chapter 5 53 5. What is a recurrence? What does it mean to solve a recurrence? What form of recurrence can be solved by substitution or cancellation? What is a divide-and-conquer recurrence?

What is a generating function? How does one solve a recurrence with generating functions? Solve the following recurrence for an by cancellation or substitution and write the answer in closed form. Given the following procedure P defined for all natural numbers n. Suppose that C n executes the operation 3n times. Write down a recurrence to describe an. Then solve it. Suppose we have a recurrence whose nth term is an.

Chapter 5 55 Find a recurrence formula for each of the following conditions. By using either cancellation or substitution we obtain the following expression for an. Using cancellation or substitution and summation formulas we obtain the following closed form solution. The recurrence fits the form given in 5. What does it mean to say two functions have the same order? What is the meaning of each of the following expressions? What problems have solutions that can be approximated by the Akra-Bazzi method?

Also be sure to indicate expressions having the same order by placing them in a set. Prove each of the following statements. Chapter 5 59 6. For convenience, we can assume that base e is used for the logs. We can use the divide-and-conquer test 5. Again, we can use the test 5. Chapter 6 Elementary Logic 6. Learning Objectives Be able to describe the modus ponens rule, a non sequitur, and a calculus.

What is the modus ponens rule? What is a non sequitur? What is a calculus? How did you learn the modus ponens rule? How would you teach a dog the modus ponens rule? Be able to construct equivalence proofs. Be able to transform truth functions and wffs into conjunctive or disjunctive normal form. What is a wff in propositional calculus? What is the meaning of a wff? What is a tautology? What is a contradiction? What is a contingency? When are two wffs equivalent?

What is a truth function? What does DNF mean? What does CNF mean? What is full DNF? What is full CNF? What is a literal? Chapter 6 63 4. Use equivalences to prove that the following wff is equivalent to True. Prove each of the following equivalences with equivalences. Since all expressions evaluate to True, it follows that W is a tautology. Chapter 6 65 9. Be able to use the proof rules to write formal proofs.

What is a proof or derivation? What is the conjunction rule? What is the simplification rule? What is the addition rule? What is the disjunctive syllogism rule? What is the conditional proof rule? What is the double negation rule? What is the contradiction rule? What is the indirect proof rule? What is the modus tollens rule? What is the cases rule?

What is the hypothetical syllogism rule? What is the constructive dilemma rule? What is the destructive dilemma rule? Chapter 6 67 Solved Problems 1. Give a formal proof for each of the following tautologies by using CP. Do not use IP and do not use T. Give a formal proof for each of the following tautologies by using CP and by using IP at least once in each proof.

Do not use T. B 5, Simp 7. False 2, 6, Contr 8. False 3, 6, Contr 7. A 3—6, IP 8. A 4, Simp 6. C 4, Simp 8. False 9, Contr False 4, 9, Contr D 5—10, IP Chapter 6 69 6. What does it mean to say a formal reasoning system is sound? What does it mean to say a formal reasoning system is complete? How can you be sure that a system is sound? What is an example of a small axiomatic system for the propositional calculus that is sound and complete?

Use this axiom system due to Rosser to prove each of the following statements without using CP. You may use MP and any statements in the list to prove subse- quent statements. Chapter 7 Predicate Logic 7. What is a predicate?

What is an atom? What is a wff? What is the scope of a quantifier? What is a bound variable? What is a free variable? What is an interpretation? What is a model? What is a countermodel? What does valid mean? What does invalid mean? What does satisfiable mean?

What does unsatisfiable mean? In each case, write down the original wff. Find examples of wffs with the given properties. The variable x has three bound occurrences and one free occurrence. The variable x has four bound occurrences and the variable y has two bound oc- currences and one free occurrence. Find a countermodel for the following wff. Give an informal argument to show that the following wff is unsatisfiable. Find a model for the wff.

Find a countermodel for the wff. Let W denote the following wff. Give a direct proof that W is valid. Give an indirect proof that W is valid. Chapter 7 73 Solutions 1. Assume, by way of contradiction, that the wff is satisfiable.

Then there is some model for the wff, say with domain D. This contradiction tells us that the original wff is unsatisfiable. Let I be an interpretation with domain D for W.

If p x, x is false, then this wff is vacuously true. Therefore W is true for I. Thus I is a model for W. Since I was arbitrary, it follows that every interpretation of W is a model. So W is valid. Assume, by way of contradiction, that W is invalid. Then there is an interpreta- tion I with domain D such that I is a countermodel for W. Therefore W is valid. Be able to transform simple English sentences into formal logic.

What does it mean to say two wffs are equivalent? What is the universal closure of a wff? What is the existential closure of a wff? What is renaming? What is a prefix normal form? Find a prenex conjunctive normal form for the following wff. Find a prenex disjunctive normal form for the following wff. Let s x mean x is a senator, let p x mean x is a politician, and let e x mean x is ethical. Find a wff to describe each sentence over the domain of people.

Some senators are ethical. Not all senators are ethical. All senators are politicians. No politician is a senator. Chapter 7 75 4. Let c x mean x is a criminal, let r x mean x is rich, and let s x mean x is sane. Every criminal is rich. Some criminals are sane. Some criminals are neither rich nor sane. Not all criminals are sane.

Let g x, y, z mean that z is the greatest common divisor of x and y, and let l x, y, z mean that z is the least common multiple of x and y. Let p x mean x is positive. Formalize the following statement. Any pair of positive natural numbers has a greatest common divisor and a least common multiple. Be able to use the quantifier rules along with the basic proof rules to write formal proofs in first-order predicate calculus.

What is the universal instantiation rule? What is the existential generalization rule? What is the existential instantiation rule? What is the universal generalization rule? Quantifiers cannot be removed and replaced all the time without restrictions. Dem- onstrate this by constructing an incorrect proof for each of the following statements by applying a quantifier proof rule without regard to the restrictions on its use.

Chapter 7 77 2. Give a formal proof that the following wff is valid. Give a formal direct proof that the following wff is valid. Hint: The constructive dilemma proof rule CD may come in handy. Therefore line 2 cannot be inferred from line 1 by UG.

Therefore line 4 cannot be inferred from line 3 by UG. Therefore UI cannot be used to replace x by y on line 2. Chapter 7 79 5. Chapter 8 Applied Logic 8. What is a first-order theory with equality? What is the equality axiom? What is EE rule for predicates?

What is EE rule for functions? What is the general EE rule? Give a formal proof that the following wff is valid in a first-order theory with equal- ity.

Chapter 8 81 4. Formalize the definition of each of the following predicates in terms of properties of integers. False 1, 6, Contr 8. Be able to construct termination proofs for simple loops.

What is a Hoare triple? What is the AA axiom? What is the composition rule? What is the consequence rule? What is the if-then rule? What is the if-then-else rule? What is the while rule? What is a loop invariant? What is a precondition? What is a postcondition?

What is the AAA axiom? What are the steps to show that a while-loop terminates? Prove the correctness of the following wff. Chapter 8 83 2. Prove the correctness of the following wff, where q x means x is an integer and odd and even are tests for the oddness and eveness of an integer.

Complete the following partial wff by applying the array assignment axiom to find the precondition. Yes No b. Yes No c. Yes No d. Yes No e. Yes No f. Yes No Solutions 1. The if-then-else rule requires two proofs. First proof 1. Chapter 8 85 Second proof 7. Chapter 8 87 8. Be able to transform simple English sentences into higher-order logic. In what way is a predicate a set? What is the order of a predicate? What is the order of a quantifier? What is the order of a wff? How is a higher-order wff given a meaning?

What is second-order logic? Write down the minimal order of logic to which each of the following wffs belong. Write a wff in higher-order logic to formalize each of the following equality ideas.

There are two sets A and B that are not equal. There are two elements x and y are not equal. Write down a wff in higher-order logic that formalizes the following statement from geometry. Do a truth analysis for the following wff. Give a formal prove that the following wff is valid. Con- sider the following claim: If there is a point on a line, then there is another point on the line.

But suppose we formalize each statement and then try to prove that Axiom 3 implies the claim. Prove that Axiom 3 implies the claim. Prove that Axiom 3 does not follow from the claim. Hint: find an interpretation that is a model for Axioms 1, 2, 4, and the claim, but not for Axiom 3. Chapter 8 89 5. So any interpretation makes the wff false.

Therefore the wff is unsatisfiable and inva- lid. Then for any interpretation with domain D, the wff can be re- stated as follows: There is a subset p of D such that p is a subset of every subset q of D. So any interpreta- tion makes the wff true. Therefore the wff is valid and satisfiable. False 4, 5, Contr 7. It is clear that this little geometry satisfies Axioms 1, 2, 4, and the claim. But Axiom 3 is not satisfied.

Chapter 9 Computational Logic 9. Be able to unify atoms from a set of clauses. Be able to describe the resolution proof rule. Be able to use resolution to write formal proofs in first-order logic. What is a clause? What is a clausal form? What is a substitution?

What is the composition of two substitutions? What is a unifier? What is a most general unifier? What is a unification algorithm? What is the resolution rule for propositions? What is the resolution rule for first-order wffs? Chapter 9 91 What are the steps to prove a wff is valid if resolution must be used? How do resolution proofs work? Transform the following wff into clausal form.

Find a clausal form and corresponding set of clauses for each of the following propositions. Given the following propositional wff. Prove that the wff is valid by using resolution to show the unsatisfiability of the set of clauses in the clausal form of the negation of the wff. Find two different resolu- tion proofs. Use the Martelli-Montanari algorithm to find a most general unifier.

Is there a unifier that is not most general? Resolve the clauses by choosing two atoms from the first clause and one literal from the second clause. Resolve the clauses by choosing one atom from the first clause and two literals from the second clause. For each of the following wffs, prove that the wff is valid by using resolution to show that set of clauses in the clausal form of the negation the wff is unsatisfiable.

After renaming variables we obtain the following wff. Now remove the conditional and move negations to the right to obtain the following wff.

One of several resolution proofs proceeds as follows: 1. A second resolution proof proceeds as follows: 1. No, because there are no variables in the denomina- tors of a most general unifier.

Yes, because z can be chosen to be any term. First, rename variables so that the clauses have distinct variable names. In each case, take the negation of the wff, find the clausal form, and use the clauses as premises in a resolution proof. Chapter 9 95 9. Be able to describe how resolution is used to execute a logic program. What is a logic program clause? What is a logic program goal or query? What is a logic program? What is the SLD-resolution rule?

What is a computation tree for a goal? If you need other predicates, be sure to define them too. In Prolog, a disjunction of two atoms is represented by placing a semicolon between them.

Explain, from a logical point of view, why the Prolog clause p :- q; r. Given the following logic program: p a. Draw the SLD-tree i. Given the following logic program and goal: p a. Write an SLD-resolution proof of the given program and its goal. Write the corresponding resolution proof for the clauses represented as first- order wffs.

Translate the following functional definition into a logic program. Chapter 9 97 Use these predicates to write a logic program to find the depth of a block, where depth A, N means that there are N blocks on top of A. Find a logic program to distribute an element over a list by pairing it with each ele- ment in the list.

Find a logic program to take an element and a list and return the list of all pairs that contain the given element in one position and an element of the list in the other po- sition. Find a logic program that takes a list and returns all possible pairs of elements in the list.

The Prolog clause p :- q; r. The last wff can be represented by the two Prolog clauses p :- q. The shortest refutation can be de- scribed as follows: 1. Chapter 9 99 The next shortest refutation can be described as follows: 1. The next shortest proof follows: 1. The following infinite SLD-tree reflects these three proofs. There are three different refutations, which are shown on the following SLD-tree. Chapter 9 9. Let cat x, y, z mean that z is the concatenation of the lists x and y.

Note that Excer- cise 7b in the book implements a logic program to concatenate lists. Now we can write a definition for p in terms of cat and the makePairs predicate from Problem Chapter 10 Algebraic Structures and Techniques What is an algebra?

What is an algebraic expression? What is high school algebra? What is a concrete algebra? What is an abstract algebra? Answer each of the following questions. What elements, if any, have inverses? Chapter 10 2. Suppose this can be demonstrated by the following two equations.

Does max have a zero? If so, what is it? Does max have an identity? Use equational reasoning to prove the following state- ment for all integers a. Write down a finite set of algebraic expressions to represent the distinct ele- ments of A. Yes, it is 0. Here is an equational proof that includes the reason for each step. This is similar to Problem 4.

Be able to apply the properties to simplify Boolean expressions. What does the symbol x mean? What is a Boolean algebra? Chapter 10 3. How are the algebra of sets and the algebra of propositions related? What is the idempotent property? What are the absorption laws? What is the involution law? How are digital circuits related to Boolean algebra? What does it mean to simplify a Boolean expression? Simplify each of the following Boolean expressions.

Prove that a b. Suppose, by way of contradiction, that a " b. Then there are three possibilities for a. Be able to apply appropriate algebraic properties to write recursive definitions for simple functions in terms of operations for abstract data types. Review Questions What is an abstract data type? Use the primitive operations in the algebra of stacks to give a recursive definition for a function to combine two stacks into a single stack by stacking one stack on the other.

For example, if A and B are stacks, then combine A, B is the stack with top the top of A and with bottom the bottom of B. An if-then-else definition can be written as follows, where we use the append func- tion from Example Be able to describe a functional algebra.

Chapter 10 Review Questions 1. What is the select operation? What is the projection operation? What is the join operation? What is a functional algebra? Why is FP an important algebra? Let R be the family relation with attributes Person, Mother, and Father. Now we can use R to answer questions about families. Construct relations to find the following sets of family members. The crops that are harvested in June. The months that wheat is harvested. The list of acreages planted in corn.

The months the Nelson farm harvests crops. The crops planted in Washington county. The counties that plant corn. The harvest months in Adams and Lincoln counties. Use FP algebra to prove the following statement. The statement follows directly from the axioms for the FP algebra. Be able to describe and use the RSA algorithm.

Be able to describe subalgebras and morphisms of algebras. What is a congruence? How is the RSA algorithm used? What is a subalgebra? What is a morphism?

Use the Chinese remainder theorem to solve each of the following sets of congru- ences for a unique smallest natural number x. Find an encryption key e for the given choices of p, q, and d. Chapter 10 Solutions 1. But we need e to be positive. Chapter 11 Regular Languages and Finite Automata Be able to use algebraic properties of regular expressions to simplify regular expressions. What is a regular language? What is a regular expression? What is the meaning of a regular expression?

What operations are used in the algebra of regular expressions? Write down a regular expression for each of the following regular languages. Simplify each of the following regular expressions. Be able to apply algorithms to transform between regular expressions and finite auto- mata. Be able to describe finite automata with output. What is a finite automaton?

What does DFA mean? What does NFA mean? What is a Mealy machine? What is a Moore machine? Chapter 11 6. How do you transform a regular expression into a finite automaton? How do you transform a finite automaton into a regular expression? Find a DFA to recognize each of the following regular languages. Find an NFA to recognize each regular expression. Find a DFA to recognize each regular expression. In each case, try to find the DFA by your wits. Compare your results. Find an NFA to recognize the language of each of the following regular expres- sions.

The following diagram represents part of an automaton. Assume that you are in the process of obtaining a regular expression for the lan- guage of the given automaton and the current task is to remove state i.

Apply the method of removing states to the following NFA to find its regular ex- pression. Remove the states in the order 0, 1, 2, and 3. Remove state 0 first. Remove state 1 first.

Prove that the regular expressions from a and b are equal. Chapter 11 8. For example, if the input string is abbaaabbbab, then the output string is abaaabab. Construct a Mealy machine to solve the problem. Construct a Moore machine to solve the problem. There are four states, 0 start , 1, 2 final , and 3. There are three states, 0 start , 1 final and 2.

There are three states, 0 start , 1, and 2 final. There are four states, 0 start , 1, 2, and 3 final. There are five states, 0 start , 1 final , 2, 3 final , and 4. There are seven states, 0 start , 1 final , 2 final , 3, 4, 5 final , and 6. One solution has four states, 0 start , 1, 2, and 3 final. One solution has six states, 0 start , 1, 2, 3, 4, and 5 final.

If the states are removed in the order 0, 1, 2, 3, then the following regular expres- sion is obtained. One solution has two states, 0 start and 1. One solution has four states, 0 start , 1, 2, and 3. What is the lambda closure of a set of states?

Chapter 11 Solved Problems 1. Write down the set E0 to start the process of finding equivalent states. Write down the states i. We can construct the DFA table by Here is the DFA table to gether with a simplification obtained by renaming states. Chapter 11 3. The start state is [0] and the final states are [5] and [8]. Therefore the states 1 and 2 are equivalent. Chapter 11 Be able to transform between regular grammars and NFAs. Be able to describe and apply the pumping lemma for regular languages.

What is a regular grammar? How do you transform a regular grammar into a finite automaton? How do you transform a finite automaton into a regular grammar? What is the pumping lemma? How is the pumping lemma used? Find a regular grammar for the language of each of the following regular expres- sions.

Find a regular grammar for each of the following languages. Use First, rename the states to capital letters with S, I, and F representing 0, 1, and 2, respectively.

First transform the grammar to the following grammar, where the right side of each production has at most one terminal followed by a nonterminal.

Chapter 11 b. Let L be the language and assume, by way of contradiction, that L is regular. It then follows from Now we can obtain a contradiction is several ways. So L is not regular. Since we are assuming that L is regular, we can use This contradiction implies that L is not regular. What is a context-free grammar? What is a context-free language? Find a context-free grammar for each of the following languages. This makes it easier to discover the following grammar.

If we let T be the start symbol for a grammar for L, then by Chapter 12 c. Be able to apply algorithms to transform between PDAs that accept by final state and those that accept by empty stack. Be able to apply algorithms to transform between context-free grammars and PDAs that accept by empty stack. What does the expression i, b, C, pop, j mean? What is a pushdown automaton PDA? What is acceptance by final state? What is acceptance by empty stack? How do you transform a context-free grammar into a PDA?

How do you transform a PDA into a context-free grammar? What is a deterministic PDA? What is a nondeterministic PDA? Do deterministic and nondeterministic PDAs have the same power? Assume that the following instruction is part of the instruction set for a single-state PDA that accepts by empty stack and uses multiple stack operations in some in- structions. Transform the instruction into a set of PDA instructions that accomplish the same purpose, where each instruction has one stack operation but may use states other than 0.

Given the following empty-stack PDA with start state 0 and starting stack symbol X. DO NOT simplify the resulting grammar. In other words, list all the productions generated by the algorithm.

Simplify the result of Part a. Try to describe the language of the PDA and corresponding grammar. Chapter 12 Solutions 1. The terminals a, b, and c give us the following three PDA instructions: 0, a, a, pop, 0 0, b, b, pop, 0. From the terminals a and b we construct the following two PDA instructions: 0, a, a, pop, 0 0, b, b, pop, 0. Chapter 12 b. Notice that X10 does not occur on the left side of any production.

Each string starts with aa and ends with bb. Be able to perform factorization, if possible, to reduce the size of k. Be able to write recursive descent procedures.

Be familiar with the parsing process for simple LL 1 grammars. Be able to describe the properties of LR k grammars. Be familiar with the parsing process for LR 1 grammars. What is a deterministic context-free language? What is top-down parsing? What is bottom-up parsing? What is an LL k grammar? What is recursive descent parsing? What are the characteristics of an LR k grammar?

What is a handle? What is the smallest value of k for this grammar? Transform the LL k grammar into an LL 1 grammar. Chapter 12 2. Remove the left recursion from each of the following grammars and note whether the resulting grammar is LL k. Write down the recursive descent procedures to parse strings in the language de- fined by the following LL 1 grammar. Given the following LR 0 grammar. Find the handle for each of the following sentential forms. Given the following LR 1 grammar.

Complete the following table of sentential forms and handles, where the handle is used to determine a rightmost derivation in reverse. To see this, notice that two letters of lookahead are sufficient to determine which production to use for a derivation step.

To see this, notice that three letters of lookahead are sufficient to deter- mine which production to use for a derivation step. Now remove the direct left recursion to obtain the following grammar.

Chapter 12 8. Be able to describe and to apply the pumping lemma for context-free languages. What is the Chomsky normal form?