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 → x² > 0): "For all x, if x is positive, then x² is positive."
• ∃x (x² = 4): "There exists an x such that x² 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

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 A^c. 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.