Knowledge Representation and First-Order Logic in Artificial Intelligence

Fundamentals of First-Order Logic

• Limitations of Propositional Logic (PL):

  • Propositional logic only represents atomic facts that evaluate strictly to either true or false.

  • It lacks the expressive power needed to represent complex sentences, general assertions, or natural language statements.

  • Natural language statements such as "Some humans are intelligent" or "Sachin likes cricket" cannot be captured adequately using propositional logic due to the absence of variables, relations, and quantifiers.

• Definition and Role of First-Order Logic (FOL):

  • First-order logic is an expressive formal system and an extension of propositional logic designed for knowledge representation in artificial intelligence.

  • It is also referred to as Predicate Logic or First-Order Predicate Logic.

  • FOL provides sufficient expressiveness to translate natural language statements into concise, formalized symbolic structures.

  • It facilitates reasoning about discrete objects in a domain and explicitly models the relationships that hold between those objects.

• Ontological Commitments of First-Order Logic:

  • Unlike propositional logic, which assumes only the existence of basic facts in the world, first-order logic models the world using three distinct ontological categories:

  • Objects: Concrete or abstract entities, such as $A$, $B$, people, numbers, colors, wars, theories, squares, and pits.

  • Relations: Properties of or connections between objects. These can be:

    • Unary relations (properties of a single object): e.g., $red$, $round$, $is\text{ }adjacent$.

    • $n$-ary relations (connections among two or more objects): e.g., $the\text{ }sister\text{ }of$, $brother\text{ }of$, $has\text{ }color$, $comes\text{ }between$.

  • Functions: Specialized relations that map an object or tuple of objects to exactly one output value: e.g., $Father\text{ }of$, $best\text{ }friend$, $third\text{ }inning\text{ }of$, $end\text{ }of$.

• Core Divisions of First-Order Logic:

  • Syntax: Governs the formal rules determining which sequences and collections of symbols constitute valid logical expressions and well-formed formulas.

  • Semantics: Dictates the meaning and truth evaluations of expressions with respect to a given domain of discourse.

Syntax and Structure of First-Order Logic

• Basic Syntactic Elements:

  • Statements in FOL are constructed from foundational symbolic elements:

  • Constants: Symbols representing specific individual entities in the domain (e.g., $1$, $2$, $A$, $John$, $Mumbai$, $cat$).

  • Variables: Placeholders that range over individual entities in the universe of discourse (e.g., $x$, $y$, $z$, $a$, $b$).

  • Predicates: Symbols denoting relations or attributes that evaluate to a boolean truth value (e.g., $Brother$, $Father$, $>$).

  • Functions: Operators that take one or more arguments and return an object entity rather than a truth value (e.g., $sqrt$, $LeftLegOf$).

  • Logical Connectives: Operators used to link sentences together (conjunction $\wedge$, disjunction $\vee$, negation $\neg$, material implication $\Rightarrow$, bi-conditional equivalence $\Leftrightarrow$).

  • Equality: Operator asserting identity between two terms ($==$ or $=$).

  • Quantifiers: Operators expressing scope and generality over variables (universal quantifier $\forall$, existential quantifier $\exists$).

• Sentence Classifications:

  • Atomic Sentences:

  • The most fundamental building blocks of FOL.

  • Constructed using a predicate symbol followed by an ordered list of terms enclosed in parentheses:       $Predicate(term_1, term_2, \dots, term_n)$

  • Examples:

    • "Ravi and Ajay are brothers":         $Brothers(Ravi, Ajay)$

    • "Chinky is a cat":         $cat(Chinky)$

  • Complex Sentences:

  • Sentences constructed by combining one or more atomic sentences using logical connectives ($\wedge$, $\vee$, $\neg$, $\Rightarrow$, $\Leftrightarrow$).

• Constituent Components of an FOL Statement:

  • Subject: The primary object or entity under consideration within the assertion.

  • Predicate: The relation, property, or action that binds atoms together or qualifies the subject.

  • For example, in the statement "$x$ is an integer":

  • $x$ serves as the subject.

  • "is an integer" serves as the predicate.

Quantifiers in First-Order Logic

• General Principles of Quantification:

  • A quantifier is a syntactic element that defines the quantity of specimens within the universe of discourse (UOD) for which a given statement holds.

  • Quantifiers define the scope and validity range of variables in logical expressions.

  • There are two fundamental types of quantifiers: universal quantifiers and existential quantifiers.

