What is meant by first-order logic?

Explain o as a natural language, first-order logic also has o Subject: Subject is the main part of the
syntax and semantics of first order logic. two main parts: statement.
o First-order logic is another way of knowledge a. Syntax o Predicate: A predicate can be defined as a
representation in artificial intelligence. It is an b. Semantics relation, which binds two atoms together in a
extension to propositional logic. Syntax of First-Order logic: statement.
o FOL is sufficiently expressive to represent the The syntax of FOL determines which collection of Consider the statement: "x is an integer.", it
natural language statements in a concise way. symbols is a logical expression in first-order consists of two parts, the first part x is the subject
o First-order logic is also known as Predicate logic. The basic syntactic elements of first-order of the statement and second part "is an integer," is
logic or First-order predicate logic. First-order logic are symbols. We write statements in short- known as a predicate.
logic is a powerful language that develops hand notation in FOL.
information about the objects in an easier way and Basic Elements of First-order logic:
can also express the relationship between those Following are the basic elements of FOL syntax:
objects.
o First-order logic (like natural language) does
not only assume that the world contains facts like Atomic sentences:
propositional logic but also assumes the following o atomic sentences are the most basic sentences
things in the world: of first-order logic. These sentences are formed
o Objects: A, B, people, numbers, colors, wars, from a predicate symbol followed by a parenthesis Quantifiers in First-order logic:
theories, squares, pits, wumpus, ...... with a sequence of terms. o A quantifier is a language element which
o Relations: It can be unary relation such as: o An atomic sentence is true in a given model if generates quantification, and quantification
red, round, is adjacent, or n-any relation such as: the relation referred to by the predicate symbol specifies the quantity of specimen in the universe
the sister of, brother of, has color, comes between holds among the objects referred to by the of discourse.
o Function: Father of, best friend, third inning of, arguments. o These are the symbols that permit to determine
end of, ...... o We can represent atomic sentences as or identify the range and scope of the variable in
Predicate (term1, term2, ......, term n). the logical expression.
Example: Ravi and Ajay are Brothers: => There are two types of quantifiers:
Brothers(Ravi, Ajay) a. Universal Quantifier, (for all, everyone,
Chinky is a cat: => cat (Chinky). everything)
b. Existential quantifier, (for some, at least
Complex Sentences: one).
o Complex sentences are made by combining
atomic sentences using connectives. Universal Quantifier:
o We can use logical connectives to construct Universal quantifier is a symbol of logical
more complex sentences, with the representation, which specifies that the statement
same syntax and semantics as in propositional within its range is true for everything or every
calculus. instance of a particular thing.
First-order logic statements can be divided into The Universal quantifier is represented by a
two parts: symbol ∀, which resembles an inverted A.
Note: In universal quantifier we use implication formal representation of the objects, is known as This pins down the meaning of the terms,
"→". knowledge engineer. enabling the expert to check the content.
If x is a variable, then ∀x is read as: In this topic, we will understand the Knowledge ⎯ Often, this step reveals misconceptions or
o For all x engineering process in an electronic circuit gaps in the vocabulary that must be
o For each x domain. This approach is mainly suitable for fixed by returning to step 3 and iterating through
o For every x. creating special-purpose knowledge base. the process.
Example: 5. Encode description of problem instance:
All man drink coffee. Following steps are follows for the knowledge ⎯ Of the ontology is well throughout, this step
∀x man(x) → drink (x, coffee). engineering process: will easy.
It will be read as: There are all x where x is a man 1. Identify the task: ⎯ It will involve writing simple automatic
who drink coffee. ⎯ the knowledge engineer must delineate the sentence about instances of concepts that are
range of questions that the knowledge base will already part of the ontology.
Existential Quantifier: support and the kinds of fact that will be available 6. Pose queries to the interface procedure and
Existential quantifiers are the type of quantifiers, for each specific problem instance. get the answer:
which express that the statement within its scope ⎯ This step is analogous to the PEAS process ⎯ This is where the reward is: we can let the
is true for at least one instance of something. for designing agents. interface procedure operate on the
It is denoted by the logical operator ∃, which 2. Assemble the relevant knowledge: axioms and problem=specific facts to derive the
resembles as inverted E. When it is used with a ⎯ The knowledge engineer might already be an facts we are interested in knowing.
predicate variable then it is called as an existential expert in the domain, or might need to work with ⎯ Thus, we avoid the need for writing an
quantifier. real expert to extract what they know- a process application-specific solution algorithm.
Note: In Existential quantifier we always use AND called knowledge acquisition 7. Debug the knowledge base:
or Conjunction symbol (∧). ⎯ At this stage, the scope of the knowledge is not ⎯ In this step debugging of the knowledge
If x is a variable, then existential quantifier will be represented formally. based takes place.
∃x or ∃(x). And it will be read as: ⎯ The idea is to understand the scope of the ⎯ This is last step of complete process; in this step
o There exists a 'x.' knowledge base, as determined by the task, and to we will try to debug the issue of knowledge.
o For some 'x.' understand how the domain actually works.
o For at least one 'x.' 3. Decide on vocabulary: FOL inference rules for quantifier:
Example: ⎯ That is, translate the important domain-level As propositional logic we also have inference
Some boys are intelligent. concepts into logic-level names. rules in first-order logic, so following are some
∃x: boys(x) ∧ intelligent(x) ⎯ This involves many questions of knowledge- basic inference rules in FOL:
It will be read as: There are some x where x is a engineering style. o Universal Generalization
boy who is intelligent. ⎯ Like programming style. This can have a o Universal Instantiation
significant impact on the eventual o Existential Instantiation
What is knowledge-engineering? success of the project. o Existential introduction
The process of constructing a knowledge-base in 4. Encode general- knowledge about the
first-order logic is called as knowledge- domain: 1. Universal Generalization:
engineering. In knowledge-engineering, someone ⎯ The knowledge engineer writes down the o Universal generalization is a valid inference
who investigates a particular domain, learns axioms for all the vocabulary terms. rule which states that if premise P(c) is true for
important concept of that domain, and generates a any arbitrary element c in the universe of
discourse, then we can have a conclusion as ∀ x o This rule states that one can infer P(c) from the o Predicate symbol must be same, atoms or
P(x). formula given in the form of ∃x P(x) for a new expression with different predicate symbol can
o It can be represented as:. constant symbol c. never be unified.
o This rule can be used if we want to show that o The restriction with this rule is that c used in o Number of Arguments in both expressions
every element has a similar property. the rule must be a new term for which P(c ) is must be identical.
o in this rule, x must not appear as a free variable. true.
o It can be represented as: o Unification will fail if there are two similar
Example: Let's represent, P(c): "A byte contains variables present in the same expression.
8 bits", so for ∀ x P(x) "All bytes contain 8 What is Unification?
bits.", it will also be true. o Unification is a process of making two different Forward Chaining:
logical atomic expressions identical by finding a Forward chaining is also known as a forward
2. Universal Instantiation: substitution. Unification depends on the deduction or forward reasoning method when
o Universal instantiation is also called as substitution process. using an inference engine. Forward chaining is a
universal elimination or UI is a valid inference o It takes two literals as input and makes them
form of reasoning which start with atomic
rule. It can be applied multiple times to add new sentences in the knowledge base and applies
identical using substitution.
sentences. inference rules (Modus Ponens) in the forward
o Let Ψ1 and Ψ2 be two atomic sentences and 𝜎
o the new KB is logically equivalent to the
direction to extract more data until a goal is
be a unifier such that, Ψ1𝜎 = Ψ2𝜎, then it can be
reached.
previous KB. expressed as UNIFY(Ψ1, Ψ2).
The Forward-chaining algorithm starts from
o as per UI, we can infer any sentence obtained o Example: Find the MGU for Unify{King(x),
known facts, triggers all rules whose premises are
by substituting a ground term for the variable. King(John)} satisfied, and add their conclusion to the known
o The UI rule state that we can infer any sentence Let Ψ1 = King(x), Ψ2 = King(John),
facts. This process repeats until the problem is
P(c) by substituting a ground term c (a constant Substitution θ = {John/x} is a unifier for these
solved.
within domain x) from ∀ x P(x) for any object in atoms and applying this substitution, and both
Properties of Forward-Chaining:
the universe of discourse. expressions will be identical.
o It is a down-up approach, as it moves from
o It can be represented as:. o The UNIFY algorithm is used for unification,
bottom to top.
Example:1. which takes two atomic sentences and returns a
o It is a process of making a conclusion based on
IF "Every person like ice-cream"=>∀x P(x) so we unifier for those sentences (If any exist).
known facts or data, by starting from the initial
can infer that "John likes ice-cream" => P(c) o Unification is a key component of all first-order
state and reaches the goal state.
inference algorithms.
o Forward-chaining approach is also called as
3. Existential Instantiation: o It returns fail if the expressions do not match
data-driven as we reach to the goal using available
o Existential instantiation is also called as with each other. data.
Existential Elimination, which is a valid inference o The substitution variables are called Most
o Forward -chaining approach is commonly used
rule in first-order logic. General Unifier or MGU.
in the expert system, such as CLIPS, business, and
o It can be applied only once to replace the
production rule systems.
existential sentence. Conditions for Unification:
o The new KB is not logically equivalent to old Following are some basic conditions for
Backward Chaining:
KB, but it will be satisfiable if old KB was unification:
Backward-chaining is also known as a backward
satisfiable. deduction or backward reasoning method when
using an inference engine. A backward chaining What is planning in AI? o Knowledge representation and reasoning (KR,
algorithm is a form of reasoning, which starts with -Planning in artificial intelligence is about decision- KRR) is the part of Artificial intelligence which
the goal and works backward, chaining through making actions performed by robots or computer concerned with AI agents thinking and how
rules to find known facts that support the goal. programs to achieve a specific goal. thinking contributes to intelligent behaviour of
Properties of backward chaining: -Execution of the plan is about choosing a sequence agents.
o It is known as a top-down approach. of tasks with a high probability of accomplishing a o It is responsible for representing information
o Backward-chaining is based on modus ponens specific task. about the real world so that a computer can
-There is one more definition of planning which
inference rule. understand and can utilize this knowledge to solve
says that planning is an activity where agent has to
the complex real-world problems such as
come up with sequence of action to accomplish the
o in backward chaining, the goal is broken into diagnosis a medical condition or communicating
target.
sub-goal or sub-goals to prove the facts true. -Here we have information about the initial status of with humans in natural language.
o It is called a goal-driven approach, as a list of agent, goal condition of agent and set of action an o It is also a way which describes how we can
goals decides which rules are selected and used. agent can take. represent knowledge in artificial intelligence.
o Backward -chaining algorithm is used in game -Aim of agent is to find the proper sequence of Knowledge representation is not just storing data
theory, automated theorem proving tools, action which will lead from start to goal state and into some database, but it also enables an
inference engines, proof assistants, and various AI produce an efficient solution. intelligent machine to learn from that knowledge
applications. -A planning agent that interacts with environment and experiences so that it can behave intelligently
o the backward-chaining method mostly used a using sensors and actuators. like a human.
depth-first search strategy for proof. When task comes to agent it has to decide the
sequence of actions to be taken and then accordingly What to Represent:
execute action. Following are the kind of knowledge which needs to
Convert following into predicate form. -Planning problem, 1) the states of an agent correspond be represented in AI systems:
1) Virat is software engineer. to the probable surrounding environment while action o Object: All the facts about objects in our world
Ans. Virat(software engineer) and goal of an agent are specified based on logical domain. E.g., Guitars contains strings, trumpets are
formulation. 2) To achieve any goal an agent has to brass instruments.
2) All vehicles have wheels.
answer few questions like what o Events: Events are the actions which occur in
Ans. For-all(x): vehicles(x) -> wheel(x)
will be the effect of its action, how it will affect the our world.
3) Some -one speaks some language in class. upcoming action. o Performance: It describe behaviour which
Ans. ∃ x ∃ y: person(x) v language(y)-> speaks(x,
y) involves knowledge about how to do things.
What is knowledge representation? o Meta-knowledge: It is knowledge about what
4) Everybody loves somebody sometimes. Humans are best at understanding, reasoning, and
Ans. (for all(x) (exists(y) -> loves sometime(x, we know.
interpreting knowledge. Human knows things, o Facts: Facts are the truths about the real world
y))) which is knowledge and as per their knowledge
5) All software engineer develops software. and what we represent.
they perform various actions in the real world. o Knowledge-Base: The central component of
Ans. For-all(x):software(x) -> software But how machines do all these things comes
engineer(y) the knowledge-based agents is the knowledge
under knowledge representation and base. It is represented as KB. The Knowledgebase
reasoning. Hence, we can describe Knowledge is a group of the Sentences (Here, sentences are
representation as following: used as a technical term and not identical with the
English language).
 o It describes the relationship that exists between accessions of having continuous actions such as
