Skip to content

First-Order Logic (FOL)

From Propositional Logic to First-Order Logic

Limitations of Propositional Logic

Propositional logic becomes extremely verbose and inefficient when dealing with problems that involve recurring structures or general patterns:

  1. Propositional logic struggles to concisely state that a particular object has a certain property (limitation in expressing attributes).
  2. Propositional logic is extremely cumbersome when describing spatial relationships between objects, such as "adjacent to" or "above" (limitation in expressing relations).
  3. Propositional logic cannot express "for every..." in a single statement — for example, there is no way to say "every pit causes a breeze in adjacent cells" as a general pattern (limitation in expressing universal patterns).

To address these problems, artificial intelligence adopted first-order logic, which builds on propositional logic (connectives such as and \(\wedge\), or \(\vee\), not \(\neg\), implies \(\rightarrow\)) by adding the following:

  1. Objects: such as cells \(x, y\).
  2. Predicates: such as \(Pit(x)\) meaning \(x\) is a pit, and \(Breeze(y)\) meaning \(y\) has a breeze.
  3. Quantifiers: for instance, using the universal quantifier (\(\forall\)), a single statement can replace thousands of propositional logic formulas:
\[ \forall s_1, s_2 \text{ Adjacent}(s_1, s_2) \wedge Pit(s_1) \Rightarrow Breeze(s_2) \]

(For any two adjacent cells \(s_1\) and \(s_2\), if \(s_1\) contains a pit, then \(s_2\) must have a breeze.)

First-Order Logic Examples

1772068181957

In the figure above, the items in blue are objects, also called constant symbols. They represent concrete nouns or entities in the real world, such as Square1, Me, Boston, etc.

The items in red are predicates, used to describe properties of objects or relationships among multiple objects. For example:

  • Square1 has a breeze.
  • I drive from Boston to Wilmington.

The items in black are connectives — the familiar tools carried over from propositional logic, used to combine short assertions into complex sentences.

A sentence in first-order logic is formed by applying predicates to objects and then connecting them with connectives.

  • Example 1: \(Cute(Animal) \rightarrow (Kitty(Animal) \vee Puppy(Animal))\)
    • Translation: If an animal is cute, then it is either a kitten or a puppy.
  • Example 2: \(Succeeds(You) \leftrightarrow Practices(You)\)
    • Translation: You succeed if and only if you practice consistently.

Quantifiers do not appear in the examples shown in these slides. Quantifiers are a new mechanism introduced by first-order logic, specifically designed to express scope over quantities. The two most common quantifiers are:

  • Universal quantifier \(\forall\)**** : means "for all / every."
  • Existential quantifier \(\exists\)**** : means "there exists / at least one."

In strict first-order logic notation, all predicates are written at the front — this is called prefix notation. For example, to express "2 is less than 3," the strict form places "less than" as a predicate relation:

  • Strict form: LessThan(2, 3)

However, for mathematicians and humans, this notation is counter-intuitive. So for "notational ease," first-order logic allows us to place familiar mathematical operators between the two objects — this is known as infix notation.

  • Shorthand: \(2 < 3\)

This is just like Python programming: although the underlying call is to the object's built-in method (2).__lt__(3), you still write 2 < 3 in your code. Logic, too, uses this kind of "syntactic sugar" to improve readability.

One point worth noting here is that in first-order logic, = is not simply a mathematical operator — it is a built-in predicate specifically designed to describe a relationship. Its sole purpose is to determine: whether two objects refer to exactly the same entity in the real world.

Examples:

  • \(Venus = MorningStar\) (Venus = the Morning Star)
  • \(MountEverest = Sagarmatha\) (Mount Everest = Sagarmatha, the Nepali name for Everest)

These two examples perfectly illustrate the role of =: even when different constant symbols (names) are used in logical expressions, as long as they refer to the same physical entity, the equality predicate evaluates to True. The iron rule: "Can't have predicates equal to each other!"

  • Wrong: \(Succeeds(You) = Practices(You)\)
  • Correct: \(Succeeds(You) \leftrightarrow Practices(You)\)

Succeeds(You), as a predicate applied to an object, yields a proposition (True or False) — it is no longer an "object." The = sign can only be used to compare objects. In programmer's terms, this is a "Type Mismatch." Since both sides have already become propositions (True/False), we must use a higher-level "glue" — a standard logical connective (here the biconditional arrow means "if and only if") — to connect them.

