Discrete Structure - Syllabus

Embark on a profound academic exploration as you delve into the Discrete Structure course (DS) within the distinguished Tribhuvan university's BIT department. Aligned with the BIT Curriculum, this course (Na) seamlessly merges theoretical frameworks with practical sessions, ensuring a comprehensive understanding of the subject. Rigorous assessment based on a 80 + 20 marks system, coupled with a challenging passing threshold of , propels students to strive for excellence, fostering a deeper grasp of the course content.

This 3 credit-hour journey unfolds as a holistic learning experience, bridging theory and application. Beyond theoretical comprehension, students actively engage in practical sessions, acquiring valuable skills for real-world scenarios. Immerse yourself in this well-structured course, where each element, from the course description to interactive sessions, is meticulously crafted to shape a well-rounded and insightful academic experience.

Course Description: The course introduces the basic concepts of discrete mathematics such as

introductory logic, proofs, sets, relations, functions, counting and probability, with an emphasis on

applications in information technology.

Course Objectives: The main objective of the course is to introduce basic concepts of discrete

mathematics, understand the concepts of graphs, functions, relations and number theory

respectively and explore applications of discrete mathematics in information technology.

Logic and Proof Methods

Propositional Logic (Introduction, Propositions, Logical Connectives/Operators, Precedence of Logical Operators, Translating English Sentences to Propositional Logic)

Propositional Equivalences (Introduction, Logical Equivalences, Proving Logical Equivalences using Truth Table and Symbolic Derivation)

Predicate Logics (Introduction, Predicates and Quantifiers, Precedence of Quantifiers, Binding Variables, Negation of Quantified Statements, Translating English Sentence to Logical Expressions, Nested Quantifiers)

Rules of Inferences (Introduction, Rules of Inference for Propositional Logic, Fallacies, Valid Arguments for Propositional Logic, Rules of Inference for Quantified Statements)

Proof Methods (Introduction and Terminologies, Direct Proof, Indirect Proof, Vacuous and Trivial Proof, Proof by Contradiction, Exhaustive and Proof by Cases, Proof of Equivalence, Existence and Uniqueness Proofs, Proofs by Counter Example), Mistakes in Proofs

Sets, Relations and Functions

Sets (Definition, Notation; Some Important Sets; Equal Sets; Empty Set; Venn Diagram; Subsets; Size of a Set; Power Sets; Cartesian Product; Set Operations – Union, Intersection, Difference and Complement; Computer Representation of Sets – Complement, Union and Intersection)

Functions (Definition and Terminologies; Equal Functions; Real Valued and Integer Valued Functions; Image of Subset of Domain; One-to-One, Onto, and One-to-One Correspondence; Inverse and Composite Functions; Graph of Functions; Ceiling Function, Floor Function, Boolean Function and Exponential Function)

Relations (Introduction; Functions as Relations; Relation on a Set; Properties of Relations – Reflexive, Symmetric, Antisymmetric, and Transitive; Combining Relations; n-Ary Relations and Applications – Database and Relations, Operations; Representing Relations using Matrices and Diagraphs; Closure of Relations – Reflexive, Symmetric and Transitive; Equivalence Relations and Classes; Partial Orderings)

Induction and Recursion

Mathematical Induction (Introduction; Proofs by Mathematical Induction; Examples – Proving Summation Formula, Proving Inequalities and Proving Divisibility Results)

Strong Induction and Well Ordering (Introduction and Examples of Strong Induction; Proofs using Well Ordering Property)

Recursive Definitions and Structural Induction (Introduction; Recursively Defined Functions, Sets and Structures; Structural Induction)

Recursive Algorithms and Proving Correctness of Recursive Algorithms

Number Theory

Integers and Division (Division Algorithm; Modular Arithmetic; Arithmetic Modulo m) Primes and Greatest Common Division (Primes; Trial Division; Prime Factorization; GCD and LCM; Relatively Prime, Pairwise Relatively Prime; Using Prime Factorization to find GCD and LCM)

Extended Euclidian Algorithm (Euclidian Algorithm; GCDs as Linear Combinations; Extended Euclidian Algorithm)

Integers and Algorithms (Integer Representations – Binary, Octal, Hexadecimal, and Conversions; Addition, Multiplication, Division, Modulus Algorithms)

Applications of Number Theory (Linear Congruencies, Chinese Remainder Theorem, Computer Arithmetic with Large Integers)

Matrices (Zero-One Matrices, Boolean Matrix Operations – Join, Meet, Product, and Power); Prime Number and its applications

Counting and Discrete Probability

Counting (Basics of Counting – Product Rule, Sum Rule and Subtraction Rule; Pigeonhole Principle and Generalized Pigeonhole Principle; Permutations and Combinations; Two Element Subsets and Counting Subsets of a Set; Binomial Coefficients and Identity; Pascal’s Identity and Triangle; Generalized Permutations and Combinations – Permutation and Combinations with Repetition, Permutations with Indistinguishable Objects; Generating Permutations and Combinations with Examples)

Discrete Probability (Finite Probability; Probabilities of Complements and Unions; Probability Theory – Assigning Probability, Conditional Probability, Independence, Random Variables, Expected Value and Variance, Randomized Algorithms, Probability Calculation in Hashing)

Advanced Counting (Recurrence Relations; Solving Recurrence Relations - Homogeneous and Non-Homogeneous equations, Theorems without Proof)