FOUNDATIONS OF ARTIFICIAL

INTELLIGENCE
BSc Data Science & AI - Semester 2

COMPREHENSIVE REVISION NOTE 3

Propositional Logic & Inference

TOPICS COVERED IN THIS REVISION NOTE

1. Introduction to Logic in AI
2. Propositional Logic - Syntax and Semantics
3. Atomic and Complex Sentences
4. Logical Connectives (NOT, AND, OR, IMPLIES, BICONDITIONAL)
5. Truth Tables and Evaluation
6. Operator Precedence in Logic
7. Logical Equivalences and Laws
8. Inference and Entailment
9. Sound and Complete Inference
10. Inference Rules (Modus Ponens, Resolution, etc.)
11. Introduction to First-Order Logic
SECTION 1: INTRODUCTION TO LOGIC IN AI

1.1 Why Logic Matters in AI

Logic provides a formal framework for representing knowledge and reasoning about it. In AI, logic serves as the
foundation for knowledge-based agents that need to store facts about the world and derive new conclusions from those
facts. Unlike search algorithms that find paths through state spaces, logic allows agents to represent complex
relationships, make inferences, and reason about abstract concepts.

The key advantage of logic-based approaches is that they are declarative - we specify WHAT we know, and the
inference engine figures out HOW to derive conclusions. This separation of knowledge from reasoning makes systems
more modular, easier to understand, and easier to modify.

Logic in AI operates in a deterministic, rule-based framework. This means we are not yet dealing with uncertainty or
probability - every statement is either TRUE or FALSE, with no middle ground. Later, we will see how probabilistic
reasoning extends these ideas to handle uncertainty.

■ KEY PURPOSES OF LOGIC IN AI

1. Knowledge Representation: Logic provides precise languages for expressing facts about the world,
relationships between objects, and rules that govern behavior.

2. Reasoning: Logic provides inference rules that allow us to derive new knowledge from existing
knowledge in a sound (correct) and sometimes complete (all conclusions derivable) manner.

3. Communication: Logic provides an unambiguous way to communicate knowledge between humans

and machines, or between different AI systems.

4. Verification: Logic allows us to prove that certain conclusions follow from certain premises, which is
essential for safety-critical AI applications.

1.2 Syntax vs. Semantics

Aspect Syntax Semantics

Definition Rules for forming valid sentences Rules for determining meaning/truth

Focus Structure and form Meaning and interpretation

Question Is this sentence well-formed? Is this sentence true or false?

Example P ∧ Q is valid; P ∧ ∧ Q is not If P=True, Q=False, then P∧Q = False

SECTION 2: PROPOSITIONAL LOGIC - SYNTAX

2.1 Atomic Sentences (Propositions)

Atomic sentences are the simplest sentences in propositional logic. They consist of single propositional symbols
(usually uppercase letters like P, Q, R, or meaningful names like "Raining", "Hot") that represent simple statements
about the world. Each atomic sentence is indivisible - it cannot be broken down further.

Each proposition can take one of two truth values: TRUE (T, 1) or FALSE (F, 0). There is no middle ground - this is the
Law of Excluded Middle. Additionally, a proposition cannot be both true and false at the same time - this is the Law of
Non-Contradiction.

EXAMPLES OF ATOMIC SENTENCES

Using symbols: P, Q, R, S, A, B, C
Using meaningful names:
• "Raining" - It is raining
• "Hot" - The temperature is hot
• "EatingRice" - I am eating rice
• "TrafficJam" - There is a traffic jam

Special Constants:
• True (■): A proposition that is always true in every model
• False (⊥): A proposition that is always false in every model

2.2 Literals
A literal is either an atomic sentence (positive literal) or its negation (negative literal). Literals are important building
blocks in many logical algorithms, especially in resolution-based theorem proving.

• Positive Literal: P, Q, Raining (the atom itself)

• Negative Literal: ¬P, ¬Q, ¬Raining (negation of the atom)

2.3 Complex Sentences using Logical Connectives

Complex sentences are formed by combining atomic sentences using logical connectives. These connectives allow
us to express relationships between propositions. There are five primary connectives in propositional logic:

Connecti
Symbol Name Read As Example
ve

1 ¬ Negation (NOT) not P ¬Raining = Not raining

2 ∧ Conjunction (AND) P and Q Hot ∧ Sunny

3 ∨ Disjunction (OR) P or Q Rain ∨ Snow

4 → Implication (IF-THEN) if P then Q Rain → Wet

