Discrete Mathematics Course: Goals and Concepts

Goals of a Discrete Mathematics Course

• A Discrete Mathematics course equips students with fundamental mathematical concepts useful in computer science, engineering, and related fields.
• The goals of a discrete mathematics course include developing mathematical thinking and logical skills and helping the student understand fundamental concepts.
• Focus is placed on mastering logic, set theory, relations, functions, and combinatorics.
• Students should gain familiarity with proof techniques, like direct proof, contradiction, and induction.
• Discrete structures like graphs and trees are used in computational and real-life problems.
• Students should understand how discrete math supports algorithms and data structures.
• The course includes analyzing and designing algorithms using counting principles and recurrence relations.
• Fibonacci numbers denoted as Fn = Fn-1 + Fn-2 are included.
• Key is connecting discrete mathematical concepts to programming and software engineering.
• Discrete mathematics has applications to almost every conceivable area of study.

Applied Discrete Mathematics and relationship to other disciplines

• Topics in discrete mathematics are important and basic in many courses that the student will take in the future
• Studying discrete mathematics will be important for Computer Science, for topics such as:
  • Computer Architecture
  • Data Structures
  • Algorithms
  • Programming Languages
  • Compilers
  • Computer Security
  • Databases
  • Artificial Intelligence
  • Networking
  • Graphics
  • Game Design
  • Theory of Computation
• Studying discrete mathematics will be important for Mathematics, for topics such as:
  • Logic
  • Set Theory
  • Probability
  • Number Theory
  • Abstract Algebra
  • Combinatorics
  • Graph Theory
  • Game Theory
  • Network Optimization
• Concepts encountered in discrete mathematics may be useful in courses in philosophy, economics, linguistics, and other departments.

The Foundations of Logic: Logic

• Logic deals with the methods of reasoning.
• Logic provides techniques for determining whether an argument is valid.
• Logical reasoning is used in mathematics to prove theorems.
• A proposition, or statement, is a declarative sentence that declares a fact.
• Sentences can be either true or false, but not both.
• The area of logic that deals with propositions is called propositional logics.
• Propositions cannot be questions, commands, opinions, probabilities, or variables.
• "Washington, D.C., is the capital of the United States of America" is an example of a true proposition.
• "Alexandria is the capital of Egypt" is an example of a false proposition.
• "What time is it?" is not a proposition because it is not a declarative sentence.
• "x + 1 = 2" is not a proposition because it is neither true nor false until a value is assigned to x.

Propositional Variables

• Letters denote propositional variables, or statement variables, which means that variables represent propositions.
• Conventional letters are p, q, r, and s
• The truth value of a proposition is true, denoted by T, if it is a true proposition, and false, denoted by F, if it is a false proposition.

Simple and Compound Propositions

• Simple (Primitive) propositions contain one sentence that is either true or false.
• Mathematical statements are constructed by combining one or more propositions.
• New propositions, called compound propositions, are formed from existing propositions using logical operators.
• Compound propositions combine between more than one proposition and need a connection between them.

Negation

• The negation of p, denoted by ¬p, is the statement "It is not the case that p."
• ¬p is read "not p.”
• The truth value of the negation of p, ¬p, is the opposite of the truth value of p.
• Alternate notations for negation: ~p, -p, p', Np, and !p.
• If p is "Cairo is the capital of Egypt" then ¬p can be expressed as "It is not the case that Cairo is the capital of Egypt" or "Cairo is not the capital of Egypt".
• The number of rows that appear in a truth table is 2 to the power of the number of propositions inputs.

Conjunction

• The conjunction of p and q, denoted by p ∧ q, is the proposition “p and q.”
• The conjunction p ∧ q is true when both p and q are true, and is false otherwise.

Disjunction

• The disjunction of p and q, denoted by p V q, is the proposition “p or q.”
• The disjunction p ∨ q is false when both p and q are false and is true otherwise.

Exclusive Or

• The exclusive or of p and q, denoted by p⊕ q, is the proposition that is true when exactly one of p and q is true and is false otherwise.
• p⊕ q = (p^ ¬ q)V(¬p^q)

Conditional Statements

• The conditional statement p → q is the proposition "if p, then q."
• The conditional statement p → q is false when p is true and q is false, and true otherwise.
• In the conditional statement p → q:
  • p is called the hypothesis (or antecedent or premise).
  • q is called the conclusion (or consequence).
• "p implies q", "p only if q", and "p is sufficient for q" are other ways of saying p -> q.
• "a sufficient condition for q is p" and "q whenever p" and "q is necessary for p" are other ways of saying p -> q.
• "a necessary condition for p is q" and "q follows from p" are other ways of saying p -> q.
• "q unless ¬p" is another way of saying p -> q.
• The statement p→q is logically equivalent to (¬pVq).

Biconditional statements

• The biconditional statement p ↔ q is the proposition “p if and only if q."
• The biconditional statement p ↔ q is true when p and q have the same truth values, and is false otherwise.
• Biconditional statements are also called bi-implications.
• ~(p+q) = p↔q
• "p is necessary and sufficient for q", "if p then q, and conversely", and "p iff q." are other ways of referring to a biconditional statement.
• p ↔ q = (p→q) ^ (q→ p)

Logical Operators

• Logical operators include:
  • Negation (¬)
  • Conjunction (∧)
  • Disjunction (∨)
  • Conditional (→)
  • Biconditional (↔)
• Brackets are always resolved first.

Logic and Bit Operations

• Computers represent information using bits.
• A bit is a symbol with two possible values, 0 (zero) and 1 (one).
• The meaning of the word bit comes from binary digit, because zeros and ones are the digits used in binary representations of numbers.
• A bit represents a truth value such that:
  • 1 represents True
  • 0 represents False.
• A variable is called a Boolean variable if its value is either true or false.
• A Boolean variable can be represented using a bit.
• In various programming languages, the notations for the OR, AND, and XOR operators are V, A, and ⊕.

Bit Strings

• Information is often represented using bit strings, which are lists of zeros and ones.
• Operations on the bit strings are used to manipulate the information.
• A bit string is a sequence of zero or more bits.
• The length of a bit string is the number of bits in the string.
• A bitwise operation replaces each bit in the first string with the result of the corresponding bit in the second string for the specified logical operator.