Propositional and predicate logic notes — Unit 2

Logic is the study of formal reasoning based on statements. The fundamental building block is a Proposition.

⇒1.1 What is a Proposition?

A proposition (or statement) is a declarative sentence that is either True (T) or False (F), but not both.

• Valid Propositions: "Delhi is the capital of India" (True). "$2 + 2 = 5$" (False).
• Invalid Propositions: "What time is it?" (Question). "Close the door!" (Command). "$x + 5 = 10$" (Variables make it a predicate, not a proposition, until $x$ is defined).

⇒1.2 Compound Propositions

Simple propositions can be combined using logical connectives to form compound propositions.

Logical connectives dictate how the truth value of a compound proposition is derived from its constituent propositions.

⇒2.1 Basic Connectives

• Negation ($\neg P$ or $\sim P$): "NOT". Reverses the truth value. If $P$ is True, $\neg P$ is False.
• Conjunction ($P \land Q$): "AND". True only if both $P$ and $Q$ are True.
• Disjunction ($P \lor Q$): "OR". True if at least one of $P$ or $Q$ is True.
• Exclusive OR ($P \oplus Q$): "XOR". True if exactly one of $P$ or $Q$ is True, but not both.

⇒2.2 Conditional Connectives

• Implication ($P \to Q$): "If P, then Q". $P$ is the hypothesis/antecedent, $Q$ is the conclusion/consequent. This is False only when $P$ is True and $Q$ is False. In all other cases, it is True.
• Biconditional ($P \leftrightarrow Q$): "P if and only if Q" (iff). True when $P$ and $Q$ have the exact same truth value.

Given a standard conditional statement $P \to Q$, there are three related conditional statements.

• Converse: $Q \to P$
• Inverse: $\neg P \to \neg Q$
• Contrapositive: $\neg Q \to \neg P$

⇒3.1 Logical Equivalence of Contrapositive

A very important rule in mathematical proofs is that a statement is logically equivalent to its contrapositive.

$(P \to Q) \equiv (\neg Q \to \neg P)$

However, a statement is not logically equivalent to its converse or inverse. (Though the converse and inverse are equivalent to each other).

We classify compound propositions based on their final truth tables.

• Tautology: A compound proposition that is always True, regardless of the truth values of its constituent variables. Example: $P \lor \neg P$.
• Contradiction (Fallacy): A compound proposition that is always False. Example: $P \land \neg P$.
• Contingency: A proposition that is neither a tautology nor a contradiction (it can be True or False depending on the variables).

⇒4.1 Satisfiability

A proposition is satisfiable if there is at least one assignment of truth values to its variables that makes it True. (Therefore, tautologies and contingencies are satisfiable, but contradictions are not).

Two propositions $A$ and $B$ are logically equivalent (denoted $A \equiv B$) if they have identical truth tables.

Alternatively, $A \equiv B$ if and only if the biconditional $A \leftrightarrow B$ is a tautology.

⇒5.1 Key Logical Equivalences (Laws of Logic)

These are identical to the laws of Set Theory:

• De Morgan's Laws: $\neg(P \land Q) \equiv \neg P \lor \neg Q$ and $\neg(P \lor Q) \equiv \neg P \land \neg Q$
• Implication Equivalence: $P \to Q \equiv \neg P \lor Q$ (This is heavily used to convert implications into standard AND/OR logic).
• Biconditional Equivalence: $P \leftrightarrow Q \equiv (P \to Q) \land (Q \to P)$
• Distributive Laws: $P \lor (Q \land R) \equiv (P \lor Q) \land (P \lor R)$

A proposition can be rewritten into standardized formats known as Normal Forms using logical equivalences. This is crucial for automated theorem proving.

⇒6.1 Disjunctive Normal Form (DNF)

A formula is in DNF if it is a sum of products (OR of ANDs). It consists of disjunctions of conjunctions.

Example: $(P \land Q) \lor (\neg P \land R) \lor (Q \land \neg R)$

A Principal DNF (PDNF) (or Sum of Minterms) is a DNF where every conjunction contains all variables exactly once (either negated or unnegated).

⇒6.2 Conjunctive Normal Form (CNF)

A formula is in CNF if it is a product of sums (AND of ORs). It consists of conjunctions of disjunctions.

Example: $(P \lor Q) \land (\neg P \lor R) \land (Q \lor \neg R)$

A Principal CNF (PCNF) (or Product of Maxterms) is a CNF where every disjunction contains all variables exactly once.

Rules of inference are templates for creating valid mathematical arguments. A valid argument ensures that if the premises are True, the conclusion must absolutely be True.

⇒7.1 Modus Ponens (Law of Detachment)

Premise 1: $P \to Q$
Premise 2: $P$
Conclusion: $\therefore Q$

⇒7.2 Modus Tollens

Premise 1: $P \to Q$
Premise 2: $\neg Q$
Conclusion: $\therefore \neg P$

⇒7.3 Hypothetical Syllogism

