In discrete mathematics, propositions form the foundation of logical reasoning. Based on their structure, propositions are classified into two main types:
Understanding this classification is essential because all logical expressions are built from these basic forms.
A simple proposition (also called an atomic proposition) is a statement that:
Simple propositions are usually denoted by symbols such as:
p, q, r, ...
p: It is rainingq: 5 is a prime numberr: The sky is blue✔ Each of these is a complete statement with a definite truth value ✔ They do not contain logical connectors
¬, ∧, ∨, →, ↔A compound proposition is formed by combining two or more simple propositions using logical operators.
If p and q are propositions, then compound propositions can be:
¬p
p ∧ q
p ∨ q
p → q
p ↔ q
Let:
p: It is rainingq: It is coldp ∧ q
“It is raining AND it is cold”
p ∨ q
“It is raining OR it is cold”
¬p
“It is not raining”
p → q
“If it is raining, then it is cold”
p ↔ q
“It is raining if and only if it is cold”
| Feature | Simple Proposition | Compound Proposition |
|---|---|---|
| Structure | Single statement | Combination of statements |
| Logical Operators | Not present | Present (¬, ∧, ∨, →, ↔) |
| Divisibility | Cannot be divided | Can be broken into parts |
| Example | p |
p ∧ q, ¬p, p → q |
Expressions like:
x > 5
are not propositions, but predicates, because:
xAfter assigning a value:
x = 7 → Truex = 2 → False✔ Then they become propositions.
Compound propositions can be further combined:
(p ∧ q) → (¬r ∨ q)
✔ This is a complex compound proposition ✔ Built using multiple operators
A simple proposition is an indivisible statement with a definite truth value
A compound proposition is formed by combining propositions using logical operators
Logical operators include:
¬ (NOT)∧ (AND)∨ (OR)→ (IMPLIES)↔ (BICONDITIONAL)Predicates are not propositions until variables are assigned values