Artificial Intelligence: Propositional and First-Order Logic

Propositional Logic

Logic dealing with true/false sentences.

First-order Logic

Logic extending propositional logic with quantifiers.

Theorem Proving

Demonstrating the truth of statements using logic.

Conjunctive Normal Form (CNF)

A conjunction of disjunctions in logical expressions.

Tautology

A sentence true in every model.

Unsatisfiable Sentence

A sentence false in every model.

Satisfiable Sentence

A sentence true in at least one model.

Logically Equivalent Sentences

Sentences true in the same models.

Resolution

A rule for deriving conclusions from premises.

Soundness

A property ensuring valid conclusions from true premises.

Completeness

A property ensuring all true statements can be proven.

Informed Searching

Search strategies using problem-specific knowledge.

Uninformed Searching

Search strategies without additional knowledge.

Genetic Algorithms

Optimization algorithms inspired by natural selection.

Reinforcement Learning

Learning through rewards and punishments.

Decision Trees

Tree-like model for decision making.

Image Processing

Manipulating images to extract information.

Natural Language Processing

AI enabling machines to understand human language.

Neural Networks

Computational models inspired by human brain structure.

Game-Playing Algorithms

Algorithms designed for strategic decision making.

Logical Reasoning Patterns

Common patterns used in logical deductions.

Conjunctive Normal Form (CNF)

A conjunction of disjunctions in propositional logic.

Double Implication

Equivalence represented as A ↔ B.

Single Implication

Conditional represented as A → B.

DeMorgan's Laws

Rules for negating conjunctions and disjunctions.

Negation of Conjunction

¬(A * B) equals ¬A + ¬B.

Negation of Disjunction

¬(A + B) equals ¬A * ¬B.

Distributing AND over OR

Transforming (A B) + C to (A + C) (B + C).

Example Problem

Convert A + ¬((B → C) * D) to CNF.

Knowledge Base (KB)

A collection of facts for logical reasoning.

Resolution

A method for proving logical statements using CNF.

Removing Double Implications

Convert A ↔ B to (A → B) * (B → A).

Removing Single Implications

Convert A → B to ¬A + B.

Moving Negations Inward

Apply DeMorgan's laws to simplify negations.

Final Results

The last CNF forms after all transformations.

Practice Problem

Convert (A + B) ↔ (C + D) to CNF.

Example of Converting KB

Step-by-step conversion of multiple sentences to CNF.

Step 1 - Remove Double Implications

Transform all double implications in the KB.

Step 2 - Remove Implications

Eliminate implications to simplify the sentences.

Step 3 - Move Negations Down

Push negations directly to the literals.

Step 4 - Distribute Conjunctions

Apply distribution of AND over OR.

Step 5 - Split Conjunctions

Separate conjunctions into individual clauses.

Quantitative Definition

CNF requires each sentence in KB to be in specific format.

Example Problem Solutions

Step-by-step solutions for converting to CNF.

CNF

Conjunctive Normal Form for logical sentences.

Conjunct

A component of a conjunction in logic.

Implication

A logical statement of the form A → B.

Double Implication

A logical statement of the form A ↔ B.

Negation

The logical operation that inverts truth values.

Disjunction

A logical operation represented by A + B.

Resolution

A rule of inference for deriving conclusions.

Resolution-Refutation

Proving a statement by deriving a contradiction.

Predicate

Indicates a property of an object in logic.

Constant

A symbol representing a specific object.

Variable

A symbol representing any object in logic.

Function

Maps objects to related objects in logic.

Knowledge Base (KB)

A set of sentences representing knowledge.

Conjunction

A logical operation represented by A * B.

Step 1 - Remove Double Implications

Transform A ↔ B into (A → B) * (B → A).

Step 2 - Remove Implications

Convert A → B into ¬A + B.

Step 3 - Move Negations Down

Apply De Morgan's laws to simplify negations.

Step 4 - Distribute Conjunctions

Apply distributive laws to logical expressions.

False

A contradiction derived from logical statements.

Entailment

When a statement logically follows from a KB.

Wumpus World

A scenario used to illustrate first-order logic.

First-Order Logic

Logic that deals with objects and their properties.

Constant

Specific objects in the universe, e.g., George.

Predicate

Property or relation, e.g., student().

Function

Mapping from terms to objects, e.g., owner-of().

Variable

Symbol representing any object, e.g., x.

Term

Represents objects; can be constants, variables, or functions.

Atomic Sentence

Statement with a truth value, e.g., dog(Spot).

Legal Sentence

Valid expression in first-order logic syntax.

Negation

¬S is true if S is false.

Conjunction

R ∧ S is true if both R and S are true.

Disjunction

R ∨ S is true if either R or S is true.

Implication

R → S is true if R is false or S is true.

Biconditional

R ↔ S is true if R and S share truth values.

Universal Quantifier

∀x S is true for every object x.

Existential Quantifier

∃x S is true for at least one object x.

Semantics

Meaning of sentences in first-order logic.

Conjunctive Normal Form

Standard form for logical expressions in CNF.

Resolution-Refutation

Proof technique using contradiction in logic.

Translation

Converting statements between natural language and logic.

Example of Predicate

girl(owner-of(Spot)) indicates a property.

Example of Function

father-of(George) returns George's father.

Example of Variable

x can represent any object in logic.

Example of Constant

Spot is a specific dog.

Example of Atomic Sentence

dog(Spot) asserts Spot's property as a dog.