Logic Programming and Knowledge

Representation
Understanding Predicate Calculus, Logic Syntax & Inference

Presented by: Kulsum Bano (1323321), Pushkar Jain (1323302)

Course: Artificial Intelligence / Knowledge Representation

Introduction to Logic Programming

What is Logic Programming? Key Applications

• Artificial Intelligence: Automated
Logic programming is a paradigm that uses reasoning and planning systems
formal logic to represent knowledge and
perform reasoning. Rather than specifying • Expert Systems: Medical diagnosis and
how to compute something, we define what decision support
is true and let the system derive conclusions • Natural Language Processing: Semantic
automatically. analysis and understanding

At its core, logic programming combines • Database Systems: Query optimization

declarative knowledge representation with and constraint checking
inference mechanisms to solve problems by
logical deduction.
Predicate Calculus (First-Order Logic)
Predicate calculus, also known as First-Order Logic (FOL), extends propositional logic by introducing variables, predicates, and quantifiers. This allows us to express much more complex relationships and reason about properties of objects.

Quantifiers

Universal ∀ and existential ∃

Variables & Constants

Terms that denote objects

Predicates

Relations and functions over terms

Predicates Variables Quantifiers

Syntax of Propositional Logic
Propositional logic forms the foundation of logical reasoning. It deals with propositions—statements that are definitively true or false—and combines them using
logical connectives to build more complex expressions.

Basic Components Logical Connectives

Propositions: Atomic statements with truth values • ¬ (NOT): Negation, reverses truth value
• ∧ (AND): Conjunction, true when both are true

Example: P = "It is raining" • ∨ (OR): Disjunction, true when at least one is true
• → (IMPLIES): Implication, "if P then Q"
Example: Q = "The ground is wet"
• ↔ (IFF): Bi-conditional, "if and only if"

Simple Expression Implication Complex Expression

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

"It is raining AND the ground is wet" "If it rains, then the ground gets wet" "If it rains or snows, then traffic slows down"
Semantics of Propositional Logic
While syntax defines the structure of logical expressions, semantics determines their meaning—specifically, the truth values of propositions under different
interpretations. Truth tables provide a systematic way to evaluate all possible combinations.

Understanding Truth Tables AND (Conjunction) Example

Truth tables enumerate all possible truth value assignments for propositions
P Q P∧Q
and show the resulting truth value of compound expressions. They're essential
for verifying logical equivalences and evaluating arguments. True True True

True False False

Each row represents a possible state of the world, and the table exhaustively
covers all scenarios.
False True False

False False False

Clausal Form Conversion
Clausal form is a standardized representation of logical formulas essential for automated reasoning. Converting formulas to Conjunctive Normal Form (CNF) enables efficient
application of inference algorithms like resolution.

01 02

Eliminate Implications Move Negation Inwards

Replace P → Q with ¬P ∨ Q Apply De Morgan's laws: ¬(P ∧ Q) becomes ¬P ∨ ¬Q

03 04

Standardize Variables Move Quantifiers to Front

Rename variables so each quantifier has unique variables Create prenex normal form with all quantifiers leading

05 06

Skolemization Convert to CNF

Remove existential quantifiers (∃) by introducing Skolem functions Express as conjunction of disjunctions (clauses)

Original Formula After Clausal Conversion

∀x (Human(x) → Mortal(x)) ∀x (¬Human(x) ∨ Mortal(x))

Inference Rules
Inference rules are the mechanisms by which we derive new knowledge from existing facts. They form the foundation of logical reasoning, allowing us to conclude
new truths without enumerating all possibilities.

Modus Ponens Modus Tollens

Rule: If we know P → Q and P is true, then Q must be true Rule: If we know P → Q and ¬Q is true, then ¬P must be true

Example: If "All humans are mortal" and "Socrates is human," then Example: If "If it rains, the ground is wet" and "The ground is not wet,"
"Socrates is mortal" then "It did not rain"

And Introduction/Elimination Or Introduction/Elimination

Introduction: From P and Q, derive P ∧ Q Introduction: From P, derive P ∨ Q

Elimination: From P ∧ Q, derive P (or Q) Elimination: Complex rule requiring case analysis
Resolution & Unification
Resolution and unification are the powerhouse algorithms behind automated theorem proving. Together, they enable computers to perform logical reasoning and prove theorems automatically.

Resolvent

Q ∨ R is produced

Resolve

Combine remaining literals

Complementary Literals

¬P and P cancel

Clause Pair

¬P ∨ Q and P ∨ R

Resolution Principle Unification Algorithm

Summary & Applications
Key Takeaways Real-World Applications

Logic Programming

Combines knowledge representation with rule-based inference

Predicate Calculus

Foundation of First-Order Logic with predicates, variables, and quantifiers

Syntax & Semantics

Structure defines form, meaning determines truth

Reasoning Tools

Clausal form, inference rules, resolution, and unification enable automated deduction

Expert Systems

Medical diagnosis and decision support systems

Chatbots & NLP

Natural language understanding and dialogue systems

Knowledge Graphs

Semantic web and intelligent information retrieval

Automated Reasoning

Prolog engines and AI planning systems

Thank You!
Questions?