Mathematical logic is a crucial topic in Discrete Mathematics and Computer Science. It provides a systematic way to reason about statements, ensuring precision in arguments, computations, and programming. Mathematical logic serves as the foundation for various fields like artificial intelligence, programming languages, database systems, and automated theorem proving.
In this tutorial, we will cover Propositional Logic and Predicate Logic in detail.
1. Propositional Logic
1.1 Definition of Propositions
A proposition is a declarative statement that is either true (T) or false (F), but not both.
Examples:
✅ Propositions (They have a definite truth value)
- “$2 + 3 = 5$” (True)
- “India is in Asia” (True)
- “$x + 2 = 7$” (Not a proposition because its truth value depends on $x$)
✅ Not Propositions (They do not have a definite truth value)
- “What time is it?” (It’s a question, not a declarative statement)
- “Study well!” (It’s an instruction, not a declarative statement)
Thus, only statements that are either true or false are considered propositions.
1.2 Logical Connectives
Logical connectives help form compound propositions from simple ones. These allow us to express complex logical relationships systematically.
| Symbol | Name | Meaning |
|---|---|---|
| $\neg p$ | Negation | “Not $p$” |
| $p \land q$ | Conjunction | “$p$ AND $q$” |
| $p \lor q$ | Disjunction | “$p$ OR $q$” |
| $p \rightarrow q$ | Implication | “If $p$, then $q$” |
| $p \leftrightarrow q$ | Biconditional | “$p$ if and only if $q$” |
1.3 Truth Tables
Truth tables define how logical connectives behave.
Negation ($\neg p$)
| $p$ | $\neg p$ |
|---|---|
| T | F |
| F | T |
Conjunction ($p \land q$) – “AND” Operation
| $p$ | $q$ | $p \land q$ |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
Disjunction ($p \lor q$) – “OR” Operation
| $p$ | $q$ | $p \lor q$ |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
Implication ($p \rightarrow q$) – “If-Then” Operation
| $p$ | $q$ | $p \rightarrow q$ |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
✅ Key Point: Implication is false only when $p$ is true and $q$ is false.
Biconditional ($p \leftrightarrow q$) – “If and only if” Operation
| $p$ | $q$ | $p \leftrightarrow q$ |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
1.4 Logical Equivalences
Two statements $p$ and $q$ are logically equivalent if they have the same truth table values.
List of ALL Logical Equivalences:
- Identity Laws:
- $p \land T = p$
- $p \lor F = p$
- Domination Laws:
- $p \lor T = T$
- $p \land F = F$
- Idempotent Laws:
- $p \lor p = p$
- $p \land p = p$
- Double Negation Law:
- $\neg (\neg p) = p$
- Commutative Laws:
- $p \lor q = q \lor p$
- $p \land q = q \land p$
- Associative Laws:
- $(p \lor q) \lor r = p \lor (q \lor r)$
- $(p \land q) \land r = p \land (q \land r)$
- Distributive Laws:
- $p \lor (q \land r) = (p \lor q) \land (p \lor r)$
- $p \land (q \lor r) = (p \land q) \lor (p \land r)$
- De Morgan’s Laws:
- $\neg (p \land q) = \neg p \lor \neg q$
- $\neg (p \lor q) = \neg p \land \neg q$
1.5 Example: Prove $\neg (p \lor q)$ is equivalent to $\neg p \land \neg q$
Using De Morgan’s Law, ¬(p∨q)=¬p∧¬q\neg (p \lor q) = \neg p \land \neg q
✅ Truth Table Verification:
| $p$ | $q$ | $p \lor q$ | $\neg (p \lor q)$ | $\neg p$ | $\neg q$ | $\neg p \land \neg 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 |
✅ Both $\neg (p \lor q)$ and $\neg p \land \neg q$ have the same truth values, proving their logical equivalence.
Practice Questions
- Construct a truth table for $(p \lor q) \rightarrow \neg p$.
- Prove that $p \rightarrow q$ is equivalent to $\neg p \lor q$.
- Use De Morgan’s laws to simplify $\neg (p \lor (q \land r))$.
- Show that $(p \rightarrow q) \land (q \rightarrow r)$ implies $p \rightarrow r$.
- Find the truth table for $(p \land q) \lor (\neg p \land r)$.