Expressing Knowledge Through First-Order Logic, Explained

UPI Study › Courses › Introduction to Artificial Intelligence › Free lessons › Lesson 6.4 Free with a free account

Expressing Knowledge Through First-Order Logic

Introduction to Artificial Intelligence · Chapter 6: Logic, Reasoning, and Knowledge SystemsSection 6.4 · lesson 42 of 6910 min · free with a free account

← Building Truth Tables with Propositional LogicNext lesson: Algorithms for Propositional Reasoning →

Earn 3 college credits for Introduction to Artificial IntelligenceRecommended for credit by NCCRS · Computer Science 373 · self-paced · one payment, lifetime access
Enroll in Introduction to Artificial Intelligence · $250 →Download the syllabus (PDF)

In this lesson

How objects, predicates and quantifiers express knowledge precisely.

  • Distinguish constants, variables, functions, predicates, terms and sentences
  • Evaluate quantified sentences in a given model
  • Translate English statements into first-order logic with the right quantifier and connective
  • Use equality and quantifier order correctly to avoid common translation errors

Free study notes

Get this lesson's notes by email

The key points and 4 practice questions with answers, in your inbox. One email, free.

One email. Unsubscribe in one click.

Transcript

Everything said in the video, section by section (1,413 words). Read along, or search it.

Opening Question

Beyond One Symbol per Fact

Suppose a knowledge system must store that Alice is a manager. In propositional logic, that's one symbol, true or false, with no inside parts. The symbol doesn't know it's about Alice, and it can't connect to a symbol about Bob. To say every manager works remotely, it would need a separate sentence for every person, and a new one each time someone joined. First-order logic removes that limit. It can name objects, describe relationships between them, and cover all objects, or some, in one short sentence. It's the standard language for writing down precise knowledge.

Building Blocks

Constants, Variables, Functions and Predicates

First-order logic describes a domain: the collection of objects we're talking about. Our example is an office with four people: Alice, Bob, Carla, and Dan. A constant names one particular object, like Alice. A variable, like x, stands for any object. A function turns objects into another object: BossOf Bob is a person. A predicate is a property, or a relation, and gives true or false: Manager of Alice, or ReportsTo Bob, Alice. Connectives join sentences, as before. And quantifiers say how many objects a sentence covers.

Key Distinction

Terms Point, Sentences Claim

Separate two kinds of expression. A term points at an object. Constants, variables, and functions applied to terms are all terms, so Bob, and BossOf Bob, both point at a person. A sentence makes a claim that's true or false. The simplest, an atomic sentence, applies a predicate to terms. The number of terms a predicate takes is its arity: Manager takes one, ReportsTo takes two. So a function must never stand where a sentence is needed. BossOf Bob names a person, it isn't a claim. To make one, put it inside a predicate, like Manager of, BossOf Bob.

Quantifiers

ALL, EXISTS, Scope and Free Variables

A quantifier says how many objects a sentence covers. The universal quantifier means for all. The existential quantifier means there exists at least one. In print they have their own symbols. Here we write ALL and EXISTS. Each quantifier introduces a variable, and the part of the sentence it governs is its scope. Inside the scope, the variable is bound. A variable that no quantifier binds is free. And a sentence with a free variable, like Manager of x on its own, doesn't have a truth value yet.

Semantics

Models Fix What Sentences Mean

Syntax is how sentences are written. Semantics is what they mean: when they're true. Meaning is fixed by a model, which supplies a domain of objects, the object each constant names, and what each predicate and function means. In our office model, Alice and Carla are managers. Bob is the only one who works remotely. Bob and Dan report to Alice, and Alice reports to Carla. Carla reports to nobody. Truth follows four rules. An atomic sentence is true if its objects are in the model's relation. Connectives work as before. ALL x is true when every object satisfies it, and EXISTS x, when at least one does.

Worked Example

Evaluating Six Sentences in the Office