• Universal Quantifier ($\forall$):

  • Symbolized as $\forall$ (resembling an inverted letter "A").

  • Asserts that a specified statement is strictly true for every entity or instance within the universe of discourse.

  • Reading conventions for $\forall x$:

  • "For all $x$"

  • "For each $x$"

  • "For every $x$"

  • The primary logical connective associated with the universal quantifier is implication ($\rightarrow$ or $\Rightarrow$).

  • Universal Expansion Example:

  • Statement: "All man drink coffee."

  • Variable definition: Let variable $x$ denote an entity in the universe of discourse.

  • FOL representation:       $\forall x\, (man(x) \rightarrow drink(x, coffee))$

  • Reading: "For all $x$, if $x$ is a man, then $x$ drinks coffee."

  • Expanded interpretation across domain instances ($x_1, x_2, x_3, \dots, x_n$) in the Universe of Discourse "Man":       $(x_1\text{ drinks coffee}) \wedge (x_2\text{ drinks}) \wedge (x_3\text{ drinks milk}) \wedge \dots \wedge (x_n\text{ drinks milk})$

• Existential Quantifier ($\exists$):

  • Symbolized as $\exists$ (resembling an inverted letter "E").

  • Asserts that a statement is true for at least one instance or specimen within the universe of discourse.

  • Reading conventions for $\exists x$:

  • "There exists an $x$"

  • "For some $x$"

  • "For at least one $x$"

  • The primary logical connective associated with the existential quantifier is conjunction ($\wedge$).

  • Existential Expansion Example:

  • Statement: "Some boys are intelligent."

  • FOL representation:       $\exists x\, (boys(x) \wedge intelligent(x))$

  • Reading: "There exists an $x$ such that $x$ is a boy and $x$ is intelligent."

  • Expanded interpretation across domain instances ($x_1, x_2, x_3, \dots, x_n$) in the Universe of Discourse "Boys":       $(x_1\text{ is intelligent}) \vee (x_2\text{ is intelligent}) \vee (x_3\text{ is intelligent}) \vee \dots \vee (x_n\text{ is intelligent})$

• Algebraic Properties and Equivalences of Quantifiers:

  • Commutativity of identical quantifiers:

  • Universal quantifiers commute:       $\forall x\, \forall y \equiv \forall y\, \forall x$

  • Existential quantifiers commute:       $\exists x\, \exists y \equiv \exists y\, \exists x$

  • Non-commutativity of mixed quantifiers:

  • Reversing mixed quantifiers changes logical meaning:       $\exists x\, \forall y \not\equiv \forall y\, \exists x$

• Standard Translation Examples:

  • "All birds fly":

  • Predicate definition: $fly(bird)$.

  • Formulation:       $\forall x\, (bird(x) \rightarrow fly(x))$

  • "Every man respects his parent":

  • Predicate definition: $respects(x, y)$, where $x$ is a man and $y$ is a parent.

  • Formulation:       $\forall x\, (man(x) \rightarrow respects(x, parent))$

  • "Some boys play cricket":

  • Predicate definition: $play(x, y)$, where $x$ is a boy and $y$ is cricket.

  • Formulation:       $\exists x\, (boys(x) \rightarrow play(x, cricket))$

  • "Not all students like both Mathematics and Science":

  • Predicate definition: $like(x, y)$, where $x$ is a student and $y$ is an academic subject.

  • Formulation:       $\neg \forall x\, [student(x) \rightarrow (like(x, Mathematics) \wedge like(x, Science))]$

Expert Systems and Inference Engines

• Overview of Expert Systems:

  • An expert system is an artificial intelligence computer application that incorporates human knowledge, facts, rules, and heuristic approaches to solve complex domain problems.

  • Benchmark systems include:

  • MYCIN: Developed to diagnose bacterial infections; utilizes backward chaining.

  • DENDRAL: Developed to infer and establish the molecular structures of unknown chemical compounds; utilizes forward chaining.

• Tripartite Architecture of Expert Systems:

  • Knowledge Base (KB): The central repository containing curated, high-quality, domain-specific facts, representations, and rule sets. The knowledge is transferred from a human domain expert into the base through a knowledge engineer.

  • Inference Engine: The operational brain of the expert system. It systematically applies formal inference and logical rules to the knowledge base to derive novel facts or determine solutions.

  • User Interface: The front-end mechanism through which non-expert human users query the system, input situational data, and receive generated recommendations or conclusions.

• Inference Modes:

  • The inference engine operates primarily via two reasoning strategies:

  • Forward Chaining (Data-driven).

  • Backward Chaining (Goal-driven).

Forward Chaining Reasoning