5 ↔ Biconditional (IFF) P if and only if Q Pass ↔ Score≥50

SECTION 3: TRUTH TABLES AND SEMANTICS

3.1 Truth Tables for Logical Connectives

Truth tables define the semantics (meaning) of logical connectives by specifying the truth value of a complex sentence
for every possible combination of truth values of its components. Let's examine each connective:

3.2 Negation (NOT) - ¬P

Negation simply flips the truth value. If P is true, ¬P is false, and vice versa.

P ¬P

T F

F T

3.3 Conjunction (AND) - P ∧ Q

Conjunction is true ONLY when BOTH operands are true. Think of it as a strict requirement - both conditions must be
satisfied.

P Q P∧Q

T T T

T F F

F T F

F F F

3.4 Disjunction (OR) - P ∨ Q

Disjunction is true when AT LEAST ONE operand is true (inclusive OR). It's only false when both are false.

P Q P∨Q

T T T

T F T

F T T

F F F

3.5 Implication (IF-THEN) - P → Q

Implication is the most important and often misunderstood connective. P → Q means "if P then Q". It's FALSE only
when P is true but Q is false (a broken promise). If P is false, the implication is vacuously true.

P Q P→Q Explanation

T T T Promise kept

T F F Promise broken!

F T T No promise made, Q still true

F F T No promise made (vacuously true)

 ■■ IMPORTANT: UNDERSTANDING IMPLICATION

The implication P → Q can be read in several equivalent ways:

• If P then Q
• P implies Q
• P only if Q
• Q if P
• P is sufficient for Q
• Q is necessary for P

Key insight: An implication P → Q is equivalent to ¬P ∨ Q (not P OR Q).

Why? The only way P → Q is false is when P is true and Q is false. In all other cases, it's true.

3.6 Biconditional (IFF) - P ↔ Q

Biconditional is true when both sides have the SAME truth value. It means "P if and only if Q" - both implications must
hold: P → Q AND Q → P.

P Q P↔Q Explanation

T T T Both true - same value

T F F Different values

F T F Different values

F F T Both false - same value

SECTION 4: OPERATOR PRECEDENCE
Just like in arithmetic where multiplication is performed before addition, logical operators have a precedence order that
determines how expressions are evaluated when parentheses are not used.

Priority Operator Name Evaluation Order

1 (Highest) ¬ Negation First - applied to its operand

2 ∧ Conjunction (AND) Second

3 ∨ Disjunction (OR) Third

4 → Implication Fourth

5 (Lowest) ↔ Biconditional Last

■ WORKED EXAMPLE: EVALUATING WITH PRECEDENCE

Expression: ¬P ∧ Q ∨ R → S

Step-by-step evaluation (following precedence):

1. First, apply ¬ to P: (¬P) ∧ Q ∨ R → S
2. Next, evaluate ∧: ((¬P) ∧ Q) ∨ R → S
3. Then, evaluate ∨: (((¬P) ∧ Q) ∨ R) → S
4. Finally, evaluate →: ((((¬P) ∧ Q) ∨ R) → S)

Tip: When in doubt, use parentheses to make your intended meaning clear!
SECTION 5: IMPORTANT LOGICAL EQUIVALENCES
Two sentences are logically equivalent (≡) if they have the same truth value in every possible model. These
equivalences are essential for simplifying logical expressions and proving theorems.

Name Equivalence Description

Double Negation ¬(¬P) ≡ P Negating twice returns original

Commutative (AND) P∧Q≡Q∧P Order doesn't matter for AND

Commutative (OR) P∨Q≡Q∨P Order doesn't matter for OR

Associative (AND) (P ∧ Q) ∧ R ≡ P ∧ (Q ∧ R) Grouping doesn't matter for AND

Associative (OR) (P ∨ Q) ∨ R ≡ P ∨ (Q ∨ R) Grouping doesn't matter for OR

Distributive P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R) AND distributes over OR

Distributive P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R) OR distributes over AND

De Morgan's Law ¬(P ∧ Q) ≡ ¬P ∨ ¬Q NOT of AND = OR of NOTs

De Morgan's Law ¬(P ∨ Q) ≡ ¬P ∧ ¬Q NOT of OR = AND of NOTs

Implication P → Q ≡ ¬P ∨ Q IF-THEN as OR

Contrapositive P → Q ≡ ¬Q → ¬P Equivalent form of implication

Biconditional P ↔ Q ≡ (P → Q) ∧ (Q → P) IFF as two implications

■ DE MORGAN'S LAWS - MUST REMEMBER!

