lecture 1

Knowledge

Humans reason based on existing knowledge and draw conclusions. The concept of representing
knowledge and drawing conclusions from it is also used in AI, and in this lecture we will explore how
we can achieve this behavior.

Knowledge-Based Agents

These are agents that reason by operating on internal representations of knowledge.

What does “reasoning based on knowledge to draw a conclusion” mean?

Let’s start answering this with a Harry Potter example. Consider the following sentences:

1. If it didn’t rain, Harry visited Hagrid today.

2. Harry visited Hagrid or Dumbledore today, but not both.

3. Harry visited Dumbledore today.

Based on these three sentences, we can answer the question “did it rain today?”, even though none
of the individual sentences tells us anything about whether it is raining today. Here is how we can go
about it: looking at sentence 3, we know that Harry visited Dumbledore. Looking at sentence 2, we
know that Harry visited either Dumbledore or Hagrid, and thus we can conclude

4. Harry did not visit Hagrid.

Now, looking at sentence 1, we understand that if it didn’t rain, Harry would have visited Hagrid.
However, knowing sentence 4, we know that this is not the case. Therefore, we can conclude

5. It rained today.

To come to this conclusion, we used logic, and today’s lecture explores how AI can use logic to reach
to new conclusions based on existing information.

Sentence

A sentence is an assertion about the world in a knowledge representation language. A sentence is

how AI stores knowledge and uses it to infer new information.

Propositional Logic

Propositional logic is based on propositions, statements about the world that can be either true or
false, as in sentences 1-5 above.

Propositional Symbols

Propositional symbols are most often letters (P, Q, R) that are used to represent a proposition.

Logical Connectives

Logical connectives are logical symbols that connect propositional symbols in order to reason in a
more complex way about the world.

 Not (¬) inverses the truth value of the proposition. So, for example, if P: “It is raining,” then
¬P: “It is not raining”.
Truth tables are used to compare all possible truth assignments to propositions. This tool will help us
better understand the truth values of propositions when connected with different logical
connectives. For example, below is our first truth table:

P ¬P

false true

true false

connected by ∧, the resulting proposition P ∧ Q is true only in the case that both P and Q
 And (∧) connects two different propositions. When these two proposition, P and Q, are

are true.

P Q P∧Q

false false false

false true false

true false false

true true true

 Or (∨) is true as as long as either of its arguments is true. This means that for P ∨ Q to be
true, at least one of P or Q has to be true.

P Q P∨Q

false false false

false true true

true false true

true true true

Or. In an exclusive Or, P ∨ Q is false if P ∧ Q is true. That is, an exclusive Or requires only
 It is worthwhile to mention that there are two types of Or: an inclusive Or and an exclusive

one of its arguments to be true and not both. An inclusive Or is true if any of P, Q, or P ∧ Q is
true. In the case of Or (∨), the intention is an inclusive Or.

A couple of side notes not mentioned in lecture:

 Sometimes an example helps understand inclusive versus exclusive Or. Inclusive Or: “in
order to eat dessert, you have to clean your room or mow the lawn.” In this case, if you do
both chores, you will still get the cookies. Exclusive Or: “For dessert, you can have either
cookies or ice cream.” In this case, you can’t have both.

⊕).
 If you are curious, the exclusive Or is often shortened to XOR and a common symbol for it is
  Implication (→) represents a structure of “if P then Q.” For example, if P: “It is raining” and
Q: “I’m indoors”, then P → Q means “If it is raining, then I’m indoors.” In the case of P
implies Q (P → Q), P is called the antecedent and Q is called the consequent.

When the antecedent is true, the whole implication is true in the case that the consequent is true
(that makes sense: if it is raining and I’m indoors, then the sentence “if it is raining, then I’m indoors”
is true). When the antecedent is true, the implication is false if the consequent is false (if I’m outside
while it is raining, then the sentence “If it is raining, then I’m indoors” is false). However, when
the antecedent is false, the implication is always true, regardless of the consequent. This can
sometimes be a confusing concept. Logically, we can’t learn anything from an implication (P → Q) if
the antecedent (P) is false. Looking at our example, if it is not raining, the implication doesn’t say
anything about whether I’m indoors or not. I could be an indoors type and never walk outside, even
when it is not raining, or I could be an outdoors type and be outside all the time when it is not
raining. When the antecedent is false, we say that the implication is trivially true.