Knowledge: Knowledge is awareness or concepts or objects. filling a bucket of water, solving a puzzle, etc.
familiarity gained by experiences of facts, data, Situation calculus can only specify condition at the
and situations. Following are the types of Write note on planning graph: start of the action and at the end of actions; but it
knowledge in artificial intelligence: • Each level contains a set of literals and a set of cannot represent what happed during the action was
Types of knowledge: actions: taking place. Considering the same example,
Following are the various types of knowledge: 1. Literals - These are all the things that could situation calculus will specify that, bucket was
1.Declarative Knowledge: empty at the start of action and at the end bucket is
be true at a time step. They depend on the full.
o Declarative knowledge is to know about actions executed at the preceding time step. One more limitation of situation calculus is that it
something.
2. Actions - These are all the actions that cannot represent simultaneous action. E.g., writing
o It includes concepts, facts, and objects.
could have their preconditions satisfied at a assignment while watching tv program. To handle
o It is also called descriptive knowledge and
time step. They depend on which literals such things, we have event calculus.
expressed in declarative sentences.
hold. Event calculus is based on time points instead of
o It is simpler than procedural language.
• Planning graph is a special data structure which is only start state and end state. Event can be
2. Procedural Knowledge described as instance of the event category. Event
o It is also known as imperative knowledge. used to get better accuracy. It is directed graph and
is useful to accomplish improved heuristic calculus consist of event and fluent. Fluent are the
o Procedural knowledge is a type of knowledge object to represents fact but do not specify its
estimates.
which is responsible for knowing how to do truthfulness.
• Any of the search technique can make use of
something. planning graph. Also, GRAPHPLAN can
o It can be directly applied to any task. be used to extract a solution directly. Write note on semantic network.
o It includes rules, strategies, procedures, • Planning graph works only for propositional Semantic nets provide graphical representation of
agendas, etc. problems without variable. knowledgebase and efficient
o Procedural knowledge depends on the task on • Similarly, in case of planning graph there are series algorithms provide inferences from the mental
which it can be applied. of levels which match to time ladle objects on the basis of category membership
3. Meta-knowledge: in the plan. every level has set of literals and a set of and decides subset superset relationships among
o Knowledge about the other types of knowledge actions. the categories.
is called Meta-knowledge. • Level 0 is the initial state of planning graph. A semantic net or semantic network is a
4. Heuristic knowledge: • Properties of planning graph: knowledge representation technique used for
o Heuristic knowledge is representing knowledge ⎯ If goal is absent from last level, then goal cannot propositional information, so it is also called a
of some experts in a filed or subject. be achieved. propositional net. In semantic networks
o Heuristic knowledge is rules of thumb based on ⎯ If there exist a path to goal the goal is present in the knowledge is represented as objects and
previous experiences, awareness of approaches, the last level.
relationships between objects.
and which are good to work but not guaranteed. ⎯ If goal is present in last then there may not exist
• They are two dimensional representations of
any path.
5. Structural knowledge: knowledge. It conveys meaning.
o Structural knowledge is basic knowledge to Relationships provide the basic structure for
What are events? Explain its importance.
problem-solving. We can represent situation of real world by organizing knowledge.
o It describes relationships between various specifying date, time, place, related people and • It uses graphical notations to draw the networks.
concepts such as kind of, part of, and grouping of many other related objects. But there are many Mathematically a semantic net can be
something.
defined as a labelled directed graph. As nodes are A truth maintenance system maintains There are two types of justification for a node.
associated with other nodes semantic consistency between old believed knowledge They are:
nets are also referred to as associative nets. and current believed knowledge in the knowledge 1. Support list [SL]
• Semantic nets consist of nodes, links and link base (KB) through revision. If the current 2. Conditional proof (CP)
labels. Nodes of the graph denote object believed statements contradict the knowledge in Many kinds of truth maintenance systems exist.
while the links indicate relations among the the KB, then the KB is updated with the new Two major types are single-context and multi-
objects. knowledge. context truth maintenance. In single context
• Nodes can appear as circles, ellipses, or It may happen that the same data will again be systems, consistency is maintained among all
rectangle to represent objects such as physical believed, and the previous knowledge will be facts in memory (KB) and relates to the notion of
objects, concepts or situations. Links are drawn as required in the KB. If the previous data are not consistency found in classical logic.
arrows to express the relationships between present, but may be required for new inference. Multi-context systems support Para consistency
objects, and link labels specify specifications of But if the previous knowledge was in the KB, by allowing consistency to be relevant to a subset
relationships. then no retracing of the same knowledge is of facts in memory, a context, according to the
• The two nodes connected to each other via a link needed. history of logical inference.
are related to each other. The The use of TMS avoids such retracing; it keeps
relationships can be of two types: "IS-A" track of the contradictory data with the help of a Write PDDL description of an air cargo
relationship or "HAS" relationship. IS-A dependency record. This record reflects the transportation planning problem.
relationship stands for one object being "part of" retractions and additions which makes the • Planning Domain Definition Language
the other related object and “HAS” inference engine (IE) aware of its current belief (PDDL)
relationship indicates one object “consists of” the set. • Standard encoding language for “classical”
other related object. Each statement having at least one valid planning tasks Components of a PDDL
justification is made a part of the current belief planning task:
set.
o Objects: Things in the world that interest us.
When a contradiction is found, the statement(s)
responsible for the contradiction are identified and o Predicates: Properties of objects that we are
the records are appropriately updated. This interested in; can be true or false.
process is called dependency-directed o Initial state: The state of the world that we
backtracking. start in.
The TMS algorithm maintains the records in o Goal specification: Things that we want to be
the form of a dependency network. Each true.
node in the network is an entry in the KB (a o Actions/Operators: Ways of changing the
premise, antecedent, or inference rule etc.) Each state of the world.
arc of the network represents the inference steps
through which the node was derived. Init (At(C1, SFO) ∧ At(C2, JFK) ∧ At(P1, SFO)
A premise is a fundamental belief which is ∧ At(P2, JFK)
assumed to be true. They do not need
∧ Cargo(C1) ∧ Cargo(C2) ∧ Plane(P1) ∧
justifications. The set of premises are the basis
Plane(P2)
from which justifications for all other nodes will
be derived.
∧ Airport (JFK) ∧ Airport (SFO))
Write note on Truth maintenance system.
Goal (At(C1, JFK) ∧ At(C2, SFO)) is In a plane; the cargo only becomes At the
Action(Load (c, p, a), new airport when it is unloaded. So At
PRECOND: At(c, a) ∧ At(p, a) ∧ Cargo(c) ∧ really means “available for use at a given
Plane(p) ∧ Airport (a) location.”
EFFECT: ￢ At(c, a) ∧ In(c, p))
Action(Unload(c, p, a), V. The following plan is a solution to the
PRECOND: In(c, p) ∧ At(p, a) ∧ Cargo(c) ∧ problem:
Plane(p) ∧ Airport (a) [Load (C1, P1, SFO), Fly (P1, SFO, JFK),
EFFECT: At(c, a) ∧ ￢In(c, p)) Unload (C1, P1, JFK),
Action(Fly(p, from, to), Load (C2, P2, JFK), Fly (P2, JFK, SFO),
PRECOND: At(p, from) ∧ Plane(p) ∧ Airport Unload (C2, P2, SFO)].
(from) ∧ Airport (to)
VI. Finally, there is the problem of spurious
EFFECT: ￢ At(p, from) ∧ At(p, to))
actions such as Fly (P1, JFK, JFK), which
should be a no-op, but which has contradictory
I.Figure shows an air cargo transport problem
effects (according to the definition, the
involving loading and unloading cargo
effect would include At(P1, JFK) ∧ ￢At(P1,
and flying it from place to place. The problem
can be defined with three actions: JFK)). It is common to ignore such
Load, Unload, and Fly. problems, because they seldom cause incorrect
plans to be produced. The correct
II. The actions affect two predicates: In(c, p) approach is to add inequality preconditions
means that cargo c is inside plane p, and saying that the from and to airports must
At(x, a) means that object x (either plane or be different.
cargo) is at airport a. Note that some care
must be taken to make sure the At predicates are
maintained properly.

III. When a plane flies from one airport to

IV. But basic PDDL does not have a universal