Logic Programming

First-order logic (FOL) was invented by mathematicians and philosophers in the late 19th century — long before the modern computer. Its original purpose had nothing to do with writing code; rather, it was designed to use rigorous symbols to precisely describe complex mathematical theorems and natural language, since the expressive power of early propositional logic was far too limited.

Although FOL was not invented for computers, modern computer science, database theory (such as the relational algebra underlying SQL), and programming language design have been profoundly influenced by mathematical logic.

In contemporary software development:

  • Objects: have evolved into programming variables, data structures, or instances in object-oriented programming (OOP), stored in computer memory. Just like Ziggy in the earlier slides.
  • Predicates: correspond perfectly to functions or methods in programming languages that return Boolean values (True or False). Just as the function Cute() takes Ziggy as an argument, computes, and returns True.

These ideas became the cornerstone of early AI (particularly during the expert systems era) and gave rise to an important programming paradigm — logic programming. A classic AI programming language called Prolog (Programming in Logic) directly transplanted first-order logic onto computers. In Prolog, you do not need to write traditional for loops or if/else statements; you simply input "objects" and "predicates (rules)," and the underlying logic inference engine derives answers to your questions automatically.

Functions

The final result of evaluating a predicate is a proposition (true or false), whereas the result of evaluating a function is a concrete object.

  • HomeState(Me) does not mean "Is my home state Delaware? (True/False)" — instead, it directly maps to and returns the object Delaware.
  • RightArmOf(Robot) takes the object "Robot" and returns a new object, RobotRightArm.

Syntactically, functions and predicates look identical — there is no way to distinguish them by appearance alone (both use an uppercase initial letter followed by arguments in parentheses). In practice, one must rely on context or prior definitions to tell them apart.

Because functions and predicates look so similar, beginners frequently confuse objects with propositions (True/False values). The final slide explicitly identifies two of the most common "syntax errors":

Error 1: Connectives cannot join objects

  • Bad example: \(Venus \rightarrow TheSun\) (Venus \(\rightarrow\) the Sun)
  • Explanation: \(\rightarrow\) is a logical connective; both sides must be propositions that can be evaluated as true or false (e.g., "it rains \(\rightarrow\) the ground gets wet"). Venus and the Sun are merely inert entities (objects) with no logical inference relationship between them.

Error 2: Propositions cannot be passed as arguments to functions

  • Bad example: \(StarOf(IsRed(Sun) \wedge IsGreen(Mars))\)
  • Explanation: The expression inside the parentheses, \(IsRed(Sun) \wedge IsGreen(Mars)\), is a predicate combination whose result is a Boolean value (True/False). But the function StarOf() is like a juicer — it needs a "fruit" (an object) to be fed in. If you feed it a "true/false" concept instead, the logic system crashes on the spot.

Quantifiers

Existential Quantifiers

The existential quantifier (\(\exists\)) addresses a core problem: we do not need to enumerate every entity in the world — as long as we can find at least one object that satisfies the conditions, the entire logical statement holds true.

In essence, it is equivalent to:

# Pseudocode for understanding ∃x. formula
for x in all_objects_in_the_world:
    if formula(x) == True:
        return True  # As soon as one is found, immediately judge as true!
return False

Example 1: \(\exists x. \text{Even}(x) \wedge \text{Prime}(x)\)

There exists a number \(x\) that is both even and prime. The logic engine searches through the sea of numbers. When it substitutes \(x=2\), it finds that \(\text{Even}(2) \wedge \text{Prime}(2)\) is True. Mission accomplished — the entire proposition is True!

Example 2: \(\exists x. \text{TallerThan}(x, me) \wedge \text{HeavierThan}(x, me)\)

There exists some person \(x\) in the world who is both taller and heavier than me. This single sentence is extraordinarily powerful. In propositional logic, you would have to enumerate all 8 billion people on Earth (Yao Ming is taller and heavier than me \(\vee\) Tyson is taller and heavier than me \(\vee \dots\)). But with first-order logic and quantifiers, one short line of symbols perfectly expresses this sweeping concept.

Universal Quantifiers