P Q P→Q

fals
false true
e

fals
true true
e

true false false

true true true

 Biconditional ( ) is an implication that goes both directions. You can read it as “if

and only if.” P Q is the same as P → Q and Q → P taken together. For example, if

P: “It is raining.” and Q: “I’m indoors,” then P Q means that “If it is raining, then
I’m indoors,” and “if I’m indoors, then it is raining.” This means that we can infer more than
we could with a simple implication. If P is false, then Q is also false; if it is not raining, we
know that I’m also not indoors.

P Q P Q

fals false true

 P Q P Q

fals
true false
e

true false false

true true true

Model

The model is an assignment of a truth value to every proposition. To reiterate, propositions are
statements about the world that can be either true or false. However, knowledge about the world is
represented in the truth values of these propositions. The model is the truth-value assignment that
provides information about the world.

For example, if P: “It is raining.” and Q: “It is Tuesday.”, a model could be the following truth-value
assignment: {P = True, Q = False}. This model means that it is raining, but it is not Tuesday. However,
there are more possible models in this situation (for example, {P = True, Q = True}, where it is both
raining and a Tuesday). In fact, the number of possible models is 2 to the power of the number of
propositions. In this case, we had 2 propositions, so 2²=4 possible models.

Knowledge Base (KB)

The knowledge base is a set of sentences known by a knowledge-based agent. This is knowledge that
the AI is provided about the world in the form of propositional logic sentences that can be used to
make additional inferences about the world.

Entailment (⊨)

If α ⊨ β (α entails β), then in any world where α is true, β is true, too.

For example, if α: “It is a Tuesday in January” and β: “It is January,” then we know that α ⊨ β. If it is
true that it is a Tuesday in January, we also know that it is January. Entailment is different from
implication. Implication is a logical connective between two propositions. Entailment, on the other
hand, is a relation that means that if all the information in α is true, then all the information in β is
true.

Inference

Inference is the process of deriving new sentences from old ones.

For instance, in the Harry Potter example earlier, sentences 4 and 5 were inferred from sentences 1,
2, and 3.

There are multiple ways to infer new knowledge based on existing knowledge. First, we will consider
the Model Checking algorithm.
  To determine if KB ⊨ α (in other words, answering the question: “can we conclude that α is
true based on our knowledge base”)

o Enumerate all possible models.

o If in every model where KB is true, α is true as well, then KB entails α (KB ⊨ α).

Consider the following example:

P: It is a Tuesday. Q: It is raining. R: Harry will go for a run. KB: (P ∧ ¬Q) → R (in words, P and not Q
imply R) P (P is true) ¬Q (Q is false) Query: R (We want to know whether R is true or false; Does KB ⊨
R?)

To answer the query using the Model Checking algorithm, we enumerate all possible models.

P Q R KB

fals
false false
e

fals
false true
e

fals
true false
e

fals
true true
e

true false false

true false true

true true false

true true true

Then, we go through every model and check whether it is true given our Knowledge Base.

First, in our KB, we know that P is true. Thus, we can say that the KB is false in all models where P is
not true.

P Q R KB

false false false false

false false true false

false true false false

false true true false

true false false

P Q R KB

true false true

true true false

true true true

Next, similarly, in our KB, we know that Q is false. Thus, we can say that the KB is false in all models
where Q is true.

P Q R KB

false false false false

false false true false

false true false false

false true true false

true false false

true false true

true true false false

true true true false

other R is false. Due to (P ∧ ¬Q) → R being in our KB, we know that in the case where P is true and Q
Finally, we are left with two models. In both, P is true and Q is false. In one model R is true and in the

is false, R must be true. Thus, we say that our KB is false for the model where R is false, and true for
the model where R is true.

P Q R KB

