Discrete Mathematics: Mathematical Logic

Syllabus: Propositional and first order logic.

Mark Distribution in Previous GATE

Welcome to the "Discrete Mathematics: Mathematical Logic" chapter of your GATE Computer Science exam preparation. This section is designed to provide a comprehensive, exam-focused overview of the fundamental concepts, formulas, and problem-solving techniques you'll need to master. Mathematical Logic is the bedrock of computer science, providing the formal tools to reason about computation, verify program correctness, design circuits, and understand artificial intelligence. For the GATE CS exam, this subject typically carries a weightage of 5-8 marks. Questions often involve determining the validity of arguments, checking logical equivalence, translating natural language statements into logical expressions, and identifying tautologies or contradictions. A strong grasp of these concepts is indispensable not just for direct questions but also for understanding the logical underpinnings of other topics like set theory, relations, and algorithms.

Topic-wise Key Concepts

Propositional Logic

Propositional Logic, also known as propositional calculus, is the study of propositions (declarative sentences that are either true or false, but not both) and their combinations using logical connectives. It forms the most basic level of logical reasoning, focusing on the truth values of simple statements and how they combine to determine the truth values of complex statements.

• Definition and Core Idea: A proposition is a statement that is unequivocally true or false. Propositional logic uses symbols to represent propositions and logical connectives to form compound propositions, allowing us to analyze their truth values systematically.

Important Formulas, Theorems, and Results:

1. Logical Connectives:

• ▪ Negation (NOT): $\neg p$ (read as "not p")

• ▪ Conjunction (AND): $p \wedge q$ (read as "p and q")

• ▪ Disjunction (OR): $p \vee q$ (read as "p or q")

• ▪ Implication (IF...THEN): $p \rightarrow q$ (read as "if p then q" or "p implies q")

• ▪ Biconditional (IF AND ONLY IF): $p \leftrightarrow q$ (read as "p if and only if q")

• ▪ Exclusive OR (XOR): $p \oplus q$ (read as "p xor q")

• ▪ NAND: $p \uparrow q \equiv \neg(p \wedge q)$

• ▪ NOR: $p \downarrow q \equiv \neg(p \vee q)$

• 2. Truth Tables: Essential for defining connectives and evaluating compound propositions.

• ▪ $\neg p$: T if p is F, F if p is T.

• ▪ $p \wedge q$: T if both p and q are T, else F.

• ▪ $p \vee q$: T if p is T or q is T (or both), else F.

• ▪ $p \rightarrow q$: F only if p is T and q is F, else T.

• ▪ $p \leftrightarrow q$: T if p and q have the same truth value, else F.

• ▪ $p \oplus q$: T if p and q have different truth values, else F.

3. Tautology, Contradiction, Contingency:

• ▪ Tautology: A compound proposition that is always true, regardless of the truth values of its atomic propositions. Example: $p \vee \neg p$.

• ▪ Contradiction (or Absurdity): A compound proposition that is always false. Example: $p \wedge \neg p$.

• ▪ Contingency: A compound proposition that is neither a tautology nor a contradiction (i.e., its truth value depends on the truth values of its atomic propositions).

• 4. Logical Equivalence ($\equiv$): Two propositions $P$ and $Q$ are logically equivalent if $P \leftrightarrow Q$ is a tautology. This means they always have the same truth value.

5. Laws of Logic (Logical Equivalences):

▪ Identity Laws:

• ▪ $p \wedge T \equiv p$

• ▪ $p \vee F \equiv p$

▪ Domination Laws:

• ▪ $p \vee T \equiv T$

• ▪ $p \wedge F \equiv F$

▪ Idempotent Laws:

• ▪ $p \vee p \equiv p$

• ▪ $p \wedge p \equiv p$

• ▪ Double Negation Law: $\neg(\neg p) \equiv p$

▪ Commutative Laws:

• ▪ $p \vee q \equiv q \vee p$

• ▪ $p \wedge q \equiv q \wedge p$

▪ Associative Laws:

• ▪ $(p \vee q) \vee r \equiv p \vee (q \vee r)$

• ▪ $(p \wedge q) \wedge r \equiv p \wedge (q \wedge r)$

