Disjunction in Discrete Mathematics [ English ]

Languages

• English

1. Introduction to Disjunction

In discrete mathematics, compound propositions are formed using logical operators. One of the most important operators is disjunction, which represents a choice or alternative between statements.

Disjunction is used when at least one condition must be true. It is widely applied in logical reasoning, programming, and digital systems.

2. Definition of Disjunction

A disjunction is a compound proposition formed by combining two propositions using the logical operator OR.

Formal Definition:

If p and q are propositions, then their disjunction is written as:

p ∨ q

The disjunction p ∨ q is true if at least one of p or q is true. It is false only when both are false.

3. Symbol and Representation

The symbol used for disjunction is:

∨

Interpretation:

• p ∨ q is read as:

  • “p OR q”
  • “either p or q (or both)”

Note: This is inclusive OR, meaning both can be true.

4. Truth Table of Disjunction

Explanation:

• The result is false only when both p and q are false
• In all other cases, it is true

5. Examples of Disjunction (Formally Correct)

Example 1: Simple Propositions

Let:

• p: It is raining
• q: It is cold

Then:

p ∨ q

means: It is raining OR it is cold

✔ This is true if at least one statement is true.

Example 2: Using Predicates (Open Sentences)

Let:

• p(x): x > 0
• q(x): x < 10

Then:

p(x) ∨ q(x)

This is a predicate, not a proposition, because x is not specified.

Converting into a Proposition

Case 1: Let x = 5

• p(5): 5 > 0 → True
• q(5): 5 < 10 → True

p(5) ∨ q(5) → True ∨ True → True

Case 2: Let x = -3

• p(-3): -3 > 0 → False
• q(-3): -3 < 10 → True

p(-3) ∨ q(-3) → False ∨ True → True

Case 3: Let x = 15

• p(15): 15 > 0 → True
• q(15): 15 < 10 → False

p(15) ∨ q(15) → True ∨ False → True

Case 4: When Both are False

Let x = 0 and modify predicate slightly for demonstration:

• p(x): x > 0 → False
• q(x): x < 0 → False

p(0) ∨ q(0) → False ∨ False → False

✔ Only in this case the disjunction is false.

Example 3: Everyday Logical Statement

Let:

• p: A number is even
• q: A number is divisible by 3

Then:

p ∨ q

means: The number is even OR divisible by 3

✔ True if at least one condition holds.

6. Properties of Disjunction

(a) Commutative Law

p ∨ q ≡ q ∨ p

(b) Associative Law

(p ∨ q) ∨ r ≡ p ∨ (q ∨ r)

(c) Identity Law

p ∨ False ≡ p

(d) Domination Law

p ∨ True ≡ True

(e) Idempotent Law

p ∨ p ≡ p

7. Disjunction with Negation

Disjunction interacts with negation in important ways.

Example:

p ∨ ¬p

This is always true and represents a tautology.

8. Inclusive OR vs Exclusive OR

Inclusive OR (∨)

• True when at least one is true
• Includes the case where both are true

Exclusive OR (XOR)

• True when exactly one is true
• Not both

Example (XOR concept):

• True OR True → False (in XOR)

9. Applications of Disjunction

(a) Computer Science

• Conditional statements
• Boolean expressions
• Logic gates (OR gate)

(b) Mathematics

• Defining alternatives
• Case-based reasoning

(c) Databases

• SQL queries using OR conditions

10. Summary

• Disjunction combines propositions using ∨
• p ∨ q is false only when both are false
• It represents an inclusive OR
• Works with predicates but becomes a proposition only after assigning values
• Plays a vital role in logic, programming, and reasoning