false false false false

false false true false

false true false false

false true true false

true false false false

true false true true

true true false false

P Q R KB

true true true false

Looking at this table, there is only one model where our knowledge base is true. In this model, we

then KB ⊨ R.
see that R is also true. By our definition of entailment, if R is true in all models where the KB is true,

Next, let’s look at how knowledge and logic can be represented as code.

from logic import *

# Create new classes, each having a name, or a symbol, representing each proposition.

rain = Symbol("rain") # It is raining.

hagrid = Symbol("hagrid") # Harry visited Hagrid

dumbledore = Symbol("dumbledore") # Harry visited Dumbledore

# Save sentences into the KB

knowledge = And( # Starting from the "And" logical connective, becasue each proposition represents
knowledge that we know to be true.

Implication(Not(rain), hagrid), # ¬(It is raining) → (Harry visited Hagrid)

Or(hagrid, dumbledore), # (Harry visited Hagrid) ∨ (Harry visited Dumbledore).

Not(And(hagrid, dumbledore)), # ¬(Harry visited Hagrid ∧ Harry visited Dumbledore) i.e. Harry
did not visit both Hagrid and Dumbledore.

dumbledore # Harry visited Dumbledore. Note that while previous propositions contained multiple
symbols with connectors, this is a proposition consisting of one symbol. This means that we take as a
fact that, in this KB, Harry visited Dumbledore.

To run the Model Checking algorithm, the following information is needed:

 Knowledge Base, which will be used to draw inferences

 A query, or the proposition that we are interested in whether it is entailed by the KB

  Symbols, a list of all the symbols (or atomic propositions) used (in our case, these
are rain, hagrid, and dumbledore)

 Model, an assignment of truth and false values to symbols

The model checking algorithm looks as follows:

def check_all(knowledge, query, symbols, model):

# If model has an assignment for each symbol

# (The logic below might be a little confusing: we start with a list of symbols. The function is
recursive, and every time it calls itself it pops one symbol from the symbols list and generates models
from it. Thus, when the symbols list is empty, we know that we finished generating models with
every possible truth assignment of symbols.)

if not symbols:

# If knowledge base is true in model, then query must also be true

if [Link](model):

return [Link](model)

return True

else:

# Choose one of the remaining unused symbols

remaining = [Link]()

p = [Link]()

# Create a model where the symbol is true

model_true = [Link]()

model_true[p] = True

# Create a model where the symbol is false

model_false = [Link]()

model_false[p] = False

# Ensure entailment holds in both models

 return(check_all(knowledge, query, remaining, model_true) and check_all(knowledge, query,
remaining, model_false))

Note that we are interested only in the models where the KB is true. If the KB is false, then the
conditions that we know to be true are not occurring in these models, making them irrelevant to our
case.

wins. Our KB specifies that P Q (P ∧ Q) → R. In other words, we know that P is true, i.e. Harry plays
An example from outside lecture: Let P: Harry plays seeker, Q: Oliver plays keeper, R: Gryffindor

seeker, and that Q is true, i.e. Oliver plays keeper, and that if both P and Q are true, then R is true,
too, meaning that Gryffindor wins the match. Now imagine a model where Harry played beater
instead of seeker (thus, Harry did not play seeker, ¬P). Well, in this case, we don’t care whether
Gryffindor won (whether R is true or not), because we have the information in our KB that Harry
played seeker and not beater. We are only interested in the models where, as in our case, P and Q
are true.)

Further, the way the check_all function works is recursive. That is, it picks one symbol, creates two
models, in one of which the symbol is true and in the other the symbol is false, and then calls itself
again, now with two models that differ by the truth assignment of this symbol. The function will
keep doing so until all symbols will have been assigned truth-values in the models, leaving the
list symbols empty. Once it is empty (as identified by the line if not symbols), in each instance of the
function (wherein each instance holds a different model), the function checks whether the KB is true
given the model. If the KB is true in this model, the function checks whether the query is true, as
described earlier.

Knowledge Engineering

Knowledge engineering is the process of figuring out how to represent propositions and logic in AI.