The universal quantifier is used to express "for all..." or "every..." — absolute statements. It is typically written as an inverted letter A, namely \(\forall\) (standing for the English word "All").

Basic form:

\(\forall x. \text{some-formula}\)

This means that within the domain of discourse, for every chosen \(x\), when \(x\) is substituted into the formula some-formula, the result must be true. If even a single \(x\) makes the formula false, the entire universal statement is false.

Example 1: \(\forall p. \text{Puppy}(p) \rightarrow \text{Cute}(p)\)

For every individual \(p\), if \(p\) is a puppy, then \(\rightarrow\) (it follows that) \(p\) is cute. In other words: "All puppies are cute."

Example 2: \(\forall x. \text{Happy}(x) \lor \text{Sad}(x)\)

For every individual \(x\), \(x\) is either happy \(\lor\) (or) sad. In other words: "Everyone is either happy or sad."

In programming, the universal quantifier \(\forall\) corresponds perfectly to a for loop that iterates over a collection, often combined with an early return mechanism. To verify that \(\forall x. P(x)\) is true, the program must check whether every element in the set satisfies \(P(x)\). If it finds even one counterexample (i.e., one that does not satisfy the condition), it immediately returns false.

// Suppose domain is the set of all x to be checked
function evaluate_universal_quantifier(domain):
    for x in domain:
        // If substituting x into the formula yields false (counterexample found)
        if some_formula(x) == False:
            return False // One failure means the entire universal claim is false

    // Loop complete, no counterexample found
    return True

In many modern programming languages, the logic of the universal quantifier is encapsulated in ready-made higher-order functions:

# For every x in the domain, evaluate some_formula(x); return True only if all are true
result = all(some_formula(x) for x in domain)

The essence of the universal quantifier is a "zero-tolerance" traversal checker — every single element must pass for the check to succeed.

Vacuous Truth

There is a noteworthy special case called vacuous truth — a fascinating edge case in logic.

For instance, suppose I say: "All the fire-breathing dragons in my garage are pink." Since there are no fire-breathing dragons in my garage (the set is empty), you can never produce a green dragon to prove me wrong. Therefore, in the strict logical sense, my statement cannot be considered false — it is true.

In logic, for universal quantifiers ("all..."), the system's default stance is "innocent until proven guilty" — that is, it defaults to True unless you can prove it False. How do you prove it False? You must produce a counterexample.

From a programming perspective, computers must be designed this way, because if the empty set did not return True, the programming world would fall apart. Consider a practical software engineering example. Suppose you write a security monitoring system that needs to check whether all errors in the system log have been fixed. Your pseudocode might look like this:

def check_system_safe(error_logs):
    # Default: system is safe
    is_safe = True

    for error in error_logs:
        if error.is_fixed == False:
            is_safe = False # Found an unfixed error — alert!
            break

    return is_safe

Now imagine a freshly started system running perfectly with zero errors. At this point, error_logs is an empty array [].

  • If the universal check over an empty set returned False: your program would conclude "not all errors have been fixed," triggering frantic alerts — even though the system is perfectly healthy with no errors at all!
  • If the universal check over an empty set returns True: the for loop is simply skipped, and the program returns is_safe = True. The system concludes: "All 0 existing errors are in a fixed state" — everything is fine.

In programming and mathematics, "all X are Y" does not imply "X exists." Its precise meaning is: "As long as you cannot produce an X that is not Y, the statement holds." Since there are no X's, you certainly cannot produce one, so the statement is true.

For any \(x\), if \(x\) satisfies condition P, then \(x\) satisfies condition Q. In mathematical notation: \(\forall x. P(x) \rightarrow Q(x)\). The ultimate secret to understanding vacuous truth lies in the truth table of \(P \rightarrow Q\). In logic, a conditional statement \(P \rightarrow Q\) is false in only one case: the premise P is true, but the conclusion Q is false. In all other cases, it is defined as true.

Premise P Conclusion Q P→Q (If P then Q) Explanation
True True True Straightforward: it rained (\(P\)), the ground is wet (\(Q\)). No problem.
True False False The only counterexample: it rained (\(P\)), the ground is not wet (\(Q\)). This is a lie!
False True True It didn't rain (\(P\)), but the ground is wet (\(Q\), perhaps a sprinkler truck). The original claim "if it rains, the ground gets wet" is not violated.
False True True It didn't rain (\(P\)), and the ground isn't wet (\(Q\)). The original claim is not violated.