▪ Distributive Laws:

• ▪ $p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)$

• ▪ $p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)$

▪ De Morgan's Laws:

• ▪ $\neg(p \wedge q) \equiv \neg p \vee \neg q$

• ▪ $\neg(p \vee q) \equiv \neg p \wedge \neg q$

▪ Absorption Laws:

• ▪ $p \vee (p \wedge q) \equiv p$

• ▪ $p \wedge (p \vee q) \equiv p$

▪ Inverse Laws (Complement Laws):

• ▪ $p \vee \neg p \equiv T$

• ▪ $p \wedge \neg p \equiv F$

▪ Implication Equivalences:

• ▪ $p \rightarrow q \equiv \neg p \vee q$

• ▪ $p \rightarrow q \equiv \neg q \rightarrow \neg p$ (Contrapositive)

• ▪ $\neg(p \rightarrow q) \equiv p \wedge \neg q$

▪ Biconditional Equivalences:

• ▪ $p \leftrightarrow q \equiv (p \rightarrow q) \wedge (q \rightarrow p)$

• ▪ $p \leftrightarrow q \equiv (\neg p \vee q) \wedge (\neg q \vee p)$

• ▪ $p \leftrightarrow q \equiv \neg p \leftrightarrow \neg q$

• ▪ $p \leftrightarrow q \equiv (p \wedge q) \vee (\neg p \wedge \neg q)$

6. Conjunctive Normal Form (CNF) and Disjunctive Normal Form (DNF)

• ▪ Literal: A propositional variable or its negation (e.g., $p$, $\neg q$).

• ▪ Clause: A disjunction of literals (e.g., $p \vee \neg q \vee r$).

• ▪ CNF: A conjunction of clauses (e.g., $(p \vee \neg q) \wedge (r \vee s)$).

• ▪ Minterm: A conjunction of literals where each variable appears exactly once (e.g., $p \wedge \neg q \wedge r$).

• ▪ Maxterm: A disjunction of literals where each variable appears exactly once (e.g., $p \vee \neg q \vee r$).

• ▪ DNF: A disjunction of minterms (e.g., $(p \wedge \neg q) \vee (r \wedge s)$).

• ▪ Any propositional formula can be converted into an equivalent CNF or DNF.

• Key Properties and Identities: All the laws of logic listed above are crucial identities for simplification and proving equivalence. Understanding the truth conditions for each connective is fundamental.

Common Pitfalls or Tricky Points:

• Confusing implication ($p \rightarrow q$) with causation or "if and only if". Remember $p \rightarrow q$ is false only when $p$ is true and $q$ is false.

• Incorrectly applying De Morgan's Laws, especially with more complex expressions.

• Misinterpreting the biconditional; it implies mutual implication.

• Errors in constructing truth tables, particularly for propositions with many variables.

• Assuming logical equivalence based on partial truth values.

Standard Problem-Solving Techniques or Shortcuts:

• Truth Tables: The most direct method for small propositions to check tautology, contradiction, or equivalence.

• Logical Equivalences: Use the laws of logic to simplify expressions or prove equivalence without truth tables. This is often faster for complex expressions.

• Substitution: Replace sub-expressions with their known equivalents.

• Proof by Contradiction: To show $P$ is a tautology, assume $\neg P$ is true and derive a contradiction. To show $P \equiv Q$, assume $\neg(P \leftrightarrow Q)$ is true and derive a contradiction.

• Conversion to CNF/DNF: Useful for standardization and for certain proof methods like resolution.

First Order Logic (Predicate Logic)

First Order Logic (FOL), also known as Predicate Logic, extends propositional logic by allowing us to express more complex statements about objects, their properties, and relationships. It introduces predicates, variables, and quantifiers, enabling reasoning about "all" or "some" elements within a domain.

• Definition and Core Idea: FOL allows us to break down propositions into predicates (properties or relations) and arguments (variables or constants). It introduces quantifiers ($\forall$ for "for all" and $\\$exists$ for "there exists") to make statements about collections of objects, providing a richer expressive power than propositional logic.

• Important Formulas, Theorems, and Results:

• 1. Components of FOL:

