Discrete Mathematics

UNIT V: Graph Theory

Mrs. S. Priyanka
Assistant Professor
Department of Computer Science & Engineering(AIML)
M L R Institute of Technology
 Overview of Presentation

• Statements & Notations

• Connectives
• Well-Formed Formulas (WFF)
• Truth Tables
• Tautology
• Equivalence & Implication
• Normal Forms (CNF, DNF)
• Logical Inference
• Rules of Inference
• Direct Method & Conditional Proof (CP)
• Consistency & Proof by Contradiction
• Automatic Theorem Proving
• Summary
Outcome of this lecture: This lecture equips students to understand logical statements,
construct truth tables, identify tautologies, apply inference rules, and use proof techniques
(direct, CP, contradiction) for mathematical reasoning and theorem proving.
 Statements and Notations

Definition:
A statement (proposition) is a declarative sentence that is either True (T) or False (F).
Notations:
Propositions: P, Q, R (e.g., "It is raining")
Truth values: T (True), F (False)
Examples:
"5 is a prime number." → True
"2 + 2 = 5." → False
"x > 3" → Not a statement (depends on x)
Non-Examples (Not Statements):
"What time is it?" (Question)
"Run fast!" (Command)
 Connectives

1. Negation (¬P) – "Not P"

Example:
P: "It is raining."
¬P: "It is not raining.“

2. Conjunction (P ∧ Q) – "P and Q"

Example:
P: "It is sunny."
Q: "It is cold."
P ∧ Q: "It is sunny and cold.“

3. Disjunction (P ∨ Q) – "P or Q" (Inclusive OR)

Example:
P: "I will eat pizza."
Q: "I will eat pasta."
P ∨ Q: "I will eat pizza or pasta (or both)."
 Connectives

4. Implication (P → Q) – "If P, then Q"

Example:
P: "You study hard."
Q: "You will pass."
P → Q: "If you study hard, then you will pass.“

5. Biconditional (P ↔ Q) – "P if and only if Q"

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."
 Well Formed Formulas

Definition:
A formula is well-formed if it follows syntax rules:
A single proposition (P, Q, R) is a WFF.
If P is a WFF, then ¬P is a WFF.
If P, Q are WFFs, then (P ∧ Q), (P ∨ Q), (P → Q), (P ↔ Q) are WFFs.

Valid WFF Examples:

P∨Q
(P → Q) ∧ R
¬(P ∧ ¬Q)

Invalid WFF Examples:

P ∧ ∨ Q (No operator between ∧ and ∨)
P → (Q ∧) (Incomplete expression)
 Truth Tables

Purpose:
Shows all possible truth values of a compound statement.
Example:
Construct a truth table for P → (Q ∨ R)

Interpretation:

The implication is only False when P=T

and (Q ∨ R)=F.
 Tautology

Definition:
A statement that is always true, regardless of input.
Examples:
P ∨ ¬P (Law of Excluded Middle)
"It is raining or it is not raining.“
 Equivalence and Implication

Logical Equivalence (≡):

Two statements have identical truth tables.

Example:
P → Q ≡ ¬P ∨ Q
Implication (⇒):

P ⇒ Q means "Whenever P is true, Q

must be true.“

Example:
P: "x is divisible by 6."
Q: "x is divisible by 3."
P ⇒ Q (Because 6 = 2×3)
 Normal Forms

1. Disjunctive Normal Form (DNF):

OR of ANDs.

Example:
(P ∧ Q) ∨ (¬P ∧ R)

2. Conjunctive Normal Form (CNF):

AND of ORs.
Example:

(P ∨ Q) ∧ (¬P ∨ R)

Conversion Example:

Convert P → Q to CNF:
P → Q ≡ ¬P ∨ Q (Already in CNF)
 Normal Forms

Disjunctive Normal Form (DNF)

Definition:
A formula is in DNF if it is an OR (∨) of one or more AND (∧) clauses.
Each AND clause is called a min-term.
Used in digital circuit design and simplification.

