Algebra of Proposition
Definition
Algebra of Proposition is the branch of logic that deals with propositions and logical operations on them, where each proposition has a definite truth value, either true (1) or false (0), and where combinations of propositions follow specific algebraic laws and identities.
A proposition is a declarative statement that can be clearly classified as true or false, but not both at the same time. For example:
- “5 is greater than 3” → True
- “Delhi is the capital of India” → True
- “x + 2 = 7” → not a proposition unless the value of x is known
In algebra of proposition, symbols are often used:
p, q, r
- → propositions
¬p
- or ~p → NOT p
p ∧ q
- → p AND q
p ∨ q
- → p OR q
p → q
- → p implies q
p ↔ q
- → p if and only if q
Main Content
1. Propositions and Truth Values
- A proposition is a statement that must be either true or false.
- Truth values are represented as 1 for true and 0 for false.
A proposition is the basic unit of logic. Unlike questions, commands, or exclamations, a proposition can be evaluated logically. For example:
- “The sky is blue” is a proposition.
- “Close the door” is not a proposition.
- “Is 10 even?” is not a proposition because it is a question.
Propositions are commonly represented by letters such as p, q, and r.
Example:
- Let p = “It is raining.”
- Let q = “The ground is wet.”
Then:
- If it is raining, p = 1
- If it is not raining, p = 0
Truth values are the foundation for all logical operations, because every compound proposition is built from simpler propositions.
2. Logical Connectives
- Logical connectives combine simple propositions to form compound propositions.
- The main connectives are negation, conjunction, disjunction, implication, and biconditional.
These connectives act like operators in algebra.
Negation (NOT)
The negation of a proposition reverses its truth value.
- If p is true, then ¬p is false.
- If p is false, then ¬p is true.
Example:
- p: “It is daytime.”
- ¬p: “It is not daytime.”
Conjunction (AND)
The conjunction p ∧ q is true only when both p and q are true.
Truth condition:
- True if p = 1 and q = 1
- False in all other cases
Example:
- p: “It is raining.”
- q: “It is cold.”
- p ∧ q: “It is raining and it is cold.”
Disjunction (OR)
The disjunction p ∨ q is true if at least one of the propositions is true.
Example:
- p: “I will study.”
- q: “I will exercise.”
- p ∨ q: “I will study or I will exercise.”
Implication (IF...THEN)
The implication p → q means “if p is true, then q must be true.”
Example:
- p: “The alarm rings.”
- q: “The door opens.”
- p → q: “If the alarm rings, then the door opens.”
Biconditional (IF AND ONLY IF)
The biconditional p ↔ q is true when both propositions have the same truth value.
Example:
- p: “A number is even.”
- q: “It is divisible by 2.”
- p ↔ q: “A number is even if and only if it is divisible by 2.”
These connectives allow formation of expressions like:
- (p ∧ q) → r
- ¬(p ∨ q)
- (p ↔ q) ∧ ¬r
3. Laws, Identities, and Simplification
- Algebra of proposition follows specific laws that help in simplifying expressions.
- These laws are similar to algebraic rules and are used to make logical expressions easier to analyze.
Some important laws are:
Commutative Laws
- p ∧ q = q ∧ p
- p ∨ q = q ∨ p
Order does not matter.
Associative Laws
- (p ∧ q) ∧ r = p ∧ (q ∧ r)
- (p ∨ q) ∨ r = p ∨ (q ∨ r)
Grouping does not matter.
Distributive Laws
- p ∧ (q ∨ r) = (p ∧ q) ∨ (p ∧ r)
- p ∨ (q ∧ r) = (p ∨ q) ∧ (p ∨ r)
These are useful for expansion and simplification.
Identity Laws
- p ∧ True = p
- p ∨ False = p
Domination Laws
- p ∨ True = True
- p ∧ False = False
Idempotent Laws
- p ∨ p = p
- p ∧ p = p
Negation Laws
- p ∨ ¬p = True
- p ∧ ¬p = False
De Morgan’s Laws
- ¬(p ∧ q) = ¬p ∨ ¬q
- ¬(p ∨ q) = ¬p ∧ ¬q
These laws are very important in simplifying expressions and proving logical equivalence.
Example of simplification:
- ¬(p ∧ q)
- Using De Morgan’s law = ¬p ∨ ¬q
This means “not both p and q” is the same as “not p or not q.”
Working / Process
1. Identify the propositions
- Break the given statement into simple logical propositions.
- Assign symbols such as p, q, r to each statement.
2. Apply logical connectives and truth rules
- Combine the propositions using AND, OR, NOT, implication, or biconditional.
- Evaluate the truth of the compound statement using truth tables or logical laws.
3. Simplify or verify the expression
- Use algebraic identities and logical equivalences to reduce the expression.
- Check whether two expressions are equivalent or whether a proposition is a tautology, contradiction, or contingency.
Example process:
Let
- p = “It is raining”
- q = “I carry an umbrella”
Statement: “If it is raining, then I carry an umbrella.”
Logical form:
- p → q
Truth table outline:
| p | q | p → q |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
This shows that implication is false only when the first statement is true and the second is false.
Another example:
Simplify
- ¬(p ∨ q)
Using De Morgan’s law:
- ¬p ∧ ¬q
This means the negation of “p or q” is “neither p nor q.”
Advantages / Applications
- Helps in simplifying complex logical expressions into easier forms, making analysis and computation more efficient.
- Used in digital circuit design, where logical propositions correspond to gates like AND, OR, and NOT.
- Essential in finite state machines, algorithm design, program verification, and decision-making systems.
Additional applications include:
Computer programming
- : Conditions in if-statements, loops, and boolean expressions.
Mathematical proof writing
- : Used for proving theorems and equivalence of statements.
Artificial intelligence and automation
- : Helps model logical reasoning and rule-based systems.
Database querying
- : Logical operators are used in search conditions and query filters.
Example in electronics:
- A circuit with AND, OR, and NOT gates can be represented by a logical expression.
- Simplifying that expression can reduce the number of gates, lower cost, and improve speed.
Example in computing:
- Condition:
if (age >= 18 AND citizen == true) - This is a propositional form that can be evaluated as true or false.
Summary
- Algebra of proposition studies logical statements and how they combine using logical operators.
- It uses truth values and logical laws to represent and simplify expressions.
- It is fundamental for logic, digital circuits, and finite state machine design.
- Propositions are the building blocks of logical reasoning in mathematics and computer science.