• ▪ Predicates: Represent properties or relations (e.g., $P(x)$ for "x is prime", $L(x, y)$ for "x loves y").

• ▪ Variables: Placeholders for objects (e.g., $x, y, z$).

• ▪ Constants: Specific objects (e.g., "Socrates", "5").

• ▪ Functions: Map objects to other objects (e.g., $f(x)$ for "father of x").

• ▪ Quantifiers:

• ▪ Universal Quantifier ($\forall$): "For all", "for every", "for each". $\forall xP(x)$ means $P(x)$ is true for every $x$ in the domain.

• ▪ Existential Quantifier ($\exists$): "There exists", "for some", "for at least one". $\exists xP(x)$ means there is at least one $x$ in the domain for which $P(x)$ is true.

• 2. Scope of Quantifiers, Free and Bound Variables:

• ▪ The scope of a quantifier is the part of the formula to which it applies.

• ▪ A variable is bound if it is within the scope of a quantifier using that variable.

• ▪ A variable is free if it is not bound by any quantifier.

• ▪ A formula with no free variables is called a sentence or closed formula and has a definite truth value.

• 3. Quantifier Equivalences (Negation Rules):

• ▪ $\neg \forall xP(x) \equiv \exists x \neg P(x)$ (It is not true that all x have property P if and only if there exists an x that does not have property P).

• ▪ $\neg \exists xP(x) \equiv \forall x \neg P(x)$ (It is not true that there exists an x with property P if and only if all x do not have property P).

• 4. Distributive Properties of Quantifiers:

• ▪ $\forall x(P(x) \wedge Q(x)) \equiv \forall xP(x) \wedge \forall xQ(x)$

• ▪ $\exists x(P(x) \vee Q(x)) \equiv \exists xP(x) \vee \exists xQ(x)$

• ▪ Important Non-Equivalences:

• ▪ $\forall x(P(x) \vee Q(x))$ is NOT equivalent to $\forall xP(x) \vee \forall xQ(x)$. (e.g., "Every number is even or odd" is true, but "Every number is even or every number is odd" is false).