General Form:

(Literal₁ ∧ Literal₂ ∧ ...) ∨ (Literal₃ ∧ Literal₄ ∧ ...) ∨ ...

Example 1:
Convert (P ∨ Q) ∧ (¬P ∨ R) to DNF:

Apply distributive law:

(P ∧ ¬P) ∨ (P ∧ R) ∨ (Q ∧ ¬P) ∨ (Q ∧ R)

Remove contradictions (P ∧ ¬P is always false):

(P ∧ R) ∨ (¬P ∧ Q) ∨ (Q ∧ R)
 Normal Forms

Example 2 (Truth Table to DNF):

For the formula P → Q (which is equivalent to ¬P ∨ Q):

 Normal Forms

Conjunctive Normal Form (CNF)

Definition:
A formula is in CNF if it is an AND (∧) of one or more OR (∨) clauses.

Each OR clause is called a maxterm.

Used in automated theorem proving (e.g., resolution).

General Form:
(Literal₁ ∨ Literal₂ ∨ ...) ∧ (Literal₃ ∨ Literal₄ ∨ ...) ∧ ...

Example 1:
Convert (P ∧ Q) ∨ (¬P ∧ R) to CNF:

Apply distributive law:

(P ∨ ¬P) ∧ (P ∨ R) ∧ (Q ∨ ¬P) ∧ (Q ∨ R)

Remove tautologies (P ∨ ¬P is always true):

(P ∨ R) ∧ (¬P ∨ Q) ∧ (Q ∨ R)
 Normal Forms

Example 2 (Truth Table to CNF):

For the formula P → Q (which is equivalent to ¬P ∨ Q):

 Logical Inference

Definition: Example 1 (Classical Syllogism):

Premise 1 (P → Q): "All humans are mortal."
Deriving conclusions from premises. (If X is human, then X is mortal.)
Premise 2 (P): "Socrates is human."
Example: Conclusion (Q): "Socrates is mortal.“

Premise 1: All humans are mortal. (P → Q) Rule Applied: Modus Ponens

Premise 2: Socrates is human. (P)
Conclusion: Socrates is mortal. (Q) P→Q
P
Example 2 (Modus Tollens): ∴Q
Premise 1 (P → Q): "If it rains, the ground will be
wet."
Premise 2 (¬Q): "The ground is not wet."
Conclusion (¬P): "It did not rain."
P→Q
¬Q
∴ ¬P
 Logical Inference

Example 3 (Hypothetical Syllogism): Example 4 (Disjunctive Syllogism):

Premise 1 (P → Q): "If I study, I will pass the Premise 1 (P ∨ Q): "Either the meeting is on
exam." Monday or Tuesday."
Premise 2 (Q → R): "If I pass the exam, I will get a Premise 2 (¬P): "The meeting is not on
job." Monday.“
Conclusion (P → R): "If I study, I will get a job.“
Conclusion (Q): "The meeting is on Tuesday.“
Symbolic Form:
P→Q Symbolic Form:
P∨Q
Q→R ¬P
∴P→R ∴Q
 Rules of Inference

Modus Ponens:
P → Q, P ⇒ Q
Example:
If it rains, the ground will be wet.
It is raining.
∴ The ground is wet.
Modus Tollens:
P → Q, ¬Q ⇒ ¬P
Example:
If it’s a cat, then it’s a mammal.
It’s not a mammal.
∴ It’s not a cat.
Hypothetical Syllogism:
P → Q, Q → R ⇒ P → R
Example:
If I study, I’ll pass.
If I pass, I’ll get a job.
∴ If I study, I’ll get a job.
 Direct Method and Conditional Proof

Direct Proof:

Assume P, derive Q to prove P → Q.

Conditional Proof (CP):

To prove P → Q, assume P and derive Q.

Example (CP):

Prove: If x is even, then x² is even.

Assume x is even (P).
Then, x = 2k for some integer k.
Thus, x² = (2k)² = 4k² = 2(2k²).
∴ x² is even (Q).
 Consistency and Proof by Contradiction