Now evaluate six sentences in this model. Manager of Alice: true. Some manager works remotely: false. Bob is the only remote worker, and he isn't a manager. Nobody who reports to Alice is a manager: true. Bob and Dan report to her, and neither is. Everyone reports to someone: false, because Carla reports to nobody. Someone reports to nobody: true, Carla. And BossOf Bob equals Alice: true.

Knowledge Bases

Sentences That Rule Out Models

A set of sentences describing what's known is a knowledge base. Many different models can satisfy the same knowledge base, and every new sentence rules some of them out. A sentence follows from the knowledge base, if it's true in every model where the knowledge base is true. Procedures for finding those consequences come in the lesson on resolution.

Quick Check

Every Manager Has a Report

Quick check, in the same office model. Is this sentence true: every manager has someone who reports to them? Written out: for all x, Manager of x implies, there exists y, ReportsTo y, x. Does every manager pass, or does Carla break it, or Bob? Pause, and decide. It holds. Alice has Bob and Dan reporting to her, and Carla has Alice. Both managers pass, so the ALL sentence is true. Carla reports to nobody, but that's a different claim. Here the question is who reports to her. And Bob has no reports, but he isn't a manager, so for him the implication is automatically true. He can't make it fail.

Translation Routine

From English to First-Order Sentences

Translation improves with a fixed routine. Identify the objects and categories. Choose names: constants, predicates, and functions for any the X of Y. Decide whether it's about all objects, some, or none. Choose the connective that fits the quantifier: ALL goes with implies, and EXISTS goes with AND. And test the result on a small model. Every manager works remotely: for all x, Manager of x implies Remote of x. Some manager works remotely: there exists x, Manager of x AND Remote of x. No manager works remotely: for all x, Manager of x implies NOT Remote of x. And Alice's boss is a manager: Manager of, BossOf Alice.

Why It Works

Pairing ALL with Implies, EXISTS with AND

Why does ALL go with implies, and EXISTS with AND? Check each person in the office. Manager implies Remote fails for Alice and Carla, so the ALL sentence is false. Correct: the managers don't work remotely. Manager AND Remote is false for everyone, so the EXISTS sentence is false. Also correct. But EXISTS x, Manager implies Remote, comes out true, only because Bob and Dan aren't managers, which makes the implication true for them. That's not what some manager works remotely means.

Quantifier Order

Order and Negation of Quantifiers

With two quantifiers, order matters. Take a model where Ann likes Ben, Ben likes Cy, and Cy likes Ann. For all x, there exists y, Likes x y: everyone likes someone. True. Reverse them: there exists y, for all x, Likes x y: there's one person everyone likes. False, since each is liked by only one other. Negation moves through quantifiers too. NOT for all x, P of x, is the same as, there exists x with NOT P of x: not everyone has it, so someone lacks it. And NOT exists x, P of x, is, for all x, NOT P of x.

Equality

Counting with the Equality Predicate

First-order logic has a special predicate, equality. t1 equals t2 is true when both terms name the same object. Equality is what makes counting possible. Alice has at least two direct reports: there exist x and y, with x not equal to y, both reporting to Alice. True: Bob and Dan. Carla has at most one: any two people who report to her must be the same person. True: only Alice. Without equality, two variables could quietly name the same object. And two different names may refer to the same object. Nothing says Alice and Carla are different people. If that matters, state it: Alice is not equal to Carla.

Quick Check

Every Remote Worker Reports to Alice

Quick check. Translate into first-order logic: every remote worker reports to Alice. Which formula says it: one, two, or three? Pause, and decide. The first. Every goes with ALL, and ALL goes with implies: for each object, if it's a remote worker, then it reports to Alice. The second says everyone in the office is a remote worker who reports to Alice: far too strong. And the third is true as soon as anyone isn't a remote worker, so it says nothing about remote workers.

Common Mistakes

Pitfalls in First-Order Translation

