Conjunction in Discrete Mathematics [ English ]

Languages

• English

1. Introduction to Conjunction

In discrete mathematics, complex logical statements are formed by combining simpler statements using logical operators. One of the most fundamental operators is conjunction, which models situations where multiple conditions must hold simultaneously.

Conjunction is essential in:

• Mathematical reasoning
• Algorithm design
• Boolean logic and circuit theory

2. Definition of Conjunction

A conjunction is a compound proposition formed using the logical operator AND.

Formal Definition:

If p and q are propositions, then their conjunction is:

p ∧ q

The proposition p ∧ q is true if and only if both p and q are true. Otherwise, it is false.

3. Symbol and Interpretation

• Symbol: ∧

• Read as:

  • “p AND q”
  • “both p and q”

4. Truth Table of Conjunction

Explanation:

• Only one case produces True: when both inputs are true
• In all other cases, the conjunction is false

5. Examples of Conjunction (Formally Correct)

Example 1: Simple Propositions

Let:

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

Then:

p ∧ q

means: It is raining AND it is cold

✔ This is a proposition, since both p and q have definite truth values.

Example 2: Using Predicates (Important Correction)

Let:

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

Then:

p(x) ∧ q(x)

⚠ This is not a proposition, because x is not specified. It is a predicate (open sentence).

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

✔ Now it is a proposition (True).

Case 2: Let x = 12

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

p(12) ∧ q(12) → True ∧ False → False

✔ Now it is a proposition (False).

Example 3: Clearly False Conjunction

Let:

• p: 7 is even (False)
• q: 10 is even (True)

p ∧ q → False ∧ True → False

✔ Since both are not true, the conjunction is false.

6. Properties (Laws) of Conjunction

(a) Commutative Law

p ∧ q ≡ q ∧ p

(b) Associative Law

(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)

(c) Identity Law

p ∧ True ≡ p

(d) Domination Law

p ∧ False ≡ False

(e) Idempotent Law

p ∧ p ≡ p

7. Conjunction with Negation

p ∧ ¬p

This expression is always false and represents a contradiction.

8. Real-Life Interpretation

Conjunction appears frequently in real-world reasoning:

• “You will pass if you study AND attend classes”
• “Access granted if username is valid AND password is correct”

In programming:

if (condition1 ∧ condition2)

9. Applications of Conjunction

(a) Computer Science

• Logical conditions
• Boolean expressions
• AND gates in digital circuits

(b) Mathematics

• Defining multiple constraints
• Combining conditions in proofs

(c) Databases

• SQL queries using AND

10. Summary

• Conjunction is written as p ∧ q
• True only when both propositions are true
• Based on strict logical combination
• Works on propositions; predicates must be instantiated first
• Obeys standard logical laws