
- 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
Atomic and Molecular Statements in Discrete Mathematics
One of the key concepts in discrete mathematics is mathematical statements. They are used to express ideas that can be either True or False. Mathematical statements come in two forms: atomic and molecular.
In this chapter, we will highlight the difference between atomic and molecular statements. In addition, we will discuss how logical connectives work and demonstrate these concepts using various examples.
Mathematical Statements
A statement is a declarative sentence that can either be True or False. It cannot be both True and False, simultaneously. Statements are the building blocks of mathematical reasoning and form the basis for developing complex logical expressions.
Atomic Statements
An atomic statement is a simple, indivisible statement. It cannot be broken down into smaller components that are also statements. In other words, atomic statements stand alone as fundamental truths or falsehoods.
Some of the examples of atomic statements include −
- "Telephone numbers in the USA have 10 digits."
- "The moon is made of cheese."
- "42 is a perfect square."
- "3 + 7 = 12" (This is false.)
Each of these sentences is either definitively True or False. There are no additional conditions or smaller statements hidden inside them.
Non-Statements
Not every sentence qualifies as a statement. We can understand them through examples:
- "Would you like some cake?"
- "Go to your room!"
These are not statements because they do not hold a truth value. They are commands or questions and cannot be classified as true or false.
Another example of a Variable Expression:
$$\mathrm{3 \:+\: x \:=\: 12}$$
This expression is not a statement either, because the truth depends on the value of "x". For instance, if x = 9, the equation is True. If x = 5, the equation is False.
Therefore, unless we assign a specific value to x, we cannot determine whether the sentence is True or False.
Molecular Statements and Logical Connectives
We understood the atomic statement. Another type is the molecular statement. These are formed by combining two or more atomic statements using logical connectives. These connectives allow us to build more complex logical expressions.
Common Logical Connectives
There are five primary logical connectives used to create molecular statements −
- Conjunction (∧): "and"
- Disjunction (∨): "or"
- Implication (→): "if...then..."
- Biconditional (↔): "if and only if"
- Negation (¬): "not"
Example of a Molecular Statement −
Telephone numbers in India have 10 digits and 42 is a perfect square.
This molecular statement connects two atomic statements with the Conjunction AND. For the entire molecular statement to be True, both components must be True.
Truth Tables for Logical Connectives
In logics, we use truth tables a lot. As we know the truth tables are a useful to analyze the truth values of molecular statements based on the truth of their atomic components. Below are the truth conditions for each connective.
Conjunction (∧)
A conjunction, P ∧ Q, is True if and only if both P and Q are True.
P | Q | P ∧ Q |
---|---|---|
T | T | T |
T | F | F |
F | T | F |
F | F | F |
Disjunction ()
A disjunction, P ∨ Q, is True if at least one of P or Q is true. This is called Inclusive OR.
P | Q | P ∨ Q |
---|---|---|
T | T | T |
T | F | T |
F | T | T |
F | F | F |
Implication (→)
An implication, P → Q, is True unless P is true and Q is False.
P | Q | P → Q |
---|---|---|
T | T | T |
T | F | F |
F | T | T |
F | F | T |
Biconditional (↔)
A biconditional, P ↔ Q, is True when both P and Q have the same truth value.
P | Q | P ↔ Q |
---|---|---|
T | T | T |
T | F | F |
F | T | F |
F | F | T |
Negation (¬)
A negation, ¬P, simply inverts the truth value of P.
P | P |
---|---|
T | F |
F | T |
Example 1: Molecular Statements
Consider the statement: "If Bob gets a 90 on the final, then Bob will pass the class."
- P "Bob gets a 90 on the final."
- Q "Bob will pass the class."
This is an implication, P → Q. According to the truth table for implication, this statement will be false only if Bob gets a 90 on the final (P is True) and does not pass the class (Q is False). In all other cases, the implication is True.
Example 2: Molecular Statements
Consider the statement: "If 1 = 1, then most horses have 4 legs."
This statement is an implication as well. Even though the conclusion about horses might seem unrelated, the statement remains true because the hypothesis 1 = 1 is True, and the conclusion most horses have 4 legs is also true. Therefore, the whole implication is True.
Conclusion
In this chapter, we explained the concept of atomic and molecular statements in discrete mathematics. We started by defining what a mathematical statement is and understood the difference between atomic and molecular statements.
We then explained the logical connectives and their associated truth tables, which help determine the truth value of molecular statements. Thereafter, we presented an overview of conjunctions, disjunctions, implications, and other logical structures.