In logic, if the premise (P) itself is false or nonexistent, then any conclusion (Q) drawn from that premise is considered "not false" — i.e., it counts as True.

This is why, in computer science and discrete mathematics, applying \(\forall\) (universal quantification) over an empty set always yields True — because you can never trigger the only row in the truth table that produces False (the second row: \(P\) is true but \(Q\) is false).

Combining Quantifiers

DeMorgan's Law for Quantifiers

Core principle: When a negation sign (\(\neg\)) passes through a quantifier, the quantifier must flip (\(\forall\) becomes \(\exists\), and \(\exists\) becomes \(\forall\)), and the predicate that follows must also be negated.

1. Negating a universal quantifier (Not All → Exists Not)

  • Formula: \(\neg \forall x. P(x) \equiv \exists x. \neg P(x)\)
  • Logical interpretation: To refute "everything satisfies \(P\)," you only need to "find at least one counterexample that does not satisfy \(P\)."
  • Semantic example:
    • Original: \(\neg\) (everyone is a good person)
    • Equivalent: \(\exists\) (there exists someone who is not a good person)

2. Negating an existential quantifier (Not Exists → All Not)

  • Formula: \(\neg \exists x. P(x) \equiv \forall x. \neg P(x)\)
  • Logical interpretation: To refute "there exists something satisfying \(P\)," you must prove "nothing satisfies \(P\)."
  • Semantic example:
    • Original: \(\neg\) (there exists a good person)
    • Equivalent: \(\forall\) (no one is a good person)

Ordering of Nested Quantifiers

Core principle: Quantifiers of the same type can be freely reordered; quantifiers of different types cannot be swapped without changing the meaning of the statement.

1. Same quantifiers: order is interchangeable

Consecutive quantifiers of the same kind can be reordered without affecting the logical truth value.

  • Nested universal quantifiers: \(\forall x \forall y: P(x,y) \equiv \forall y \forall x: P(x,y)\)
  • Nested existential quantifiers: \(\exists x \exists y: P(x,y) \equiv \exists y \exists x: P(x,y)\)

2. Different quantifiers: order matters

When \(\forall\) and \(\exists\) alternate, the quantifier that appears later depends on the one that appears earlier (it has a local scope).

  • Formula: \(\forall x \exists y: \text{Formula} \not\equiv \exists y \forall x: \text{Formula}\)
  • Classic analysis (let \(P(x,y)\) mean "\(x\) likes \(y\)"):
  • Case A (\(\forall x \exists y\)): For every person \(x\), there exists someone \(y\) whom they like.
    • Key point: Here \(y\) depends on \(x\) (each person may like a different person).
  • Case B (\(\exists y \forall x\)): There exists a particular person \(y\) whom everyone \(x\) likes.
    • Key point: Here \(y\) is globally fixed and unique (everyone likes the same universally beloved person).

FOL Translation

The Golden Rules

When translating natural language into logical formulas, mastering two fundamental patterns is key. Virtually all complex sentences are built from them:

  1. "Some A are B" (existential statements)
  2. "All A are B" (universal statements)

For the first pattern — "Some A are B" — we use \(\exists\) paired with \(\land\). Example formula: \(\exists x. mushroom(x) \land purple(x)\), meaning there exists an entity \(x\) that is a mushroom and is purple.

For the second pattern — "All A are B" — we use \(\forall\) paired with \(\rightarrow\). Example formula: \(\forall x \forall y. [gardener(x) \land mushroom(y) \land purple(y)] \rightarrow allergicTo(x, y)\), meaning for any \(x\) and \(y\), if the preconditions are met, then the conclusion follows.

Using logical equivalences, we can restructure nested implications with multiple conditions to improve readability:

  • Core rule: \(A \rightarrow (B \rightarrow C) \equiv (A \land B) \rightarrow C\)
  • Application: Converting the "all gardeners..." formula into a two-level implication form:
\[ \forall x. gardener(x) \rightarrow \forall y [(mushroom(y) \land purple(y)) \rightarrow allergicTo(x, y)] \]

An important pitfall to watch out for here: guarding against vacuous truth.

Under the existential quantifier (\(\exists\)), one must never casually use implication (\(\rightarrow\)).