Let’s practice knowledge engineering using the game Clue.

In the game, a murder was committed by a person, using a tool in a location. People, tools, and
locations are represented by cards. One card of each category is picked at random and put in an
envelope, and it is up to the participants to uncover whodunnit. Participants do so by uncovering
cards and deducing from these clues what must be in the envelope. We will use the Model Checking
algorithm from before to uncover the mystery. In our model, we mark as True items that we know
are related to the murder and False otherwise.

For our purposes, suppose we have three people: Mustard, Plum, and Scarlet, three tools: knife,
revolver, and wrench, and three locations: ballroom, kitchen, and library.

We can start creating our knowledge base by adding the rules of the game. We know for certain that
one person is the murderer, that one tool was used, and that the murder happened in one location.
This can be represented in propositional logic the following way:

(Mustard ∨ Plum ∨ Scarlet)

(knife ∨ revolver ∨ wrench)

(ballroom ∨ kitchen ∨ library)

The game starts with each player seeing one person, one tool, and one location, thus knowing that
they are not related to the murder. Players do not share the information that the saw in these cards.
Suppose our player gets the cards of Mustard, kitchen, and revolver. Thus, we know that these are
not related to the murder and we can add to our KB

¬(Mustard)

¬(kitchen)

¬(revolver)

In other situations in the game, one can make a guess, suggesting one combination of person, tool
and location. Suppose that the guess is that Scarlet used a wrench to commit the crime in the library.
If this guess is wrong, then the following can be deduced and added to the KB:

(¬Scarlet ∨ ¬library ∨ ¬wrench)

Now, suppose someone shows us the Plum card. Thus, we can add

¬(Plum)

to our KB.

At this point, we can conclude that the murderer is Scarlet, since it has to be one of Mustard, Plum,
and Scarlet, and we have evidence that the first two are not it.

Adding just one more piece of knowledge, for example, that it is not the ballroom, can give us more
information. First, we update our KB

¬(ballroom)

And now, using multiple previous pieces of data, we can deduce that Scarlet committed the murder
with a knife in the library. We can deduce that it’s the library because it has to be either the
ballroom, the kitchen, or the library, and the first two were proven to not be the locations. However,
when someone guessed Scarlet, library, wrench, the guess was false. Thus, at least one of the
elements in this statement has to be false. Since we know both Scarlet and library to be true, we
know that the wrench is the false part here. Since one of the three instruments has to be true, and
it’s not the wrench nor the revolver, we can conclude that it is the knife.

Here is how the information would be added to the knowledge base in Python:

# Add the clues to the KB