• Operational Mechanism:

  • Forward chaining is an inference method that starts from known initial data and facts, sequentially firing inference rules whose conditions are satisfied, to produce new facts until an ultimate goal or endpoint is derived.

  • It systematically evaluates known conditions and rules to construct new derivations from the ground up.

• Core Characteristics:

  • Operates as a bottom-up (down-up) strategy.

  • Completely data-driven: uses known premises to move toward conclusions.

  • Typical reasoning engine choice in production rule systems and synthesis-oriented expert systems.

• Illustrative Adoption Scenario:

  • Fact 1: A dog is up for adoption through person A.

  • Fact 2: Person B is looking for a dog.

  • Inference Rule: If a dog is up for adoption and someone is looking to adopt it, that person is permitted to adopt it.

  • Derived Decision: Person B can adopt the dog from person A.

• Advantages and Disadvantages:

  • Advantages:

  • Highly effective for deriving multiple valid conclusions concurrently.

  • Provides greater operational flexibility during exploration.

  • Produces thoroughly supported conclusions directly grounded in raw data.

  • Disadvantages:

  • Computationally expensive and time-consuming because of extensive search space and data synchronization overhead.

  • May trigger rules that are irrelevant to the specific goal, leading to poor fact explanation.

• Step-by-Step Implementation Procedure:

  • Step 1: Identify domain facts and configure the necessary knowledge representation data structures.

  • Step 2: Initialize the working memory with all known initial facts.

  • Step 3: Enter an iterative evaluation loop:

  • Compare current working memory against termination criteria and target goals.

  • If the goal matches, terminate execution.

  • If the goal is not reached, scan the rule base for rules whose antecedents match working memory facts.

  • If rule conditions require sub-proofs, recursively invoke backward chaining on those conditions.

  • Add the consequent of fired rules to working memory and repeat.

  • Step 4: Detect the specified termination condition (e.g., goal satisfaction or maximum iteration limit) and output the final state of working memory.

Backward Chaining Reasoning

• Operational Mechanism:

  • Backward chaining (or backward deduction) reverses the direction of forward chaining.

  • It starts with an initial hypothesis, decision, or target goal and works backward to identify the supporting facts required to substantiate that goal.

  • Widely employed in diagnostics, troubleshooting, software debugging, and medical prescription systems.

• Core Characteristics:

  • Operates as a top-down strategy.

  • Based directly on the Modus Ponens inference rule.

  • Goal-driven: a targeted list of goals dictates which rules are searched, selected, and executed.

  • Deconstructs primary goals into sets of sub-goals to verify premise truth values.

  • Primarily executes using a depth-first search (DFS) traversal strategy.

• Illustrative Adoption Scenario:

  • Target Goal / Decision: Person B adopts a dog.

  • Fact 1: A dog is up for adoption from person A.

  • Fact 2: Person B is looking for a dog.

  • Inference Rule: If a person wants to adopt a dog, they can if one is available for adoption.

  • Reasoning Flow: The inference engine targets the goal "Person B adopts a dog" and backtracks to query whether Fact 1 and Fact 2 hold. Because both conditions are satisfied, the goal is validated.

• Advantages and Disadvantages:

  • Advantages:

  • Significantly faster than forward chaining when searching for a targeted hypothesis.

  • Follows a direct, easier-to-trace derivation path.

  • Highly efficient at confirming specific outcomes.

  • Disadvantages:

  • Restrictive: typically pursues and validates only a single target outcome at a time.

  • Lacks general exploratory flexibility.

  • Strictly requires an endpoint/goal to be predefined before reasoning can begin.

  • Can become difficult to manage if sub-goal backtracking is deep.

• Step-by-Step Implementation Procedure:

  • Step 1: Define and populate the rule-based knowledge base.

  • Step 2: Explicitly establish the primary goal or conclusion hypothesis.

  • Step 3: Start the evaluation loop:

  • Check if the target goal is already established within known facts; if so, terminate with success.

  • Otherwise, locate rules whose conclusions match the target goal.

  • Recursively invoke backward chaining on each antecedent condition (sub-goal) of the matching rule.

  • Continue iterating until all sub-goals resolve to verified base facts or all rule paths fail.

  • Step 4: Check termination criteria and output whether the target hypothesis is substantiated.

• Canonical Benchmark Problem:

  • Legal Premise: As per the law, it is a crime for an American citizen to sell weapons to hostile nations.

  • Domain Facts:

  • Country A is an enemy of America.

  • Country A has missiles.

  • All missiles possessed by Country A were sold to it by Robert.

  • Robert is an American citizen.

  • Proving Objective: Use chaining to prove the formal proposition "Robert is a criminal."

Knowledge Representation Concepts and Categories