Case study: "Some gardeners are allergic to every mushroom."

Wrong translation

\[ \exists x. \forall y. (gardener(x) \land mushroom(y)) \rightarrow allergicTo(x, y) \]

Why this is wrong (the Ziggy effect):

  1. In formal logic, the implication \(False \rightarrow \text{anything}\) always evaluates to True.
  2. If we substitute a non-gardener entity (e.g., a dog named Ziggy from the knowledge base), the premise \(gardener(Ziggy)\) becomes False.
  3. This causes \((False \land mushroom(y))\) to be False overall.
  4. Ultimately, \(False \rightarrow allergicTo(x, y)\) is forced to output True. This absurdly makes the statement about "gardeners" true merely because a dog exists in the world.

Correct version

\[ \exists x. gardener(x) \land \forall y. (mushroom(y) \rightarrow allergicTo(x, y)) \]

Why this is correct:

  1. The logical conjunction (\(\land\)) strictly "locks in" the identity of the subject.
  2. The syntactic structure becomes: there exists an entity \(x\) that must be a gardener and satisfies the subsequent allergy condition.
  3. If we again substitute a non-gardener entity (e.g., the dog Ziggy), \(gardener(Ziggy)\) is False, so \(False \land \text{subsequent condition}\) immediately yields False, successfully blocking the logical loophole.

Summary of the golden rules:

  • To express "all": \(\forall\) always pairs with \(\rightarrow\) — "whenever something is..., it must be..."
  • To express "some/exists": \(\exists\) always pairs with \(\land\) — "there really is such a thing that is both... and..."

The reasoning is as follows. When expressing "all," we are laying down a rule. When you say "all gardeners are allergic," you are not claiming that everything in the universe is a gardener (using \(\land\) would produce this absurd meaning: everything is both a gardener and allergic). What you really mean is to apply a filter: "across the entire universe, if I catch a gardener, then they must be allergic." The implication (\(\rightarrow\)) perfectly captures this "if...then..." conditional relationship.

When expressing "exists," we are actually hunting for evidence (catching someone in the act). When you say "some mushrooms are purple," you need to concretely find an entity that simultaneously satisfies two conditions: it must be a mushroom, and (\(\land\)) it must be purple. You absolutely cannot use \(\rightarrow\) (if...then...), because as we saw with the "dog (Ziggy)" example, if you say "there exists something such that if it is a mushroom, then it is purple," any random dog will do — since it is not a mushroom, the premise is false, and the entire sentence becomes vacuously true. This is clearly exploiting a logical loophole.

To reiterate:

  • \(\forall\) + \(\rightarrow\)* = *"whenever..." (setting a rule)
  • \(\exists\) + \(\land\)* = *"both...and..." (catching something in the act)

Case Study 1

"There is a country that borders both Iraq and Pakistan."

Consider the following four FOL expressions:

  1. \((\exists c\ Country(c) \land Border(c, Iraq) \land Border(c, Pakistan))\)
  2. \((\exists c\ Country(c) \Rightarrow [Border(c, Iraq) \land Border(c, Pakistan)])\)
  3. \((\exists c\ Country(c)) \Rightarrow [Border(c, Iraq) \land Border(c, Pakistan)]\)
  4. \((\exists c\ Border(Country(c), Iraq \land Pakistan))\)

We "examine" each expression and classify it into one of the following three categories:

  1. The expression perfectly and correctly translates the English sentence. (If this is selected, no further explanation is needed.)
  2. The expression is syntactically invalid, and therefore meaningless. If this is selected, you must explain why the syntax is wrong.
  3. The expression is syntactically valid but does not express the same meaning as the English sentence. If this is selected, you must explain what logical error it commits / what it actually says.

In logic, syntactically valid means that the spelling of symbols, the closure of parentheses, and the use of connectives all conform to the grammar rules of first-order logic. The logic system or computer can parse the sentence. Even if the sentence is a bald-faced lie or commits a logical fallacy in reality (e.g., "all pigs can fly"), as long as the format is correct, it is valid. Any formula that can be evaluated to a result (True or False) is syntactically valid.