• ▪ $\exists x(P(x) \wedge Q(x))$ is NOT equivalent to $\exists xP(x) \wedge \exists xQ(x)$. (e.g., "There is a number that is both even and prime" (2) is true, but "There is an even number and there is a prime number" is also true, but the existence of one doesn't imply the other is the same number).

• 5. Interchange of Quantifiers:

• ▪ $\forall x \forall y P(x, y) \equiv \forall y \forall x P(x, y)$

• ▪ $\exists x \exists y P(x, y) \equiv \exists y \exists x P(x, y)$

• ▪ Order Matters for Mixed Quantifiers:

• ▪ $\forall x \exists y P(x, y)$ (For every x, there exists a y such that $P(x, y)$) is NOT equivalent to $\exists y \forall x P(x, y)$ (There exists a y such that for every x, $P(x, y)$).

• ▪ Example: Let $P(x, y)$ be "x loves y". $\forall x \exists y L(x, y)$ means "Everyone loves someone". $\exists y \forall x L(x, y)$ means "There is someone whom everyone loves". These are clearly different.

• 6. Prenex Normal Form (PNF): A formula is in PNF if all quantifiers are at the beginning of the formula, followed by a quantifier-free formula (called the matrix). Any FOL formula can be converted to an equivalent PNF.

• Key Properties and Identities: The quantifier negation rules are fundamental for manipulating and simplifying FOL expressions. Understanding the implications of quantifier order is critical.

• Common Pitfalls or Tricky Points:

• Incorrect Translation: Translating natural language statements into FOL is a major source of errors. Pay close attention to words like "all", "some", "no", "only if", "unless".

• ▪ "All A are B": $\forall x(A(x) \rightarrow B(x))$ (NOT $\forall x(A(x) \wedge B(x))$)

• ▪ "Some A are B": $\exists x(A(x) \wedge B(x))$ (NOT $\exists x(A(x) \rightarrow B(x))$)

• ▪ "No A are B": $\forall x(A(x) \rightarrow \neg B(x))$ or $\neg \exists x(A(x) \wedge B(x))$

• Scope Errors: Misplacing parentheses or incorrectly determining the scope of a quantifier.

• Variable Binding: Confusing free and bound variables, or using the same variable name for different purposes in nested scopes.

• Order of Mixed Quantifiers: Assuming $\forall x \exists y P(x, y)$ is the same as $\exists y \forall x P(x, y)$.

Standard Problem-Solving Techniques or Shortcuts:

• Step-by-step Translation: Break down complex natural language sentences into smaller parts, translate each, and then combine them. Identify predicates, variables, and connectives first.

• Applying Quantifier Equivalences: Use negation rules to simplify expressions or move negations inwards.

• Domain Awareness: Always consider the domain of discourse when evaluating truth values or translating.

• Counterexamples: To show a statement is false or not equivalent, try to find a specific example in a small domain that makes it false.

Logical Reasoning (Inference)

Logical Reasoning, or Inference, is the process of deriving conclusions from a set of premises using valid rules. It focuses on the structure of arguments to determine whether a conclusion necessarily follows from the premises, regardless of the actual truth of the premises.

• Definition and Core Idea: An argument is a sequence of propositions, where the first propositions are premises and the final proposition is the conclusion. An argument is valid if, whenever all its premises are true, the conclusion must also be true. The goal is to determine if an argument's structure guarantees the truth of its conclusion given true premises.

Important Formulas, Theorems, and Results:

• 1. Argument Validity: An argument with premises $P_1, P_2, \dots, P_n$ and conclusion $C$ is valid if the proposition $(P_1 \wedge P_2 \wedge \dots \wedge P_n) \rightarrow C$ is a tautology.
• 2. Rules of Inference (for Propositional Logic): These are fundamental valid argument forms.

▪ Modus Ponens (Law of Detachment):

$\begin{array}{c} p \rightarrow q \\ \underline{p} \\ \therefore q \end{array}$

Equivalent to $((p \rightarrow q) \wedge p) \rightarrow q$ being a tautology.

▪ Modus Tollens:

$\begin{array}{c} p \rightarrow q \\ \underline{\neg q} \\ \therefore \neg p \end{array}$

Equivalent to $((p \rightarrow q) \wedge \neg q) \rightarrow \neg p$ being a tautology.

▪ Hypothetical Syllogism:

$\begin{array}{c} p \rightarrow q \\ \underline{q \rightarrow r} \\ \therefore p \rightarrow r \end{array}$

Equivalent to $((p \rightarrow q) \wedge (q \rightarrow r)) \rightarrow (p \rightarrow r)$ being a tautology.

▪ Disjunctive Syllogism:

$\begin{array}{c} p \vee q \\ \underline{\neg p} \\ \therefore q \end{array}$

Equivalent to $((p \vee q) \wedge \neg p) \rightarrow q$ being a tautology.

▪ Addition:

$\begin{array}{c} p \\ \hline \therefore p \vee q \end{array}$

▪ Simplification:

$\frac{p \wedge q}{\therefore p}$

▪ Conjunction:

$\begin{array}{c} p \\ q \\ \hline \therefore p \wedge q \end{array}$

▪ Resolution:

$\begin{array}{c} p \vee q \\ \neg q \vee r \\ \hline \therefore p \vee r \end{array}$

This is particularly useful in automated theorem proving and for converting to CNF.

▪ Constructive Dilemma:

$\begin{array}{c} (p \rightarrow q) \wedge (r \rightarrow s) \\ p \vee r \\ \hline \therefore q \vee s \end{array}$

▪ Destructive Dilemma:

$\begin{array}{c} (p \rightarrow q) \wedge (r \rightarrow s) \\ \neg q \vee \neg s \\ \hline \therefore \neg p \vee \neg r \end{array}$

3. Rules of Inference (for First Order Logic)

• ▪ Universal Instantiation (UI): If $\forall xP(x)$ is true, then $P(c)$ is true for any arbitrary individual $c$ in the domain.

$\frac{\forall xP(x)}{\therefore P(c)}$

• ▪ Universal Generalization (UG): If $P(c)$ is true for an arbitrary individual $c$ in the domain, then $\forall xP(x)$ is true.

$\frac{P(c) \text{ for an arbitrary } c}{\therefore \forall xP(x)}$

• ▪ Existential Instantiation (EI): If $\exists xP(x)$ is true, then $P(c)$ is true for some specific individual $c$ in the domain. This $c$ must be a new constant not previously used in the proof.

$\frac{\exists xP(x)}{\therefore P(c) \text{ (for some new } c\text{)}}$

• ▪ Existential Generalization (EG): If $P(c)$ is true for some specific individual $c$ in the domain, then $\exists xP(x)$ is true.

$\frac{P(c) \text{ for some specific } c}{\therefore \exists xP(x)}$

4. Proof Methods

• ▪ Direct Proof: Assume premises are true, and use inference rules and logical equivalences to derive the conclusion.

• ▪ Indirect Proof (Proof by Contradiction): To prove $C$ from premises $P_1, \dots, P_n$, assume $\neg C$ is true along with $P_1, \dots, P_n$, and derive a contradiction ($F$).

• ▪ Proof by Contraposition: To prove $p \rightarrow q$, prove its contrapositive $\neg q \rightarrow \neg p$.

• Key Properties and Identities: The validity of each inference rule is a key property. Understanding that these rules preserve truth is fundamental.

Common Pitfalls or Tricky Points:

• Fallacies: Invalid argument forms that resemble valid ones.

• ▪ Fallacy of Affirming the Consequent: $((p \rightarrow q) \wedge q) \rightarrow p$ (NOT a tautology). Example: "If it rains, the ground is wet. The ground is wet. Therefore, it rained." (Could be wet from a sprinkler).

• ▪ Fallacy of Denying the Antecedent: $((p \rightarrow q) \wedge \neg p) \rightarrow \neg q$ (NOT a tautology). Example: "If it rains, the ground is wet. It did not rain. Therefore, the ground is not wet." (Could be wet from a sprinkler).

• Confusing Validity with Soundness: A valid argument can have false premises and a false conclusion. A sound argument is a valid argument with all true premises (and thus, a true conclusion). GATE questions usually focus on validity.

• Incorrect Application of Quantifier Rules: Especially with EI and UG, ensure the constant chosen for instantiation is new (for EI) or truly arbitrary (for UG).

• Circular Reasoning: Assuming the conclusion (or something equivalent to it) as a premise.

Standard Problem-Solving Techniques or Shortcuts:

• Formal Proofs: List premises and then systematically apply inference rules and logical equivalences to derive the conclusion, citing the rule for each step.

• Truth Tables (for small arguments): Convert the argument into a single conditional statement $(P_1 \wedge \dots \wedge P_n) \rightarrow C$ and check if it's a tautology.

• Resolution Principle: Convert all premises and the negation of the conclusion into CNF clauses. Add the negation of the conclusion as a clause. If an empty clause ($\square$) can be derived through resolution, the original argument is valid.

• Look for Fallacies: If an argument resembles a common fallacy, it's likely invalid.

Quick Formula Reference

Propositional Logic Equivalences

• $\neg(\neg p) \equiv p$ (Double Negation)

• $p \vee q \equiv q \vee p$ (Commutative)

• $p \wedge q \equiv q \wedge p$ (Commutative)

• $(p \vee q) \vee r \equiv p \vee (q \vee r)$ (Associative)

• $(p \wedge q) \wedge r \equiv p \wedge (q \wedge r)$ (Associative)

• $p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)$ (Distributive)