knowledge = And(

# Start with the game conditions: one item in each of the three categories has to be true.

Or(mustard, plum, scarlet),

Or(ballroom, kitchen, library),

Or(knife, revolver, wrench),

# Add the information from the three initial cards we saw

Not(mustard),
 Not(kitchen),

Not(revolver),

# Add the guess someone made that it is Scarlet, who used a wrench in the library

Or(Not(scarlet), Not(library), Not(wrench)),

# Add the cards that we were exposed to

Not(plum),

Not(ballroom)

We can look at other logic puzzles as well. Consider the following example: four different people,
Gilderoy, Pomona, Minerva, and Horace, are assigned to four different houses, Gryffindor,
Hufflepuff, Ravenclaw, and Slytherin. There is exactly one person in each house. Representing the
puzzle’s conditions in propositional logic is quite cumbersome. First, each of the possible
assignments will have to be a proposition in itself: MinervaGryffindor, MinervaHufflepuff,
MinervaRavenclaw, MinervaSlytherin, PomonaGryffindor… Second, to represent that each person
belongs to a house, an Or statement is required with all the possible house assignments per person

(MinervaGryffindor ∨ MinervaHufflepuff ∨ MinervaRavenclaw ∨ MinervaSlytherin), repeat for

every person.

Then, to encode that if one person is assigned to one house, they are not assigned to the other
houses, we will write

(MinervaGryffindor → ¬MinervaHufflepuff) ∧ (MinervaGryffindor → ¬MinervaRavenclaw) ∧

(MinervaGryffindor → ¬MinervaSlytherin) ∧ (MinervaHufflepuff → ¬MinervaGryffindor)…

and so on for all houses and all people. A solution to this inefficiency is offered in the section on first
order logic. However, this type of riddle can still be solved with either type of logic, given enough
cues.

Another type of puzzle that can be solved using propositional logic is a Mastermind game. In this
game, player one arranges colors in a certain order, and then player two has to guess this order.
Each turn, player two makes a guess, and player one gives back a number, indicating how many
colors player two got right. Let’s simulate a game with four colors. Suppose player two suggests the
following ordering:
Player one answers “two.” Thus we know that some two of the colors are in the correct position, and
the other two are in the wrong place. Based on this information, player two tries to switch the
locations of two colors.

Now player one answers “zero.” Thus, player two knows that the switched colors were in the right
location initially, which means the untouched two colors were in the wrong location. Player two
switches them.

Player one says “four” and the game is over.

Representing this in propositional logic would require us to have (number of colors)² atomic
propositions. So, in the case of four colors, we would have the propositions red0, red1, red2, red3,
blue0… standing for color and position. The next step would be representing the rules of the game in
propositional logic (that there is only one color in each position and no colors repeat) and adding
them to the KB. The final step would be adding all the cues that we have to the KB. In our case, we
would add that, in the first guess, two positions were wrong and two were right, and in the second
guess, none was right. Using this knowledge, a Model Checking algorithm can give us the solution to
the puzzle.

Inference Rules

Model Checking is not an efficient algorithm because it has to consider every possible model before
giving the answer (a reminder: a query R is true if under all the models (truth assignments) where
the KB is true, R is true as well). Inference rules allow us to generate new information based on
existing knowledge without considering every possible model.

Inference rules are usually represented using a horizontal bar that separates the top part, the
premise, from the bottom part, the conclusion. The premise is whatever knowledge we have, and
the conclusion is what knowledge can be generated based on the premise.

In this example, our premise consists of the following propositions:

 If it is raining, then Harry is inside.

 It is raining.

Based on this, most reasonable humans can conclude that

 Harry is inside.

Modus Ponens

The type of inference rule we use in this example is Modus Ponens, which is a fancy way of saying
that if we know an implication and its antecedent to be true, then the consequent is true as well.
And Elimination

If an And proposition is true, then any one atomic proposition within it is true as well. For example, if
we know that Harry is friends with Ron and Hermione, we can conclude that Harry is friends with
Hermione.

Double Negation Elimination

A proposition that is negated twice is true. For example, consider the proposition “It is not true that
Harry did not pass the test”. We can parse it the following way: “It is not true that (Harry did not
pass the test)”, or “¬(Harry did not pass the test)”, and, finally “¬(¬(Harry passed the test)).” The two
negations cancel each other, marking the proposition “Harry passed the test” as true.

Implication Elimination

An implication is equivalent to an Or relation between the negated antecedent and the consequent.
As an example, the proposition “If it is raining, Harry is inside” is equivalent to the proposition “(it is
not raining) or (Harry is inside).”
This one can be a little confusing. However, consider the following truth table:

P Q P → Q ¬P ∨ Q

false false true true

false true true true

true false false false

true true true true

Since P → Q and ¬P ∨ Q have the same truth-value assignment, we know them to be equivalent
logically. Another way to think about this is that an implication is true if either of two possible

in the section on implication). This is represented by the negated antecedent P in ¬P ∨ Q, meaning

