Proposition in Discrete Mathematics [ English ]

Languages

• English

1. Introduction to Proposition

In discrete mathematics, logic forms the backbone of reasoning and problem-solving. The most basic unit of logic is a proposition. All logical operations—such as conjunction, disjunction, negation, and implication—are built upon propositions.

Understanding propositions is essential before studying more advanced logical concepts.

2. Definition of Proposition

A proposition is a declarative statement that has a definite truth value, either True or False, but not both.

Key Characteristics:

• It must be a statement (not a question or command)
• It must have a clear truth value

3. Examples of Propositions

Valid Propositions

• “2 + 3 = 5” → True
• “7 is an even number” → False
• “The Earth revolves around the Sun” → True

✔ Each of these statements is either true or false.

Not Propositions

• “What is your name?” ❌ (question)
• “Close the door” ❌ (command)
• “x > 5” ❌ (depends on value of x)

✔ These do not have definite truth values.

4. Propositional Variables

Propositions are often represented using symbols such as:

p, q, r, ...

Each variable represents a proposition with a truth value:

• p = True or False
• q = True or False

5. Types of Propositions

(a) Simple (Atomic) Proposition

A simple proposition cannot be broken down into smaller parts.

Example:

• p: It is raining

(b) Compound Proposition

A compound proposition is formed by combining simple propositions using logical operators.

Examples:

p ∧ q
p ∨ q
¬p
p → q
p ↔ q

6. Logical Operators Used with Propositions

7. Open Sentences vs Propositions

An important distinction:

Open Sentence (Predicate)

• Example: x > 5
• Depends on variable x
• Not a proposition

Proposition

• Example: 5 > 5 → False
• Has definite truth value

8. Truth Value of a Proposition

Every proposition has exactly one truth value:

• True (T)
• False (F)

There is no ambiguity.

9. Importance of Propositions

(a) Foundation of Logic

All logical expressions are built using propositions.

(b) Computer Science

• Boolean logic
• Programming conditions
• Circuit design

(c) Mathematics

• Proofs
• Theorems
• Logical reasoning

10. Key Observations

• Only statements with definite truth values are propositions
• Variables without values form predicates, not propositions
• Logical operators combine propositions into complex expressions

11. Summary

• A proposition is a statement that is either true or false

• Represented using variables like p, q

• Two types:

  • Simple
  • Compound

• Forms the basis of all logical operations

• Must not be confused with:

  • Questions
  • Commands
  • Open sentences