- 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
Logical Equivalence in Discrete Mathematics
Logical equivalence is a fundamental concept in propositional logic. It is used in analyzing and transforming logical statements into more manageable forms.
In this chapter, we will explain the meaning of logical equivalence and understand how truth tables help us verify equivalence. We will also demonstrate how recognizing logical equivalence can simplify complex expressions.
What is Logical Equivalence?
Logical equivalence is the relationship between two statements that have the same truth value in every possible scenario. In simpler terms, we can say two statements are logically equivalent if they are both either True or False. It is like saying two people always agreeing on every topic.
Mathematically, we can express this relationship between two statements P and Q by writing P ≡ Q, which means P and Q are logically equivalent.
Understanding Logical Equivalence Using Truth Tables
Like logics, a truth table is a tool to determine whether two statements are logically equivalent. We list out all possible truth values for each statement and then compare the results. If the truth values match in every case, the statements are logically equivalent.
Example of Logical Equivalence of P → Q and ¬P ∨ Q
Let us see an example of logical equivalence between two statements, P → Q (if P then Q) and ¬P ∨ Q (not P or Q). To prove these two statements are logically equivalent, we construct the truth table −
| P | Q | P → Q | ¬P ∨ Q |
|---|---|---|---|
| T | T | T | T |
| T | F | F | F |
| F | T | T | T |
| F | F | T | T |
As we can see, the final columns of both statements are the same, meaning P → Q and ¬P ∨ Q are logically equivalent.
De Morgan's Laws
We have learnt the concept of De Morgan’s Laws in Set Theory and Boolean algebra. They are a set of logical equivalences in discrete mathematics. These laws show us a way to distribute negations across conjunctions (ANDs) and disjunctions (ORs). They are useful in simplifying complex logical expressions.
De Morgan's Laws are −
- ¬(P ∧ Q) ≡ ¬P ∨ ¬Q
- ¬(P ∨ Q) ≡ ¬P ∧ ¬Q
Example of Logical Equivalence Using De Morgans Law
Let us see how to apply De Morgan's law to check if the statements ¬(P ∨ Q) and ¬P ∧ ¬Q are logically equivalent.
| P | Q | ¬(P ∨ Q) | ¬P ∧ ¬Q |
|---|---|---|---|
| T | T | F | F |
| T | F | F | F |
| F | T | F | F |
| F | F | T | T |
As the truth values are the same, De Morgan's law holds, confirming that ¬(P ∨ Q) ≡ ¬P ∧ ¬Q
Negation of Implications
Another useful but trickier thing is negation of implications. The negation of an implication P → Q is not another implication. It is a conjunction of the hypothesis being true and the conclusion being false. In other words, ¬(P → Q) ≡ P ∧ ¬Q
Example of Negating an Implication
Let us see the prove that ¬(P → Q) ≡ P ∧ ¬Q without using a truth table by breaking it down step-by-step −
- Start with ¬(P → Q).
- Recall that P → Q is equivalent to ¬P ∨ Q (We also proved this in the first example)
- Now apply negation: ¬(¬P ∨ Q)
- Using De Morgan’s Law, we get ¬¬P ∧ ¬Q
- Finally, simplify the double negation to P ∧ ¬Q
By using logical transformations instead of truth tables, we showed that ¬(P → Q) ≡ P ∧ ¬Q
More Complex Examples of Logical Equivalence
We have understood the basics examples. Let us see some of the complex examples where we have much things to do. Let us determine whether it is logically equivalent to another statement using a truth table.
Example: Are (P ∨ Q) → R and (P → R) ∨ (Q → R) Logically Equivalent?
Constructing the truth table −
| P | Q | R | (P ∨ Q) → R | (P → R) ∨ (Q → R) |
|---|---|---|---|---|
| T | T | T | T | T |
| T | T | F | F | F |
| T | F | T | T | T |
| T | F | F | F | T |
| F | T | T | T | T |
| F | T | F | F | T |
| F | F | T | T | T |
| F | F | F | T | T |
In the fourth and sixth rows, the truth values differ, meaning that the two statements are not logically equivalent. However, in certain scenarios, (P ∨ Q) → R implies (P → R) ∨ (Q → R), but not the reverse.
Applications of Logical Equivalence
Let us see where we can use logical equivalence to solve complex problems −
- Simplifying Proofs − When tackling a complex proof, recognizing equivalent statements can simplify the process. This allows us to rephrase parts of the proof into simpler forms.
- Boolean Algebra − Logical equivalence plays a key role in Boolean algebra, which is used in circuit design and computer programming. By using logical equivalences, complex Boolean expressions can be simplified for easier implementation.
- Algorithm Optimization − In computer science, algorithms that involve decision-making processes can be optimized by identifying and using logically equivalent expressions that are faster to compute.
Conclusion
In this chapter, we provided an overview of logical equivalence in discrete mathematics, covering its definition and how truth tables help verify whether two statements are logically equivalent.
We explored De Morgans Laws and applied them to practical examples, discussed the negation of implications, and showed how to handle more complex logical expressions. We also highlighted the importance of logical equivalence in simplifying proofs, Boolean algebra, and computer science applications.