• $p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)$ (Distributive)

• $\neg(p \wedge q) \equiv \neg p \vee \neg q$ (De Morgan's)

• $\neg(p \vee q) \equiv \neg p \wedge \neg q$ (De Morgan's)

• $p \rightarrow q \equiv \neg p \vee q$

• $p \rightarrow q \equiv \neg q \rightarrow \neg p$ (Contrapositive)

• $\neg(p \rightarrow q) \equiv p \wedge \neg q$

• $p \leftrightarrow q \equiv (p \rightarrow q) \wedge (q \rightarrow p)$

• $p \leftrightarrow q \equiv (p \wedge q) \vee (\neg p \wedge \neg q)$

• $p \vee \neg p \equiv T$ (Inverse Law)

• $p \wedge \neg p \equiv F$ (Inverse Law)

• $p \vee T \equiv T$ (Domination Law)

• $p \wedge F \equiv F$ (Domination Law)

• $p \wedge T \equiv p$ (Identity Law)

• $p \vee F \equiv p$ (Identity Law)

• $p \vee p \equiv p$ (Idempotent Law)

• $p \wedge p \equiv p$ (Idempotent Law)

• $p \vee (p \wedge q) \equiv p$ (Absorption Law)

• $p \wedge (p \vee q) \equiv p$ (Absorption Law)

Quantifier Equivalences

• $\neg \forall x P(x) \equiv \exists x \neg P(x)$

• $\neg \exists x P(x) \equiv \forall x \neg P(x)$

• $\forall x(P(x) \wedge Q(x)) \equiv \forall xP(x) \wedge \forall xQ(x)$

• $\exists x(P(x) \vee Q(x)) \equiv \exists xP(x) \vee \exists xQ(x)$

• $\forall x\forall yP(x, y) \equiv \forall y\forall xP(x, y)$

• $\exists x\exists yP(x, y) \equiv \exists y\exists xP(x, y)$

Rules of Inference (Propositional Logic)

• Modus Ponens: $(p \rightarrow q) \wedge p \implies q$

• Modus Tollens: $(p \rightarrow q) \wedge \neg q \implies \neg p$

• Hypothetical Syllogism: $(p \rightarrow q) \wedge (q \rightarrow r) \implies p \rightarrow r$

• Disjunctive Syllogism: $(p \vee q) \wedge \neg p \implies q$

• Addition: $p \implies p \vee q$

• Simplification: $p \wedge q \implies p$

• Conjunction: $p, q \implies p \wedge q$

• Resolution: $(p \vee q) \wedge (\neg q \vee r) \implies p \vee r$

Rules of Inference (First Order Logic)

• Universal Instantiation (UI): $\forall xP(x) \implies P(c)$

• Universal Generalization (UG): $P(c) \text{ for arbitrary } c \implies \forall xP(x)$

• Existential Instantiation (EI): $\exists xP(x) \implies P(c) \text{ (for new } c\text{)}$

• Existential Generalization (EG): $P(c) \text{ for specific } c \implies \exists xP(x)$

Important Tips for GATE

• 1. Master Truth Tables: They are the foundation. Be able to quickly construct and interpret truth tables for any compound proposition, especially for 2-3 variables. This helps in verifying tautologies, contradictions, and equivalences.
• 2. Memorize Key Equivalences and Inference Rules: Speed and accuracy in GATE questions heavily rely on your ability to recall and apply De Morgan's laws, implication equivalences, and the common rules of inference (Modus Ponens, Modus Tollens, etc.) without hesitation.
• 3. Practice Natural Language Translation: A significant portion of GATE questions involves translating English sentences into logical expressions (and vice-versa). Pay close attention to keywords like "all", "some", "no", "only if", "unless", and the correct use of quantifiers and connectives.
• 4. Understand Quantifier Scope and Order: Incorrectly interpreting the scope of quantifiers or swapping the order of mixed quantifiers ($\forall x\exists y$ vs. $\exists y\forall x$) is a very common mistake. Always visualize the domain and what each quantifier implies.
• 5. Distinguish Validity from Soundness: GATE questions usually ask about the validity of an argument (whether the conclusion logically follows from the premises), not its soundness (which also requires premises to be true in the real world). Focus on the logical structure.
• 6. Systematic Approach to Proofs: When asked to prove an argument's validity, don't guess. Start with the premises and systematically apply inference rules and logical equivalences, one step at a time, until you reach the conclusion. Clearly state the rule used for each step.
• 7. Identify Common Fallacies: Be aware of fallacies like "Affirming the Consequent" and "Denying the Antecedent". If an argument structure matches a known fallacy, you can quickly identify it as invalid.
• 8. Time Management: Some logical reasoning problems can be lengthy, especially those involving formal proofs or complex translations. If a question seems too time-consuming, make an educated guess or mark it for review if time permits, and move on to other questions.