Syntactically invalid means that fundamental writing rules have been violated — for example, mismatched parentheses or symbols forced together in ways that make no sense. The logic system throws an error and crashes; it cannot even parse the expression, let alone determine its truth value. It is like the English sentence "I eat dinner a was by" — you recognize the individual words, but strung together they are meaningless.

Let us examine each one:

Expression 1: (∃c Country(c) ∧ Border(c, Iraq) ∧ Border(c, Pakistan))

  • What it says: There exists an entity \(c\) such that \(c\) is a country, and \(c\) borders Iraq, and \(c\) borders Pakistan.
  • Category: 1. The expression correctly expresses the English sentence.
  • Explanation: It perfectly and correctly applies the standard "recipe" for existential quantifiers. When expressing "there exists something satisfying multiple conditions," we must use the existential quantifier (\(\exists\)) paired with logical conjunction (\(\land\)) to chain all the constraints together.

Expression 2: (∃c Country(c) ⇒ [Border(c, Iraq) ∧ Border(c, Pakistan)])

  • What it says: There exists an entity \(c\) such that if \(c\) is a country, then it borders both Iraq and Pakistan.
  • Category: 3. The expression is syntactically valid but does not express the meaning of the English sentence.
  • Explanation: The expression does not violate any symbol or connective rules (so syntactically it is valid), but it falls into the vacuous truth trap. Because the implication (\(\Rightarrow\)) is used, as long as we find any entity that is not a country (e.g., a rock), the premise Country(rock) becomes False. In logic, "False implies anything" always evaluates to True. Thus, merely because a rock exists in the world, the statement is judged true — which provides no guarantee that a qualifying "country" actually exists.

Expression 3: (∃c Country(c)) ⇒ [Border(c, Iraq) ∧ Border(c, Pakistan)]

  • What it says: If (there exists an entity \(c\) that is a country), then (some unknown \(c\) borders Iraq and Pakistan).
  • Category: 2. The expression is syntactically invalid and therefore meaningless.
  • Explanation: The problem lies in the placement of parentheses. The left side, (∃c Country(c)), forms a completely closed scope. This means the jurisdiction of the quantifier \(\exists c\) ends at that closing parenthesis. Consequently, the \(c\) inside the right-side brackets [Border(c...)] loses its binding to the quantifier and becomes a free variable. In first-order logic, a sentence containing a free variable cannot be evaluated for truth or falsity — this constitutes a serious syntax error.
  • If forced into natural language, the sentence sounds disjointed, as if two people are talking past each other: "If (some country exists in this world), then (a mysterious unidentified entity \(c\) is next to Iraq, and this mysterious entity \(c\) is next to Pakistan)." Notice that the \(c\) in the second half appears out of nowhere — we have no idea what this \(c\) refers to!

The fatal error in Expression 3 lies in the placement of parentheses, which causes a "variable not bound (free variable)" syntax error.

  • Step 1: Examine the quantifier's scope. In first-order logic, a quantifier (such as \(\exists c\)) is like a "declaration" that only applies to the portion immediately following it that is enclosed in parentheses. Look at the first half: (∃c Country(c)). The closing parenthesis ) seals off the scope of \(\exists c\) right there. Within these parentheses, \(c\) represents a country, and the logic is self-consistent.
  • Step 2: Examine what comes after the implication (\(\Rightarrow\)). Past the implication, we enter the second half in brackets: [Border(c, Iraq) ∧ Border(c, Pakistan)]. A variable \(c\) appears here again. However, because the scope of \(\exists c\) already ended at the earlier closing parenthesis, the \(c\) in the second half has no connection whatsoever to the earlier \(\exists c\).
  • Step 3: Why is it judged syntactically invalid (meaningless)? In logic, this \(c\) in the second half is called a "free variable." It is like encountering the equation \(x + 2 = 5\) in the middle of a math problem where \(x\) was never defined. The logic system (or computer) reaches the second half and is baffled: "Is this \(c\) a constant? A place name? A person's name?" Because its identity cannot be determined, the entire proposition cannot be evaluated for truth or falsity, and it is therefore judged syntactically meaningless.

