MATHEMATICAL STRUCTURES IN COMPUTER SCIENCE

For detailed content go for this e-Book -:****Download Book****:- 

For fast searching here are some links direct to those topics....

Unit 1:- 

Mathematical Logic topics all links 

• Proposition logics
• Demorgans law
• Equivalences 
• Predicates and Quantifiers 
• Predicates and quantifiers part 2
• Nested Quantifiers 
• Inference theorey 

Duality Principle: -

Duality principle states that for any true statement, the dual statement obtained by interchanging unions into intersections (and vice versa) and interchanging Universal set into Null set (and vice versa) is also true. If dual of any statement is the statement itself, it is said self-dual statement.

Example − The dual of (A∩B)∪C$(A\cap B)\cup C$ is (A∪B)∩C$(A\cup B)\cap C$

Normal Forms

We can convert any proposition in two normal forms −

• Conjunctive normal form
• Disjunctive normal form

Conjunctive Normal Form

A compound statement is in conjunctive normal form if it is obtained by operating AND among variables (negation of variables included) connected with ORs. In terms of set operations, it is a compound statement obtained by Intersection among variables connected with Unions.

Examples

• (A∨B)∧(A∨C)∧(B∨C∨D)$(A\vee B)\wedge (A\vee C)\wedge (B\vee C\vee D)$

• (P∪Q)∩(Q∪R)$(P\cup Q)\cap (Q\cup R)$

Disjunctive Normal Form

A compound statement is in disjunctive normal form if it is obtained by operating OR among variables (negation of variables included) connected with ANDs. In terms of set operations, it is a compound statement obtained by Union among variables connected with Intersections.

Examples

• (A∧B)∨(A∧C)∨(B∧C∧D)$(A\wedge B)\vee (A\wedge C)\vee (B\wedge C\wedge D)$

• (P∩Q)∪(Q∩R)

Unit 2: -

Ordered Sets, Latices, Boolean Algebra all topics links: -

• Partial Orders and Lattices 
• Introduction and types of Relations 
• Representing Relations 
• Hasse Diagram 

Unit -2 Chapter -4 

Finite state Machines all links: -

• Finite Automata(Finite State Machines) 
• Mealy and Moore machines in FSM in (Finite State Machines) 
• Designing deterministic Finite Automata Part-1 
• Designing DFA Part-2 
• Minimization of DFA 
• Conversion of NFA to DFA 
• Deterministic Finite Automata from Regular Expression

Unit -3

Chapter-5 Graphs

Graph theory basics 

Incidence and Degree, Isomorphism

Connectedness

Walk, Path and Circuits 

Shortest Path Dijkstra's Algorithm , Algorithm between two Vertices

Eulerian graph

Chapter-6 Trees

• Properties of Trees 
• Rooted and Binary Trees 
• Spanning Tree and tree traversals (Inorder, Preorder and Postorder)
• Difference between graph and tree

Chapter-7 Functions

• Composite functions & their range 
• Domain  
• Hashing function
• Growth of a function

Chapter-8 Recurrence Relations and coding theory

• Recursion
• Recurrence Relation
• Recurrence Relations Part1
• Recurrence Relations Part2
• Coding of binary Information & Error detection
• Decoding & error correction same as computer organization and assembly language.