# Elements Of Discrete Mathematics A Computer Oriented Approach

**Elements** **Of Discrete Mathematics A Computer Oriented Approach**: Element of Discrete Mathematics, is recognized for its signature mathematical emphasis and appropriate coverage for a first course taught at the freshmen level. The book presents the concepts of Discrete Mathematics from an algorithmic point of view. The pedagogy is added in sync with the book’s creditable style where concepts along with solved examples are juxtaposed against each other appositely to strengthen students’ conceptual base of the subject.

**Best Books for Elements** **Of Discrete Mathematics A Computer Oriented Approach:**

Elements of Discrete Mathematics: A Computer Oriented Approach Book by C Liu (Author), D. Mohapatra (Author).

Book Published in 2017.

Book Explains Concepts of Discrete Mathematics.

Some of the Customer give the Review on this book is

This is really a great book.

Don t read the local author books.

Instead read this first to understand your concepts thoroughly.

The entire matter is represented in lucid, clear language and is easy to understand.

This is a good book.

**Elements Of Discrete Mathematics A Computer Oriented Approach PDF:**

PDF is available at Online.

S creditable style where concepts along with solved examples are juxtaposed against each other appositely to strengthen students?

Conceptual base of the subject

**TABLE OF CONTENTS: **

- Sets and Propositions
- Permutations, Combinations, and Discrete Probability
- Relations and Functions
- Graphs and Planar Graphs
- Trees and Cut-Sets
- Modeling Computation
- Analysis of Algorithms
- Discrete Numeric Functions and Generating Functions
- Recurrence Relations and Recursive Algorithms
- Groups and Rings
- Boolean Algebras

**MATHEMATICAL FUNDATION FOR COMPUTER SCIENCE Syllabus:**

**UNIT-I**

Mathematical Logic: Truth Tables, tautology, equivalence implication, Normal forms, Quantifiers, universal quantifiers, Statements and notations, Connectives, Well formed formulas.

**UNIT-II**

Predicates: Rules of inference, Consistency, proof of contradiction, Automatic Theorem Proving, Predicative logic, Free & Bound variables.

**UNIT-III**

Relations: Hasse diagram. Functions: Inverse Function Compositions of functions, recursive Functions, Lattice and its Properties, Properties of binary Relations, equivalence, transitive closure,compatibility and partial ordering relations, Lattices.

**UNIT-IV**

Algebraic structures: Semi groups and monads, groups sub groups’ homomorphism, Algebraic systems Examples and general properties, Isomorphism.

**UNIT-V**

Elementary Combinatorics: Binomial Multinomial theorems, the principles of Inclusion – Exclusion.Pigeon hole principles and its applications, Basis of counting, Combinations & Permutations, with repetitions, Constrained repetitions, Binomial Coefficients.

**UNIT-VI**

Recurrence Relation : Solving recurrence relation by substitution and Generating funds. Characteristics roots solution of In homogeneous Recurrence Relation, Generating Functions, Function of Sequences Calculating Coefficient of generating function, Recurrence relations,.

**UNIT-VII**

Graph Theory: Representation of Graph, DFS, BFS, Spanning Trees, planar Graphs

**UNIT-VIII**

Basic Concepts Isomorphism and Sub graphs, Graph Theory and Applications, Multi graphs and Euler circuits, Hamiltonian graphs, Chromatic Numbers

It has many practical applications in computer science like design of computing machines, artificial intelligence, definition of data structures for programming languages etc.

**Propositional Logic** is concerned with statements to which the truth values, “true” and “false”, can be assigned. The purpose is to analyze these statements either individually or in a composite manner.

Prepositional Logic – Definition

A proposition is a collection of declarative statements that has either a truth value “true” or a truth value “false”. A propositional consists of propositional variables and connectives.

- It is because unless we give a specific value of A, we cannot say whether the statement is true or false.

Connectives

In propositional logic generally we use five connectives which are −

- OR (∨∨)
- AND (∧∧)
- Negation/ NOT (¬¬)
- Implication / if-then (→→)
- If and only if (⇔⇔).

**OR (**∨∨**)** − The OR operation of two propositions A and B (written as A∨BA∨B) is true if at least any of the propositional variable A or B is true.

The truth table is as follows −

A |
B |
A ∨ B |

True | True | True |

True | False | True |

False | True | True |

False | False | False |

**AND (**∧∧**)** − The AND operation of two propositions A and B (written as A∧BA∧B) is true if both the propositional variable A and B is true.

The truth table is as follows −

A |
B |
A ∧ B |

True | True | True |