Consistency:

A set of statements is consistent if they can all be true at the same time.

Example:
{P → Q, P, Q} is consistent.
{P ∨ Q, ¬P, ¬Q} is inconsistent.

Proof by Contradiction:

Assume the opposite of the statement, derive a contradiction.

Example:
Statement: √2 is irrational.
Assume: √2 is rational ⇒ √2 = a/b (reduced).
Contradiction: 2b² = a² ⇒ a and b both even (not reduced).
 Consistency and Proof by Contradiction

Consistency:

A set of statements is consistent if they can all be true at the same time.

Example:
{P → Q, P, Q} is consistent.
{P ∨ Q, ¬P, ¬Q} is inconsistent.

Proof by Contradiction:

Assume the opposite of the statement, derive a contradiction.

Example:
Statement: √2 is irrational.
Assume: √2 is rational ⇒ √2 = a/b (reduced).
Contradiction: 2b² = a² ⇒ a and b both even (not reduced).
 Automatic Theorem Proving

Definition:
ATP uses algorithms to automatically derive proofs of mathematical theorems
or logical statements without human intervention.
Key Applications:
Verification of hardware/software correctness (e.g., chip design).
Mathematical research (e.g., proving conjectures).
AI reasoning (e.g., knowledge bases in Prolog).
 Automatic Theorem Proving

Step-by-Step Process: Example Workflow:

Input: Premises (axioms) + Conjecture to Goal: Prove "Socrates is mortal" from premises.
prove.
Premises:
Conversion: Encode premises into a formal
language (e.g., CNF for resolution). human(X) → mortal(X).
Inference: Apply rules (e.g., resolution,
human(socrates).
superposition).
Output: Proof or counterexample. ATP Action: Apply Modus Ponens to derive
mortal(socrates).
 Automatic Theorem Proving

1. Resolution Refutation

What it does: Assume the negation of the conjecture and derive a contradiction.

Example:

Premises:
¬P ∨ Q (P → Q).

P
Conjecture: Q.
Step 1: Negate conjecture: ¬Q.

Step 2: Resolve ¬P ∨ Q with ¬Q to get ¬P.

Step 3: Resolve ¬P with P → contradiction (empty clause).

Conclusion: Original conjecture Q is true.

 Automatic Theorem Proving

2. DPLL Algorithm

What it does: Checks satisfiability of CNF formulas (used in SAT solvers).

Example:

Formula: (P ∨ Q) ∧ (¬P ∨ R) ∧ (¬Q ∨ R).

DPLL Steps:

Assign P = true: Simplify to (R) ∧ (¬Q ∨ R).

Assign Q = false: Simplify to (R).

Assign R = true → Formula is satisfiable.

 Automatic Theorem Proving

Real-World ATP Examples

Example 1: Prolog (Logic Programming)

How ATP Works Here:

Uses backward chaining to unify the query with rules/facts.
Example 2: Robbins Algebra Proof
Conjecture: All Robbins algebras are Boolean algebras.
ATP Role: EQP prover (1996) found a proof after decades of human effort.
Example 3: Hardware Verification
Goal: Verify a CPU design correctly implements arithmetic.
ATP Tool: ACL2 or Coq proves correctness by induction.
 Summary

• Mathematical logic studies formal reasoning using propositions (T/F statements) and logical
connectives (AND, OR, NOT).
• Well-formed formulas (WFFs) follow strict syntax rules for valid logical expressions.
• Truth tables systematically evaluate compound statements for all possible truth values.
• Tautologies are always-true statements, while equivalence shows identical truth tables.
• Normal forms (CNF/DNF) standardize logical expressions for analysis and computation.
• Logical inference derives conclusions using rules like Modus Ponens and Hypothetical
Syllogism.
• Proof methods include Direct, Conditional Proof (CP), and Contradiction approaches.
• Automatic Theorem Proving (ATP) uses algorithms to verify arguments without human
intervention.