conditions is met: first, if the antecedent is false, the implication is trivially true (as discussed earlier,

true only when the consequent is true as well. That is, if P and Q are both true, then ¬P ∨ Q is true.
that the proposition is always true if P is false. Second, the implication is true when the antecedent is

However, if P is true and Q is not, then ¬P ∨ Q is false.

Biconditional Elimination

A biconditional proposition is equivalent to an implication and its inverse with an And connective.
For example, “It is raining if and only if Harry is inside” is equivalent to (“If it is raining, Harry is
inside” And “If Harry is inside, it is raining”).

De Morgan’s Law

It is possible to turn an And connective into an Or connective. Consider the following proposition: “It
is not true that both Harry and Ron passed the test.” From this, it is possible to conclude that “It is
not true that Harry passed the test” Or “It is not true that Ron passed the test.” That is, for the And
proposition earlier to be true, at least one of the propositions in the Or propositions must be true.

Similarly, it is possible to conclude the reverse. Consider the proposition “It is not true that Harry or
Ron passed the test.” This can be rephrased as “Harry did not pass the test” And “Ron did not pass
the test.”

Distributive Property
A proposition with two elements that are grouped with And or Or connectives can be distributed, or
broken down into, smaller units consisting of And and Or.

Knowledge and Search Problems

Inference can be viewed as a search problem with the following properties:

 Initial state: starting knowledge base

 Actions: inference rules

 Transition model: new knowledge base after inference

  Goal test: checking whether the statement that we are trying to prove is in the KB

 Path cost function: the number of steps in the proof

This shows just how versatile search algorithms are, allowing us to derive new information based on
existing knowledge using inference rules.

Resolution

Resolution is a powerful inference rule that states that if one of two atomic propositions in an Or
proposition is false, the other has to be true. For example, given the proposition “Ron is in the Great
Hall” Or “Hermione is in the library”, in addition to the proposition “Ron is not in the Great Hall,” we
can conclude that “Hermione is in the library.” More formally, we can define resolution the following
way:

Resolution relies on Complementary Literals, two of the same atomic propositions where one is
negated and the other is not, such as P and ¬P.

Resolution can be further generalized. Suppose that in addition to the proposition “Ron is in the
Great Hall” Or “Hermione is in the library”, we also know that “Ron is not in the Great Hall” Or
“Harry is sleeping.” We can infer from this, using resolution, that “Hermione is in the library” Or
“Harry is sleeping.” To put it in formal terms:
Complementary literals allow us to generate new sentences through inferences by resolution. Thus,
inference algorithms locate complementary literals to generate new knowledge.

A Clause is a disjunction of literals (a propositional symbol or a negation of a propositional symbol,

connective (P ∨ Q ∨ R). A conjunction, on the other hand, consists of propositions that are
such as P, ¬P). A disjunction consists of propositions that are connected with an Or logical

connected with an And logical connective (P ∧ Q ∧ R). Clauses allow us to convert any logical

∨ B ∨ C) ∧ (D ∨ ¬E) ∧ (F ∨ G).
statement into a Conjunctive Normal Form (CNF), which is a conjunction of clauses, for example: (A

Steps in Conversion of Propositions to Conjunctive Normal Form

 Eliminate biconditionals

o Turn (α β) into (α → β) ∧ (β → α).

 Eliminate implications

o Turn (α → β) into ¬α ∨ β.

 Move negation inwards until only literals are being negated (and not clauses), using De
Morgan’s Laws.

o Turn ¬(α ∧ β) into ¬α ∨ ¬β

Here’s an example of converting (P ∨ Q) → R to Conjunctive Normal Form:

 (P ∨ Q) → R

 ¬(P ∨ Q) ∨ R /Eliminate implication

 (¬P ∧ ¬Q) ∨ R /De Morgan’s Law

 (¬P ∨ R) ∧ (¬Q ∨ R) /Distributive Law

At this point, we can run an inference algorithm on the conjunctive normal form. Occasionally,
through the process of inference by resolution, we might end up in cases where a clause contains

removed. For example, (P ∨ Q ∨ S) ∧ (¬P ∨ R ∨ S) allow us to infer by resolution that (Q ∨ S ∨ R ∨

the same literal twice. In these cases, a process called factoring is used, where the duplicate literal is

S). The duplicate S can be removed to give us (Q ∨ R ∨ S).

Resolving a literal and its negation, i.e. ¬P and P, gives the empty clause (). The empty clause is
always false, and this makes sense because it is impossible that both P and ¬P are true. This fact is
used by the resolution algorithm.

 To determine if KB ⊨ α:

o Check: is (KB ∧ ¬α) a contradiction?

 If so, then KB ⊨ α.

 Otherwise, no entailment.

Proof by contradiction is a tool used often in computer science. If our knowledge base is true, and it
contradicts ¬α, it means that ¬α is false, and, therefore, α must be true. More technically, the
algorithm would perform the following actions:

 To determine if KB ⊨ α:

o Convert (KB ∧ ¬α) to Conjunctive Normal Form.

o Keep checking to see if we can use resolution to produce a new clause.

arrived at a contradiction, thus proving that KB ⊨ α.

o If we ever produce the empty clause (equivalent to False), congratulations! We have

o However, if contradiction is not achieved and no more clauses can be inferred, there
is no entailment.

Here is an example that illustrates how this algorithm might work:

 Does (A ∨ B) ∧ (¬B ∨ C) ∧ (¬C) entail A?

First, to prove by contradiction, we assume that A is false. Thus, we arrive at (A ∨ B) ∧ (¬B ∨

C) ∧ (¬C) ∧ (¬A).


way (¬B ∨ C) can be true is if B is false, too. Thus, we can add (¬B) to our KB.
 Now, we can start generating new information. Since we know that C is false (¬C), the only

 Next, since we know (¬B), the only way (A ∨ B) can be true is if A is true. Thus, we can add
(A) to our KB.

 Now our KB has two complementary literals, (A) and (¬A). We resolve them, arriving at the
empty set, (). The empty set is false by definition, so we have arrived at a contradiction.

First Order Logic

First order logic is another type of logic that allows us to express more complex ideas more
succinctly than propositional logic. First order logic uses two types of symbols: Constant
Symbols and Predicate Symbols. Constant symbols represent objects, while predicate symbols are
like relations or functions that take an argument and return a true or false value.
For example, we return to the logic puzzle with different people and house assignments at
Hogwarts. The constant symbols are people or houses, like Minerva, Pomona, Gryffindor, Hufflepuff,
etc. The predicate symbols are properties that hold true or false of some constant symbols. For
example, we can express the idea that Minerva is a person using the sentence Person(Minerva).
Similarly, we can express the idea the Gryffindor is a house using the sentence House(Gryffindor). All
the logical connectives work in first order logic the same way as before. For example,
¬House(Minerva) expresses the idea that Minerva is not a house. A predicate symbol can also take
two or more arguments and express a relation between them. For example, BelongsTo expresses a
relation between two arguments, the person and the house to which the person belongs. Thus, the
idea that Minerva belongs to Gryffindor can be expressed as BelongsTo(Minerva, Gryffindor). First
order logic allows having one symbol for each person and one symbol for each house. This is more
succinct than propositional logic, where each person—house assignment would require a different
symbol.

Universal Quantification

specific constant symbol. Universal quantification uses the symbol ∀ to express “for all.” So, for
Quantification is a tool that can be used in first order logic to represent sentences without using a

example, the sentence ∀x. BelongsTo(x, Gryffindor) → ¬BelongsTo(x, Hufflepuff) expresses the idea
that it is true for every symbol that if this symbol belongs to Gryffindor, it does not belong to
Hufflepuff.

Existential Quantification

Existential quantification is an idea parallel to universal quantification. However, while universal

to create sentences that are true for at least one x. It is expressed using the symbol ∃. For example,
quantification was used to create sentences that are true for all x, existential quantification is used

the sentence ∃x. House(x) ∧ BelongsTo(Minerva, x) means that there is at least one symbol that is
both a house and that Minerva belongs to it. In other words, this expresses the idea that Minerva
belongs to a house.

∀x. Person(x) → (∃y. House(y) ∧ BelongsTo(x, y)) expresses the idea that if x is a person, then there
Existential and universal quantification can be used in the same sentence. For example, the sentence

is at least one house, y, to which this person belongs. In other words, this sentence means that every
person belongs to a house.

There are other types of logic as well, and the commonality between them is that they all exist in
pursuit of representing information. These are the systems we use to represent knowledge in our AI