Unit 3: Propositional
Propositional Logic
Propositional Logic (also called Statement Logic) is a branch of logic that deals with statements (propositions) which are either true (T) or false (F), but not both.
It is a very important unit for MCA students because it is widely used in:
- Computer programming
- Digital circuits
- Artificial Intelligence
- Database queries
- Compiler design
Propositions
A proposition is a declarative statement that has a definite truth value, either true or false.
Examples
- “2 + 3 = 5” → True
- “Lucknow is the capital of UP” → True
- “5 is a prime number” → True
Not Propositions
- Questions: “What is your name?”
- Commands: “Close the door”
- Open statements: “x > 5” (truth depends on x)
Simple and Compound Propositions
| Type | Description | Example |
|---|---|---|
| Simple | Cannot be broken further | p: 5 > 3 |
| Compound | Formed using connectives | p ∧ q |
Logical Connectives (Operators)
Logical connectives are used to join propositions.
| Symbol | Name | Meaning | Example |
| ¬ | NOT | Negation | ¬p |
| ∧ | AND | Conjunction | p ∧ q |
| ∨ | OR | Disjunction | p ∨ q |
| → | IF–THEN | Implication | p → q |
| ↔ | IF AND ONLY IF | Biconditional | p ↔ q |
Truth Tables (Very Important for Exams)
A truth table shows all possible truth values of propositions and the resulting truth value of a compound proposition.
Truth Table for NOT (¬)
| p | ¬p |
| T | F |
| F | T |
Truth Table for AND (∧)
| p | q | p ∧ q |
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
Truth Table for OR (∨)
| p | q | p ∨ q |
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
Truth Table for Implication (→)
| p | q | p → q |
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
Memory Tip: Implication is false only when p is True and q is False.
Tautology and Contradiction
Tautology
A compound proposition that is always true for all truth values.
Example: p ∨ ¬p
| p | ¬p | p ∨ ¬p |
| T | F | T |
| F | T | T |
Contradiction
A compound proposition that is always false.
Example: p ∧ ¬p
| p | ¬p | p ∧ ¬p |
| T | F | F |
| F | T | F |
Contingency
A proposition that is sometimes true and sometimes false.
Algebra of Propositions (Logical Laws)
These laws help simplify logical expressions and are heavily asked in exams.
Important Laws
| Law Name | Expression |
| Identity | p ∧ T = p, p ∨ F = p |
| Domination | p ∨ T = T, p ∧ F = F |
| Idempotent | p ∧ p = p, p ∨ p = p |
| Double Negation | ¬(¬p) = p |
| Commutative | p ∧ q = q ∧ p |
| Associative | (p ∧ q) ∧ r = p ∧ (q ∧ r) |
| Distributive | p ∧ (q ∨ r) = (p ∧ q) ∨ (p ∧ r) |
De Morgan’s Laws (Most Important)
| Expression | Equivalent |
| ¬(p ∧ q) | ¬p ∨ ¬q |
| ¬(p ∨ q) | ¬p ∧ ¬q |
Theory of Inference
Inference is the process of deriving a logical conclusion from one or more given propositions (premises).
Common Rules of Inference
| Rule | Form |
| Modus Ponens | p, p → q ⟹ q |
| Modus Tollens | ¬q, p → q ⟹ ¬p |
| Hypothetical Syllogism | p → q, q → r ⟹ p → r |
| Disjunctive Syllogism | p ∨ q, ¬p ⟹ q |
Example (Modus Ponens)
- If it rains, roads are wet (p → q)
- It rains (p)
- Therefore, roads are wet (q)
Natural Deduction (Natural Detection)
Natural Deduction is a formal method of proving the validity of arguments using rules of inference step by step.
It mimics human logical reasoning and is commonly asked as long-answer questions.
Structure of Natural Deduction Proof
- Given premises
- Apply inference rules
- Reach a conclusion
Simple Natural Deduction Example
Premises:
- p → q
- q → r
Conclusion: ∴ p → r
(Using Hypothetical Syllogism)
Visual Flow (Easy to Memorize)
Exam-Oriented Important Points
- Definition of proposition is frequently asked
- Truth tables carry high weightage
- De Morgan’s laws are compulsory
- Inference rules appear in proof-based questions
- Natural deduction is asked in long answers
Conclusion
Propositional logic builds the foundation of logical reasoning in computer science. For MCA students, mastering this unit helps in programming logic, algorithm design, and artificial intelligence.
Solved Numerical Problems (Exam-Oriented)
Problem 1: Construct Truth Table
Question: Construct the truth table for the proposition:
F = (p ∧ q) → p
Solution:
| p | q | p ∧ q | (p ∧ q) → p |
| T | T | T | T |
| T | F | F | T |
| F | T | F | T |
| F | F | F | T |
Result: Since the final column is always True, the proposition is a Tautology.
Problem 2: Check Whether a Proposition is a Tautology
Question: Prove that p ∨ ¬p is a tautology.
Solution:
| p | ¬p | p ∨ ¬p |
| T | F | T |
| F | T | T |
Conclusion: Always true → Tautology
Problem 3: Check Whether a Proposition is a Contradiction
Question: Show that p ∧ ¬p is a contradiction.
Solution:
| p | ¬p | p ∧ ¬p |
| T | F | F |
| F | T | F |
Conclusion: Always false → Contradiction
Problem 4: Logical Equivalence Using Laws
Question: Prove that ¬(p ∨ q) ≡ ¬p ∧ ¬q
Solution (Truth Table Method):
| p | q | p ∨ q | ¬(p ∨ q) | ¬p | ¬q | ¬p ∧ ¬q |
| T | T | T | F | F | F | F |
| T | F | T | F | F | T | F |
| F | T | T | F | T | F | F |
| F | F | F | T | T | T | T |
Conclusion: Both columns are identical → Logically Equivalent (De Morgan’s Law)
Problem 5: Simplification Using Algebra of Propositions
Question: Simplify:
(p ∧ q) ∨ (p ∧ ¬q)
Solution:
(p ∧ q) ∨ (p ∧ ¬q)
= p ∧ (q ∨ ¬q)
= p ∧ T
= p
Problem 6: Validity Using Rules of Inference
Question: From the premises:
p → q
p
Prove q.
Solution:
- Given: p → q
- Given: p
- By Modus Ponens: q
Conclusion: Argument is Valid
Problem 7: Inference – Modus Tollens
Question: Given:
p → q
¬q
Prove ¬p.
Solution:
Using Modus Tollens:
∴ ¬p
Problem 8: Hypothetical Syllogism
Question: From the premises:
p → q
q → r
Derive p → r.
Solution:
Using Hypothetical Syllogism:
∴ p → r
Problem 9: Natural Deduction Proof
Question: Prove using natural deduction:
Premises: p → q, q → r
Conclusion: p → r
Solution Steps:
- p → q (Given)
- q → r (Given)
- p → r (By Hypothetical Syllogism)
Problem 10: Classify the Proposition
Question: Determine whether the proposition (p → q) ∧ (q → p) is a tautology, contradiction, or contingency.
Solution (Key Observation): (p → q) ∧ (q → p) ≡ p ↔ q
Truth table gives both T and F values.
Conclusion: Contingency
Predicate Logic
Predicate Logic (also called First Order Logic) is an extension of propositional logic. While propositional logic deals with whole statements, predicate logic analyzes the internal structure of statements using variables, predicates, and quantifiers.
Predicate logic is extremely important in computer science, artificial intelligence, databases, logic programming, and compiler design.
Theory of Predicates
Predicate
A predicate is a statement containing one or more variables that becomes a proposition when specific values are assigned to those variables.
Representation
A predicate is denoted by capital letters such as P(x), Q(x, y).
Examples
- P(x): x > 5
- Q(x, y): x + y = 10
These are not propositions until values of x and y are specified.
Domain of Discourse
The domain of discourse is the set of all possible values that a variable can take.
Example:
- Domain = Natural numbers
- P(x): x is even
First Order Predicate Logic (FOPL)
First Order Predicate Logic allows:
- Variables that range over individuals
- Quantification over variables
It does not allow quantification over predicates or functions.
Difference Between Propositional Logic and Predicate Logic
| Basis | Propositional Logic | Predicate Logic |
|---|---|---|
| Variables | Propositions | Objects |
| Structure | Simple | Rich & expressive |
| Quantifiers | Not used | Used |
Predicate Formulas
Atomic Formula
An atomic formula is a predicate applied to variables or constants.
Example:
- P(x)
- Q(a, b)
Compound Predicate Formula
Compound formulas are formed using:
- Logical connectives (¬, ∧, ∨, →, ↔)
- Quantifiers (∀, ∃)
Example: ∀x (P(x) → Q(x))
Well-Formed Formula (WFF)
A well-formed formula is a syntactically correct predicate formula constructed using valid rules.
Quantifiers (Very Important)
Quantifiers specify how many elements in the domain satisfy a predicate.
Universal Quantifier (∀)
- Meaning: “For all” or “For every”
- Notation: ∀x P(x)
- Example: ∀x (x > 0) → All x are greater than zero
Existential Quantifier (∃)
- Meaning: “There exists” or “At least one”
- Notation: ∃x P(x)
- Example: ∃x (x is even)
Negation of Quantifiers (De Morgan Type)
| Original | Equivalent |
| ¬∀x P(x) | ∃x ¬P(x) |
| ¬∃x P(x) | ∀x ¬P(x) |
Exam Tip: This is very frequently asked.
Order of Quantifiers
∀x ∃y P(x, y) ≠ ∃y ∀x P(x, y)
Order of quantifiers changes the meaning completely.
Inference Theory of Predicate Logic
Inference
Inference is the process of deriving new logical conclusions from given premises.
Predicate logic inference extends propositional inference by handling quantifiers.
Important Rules of Inference in Predicate Logic
| Rule | Form |
| Universal Instantiation (UI) | ∀x P(x) ⟹ P(a) |
| Existential Instantiation (EI) | ∃x P(x) ⟹ P(a) |
| Universal Generalization (UG) | P(x) ⟹ ∀x P(x) |
| Existential Generalization (EG) | P(a) ⟹ ∃x P(x) |
Example: Universal Instantiation
- Premise: ∀x (x is mortal)
- Conclusion: Socrates is mortal
Combined Inference Example
Premises:
- ∀x (Human(x) → Mortal(x))
- Human(Socrates)
Conclusion: ∴ Mortal(Socrates)
Rules Used:
- Universal Instantiation
- Modus Ponens
Validity of Arguments in Predicate Logic
An argument is valid if the conclusion logically follows from the premises using inference rules.
Predicate logic validity often involves:
- Removing quantifiers
- Applying inference rules
Common Mistakes (Exam Warning)
- Confusing ∀ and ∃
- Wrong negation of quantifiers
- Ignoring domain of discourse
- Changing order of quantifiers
Exam-Oriented Important Points
- Definition of predicate is frequently asked
- Quantifiers carry high weightage
- Negation of quantifiers is compulsory
- Inference rules appear in long answers
- Examples are important for full marks
Conclusion
Predicate logic increases the expressive power of logic and is essential for modeling real-world problems in computer science. For MCA students, this unit is a bridge between logic theory and practical applications like AI and databases.