Common pitfalls, then. Using AND with ALL claims everyone is a manager who works remotely. Using implies with EXISTS is true whenever anyone isn't a manager. Swapping quantifier order changes everyone likes someone into one person liked by everybody. Leaving a variable free leaves no truth value. And a function, used as a sentence, names a person rather than making a claim. A function must give a value for every object, so BossOf Carla needs a convention: here, Carla is her own boss. And forgetting that two variables can match the same object: add x not equal to y, to say two. Above all, don't translate word by word: test each translation on a small model. Remember a sentence only states a fact, while inference draws conclusions. And check what each quantifier's scope covers.

Key Takeaways

Objects, Quantifiers and Models

To sum up. First-order logic talks about objects, relations, and functions, and its quantifiers cover all or some objects in one sentence. A term points at an object, a sentence is true or false. Predicates make atomic sentences, and functions only build terms. A model supplies the domain and the meanings, and truth is always relative to a model. Pair ALL with implies, and EXISTS with AND, watch quantifier order, and use equality for counting.

About Introduction to Artificial Intelligence at UPI Study

Introduction to Artificial Intelligence (Computer Science 373) is a self-paced online course of 69 video lessons in 9 chapters, from intelligent agents and search to game strategy, neural networks, logic and reasoning, machine learning, language, robotics and AI ethics. It carries a NCCRS credit recommendation for 3 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →

Compare: AI vs Current Trends in CS and IT

Why take it here

Why students take Introduction to Artificial Intelligence with UPI Study

How machines search, reason and learnIntroduction to Artificial Intelligence covers how AI systems are built: intelligent agents, search and heuristics, game strategy, logic, neural networks, machine learning, language and perception, and the ethics of AI. It is a common upper-level course in computer science degrees.
Credit at a fraction of the priceThe same 3 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Introduction to Artificial Intelligence carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Expressing Knowledge Through First-Order Logic

What is the difference between propositional logic and first-order logic?
Propositional logic treats each statement as one true-or-false symbol with no inner parts, while first-order logic can name objects, describe relations between them, and use quantifiers. To say every manager works remotely, propositional logic needs a separate sentence for each person. First-order logic says it once: for all x, Manager(x) implies Remote(x).
Why does the universal quantifier go with implies and the existential quantifier with AND?
Pairing the universal quantifier with implies limits the claim to objects that meet the condition, while pairing the existential quantifier with AND requires one object to meet both parts. For all x, Manager(x) AND Remote(x) wrongly claims everyone is a remote manager. There exists x, Manager(x) implies Remote(x) is true as soon as anyone is not a manager, so it says nothing useful.
Does the order of quantifiers matter in first-order logic?
Yes, swapping a universal and an existential quantifier can change the meaning. For all x, there exists y, Likes(x, y) says everyone likes someone, while there exists y, for all x, Likes(x, y) says one person is liked by everybody. If Ann likes Ben, Ben likes Cy and Cy likes Ann, the first is true and the second false, since each person is liked by only one other.
How is equality used for counting in first-order logic?
Equality lets a sentence say that two variables name different objects, which counting requires. Alice has at least two direct reports becomes: there exist x and y with x not equal to y, ReportsTo(x, Alice) AND ReportsTo(y, Alice). Without the inequality, x and y could name the same person. Two different constants can also name one object unless the knowledge base states that they differ.

About the Introduction to Artificial Intelligence course

How many college credits is Introduction to Artificial Intelligence?
Introduction to Artificial Intelligence (Computer Science 373) carries a NCCRS credit recommendation for 3 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Introduction to Artificial Intelligence cost and what is included?
$250, paid once, with lifetime access: all 69 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Introduction to Artificial Intelligence take?
It is self-paced with no deadlines. The 69 lessons total about 16 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 3 credits in Introduction to Artificial Intelligence.

69 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Introduction to Artificial Intelligence →Download the syllabusEvery course with PRO →
Introduction to Artificial Intelligence
3 credits · NCCRSEnroll →