Premise 1: $P \to Q$
Premise 2: $Q \to R$
Conclusion: $\therefore P \to R$

⇒7.4 Disjunctive Syllogism

Premise 1: $P \lor Q$
Premise 2: $\neg P$
Conclusion: $\therefore Q$

Propositional logic cannot handle statements with variables, such as "$x > 3$". This is where Predicate Logic (or First-Order Logic) comes in.

⇒8.1 Predicates

A predicate is a statement containing one or more variables, which becomes a proposition when values are substituted for the variables.

Let $P(x)$ denote "$x > 3$".
$P(4)$ is True (proposition).
$P(2)$ is False (proposition).

⇒8.2 Universe of Discourse (Domain)

The set of all possible values that can be substituted for the variables in a predicate. If $P(x)$ is "$x$ is a student", the domain might be "all people in the university".

Quantifiers are used to express the extent to which a predicate is true over a domain.

⇒9.1 Universal Quantifier ($\forall$)

Read as "For all" or "For every".

$\forall x P(x)$ means $P(x)$ is true for every $x$ in the domain.

⇒9.2 Existential Quantifier ($\exists$)

Read as "There exists" or "For some".

$\exists x P(x)$ means there is at least one $x$ in the domain for which $P(x)$ is true.

⇒9.3 Bound vs Free Variables

A variable is bound if a quantifier is attached to it. A variable is free if it is not bound.
In $\forall x P(x, y)$, $x$ is bound, but $y$ is free.

When we negate a quantified statement, the quantifier flips and the negation moves inside to the predicate.

⇒10.1 Negating Universal

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

"It is not true that everyone is happy" $\equiv$ "There exists someone who is not happy."

⇒10.2 Negating Existential

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

"It is not true that there exists a flying pig" $\equiv$ "All pigs do not fly."

Complex statements require multiple quantifiers. The order in which they appear drastically changes the meaning of the statement.

⇒11.1 Same Quantifiers

The order does not matter if the quantifiers are the same.

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

⇒11.2 Mixed Quantifiers (Order Matters!)

$\forall x \exists y P(x,y)$ is NOT equivalent to $\exists y \forall x P(x,y)$.

• Let $L(x, y)$ be "x loves y".
• $\forall x \exists y L(x, y)$: "For every person $x$, there is someone $y$ that they love." (Everyone loves somebody).
• $\exists y \forall x L(x, y)$: "There is someone $y$ who is loved by every person $x$." (There is one specific person whom everyone loves).

To apply rules of inference (like Modus Ponens) to quantified statements, we must first remove the quantifiers using Instantiation, apply the rules on specific elements, and then re-apply quantifiers using Generalization.

⇒12.1 Four Rules of Instantiation/Generalization

• Universal Instantiation: If $\forall x P(x)$ is true, then $P(c)$ is true for any arbitrary element $c$ in the domain.
• Universal Generalization: If $P(c)$ is proven true for an arbitrary element $c$, then we can conclude $\forall x P(x)$.
• Existential Instantiation: If $\exists x P(x)$ is true, there is some specific element $c$ for which $P(c)$ is true. (You cannot assume $c$ is arbitrary).
• Existential Generalization: If $P(c)$ is true for a specific element $c$, then we can conclude $\exists x P(x)$.

A powerful proof technique used to prove that a proposition $P(n)$ is true for all positive integers $n$.

⇒13.1 Principle of Mathematical Induction

• Step 1 (Base Case): Prove that $P(1)$ is true.
• Step 2 (Inductive Hypothesis): Assume that $P(k)$ is true for some arbitrary positive integer $k$.
• Step 3 (Inductive Step): Using the assumption from Step 2, prove that $P(k+1)$ is true.

If all three steps are successful, then by the principle of mathematical induction, $P(n)$ is true for all $n \ge 1$.

⇒13.2 Strong Induction

A variant where the inductive hypothesis assumes that $P(1), P(2), \dots, P(k)$ are all true, and uses this stronger assumption to prove $P(k+1)$.

Logic is the grammar of computer science.

⇒14.1 University Exam Checklist

• Construct a truth table to prove that two compound propositions are logically equivalent.
• Convert a given proposition into Principal Disjunctive Normal Form (PDNF) and Principal Conjunctive Normal Form (PCNF).
• Translate English sentences into Predicate Logic using quantifiers.
• Write the negation of a nested quantified statement (e.g., $\neg(\forall x \exists y P(x,y))$).
• Test the validity of an argument using rules of inference (Modus Ponens, Modus Tollens).
• Prove a formula (like the sum of the first $n$ numbers) using Mathematical Induction.

⇒14.2 Application Focus

• How does Propositional Logic directly map to Digital Logic gates (AND/OR/NOT)?
• How is Predicate Logic used in Artificial Intelligence (specifically in rule-based expert systems and Prolog)?
• How does the concept of Satisfiability relate to the famous boolean SAT problem in algorithm complexity?