
- Discrete Mathematics - Home
- Discrete Mathematics Introduction
- Mathematical Statements and Operations
- Atomic and Molecular Statements
- Implications
- Predicates and Quantifiers
- Sets
- Sets and Notations
- Relations
- Operations on Sets
- Venn Diagrams on Sets
- Functions
- Surjection and Bijection Functions
- Image and Inverse-Image
- Mathematical Logic
- Propositional Logic
- Logical Equivalence
- Deductions
- Predicate Logic
- Proof by Contrapositive
- Proof by Contradiction
- Proof by Cases
- Rules of Inference
- Group Theory
- Operators & Postulates
- Group Theory
- Algebric Structure for Groups
- Abelian Group
- Semi Group
- Monoid
- Rings and Subring
- Properties of Rings
- Integral Domain
- Fields
- Counting & Probability
- Counting Theory
- Combinatorics
- Additive and Multiplicative Principles
- Counting with Sets
- Inclusion and Exclusion
- Bit Strings
- Lattice Path
- Binomial Coefficients
- Pascal's Triangle
- Permutations and Combinations
- Pigeonhole Principle
- Probability Theory
- Probability
- Sample Space, Outcomes, Events
- Conditional Probability and Independence
- Random Variables in Probability Theory
- Distribution Functions in Probability Theory
- Variance and Standard Deviation
- Mathematical & Recurrence
- Mathematical Induction
- Formalizing Proofs for Mathematical Induction
- Strong and Weak Induction
- Recurrence Relation
- Linear Recurrence Relations
- Non-Homogeneous Recurrence Relations
- Solving Recurrence Relations
- Master's Theorem
- Generating Functions
- Graph Theory
- Graph & Graph Models
- More on Graphs
- Planar Graphs
- Non-Planar Graphs
- Polyhedra
- Introduction to Trees
- Properties of Trees
- Rooted and Unrooted Trees
- Spanning Trees
- Graph Coloring
- Coloring Theory in General
- Coloring Edges
- Euler Paths and Circuits
- Hamiltonion Path
- Boolean Algebra
- Boolean Expressions & Functions
- Simplification of Boolean Functions
- Advanced Topics
- Number Theory
- Divisibility
- Remainder Classes
- Properties of Congruence
- Solving Linear Diophantine Equation
- Useful Resources
- Quick Guide
- Useful Resources
- Discussion
Mathematical Statements and Operations in Discrete Mathematics
In discrete mathematics, mathematical statements and operations form the building blocks for logical reasoning, problem-solving, and algorithm development in computer science.
In this chapter, we will explain the various types of mathematical statements, logical operations, and their applications in discrete mathematics and computer science. We will break down complex ideas into simpler terms for a better understanding.
Types of Mathematical Statements
Mathematical statements are used in logical reasoning in discrete mathematics. Let us see the main types of statements −
Propositions
A proposition is a declarative sentence that is either true or false, but not both. Let us see some examples −
- "The sky is blue." (This can be true or false depending on the time of day and weather conditions.)
- "2 + 2 = 4" (This is always true.)
- "All prime numbers are odd." (This is false, as 2 is an even prime number.)
Predicates
A predicate is a statement that contains one or more variables and becomes a proposition when specific values are assigned to the variables. For example −
- P(x): "x is greater than 5" This becomes a proposition when we assign a value to x −
- P(7) is true
- P(3) is false
Quantified Statements
Quantified statements use quantifiers which claims about the elements of a set. There are two types of quantifiers −
- Universal Quantifier (∀): "for all"
- Existential Quantifier (∃): "there exists"
For example −
- ∀x (x > 0 → x2 > 0): "For all x, if x is positive, then x2 is positive."
- ∃x (x2 = 4): "There exists an x such that x2 equals 4."
Logical Operations
Logical operations allow us to combine and manipulate propositions. Some of the fundamental logical operations are −
Negation (NOT)
Negation reverses the truth value of a proposition. It is expressed as ¬ or ~. The example for negation is like −
p: "It is raining", then ¬p: "It is not raining".
Conjunction (AND)
Conjunction combines two propositions and is true only if both propositions are true. Denoted as ∧. For example,
p: "It is cold", q: "It is windy", p q: "It is cold and windy".
Disjunction (OR)
Disjunction combines two propositions and is true if at least one of the propositions is true. Denoted as ∨. For example,
p: "I will study math", q: "I will study physics" p q: "I will study math or physics (or both)".
Implication (IF-THEN)
Implication represents a conditional statement, where one proposition implies another. Denoted as →. For example,
p: "It is raining", q: "The ground is wet", p q: "If it is raining, then the ground is wet".
Biconditional (IF AND ONLY IF)
Biconditional represents a two-way implication, where two propositions imply each other. It's denoted as ↔. For example,
p: "A triangle has three sides", q: "A triangle has three angles", then p ↔ q: "A shape is a triangle if and only if it has three sides and three angles"
Truth Tables
Another important thing in discrete maths are truth tables. These are used to display all possible combinations of truth values for compound propositions. They are used for understanding and analyzing logical expressions.
Consider an example of Truth table for p → q
p | q | p → q |
---|---|---|
T | T | T |
T | F | F |
F | T | T |
F | F | T |
Logical Equivalences
Logical equivalences are pairs of compound propositions that always have the same truth value. Some important logical equivalences include −
Commutative Laws
- p ∧ q ≡ q ∧ p
- p ∨ q ≡ q ∨ p
Associative Laws
- (p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
- (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
Distributive Laws
- p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
- p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
De Morgan's Laws
- ¬(p ∧ q) ≡ ¬p ∨ ¬q
- ¬(p ∨ q) ≡ ¬p ∧ ¬q
Set Operations
In set theory, there are some basic set of operations −
Union
The union of two sets A and B is the set of elements that are in A, in B, or in both A and B. Denoted as ∪, For example,
A = {1, 2, 3}, B = {3, 4, 5}, then A ∪ B = {1, 2, 3, 4, 5}
Intersection
The intersection of two sets A and B is the set of elements that are in both A and B. Denoted as ∩, For example,
A = {1, 2, 3}, B = {3, 4, 5}, then A ∩ B = {3}
Complement
The complement of a set A is the set of elements that are not in A. Denoted as A' or Ac. For example,
If universal set U = {1, 2, 3, 4, 5} and A = {1, 2, 3}, then A' = {4, 5}
Set Difference
The set difference A - B is the set of elements that are in A but not in B. Denoted as –. For example,
A = {1, 2, 3, 4}, B = {3, 4, 5}, then A - B = {1, 2}
Conclusion
In this chapter, we touched upon the fundamental concepts of mathematical statements and operations in discrete mathematics. We explained the various types of statements, including propositions, predicates, and quantified statements.
We also understood logical operations, truth tables, and logical equivalences, which form the basis of logical reasoning in discrete mathematics. In addition, we highlighted the set operations and their importance in discrete mathematics and computer science.