Logic in Modern Technology

Unit 5: Introduction to Logic in AI — Section 5.5

You have learned what logic is, how to manipulate propositional formulas, and where the field came from. Now the question is: where does it live today? The answer is everywhere you do not expect it — inside the query you type in a search engine, inside the chip that runs your phone, inside the software that controls aircraft, and inside the AI planning systems that route packages across continents.

See how English statements translate into formal logic.

Converting English to Logic

Learn how first-order logic extends propositional logic to handle objects and relationships.

First-Order Logic Introduction

The Limits of Propositional Logic

Propositional logic handles statements about specific, named situations. But the world is full of general statements — claims about categories of objects, not just individual instances.

Why propositional logic falls short:

Statement: "All students are eligible to use the library."

Propositional logic attempt:

AliceEligible ∧ BobEligible ∧ CarolEligible ∧ ...

You would need one atomic proposition per student — potentially thousands. And if a new student enrolls, you must add a new proposition by hand. The formula can never be complete.

First-order logic solution:

∀x (Student(x) → LibraryEligible(x))

One formula. Covers every student who has ever enrolled or ever will enroll.

This is the practical motivation for first-order logic (FOL): it lets us write one formula to cover infinitely many cases.

Components of First-Order Logic

First-order logic extends propositional logic with four new elements: constants, variables, predicates, and quantifiers.

Constants and Variables

Constants are names for specific individuals in the domain. In a university system: Alice, CPCC, CS114. In a medical system: Patient47, Aspirin.

Variables stand for arbitrary members of the domain. They are typically lowercase letters (x, y, z) or descriptive lowercase names (student, drug, city).

Predicates

A predicate is a property or relationship expressed as a function that returns true or false.

Predicate

A symbol that expresses a property of one individual (unary predicate) or a relationship between individuals (binary or n-ary predicate). Predicates return true or false. Examples: Student(x) ("x is a student"), Loves(x, y) ("x loves y"), GreaterThan(x, y) ("x > y"). Predicates are the building blocks of first-order logic formulas.

Type Example Meaning

Unary (property)

Enrolled(x)

x is enrolled

Unary (property)

Warm(x)

x is warm

Binary (relation)

ParentOf(x, y)

x is a parent of y

Binary (relation)

Teaches(x, y)

x teaches course y

Ternary

Between(x, y, z)

x is between y and z

Quantifiers

Quantifiers let us make claims about all or some members of a domain.

Universal Quantifier (∀)

Written ∀x, read "for all x." A formula ∀x P(x) is true when P(x) is true for every individual x in the domain. Used to express "all," "every," "each," "any." Typically paired with implication (→): ∀x (Student(x) → Enrolled(x)).

Existential Quantifier (∃)

Written ∃x, read "there exists an x such that." A formula ∃x P(x) is true when P(x) is true for at least one individual x in the domain. Used to express "some," "there is," "at least one." Typically paired with conjunction (∧): ∃x (Student(x) ∧ Smart(x)).

The critical pattern to remember:

  • ∀x (P(x) → Q(x)) — "All P are Q" uses implication with the universal quantifier

  • ∃x (P(x) ∧ Q(x)) — "Some P are Q" uses conjunction with the existential quantifier

The most common mistake is using ∀x (P(x) ∧ Q(x)). This says "everything in the domain is both P and Q" — probably not what you meant.

Translating English to First-Order Logic

The five-step translation method:

  1. Identify the domain — What objects are we talking about? People? Cities? Courses?

  2. Define predicates — What properties and relationships do we need to express?

  3. Choose quantifiers — Is this about all objects (∀), some objects (∃), or a specific named object?

  4. Identify connectives — Are there "and," "or," "not," "if…​then" connecting clauses?

  5. Build the formula — Combine quantifiers, predicates, and connectives with explicit parentheses.

Pattern 1: "All X are Y"

English: "All birds can fly."

Domain: animals. Predicates: Bird(x), CanFly(x).

Formula: ∀x (Bird(x) → CanFly(x))

Pattern 2: "Some X are Y"

English: "Some professors are funny."

Domain: people. Predicates: Professor(x), Funny(x).

Formula: ∃x (Professor(x) ∧ Funny(x))

Pattern 3: "No X are Y"

English: "No student is perfect."

Two equivalent formulations:

  • Method 1: ∀x (Student(x) → ¬Perfect(x))

  • Method 2: ¬∃x (Student(x) ∧ Perfect(x))

Pattern 4: "Only X can Y"

English: "Only faculty members can teach courses."

Trick: "Only X are Y" means "if Y then X" — the implication is reversed.

