Propositional Logic & First-Order Logic in AI

Logic gives AI a precise way to represent facts and reason about them. Propositional logic works with whole statements; first-order logic breaks statements apart so a system can reason about objects, their properties, and groups of them.

What Is Propositional Logic? 

Propositional logic deals with propositions — statements that are either true or false, like "It is raining" or "2 + 2 = 4." Simple propositions can be combined with connectives to build more complex ones, like "It is raining AND it is cold."

Logical Connectives

Connectives are the symbols used to combine or modify propositions.

• NOT (¬P) — flips true to false and false to true.
• AND (P ∧ Q) — true only if both P and Q are true.
• OR (P ∨ Q) — true if at least one of P or Q is true.
• IMPLIES (P → Q) — false only when P is true and Q is false.
• IFF (P ↔ Q) — true when P and Q have the same truth value.

Truth Tables

A truth table lists every possible combination of true/false values for the propositions involved, and shows the result of a connective for each combination. It's the definitive way to check what a logical expression means.

Example: Generating a Truth Table

from itertools import product
def AND(p, q): return p and q
def OR(p, q): return p or q
def NOT(p): return not p
def IMPLIES(p, q): return (not p) or q
print(f"{'P':<6}{'Q':<6}{'P AND Q':<9}{'P OR Q':<9}{'NOT P':<7}{'P -> Q'}")
for p, q in product([True, False], repeat=2):
   print(f"{str(p):<6}{str(q):<6}{str(AND(p,q)):<9}{str(OR(p,q)):<9}{str(NOT(p)):<7}{str(IMPLIES(p,q))}")

Output

P     Q    P AND Q  P OR Q   NOT P P -> Q
True  True True     True     False True
True  False False   True     False  False
False True  False   True     True   True
False False False    False   True   True

Explanation:

Each row is one combination of P and Q. Notice P -> Q is only false in row 2, where P is true but Q is false — that's the one case that breaks the implication. Every other combination makes it true, even when P is false.

First-Order Logic

Propositional logic can't say "every bird can fly" — it only knows about whole, fixed statements. First-order logic (FOL) fixes this by adding objects, predicates, and quantifiers, so a single statement can apply to many objects at once.

Predicates and Quantifiers

Predicates 

A predicate is a property or relationship that takes objects as input and returns true or false, like Bird(Sparrow) or Likes(Alice, Bob).

Universal Quantifier (∀)

∀x means "for all x." The statement ∀x Bird(x) → CanFly(x) reads: "for every x, if x is a bird, then x can fly."

Existential Quantifier (∃)

∃x means "there exists an x." The statement ∃x Bird(x) ∧ ¬CanFly(x) reads: "there is some x that is a bird and cannot fly."

Example: Evaluating Quantifiers Over a Domain

animals = {
    "Sparrow": {"Bird": True, "CanFly": True},
    "Penguin": {"Bird": True, "CanFly": False},
    "Eagle":   {"Bird": True, "CanFly": True},
    "Dog":     {"Bird": False, "CanFly": False},
}
def Bird(x):   return animals[x]["Bird"]
def CanFly(x): return animals[x]["CanFly"]
def forall_birds_can_fly():
    return all((not Bird(x)) or CanFly(x) for x in animals)
def exists_bird_that_cannot_fly():
    return any(Bird(x) and not CanFly(x) for x in animals)
print("Domain:", list(animals.keys()))
print("forall x: Bird(x) -> CanFly(x)   =", forall_birds_can_fly())
print("exists x: Bird(x) AND NOT CanFly(x) =", exists_bird_that_cannot_fly())

Output

Domain: ['Sparrow', 'Penguin', 'Eagle', 'Dog']
forall x: Bird(x) -> CanFly(x)   = False
exists x: Bird(x) AND NOT CanFly(x) = True

Explanation:

The universal statement is false because Penguin is a counterexample — one bird that can't fly is enough to break "for all." The existential statement is true for that same reason: Penguin proves a bird exists that cannot fly.

Quick Comparison