• Definition and Scope of Knowledge Representation and Reasoning (KR / KRR):

  • KR is the subfield of artificial intelligence dedicated to structuring information about the real world into computer-interpretable formats.

  • It enables autonomous agents to perform cognitive tasks, interpret knowledge, reason about environments, and solve complex real-world tasks (e.g., medical diagnostics, natural language comprehension).

  • Knowledge representation goes beyond simple data storage in a database; it allows an intelligent system to draw inferences, learn from historical experiences, and exhibit human-like intelligent behavior.

• Knowledge versus Representation:

  • Knowledge: A descriptive model of the world that determines an intelligent system's competence (what it knows).

  • Representation: The specific computational encoding of knowledge that determines an intelligent system's operational performance (how it acts and computes).

• Entities Required in Knowledge Representation:

  • Objects: Facts concerning discrete entities within the problem universe.

  • Events: Actions, occurrences, and temporal transitions in the world.

  • Performance: Behavioral knowledge detailing the procedures for how tasks are executed.

  • Meta-knowledge: Knowledge about knowledge (e.g., the limits, reliability, and structure of what is known).

  • Facts: Assertions of fundamental truths about the real-world domain.

  • Knowledge-Base (KB): The core store of a knowledge-based agent, structured as a set of logical sentences.

• Dichotomy of Human Knowledge:

  • Tacit (Implicit / Informal) Knowledge:

  • Exists solely inside human minds; inherently embodied.

  • Acquired through direct experiential action and subjective insight.

  • Extremely difficult to formalize, articulate, communicate, or share.

  • Highly resistant to being stolen, copied, or directly transferred.

  • Explicit (Formal) Knowledge:

  • Exists externally to human beings; embedded in artifacts, documents, or systems.

  • Derived from standardized principles, structured procedures, and formal concepts.

  • Readily articulated, shared, stored, copied, and communicated.

  • Susceptible to duplication and theft.

• Five Major Categories of Knowledge:

  • Declarative Knowledge: Explicit assertions representing concepts, facts, and objects.

  • Structural Knowledge: Conceptual linkages, associations, and relationships between objects and higher-order concepts.

  • Procedural Knowledge: Operational rules, algorithms, and step-by-step procedures detailing how to perform specific actions.

  • Heuristic Knowledge: Rules of thumb, expert insights, and practical reasoning shortcuts.

  • Meta-Knowledge: Higher-level knowledge that monitors, organizes, and reasons about other knowledge.

The Knowledge Representation Framework and Mappings

• The Knowledge Representation Framework:

  • Problem solving in artificial intelligence requires transforming an informal problem in the real world into an internal formal representation that an algorithm can compute.

  • Operational Stages:

  • Problem Definition: An informal description of the real-world problem is articulated.

  • Representation: The informal problem description is translated into formal knowledge structures.

  • Computation: Automated inference engines and algorithms process the formal representation to compute a formal output.

  • Interpretation: The computed output is converted back into an informal solution for human understanding and consistency verification.

• Levels of Representation:

  • Knowledge Level: The real-world semantic layer where domain facts are defined.

  • Symbol Level: The computational syntax layer where facts are translated into symbolic tokens that programs can manipulate.

• Mappings Between Natural Language and Internal Representations:

  • Natural language (e.g., standard English) is too ambiguous and computationally challenging for direct reasoning.

  • Intelligent agents employ translation processes:

  • English Understanding: Translates an English representation into an internal formal symbolic representation.

  • Reasoning Programs: Generate inferences, update state, and deduce new facts within the internal representation.

  • English Generation: Translates internal representation structures back into natural language output.

• Primary Models and Mechanisms of Knowledge Representation:

  • Logic (e.g., Propositional and First-Order Predicate Logic).

  • Production Rules (Condition-Action / If-Then statements).

  • Frames (Object-attribute-value structures).

  • Semantic Networks (Graph-based associative structures).

Approaches to Knowledge Representation

• 1. Simple Relational Knowledge:

  • Organizes domain facts systematically into tables composed of rows and columns, similar to relational databases.

  • Direct representation of entity relationships.

  • Provides virtually no capability for internal logical inference.

  • Tabular Example:

• 2. Inheritable Knowledge:

  • Organizes data into an explicit generalization-specialization class hierarchy.

  • Employs inheritance: child entities automatically inherit properties, attributes, and default values from parent classes.

  • Distinguishes between two foundational relationships:

  • IS-A: Subclass to superclass relationship.

  • instance: Individual object to class membership.

  • Represented graphically as boxed nodes (concepts, individuals, or attribute values) interconnected by directed labeled edges.