De Morgan's Laws are among the most important equivalences in logic:

¬(P ∧ Q) ≡ ¬P ∨ ¬Q
"NOT (P AND Q)" is the same as "(NOT P) OR (NOT Q)"
Example: "It's not the case that it's hot AND sunny" = "It's not hot OR it's not sunny"

¬(P ∨ Q) ≡ ¬P ∧ ¬Q
"NOT (P OR Q)" is the same as "(NOT P) AND (NOT Q)"
Example: "It's not the case that it's raining OR snowing" = "It's not raining AND it's not snowing"
SECTION 6: INFERENCE AND ENTAILMENT

6.1 What is Entailment?

Entailment (written as ■) is the fundamental concept connecting sentences in logic. We say that a knowledge base KB
entails a sentence α (written KB ■ α) if α is true in every model where KB is true. In other words, if KB is true, then α
MUST be true - there's no possible world where KB is true but α is false.

Example: If KB = {P, P → Q}, then KB ■ Q. Why? In any model where both P is true and P → Q is true, Q must also be
true. There's no way to make P true and P → Q true while having Q be false.

6.2 Inference vs. Entailment

Concept Symbol Meaning Nature

Entailment KB ■ α α is true in all models where KB is true Semantic (about truth)

Syntactic (about
Inference KB ■ α α can be derived from KB using rules
derivation)

6.3 Sound and Complete Inference

■ CRITICAL CONCEPTS: SOUNDNESS AND COMPLETENESS

SOUNDNESS: An inference procedure is sound if it only derives sentences that are actually entailed by
the KB. In other words, it never makes things up - everything it concludes is actually true.
Formally: If KB ■ α then KB ■ α (if we can derive it, it's true)

COMPLETENESS: An inference procedure is complete if it can derive every sentence that is entailed
by the KB. It doesn't miss anything - if something is true, it can find it.
Formally: If KB ■ α then KB ■ α (if it's true, we can derive it)

IDEAL: We want inference procedures that are BOTH sound AND complete:
KB ■ α if and only if KB ■ α

6.4 Important Inference Rules

Rule Name Form Description Example

Modus Ponens P, P→Q ■ Q If P and P implies Q, then Q Rain, Rain→Wet ■ Wet

If not Q and P implies Q, ¬Wet, Rain→Wet ■

Modus Tollens ¬Q, P→Q ■ ¬P
then not P ¬Rain

From conjunction, derive

And-Elimination P ∧ Q ■ P (or Q) Hot∧Sunny ■ Hot
either part

From two facts, form

And-Introduction P, Q ■ P ∧ Q Hot, Sunny ■ Hot∧Sunny
conjunction

From one fact, form

Or-Introduction P■P∨Q Rain ■ Rain∨Snow
disjunction
 Resolve complementary
Resolution P∨Q, ¬P∨R ■ Q∨R A∨B, ¬A∨C ■ B∨C
literals

■ MODUS PONENS - THE MOST IMPORTANT RULE

Modus Ponens (Latin: "method of affirming") is the fundamental rule of logical inference:

Structure:
Premise 1: P (the antecedent is true)
Premise 2: P → Q (the implication holds)
Conclusion: Q (therefore the consequent is true)

Real-world example:
Premise 1: It is raining (P)
Premise 2: If it is raining, then the ground is wet (P → Q)
Conclusion: Therefore, the ground is wet (Q)

Why it works: Look at the truth table for implication. The only row where P is true AND P→Q is true is
the row where Q is also true.
SECTION 7: INTRODUCTION TO FIRST-ORDER LOGIC

7.1 Limitations of Propositional Logic

While propositional logic is simple and useful, it has significant limitations:

• Cannot represent objects and their properties individually

• Cannot express relationships between objects
• Cannot make general statements (e.g., 'All birds can fly')
• Each fact requires a separate proposition

7.2 First-Order Logic (FOL) Extensions

First-Order Logic (also called Predicate Logic) extends propositional logic with:

Element Description Examples

Constants Specific objects in the domain John, Mary, 5, Delhi

Variables Placeholders for any object x, y, z

Predicates Properties or relations Bird(x), Loves(x,y), GreaterThan(x,y)

Functions Mappings from objects to objects Father(x), Age(x), Plus(x,y)

Quantifiers Express generality ∀ (for all), ∃ (there exists)

7.3 Quantifiers

UNIVERSAL AND EXISTENTIAL QUANTIFIERS

Universal Quantifier (∀): "For all" - makes statements about every object
∀x Bird(x) → CanFly(x) means "For all x, if x is a bird then x can fly"
Read as: "All birds can fly"

Existential Quantifier (∃): "There exists" - asserts existence of at least one object
∃x Bird(x) ∧ ¬CanFly(x) means "There exists an x such that x is a bird and x cannot fly"
Read as: "Some bird cannot fly" (like a penguin!)

Important Relationship:
¬(∀x P(x)) ≡ ∃x ¬P(x) (Not all P = Some not P)
¬(∃x P(x)) ≡ ∀x ¬P(x) (No P exists = All are not P)
SECTION 8: SAMPLE QUIZ QUESTIONS

8.1 Multiple Choice Questions

1. What is the truth value of P → Q when P is FALSE?
a) Always FALSE
b) Always TRUE
c) Depends on Q
d) Undefined
Answer: b) Always TRUE (vacuously true when antecedent is false)