Formula: ∀x ∀y Teaches(x, y) ∧ Course(y → Faculty(x))

The statement "Everybody loves somebody" and the statement "There is somebody whom everybody loves" are different in English — one says each person has their own person they love, the other says there is one universal beloved.

Try translating both into first-order logic using the predicate Loves(x, y) and the quantifiers ∀ and ∃.

Hint: the difference comes down to the order of the quantifiers.

Logic in Databases

Relational databases — the technology behind virtually every application that stores data — are built on first-order logic. The relational model was created by Edgar Codd in 1970 explicitly as an application of predicate logic.

Every SQL WHERE clause is a propositional logic formula evaluated over database records.

SQL as propositional logic:

SELECT * FROM students
WHERE (gpa > 3.5) AND (state = 'NC' OR state = 'SC')

For each record, the database evaluates:

GpaAbove3point5 ∧ (StateIsNC ∨ StateIsSC)

Only records where this formula is true are returned. The WHERE clause is a propositional formula; the database is a truth-value evaluator running it over millions of rows per second.

More powerful queries use the equivalent of quantifiers. EXISTS in SQL corresponds to ∃; aggregate conditions over ALL correspond to ∀.

Logic in Digital Circuits

Every logic gate in a computer chip is a physical implementation of a Boolean operator. An AND gate outputs 1 when both inputs are 1. An OR gate outputs 1 when at least one input is 1. A NOT gate inverts its input.

Circuit design begins with a truth table specifying the desired output for every combination of inputs, then minimizes the circuit using Boolean algebra — the same equivalence laws from Section 5.3.

From truth table to circuit:

Requirement: A light should be ON when either (sensor A fires AND sensor B fires) OR (override switch is ON).

Logical formula: (A ∧ B) ∨ Override

This directly maps to a circuit: an AND gate with inputs A and B, whose output feeds into an OR gate along with the Override signal.

The same formula, the same connectives — physics just implements ∧ and ∨ in silicon instead of on paper.

Logic in Software Verification

Safety-critical software must be correct — not just "usually correct" or "correct for the cases we tested." Formal verification uses logic to prove that software satisfies its specification for all possible inputs.

Verifying a simple access control rule:

Specification (in natural language): "A user may access a resource only if they are authenticated AND either an admin or the resource owner."

Formal specification:

∀u ∀r (CanAccess(u, r) →
    (Authenticated(u) ∧ (Admin(u) ∨ Owner(u, r))))

A formal verifier checks that every code path in the access control module satisfies this formula. If any execution sequence would allow access without authentication, the verifier finds it — even if no tester thought to try that sequence.

Tools like TLA+, Coq, and Isabelle are used to verify operating systems (seL4), cryptographic protocols (TLS), and hardware (Intel’s floating-point units after the FDIV disaster).

Logic in AI Planning

AI planning systems — used in robotics, logistics, and game-playing — represent the world’s state as a set of logical facts and represent actions as logical rules specifying preconditions and effects.

Warehouse robot planning (propositional representation):

State: DoorClosed ∧ NeedToPass ∧ RobotAt(Entrance)

Rules:

DoorClosed ∧ NeedToPass → action: OpenDoor
DoorOpen → action: MoveThrough

The robot applies modus ponens to its current state and rules to determine the next action. The planning loop is a forward-chaining inference engine — exactly the structure you will build with knowledge-based agents in Unit 6.

Logic in Knowledge Graphs

When you search for "Barack Obama" on Google and see a knowledge panel with his birth date, family members, and career, you are seeing the output of a knowledge graph — a massive store of logical facts.

Google Knowledge Graph facts (in FOL):

Person(BarackObama)
President(BarackObama)
∀x (President(x) → Politician(x))

Inference: Politician(BarackObama) — derived, never explicitly stored.

The knowledge graph does not just store what it is told. It reasons with what it is told, using the same entailment rules from Section 5.3. When you search for "Barack Obama" and the panel mentions he is a politician even though no one typed that fact, inference did the work.

First-order logic is the foundation of knowledge representation in AI. Databases are logic applied to stored records. Circuits are logic implemented in hardware. Formal verification is logic applied to program behavior. Planning is logic applied to actions and goals. You have been using logic your entire digital life — now you know what it is.

Test your ability to translate English statements into first-order logic and recognize logic in real-world systems.

Next: 5.L Logic Puzzles Lab →

Based on the UC Berkeley CS 188 Online Textbook by Nikhil Sharma, Josh Hug, Jacky Liang, and Henry Zhu, licensed under CC BY-SA 4.0.

This work is licensed under CC BY-SA 4.0.