Expression 4: (∃c Border(Country(c), Iraq ∧ Pakistan))

  • What it says: (Translated into human language, this is pure nonsense): There exists an entity \(c\) such that the truth value of whether it is a country borders "Iraq and Pakistan."
  • Category: 2. The expression is syntactically invalid and therefore meaningless.
  • Explanation: This expression commits a severe "type mismatch" syntax error.
    1. The predicate Border(x, y) requires its arguments to be concrete object entities (such as variables or place names). However, Country(c) is a predicate that outputs True or False — it cannot serve as an entity argument inside another predicate.
    2. Logical conjunction (\(\land\)) can only connect two Boolean-type logical propositions (e.g., A and B). Iraq and Pakistan are object constants and cannot be directly joined with a logical operator.

Case Study 2

Target sentence: "No region in South America borders any region in Europe."

Expression 1: (¬∃c, d In(c, SouthAmerica) ∧ In(d, Europe) ∧ Borders(c, d))

  • What it says: There do not exist (\(\neg\exists\)) two entities \(c\) and \(d\) such that \(c\) is in South America, \(d\) is in Europe, and \(c\) borders \(d\).
  • Category: 1. The expression correctly expresses the English sentence.
  • Explanation: This is a very standard and elegant "inverse translation." The original sentence says "no South American region borders a European region," which is logically equivalent to "we cannot find a single instance (in South America, in Europe, and bordering each other)." Using the negation (\(\neg\)) combined with the existential quantifier (\(\exists\)) and conjunction (\(\land\)), the expression precisely and directly captures the mutual exclusion expressed in the original sentence, with correct syntax.

Expression 2: (∀c, d [In(c, SouthAmerica) ∧ In(d, Europe)] ⇒ ¬Borders(c, d))

  • What it says: For any two entities \(c\) and \(d\), if \(c\) is in South America and \(d\) is in Europe, then they necessarily do not border each other.
  • Category: 1. The expression correctly expresses the English sentence.
  • Explanation: This is another standard way to express "none of... are..." — applying our rule of thumb "set the rule (\(\forall\) paired with \(\Rightarrow\))". It establishes a global conditional rule (premise): whenever one entity is in South America and the other in Europe, the conclusion (\(\neg Borders\)) necessarily follows. The syntax is fully valid and the logic precisely matches the original meaning. (Note: In FOL translation, a single sentence can have multiple logically equivalent correct translations, so both Expressions 1 and 2 fall under Category 1.)

Expression 3: (¬∀c In(c, SouthAmerica) ⇒ (∃d In(d, Europe) ∧ ¬Borders(c, d)))

  • We need to verify whether the scope of \(c\) covers the right-hand side. Upon investigation, it is generally accepted that \(c\)'s scope does include the right-hand side in this expression, so the syntax is valid.
  • Incorrect meaning: "If not everything is in South America (i.e., there exists something not in South America), then there exists a European region d such that it does not border some \(c\)."

Expression 4: (∀c In(c, SouthAmerica) ⇒ (∀d In(d, Europe) ⇒ ¬Borders(c, d)))

  • What it says: For any entity \(c\), if it is in South America, then (for any entity \(d\), if it is in Europe, then \(c\) and \(d\) do not border each other).
  • Category: 1. The expression correctly expresses the English sentence.
  • Explanation: Recall the "advanced technique" from earlier in these notes: in logic, a two-level nested implication \(A \Rightarrow (B \Rightarrow C)\) is completely equivalent to the combined-condition form \((A \land B) \Rightarrow C\). This means that Expression 4 is mathematically and logically identical to Expression 2, which we already judged correct. It simply splits the preconditions into two levels of "if...then..." The syntax is valid, and it likewise perfectly expresses the original meaning.

Unifier

FOL — Second set of slides

  • Substitution (θ) can only replace variables: the form is always

    θ={ v1/t1, v2/t2,… }\theta={\,v_1/t_1,\ v_2/t_2,\dots}θ={v1/t1, v2/t2,…} where viv_ivi must be a variable and tit_iti is a term.

  • This term can be:
    1. A constant: x/Ax/Ax/A
    2. Another variable: x/yx/yx/y
    3. A function term: x/G(A,B)x/G(A,B)x/G(A,B)
  • Constants, predicates, and function symbols cannot be replaced: for example, A/xA/xA/x and G(x,x)/yG(x,x)/yG(x,x)/y are not legal.
  • Additionally, a variable can only map to one result within the same θ: you cannot simultaneously have x/Ax/Ax/A and x/Bx/Bx/B (unless A=BA=BA=B).

评论 #