2. Which logical equivalence is De Morgan's Law?

a) P ∧ Q ≡ Q ∧ P
b) ¬(P ∧ Q) ≡ ¬P ∨ ¬Q
c) P → Q ≡ ¬P ∨ Q
d) ¬(¬P) ≡ P
Answer: b) ¬(P ∧ Q) ≡ ¬P ∨ ¬Q

3. In Modus Ponens, given P and P → Q, we can conclude:

a) P
b) ¬P
c) Q
d) ¬Q
Answer: c) Q

4. Which operator has the HIGHEST precedence?

a) ∧ (AND)
b) ∨ (OR)
c) → (IMPLIES)
d) ¬ (NOT)
Answer: d) ¬ (NOT)

5. P ↔ Q is TRUE when:
a) P and Q are both TRUE only
b) P and Q have the same truth value
c) At least one is TRUE
d) P implies Q
Answer: b) P and Q have the same truth value

6. An inference procedure that only derives true conclusions is called:

a) Complete
b) Sound
c) Valid
d) Consistent
Answer: b) Sound

7. The symbol ∀ in first-order logic means:

a) There exists
b) For some
c) For all
d) Implies
Answer: c) For all (universal quantifier)

8. P → Q is logically equivalent to:

a) Q → P
 b) ¬P → ¬Q
c) ¬Q → ¬P
d) P ∧ Q
Answer: c) ¬Q → ¬P (contrapositive)

8.2 True/False Questions

1. P ∧ Q is true only when both P and Q are true. (TRUE)

2. The implication P → Q is false when P is false. (FALSE (vacuously true when P is false))

3. Modus Tollens allows us to conclude ¬P from ¬Q and P → Q. (TRUE)

4. De Morgan's Law: ¬(P ∨ Q) ≡ ¬P ∨ ¬Q (FALSE (should be ¬P ∧ ¬Q))

5. A sound inference procedure may derive false conclusions. (FALSE (sound means only true conclusions))

6. In propositional logic, we can express 'All birds can fly'. (FALSE (need first-order logic))

7. ∃x means 'for all x'. (FALSE (∃ means 'there exists'))

8. P ↔ Q is equivalent to (P → Q) ∧ (Q → P). (TRUE)

SECTION 9: KEY FORMULAS AND QUICK REFERENCE

ESSENTIAL FORMULAS TO REMEMBER

TRUTH TABLE SUMMARY:

• ¬T = F, ¬F = T
• T ∧ T = T, all else F
• F ∨ F = F, all else T
• T → F = F, all else T
• P ↔ Q = T when P and Q have same value

KEY EQUIVALENCES:
• P → Q ≡ ¬P ∨ Q (Implication as OR)
• P → Q ≡ ¬Q → ¬P (Contrapositive)
• ¬(P ∧ Q) ≡ ¬P ∨ ¬Q (De Morgan)
• ¬(P ∨ Q) ≡ ¬P ∧ ¬Q (De Morgan)
• P ↔ Q ≡ (P → Q) ∧ (Q → P)

INFERENCE RULES:
• Modus Ponens: P, P → Q ■ Q
• Modus Tollens: ¬Q, P → Q ■ ¬P
• Resolution: P ∨ Q, ¬P ∨ R ■ Q ∨ R

OPERATOR PRECEDENCE (high to low):

¬→∧→∨→→→↔

QUANTIFIER NEGATION:
• ¬(∀x P(x)) ≡ ∃x ¬P(x)
• ¬(∃x P(x)) ≡ ∀x ¬P(x)

— End of Revision Note 3 —

Best of luck with your exam preparation!