• 3. Inferential Knowledge:

  • Encodes domain knowledge using formal logics (such as first-order logic).

  • Enables formal deduction to derive guaranteed correct, novel facts from existing premises.

  • Classical Deductive Example:

  • Premise 1: "Marcus is a man"       $man(Marcus)$

  • Premise 2: "All men are mortal"       $\forall x\, (man(x) \rightarrow mortal(x))$

  • Derived Conclusion: "Marcus is mortal"       $mortal(Marcus)$

• 4. Procedural Knowledge:

  • Represents domain knowledge as executable instructions, subroutines, and small code blocks that specify how to accomplish a task.

  • Primarily implemented using declarative condition-action statements (If-Then rules).

  • Commonly built using symbolic AI programming languages like LISP and Prolog.

  • Suitable for heuristic and specialized domain procedures, though it cannot easily represent all forms of general knowledge.

Evaluation Criteria for Knowledge Representations

• Representational Adequacy:

  • The capacity of a representation scheme to express all types of knowledge required within a given problem domain.

• Inferential Adequacy:

  • The capability of the representation to manipulate its internal structures to infer new knowledge from previously stored information.

• Inferential Efficiency:

  • The ability to incorporate focus and guidance information into the knowledge structure, directing the inference engine toward the most promising search paths.

• Acquisitional Efficiency:

  • The ease with which the system acquires, integrates, and validates new knowledge using automated techniques rather than relying entirely on manual human intervention.

Foundational Issues in Knowledge Representation

• 1. Identification of Important Attributes:

  • Certain core attributes recur across almost all domains.

  • The attributes instance and isa are of fundamental importance because they enable property inheritance across hierarchies.

• Structural Relationships in the Inheritable Knowledge Graph:

  • Class Person possesses the attribute Handed = Left.

  • Class Male has an isa link to Person, with inherited properties plus a localized Height = 6.

  • Class Cricket Player has an isa link to Male, with overridden Height = 5.5, Bats = Left Handed, and Batting Average = 60.54.

  • Class Batsman has an isa link to Cricket Player, with specialized Batting Average = 55.60.

  • Class Bowler has an isa link to Cricket Player, with specialized Bowling Average = 19.20.

  • Individual Virat is an instance of Batsman with location link Delhi.

  • Individual Ashwin is an instance of Bowler with location link Chennai.

  • 2. Relationships Among Attributes:

• Attributes used to characterize objects are themselves formal entities requiring representation and can possess structural relationships:

  • Inverse Relationships: Maintains database consistency when updating values (e.g., if $X$ is child of $Y$, then $Y$ is parent of $X$).

  • Existence in an isa Hierarchy: Attributes themselves exhibit specialization hierarchies (e.g., height is a specialization of physical-size, which is a specialization of physical-attribute), enabling attribute inheritance.

  • Techniques for Reasoning About Values: Constraints and inference logic applied to deduce missing values (e.g., height must be expressed in units of length; a person's age cannot exceed the age of their biological parents).

  • Single-Valued Attributes: Semantic guarantees that an attribute takes a unique value at any given time (e.g., a person has exactly one biological height; a player can play for only one team at a time).

  • 3. Choosing Representation Granularity:

• Deciding the level of abstraction at which domain primitives are modeled.

• The Granularity Dilemma:

  • Using high-level facts reduces storage requirements but can limit inferential power.

  • Using low-level primitives supports deep semantic reasoning but requires substantial storage and processing overhead.

• Example Analysis:

  • Representing "John spotted Alex" as:       $Spotted(agent(John), object(Alex))$

  • This structure directly answers queries such as "Who spotted Alex?".

  • However, it cannot answer "Did John see Sue?" unless an inferential bridging rule is added, such as:       $\forall x\, \forall y\, (Spotted(x, y) \rightarrow saw(x, y))$

  • 4. Representing Sets of Objects:

• Some real-world properties apply to a collection or set as a whole rather than to individual members.

• Examples:

  • "There are more sheep than people in Australia."

  • "English speakers can be found all over the world."

• These statements require knowledge representation formalisms that support collective set assertions rather than purely individual object predications.

  • 5. Finding and Managing the Right Representation Structure:

• Complex domains require selecting an initial knowledge structure and dynamically revising it as context changes.

• Key Challenges:

  • Selecting an initial appropriate structure.

  • Populating necessary details from the current state of the world.

  • Detecting when the active structure is inappropriate and transitioning to a better one.

  • Handling situations where no pre-existing structure is suitable.

  • Constructing, indexing, and remembering novel structures for unfamiliar conditions.