Grokking Modern System Design Interview for Engineers & Managers
Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.
To understand why we should use first-order logic (FOL), we must first understand the need for it and background behind it.
Propositional logic (PL) is declarative, so it guides us on how to represent information in a logical form and draw conclusions.
We can only represent information as either
true
orfalse
in propositional logic.
If you want to represent complicated sentences or natural language statements, PL is not sufficient.
There is very limited expressive power in PL, so we use
The sentence shown below cannot be represented we cannot using PL logic.
I love mankind. It’s the people I can’t stand!
Joe Root likes football.
I like to eat mangos.
PL is not enough to represent the sentences above, so we require powerful logic (such as FOL).
FOL is a mode of representation in Artificial Intelligence. It is an extension of PL.
FOL represents natural language statements in a concise way.
FOL is also called predicate logic. It is a powerful language used to develop information about an object and express the relationship between objects.
FOL not only assumes that does the world contains facts (like PL does), but it also assumes the following:
Objects: A, B, people, numbers, colors, wars, theories, squares, pit, etc.
Relations: It is unary relation such as red, round, sister of, brother of, etc.
Function: father of, best friend, third inning of, end of, etc.
FOL also has two parts:
The syntax of FOL decides which collection of symbols is a logical expression.
The basic syntactic elements of FOL are symbols. We use symbols to write statements in shorthand notation.
Name | Symbol |
Constant | 1, 6, A,W,New York, Elie, Dog... |
Variables | a, b, c, x, y, z... |
Predicates | <, >, brother, sister, father... |
Equality | == |
Function | Sqrt, LessThan, Sin(θ)... |
Quantifier | ∀, ∃ |
Connectives | ∧, ∨, ¬, ⇒, ⇔ |
This is a basic sentence of FOL formed from a predicate symbol followed by a parenthesis with a sequence of terms.
We can represent atomic sentences as a predicate (value1, value2…., value n).
John and Michael are colleagues → Colleagues (John, Michael)
German Shepherd is a dog → Dog (German Shepherd)
Complex sentences are made by combining atomic sentences using connectives.
FOL is further divided into two parts:
Subject: the main part of the statement.
Predicate: defined as a relation that binds two atoms together.
Colleague (Oliver, Benjamin) ∧
Colleague (Benjamin, Oliver)
“x is an integer”
It has two parts;
x
is the subject.“is an integer”
is called a predicate.Propositional logic assumes that some facts exist that can either hold or do not hold.
The universe consists of multiple objects with certain relations among them that can either hold or do not hold.
There are other special-purpose logics that support FOL:
Quantifiers generate quantification and specify the number of specimen in the universe.
Quantifiers allow us to determine or identify the range and scope of the variable in a logical expression.
There are two types of quantifiers:
Universal quantifier: for all, everyone, everything.
Existential quantifier: for some, at least one.
Universal quantifiers specify that the statement within the range is true
for everything or every instance of a particular thing.
Universal quantifiers are denoted by a symbol (∀
) that looks like an inverted A. In a universal quantifier, we use →
.
If x
is a variable, then ∀x
can read as:
x
x
x
Every Student Likes Educative.
So, in logical notation, it can be written as:
∀x student(x) → likes(x, Educative)
This can be interpreted as: There is every x where x is a student who likes Educative.
Existential quantifiers are used to express that the statement within their scope is true for at least one instance of something.
∃
, which looks like an inverted E, is used to represent them. We always use AND
or conjunction symbols.
If x
is a variable, the existential quantifier will be ∃x
:
x
x
x
Some people like Football.
So, in logical notation, it can be written as:
∃x: people(x) ∧ likes Football(x)
It can be interpreted as: There are some x where x is people who like football.
We can use both quantifiers together, but it’s not a type of quantifier; rather, it’s an outlier category.
These quantifiers can be represented using the ∃x∀x
signs.
Here are some examples to understand this type of quantifier.
∃xy ∀x ∀y((x< 0) ∧ (y< 0) → (xy = 8))
This can be interpreted as:
For every real number x
and y
∈ ℝ
, if x
is negative and y
is also negative, implies for some values of xy
must be equal to 8
.
RELATED TAGS
CONTRIBUTOR
Grokking Modern System Design Interview for Engineers & Managers
Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.