True | False | False |

False | True | False |

False | False | False |

**Negation (**¬¬**)** − The negation of a proposition A (written as ¬A¬A) is false when A is true and is true when A is false.

The truth table is as follows −

A |
¬ A |

True | False |

False | True |

**Implication / if-then (**→→**)** − An implication A→BA→B is the proposition “if A, then B”. It is false if A is true and B is false. The rest cases are true.

The truth table is as follows −

A |
B |
A → B |

True | True | True |

True | False | False |

False | True | True |

False | False | True |

**If and only if (**⇔⇔**)** − A⇔BA⇔B is bi-conditional logical connective which is true when p and q are same, i.e. both are false or both are true.

The truth table is as follows −

A |
B |
A ⇔ B |

True | True | True |

True | False | False |

False | True | False |

False | False | True |

Tautologies

A Tautology is a formula which is always true for every value of its propositional variables.

**Example** − Prove [(A→B)∧A]→B[(A→B)∧A]→B is a tautology

The truth table is as follows −

A |
B |
A → B |
(A → B) ∧ A |
[( A → B ) ∧ A] → B |

True | True | True | True | True |

True | False | False | False | True |

False | True | True | False | True |

False | False | True | False | True |

As we can see every value of [(A→B)∧A]→B[(A→B)∧A]→B is “True”, it is a tautology.

Contradictions

A Contradiction is a formula which is always false for every value of its propositional variables.

**Example** − Prove (A∨B)∧[(¬A)∧(¬B)](A∨B)∧[(¬A)∧(¬B)] is a contradiction

The truth table is as follows −

A |
B |
A ∨ B |
¬ A |
¬ B |
(¬ A) ∧ ( ¬ B) |
(A ∨ B) ∧ [( ¬ A) ∧ (¬ B)] |

True | True | True | False | False | False | False |

True | False | True | False | True | False | False |

False | True | True | True | False | False | False |

False | False | False | True | True | True | False |

As we can see every value of (A∨B)∧[(¬A)∧(¬B)](A∨B)∧[(¬A)∧(¬B)] is “False”, it is a contradiction.

Contingency

** **

**Elements Of Discrete Mathematics A Computer Oriented Approach:**

Here, we can see the truth values of ¬(A∨B)and[(¬A)∧(¬B)]¬(A∨B)and[(¬A)∧(¬B)] are same, hence the statements are equivalent.

Testing by 2^{nd} method (Bi-conditionality)

A |
B |
¬ (A ∨ B ) |
[(¬ A) ∧ (¬ B)] |
[¬ (A ∨ B)] ⇔ [(¬ A ) ∧ (¬ B)] |

True | True | False | False | True |

True | False | False | False | True |

False | True | False | False | True |

False | False | True | True | True |

As [¬(A∨B)]⇔[(¬A)∧(¬B)][¬(A∨B)]⇔[(¬A)∧(¬B)] is a tautology, the statements are equivalent.

Inverse, Converse, and Contra-positive

** **

**Elements Of Discrete Mathematics A Computer Oriented Approach:**

Implication / if-then (→)(→) is also called a conditional statement. It has two parts −

- Hypothesis, p
- Conclusion, q

As mentioned earlier, it is denoted as p→qp→q.

**Example of Conditional Statement** − “If you do your homework, you will not be punished.” Here, “you do your homework” is the hypothesis, p, and “you will not be punished” is the conclusion, q.

**Inverse** − An inverse of the conditional statement is the negation of both the hypothesis and the conclusion. If the statement is “If p, then q”, the inverse will be “If not p, then not q”. Thus the inverse of p→qp→q is ¬p→¬q¬p→¬q.

**Elements Of Discrete Mathematics A Computer Oriented Approach:**

**Example** − The inverse of “If you do your homework, you will not be punished” is “If you do not do your homework, you will be punished.”

**Converse** − The converse of the conditional statement is computed by interchanging the hypothesis and the conclusion. If the statement is “If p, then q”, the converse will be “If q, then p”. The converse of p→qp→q is q→pq→p.

**Example** − The converse of “If you do your homework, you will not be punished” is “If you will not be punished, you do not do your homework”.

**Contra-positive** − The contra-positive of the conditional is computed by interchanging the hypothesis and the conclusion of the inverse statement. If the statement is “If p, then q”, the contra-positive will be “If not q, then not p”. The contra-positive of p→qp→q is ¬q→¬p¬q→¬p.

**Example** − The Contra-positive of ” If you do your homework, you will not be punished” is “If you are not punished, then you do not do your homework”.

** **

** **