Propositional Logic in AI (Artificial Intelligence) – A Complete Guide

When most people say ‘logic’, they mean either propositional logic or first-order predicate logic. However, the precise definition is quite broad,and literally hundreds of logics have been studied by philosophers, computer scientists and mathematicians. Any ‘formal system’ can be considered a logic if it has:

• A well-defined syntax
• Well-defined semantics
• A proof-theory

The syntax of a logic defines the syntactically acceptable objects of the language, which are properly called well-formed formulae. The semantics of a logic associate each formula with a meaning. The proof theory is concerned with manipulating formulae according to certain rules.

What is Propositional Logic?

A proposition is a statement that can be either true or false; it must be one or the other, and it cannot be both. The following are propositions:

A: “It is raining.”

B: “The grass is wet.”

These propositions are represented by capital letters, and their truth values help determine the logical relationships between them. Logical operations are used to combine and manipulate propositions to evaluate their overall truthfulness.

Also Read: Frames in AI 

The connectives we introduce are:

∧             and (& or .)

∨             or (| or +)

¬             not (∼)

⇒         implies (⊃ or →)

⇔         iff

If p and q are arbitrary propositions, then the conjunction of p and q is written,

p ∧ q

and will be true iff both p and q are true.

Common operators in propositional logic include:

• Negation (¬): Represents “not.” For example, ¬A means “it is not raining.”
• Conjunction (∧): Represents “and.” A ∧ B means “It is raining and the grass is wet.”
• Disjunction (∨): Represents “or.” A ∨ B means “It is raining or the grass is wet.”
• Implication (→): Represents “if… then.” A → B means “If it is raining, then the grass is wet.”
• Biconditional (↔): Represents “if and only if.” A ↔ B means “The grass is wet if and only if it is raining.”

Syntax and Semantics

In propositional logic, syntax refers to the structure of the formulas created using the logical operators and propositions. For example:

Atomic formulas: Simple statements like A or B.

Complex formulas: Created by combining atomic formulas, such as ¬A ∨ B or A ∧ (¬C → B).

Truth tables help in calculating the true value of complex formulas based on their individual components.

For example, in the case of A→B:

If A is true and B is false, the implication A→B is false.

If A is false, the entire implication is considered true, regardless of B’s value.

Also Read: AdaBoost Algorithm in Machine Learning

Normal Forms

To make logical operations more manageable, formulas are often converted into standard forms known as normal forms:

• Conjunctive Normal Form (CNF): A formula is in CNF if it is a conjunction (AND) of disjunctions (OR) of literals
• Disjunctive Normal Form (DNF): A formula is in DNF if it is a disjunction (OR) of conjunctions (AND) of literals.

For example:

(A∨B)∧(¬A∨C) is in CNF.

(A∧B)∨(¬C∧D) is in DNF.

Converting formulas to CNF or DNF makes them easier to work with in automated reasoning systems.

Resolution and Proofs

The resolution method is a key inference technique in propositional logic. It involves deriving new clauses by resolving pairs of clauses that contain complementary literals. Resolution is widely used in automated theorem proving, where the goal is to determine whether a formula or a set of formulas is satisfiable.

For instance, given the clauses:

• A∨B
• ¬A∨C

You can resolve them by eliminating A and ¬A, leading to B∨C.

Formal proofs in propositional logic consist of step-by-step derivations of a conclusion (formula G) from a set of assumptions (formula F). The proof system applies logical rules, like “modus ponens” (if A→B and A are true, then B is true).

Applications of Propositional Logic in AI

In AI, propositional logic plays an important role in areas such as:

Knowledge representation: Systems like knowledge bases store facts and rules in a way that can be processed logically. For example, an AI might represent “If it rains, then the ground is wet” using A→B

Automated reasoning: AI systems use propositional logic to infer new facts from existing ones. Resolution and entailment help the system make decisions based on logical deductions.

Model checking: This involves verifying whether a model satisfies certain properties by checking if all logical statements are true under a given assignment of truth values.

For instance, a model checker might assess whether the formula

A∧(B∨¬C) is valid under a specific set of truth values for A, B, and C.

Pros and Cons of Propositional Logic

• Declarative propositional logic holds that syntactic elements match facts.
• As opposed to most databases and data structures, propositional logic permits partial, disjunctive, and negated data.
• Compositional logic derives the meaning of P Q from the meanings of P and Q.
• Propositional logic does not rely on context for meaning, in contrast to natural language, where context determines meaning.
• Unlike natural language, propositional logic has very little expressive power.
• You cannot write one sentence for each square and say, “Pits cause breezes in adjacent squares.”

Challenges and Limits

While propositional logic is powerful, it has its limitations. It cannot handle the complexity of scenarios that involve quantifiers (like “for all” or “there exists”) or reasoning about objects and their properties. For such cases, first-order logic (which extends propositional logic) is required.

Difference between Propositional Logic and Predicate Logic