FAI Notes - Unit 3_1a3dfb41b828a3aa20180e9b401c8914.pdf

FUNDAMENTALS OF AI UNIT-3 INFERENCE TECHNIQUES 3.1. Propositio...

FUNDAMENTALS OF AI UNIT-3 INFERENCE TECHNIQUES 3.1. Propositional Logic Propositional Logic: The simplest kind of logic is propositional logic (PL), in which all statements are made up of propositions. The term "Proposition" refers to a declarative statement that can be true or false. It's a method of expressing knowledge in logical and mathematical terms. Example: It is Sunday. The Sun rises from West (False proposition) 3 + 3 = 7 (False proposition) 5 is a prime number. Following are some basic facts about propositional logic: Because it operates with 0 and 1, propositional logic is also known as Boolean logic. In propositional logic, symbolic variables are used to express the logic, and any symbol can be used to represent a proposition, such as A, B, C, P, Q, R, and so on. Propositions can be true or false, but not both at the same time. An object, relations or functions, and logical connectives make up propositional logic. Logical operators are another name for these connectives. The essential parts of propositional logic are propositions and connectives. Connectives are logical operators that link two sentences together. Tautology, commonly known as a legitimate sentence, is a proposition formula that is always true. Contradiction is a proposition formula that is always false. Statements that are inquiries, demands, or opinions are not propositions, such as "Where is Raj”, “How are you", and "What is your name" are not propositions. Syntax of propositional logic: The allowed sentences for knowledge representation are defined by the syntax of propositional logic. Propositions are divided into two categories: 1) Atomic Propositions. 2) Compound propositions.  FUNDAMENTALS OF AI Atomic propositions: Simple assertions are referred to as atomic propositions. It is made up of only one proposition sign. These are the sentences that must be true or false to pass. Example: 2+2 is 4, it is an atomic proposition as it is a fact. "The Sun is cold" is also a proposition as it is a false fact. Compound proposition: Simpler or atomic statements are combined with parenthesis and logical connectives to form compound propositions. Example: 1) "It is raining today, and the street is wet." 2) "Ankit is a doctor, and his clinic is in Mumbai." Logical Connectives: Logical connectives are used to link two simpler ideas or to logically represent a statement. With the use of logical connectives, we can form compound assertions. There are five primary connectives, which are listed below: 1) Negation: A statement like ¬P is referred to as a negation of P. There are two types of literals: positive and negative literals. 2) Conjunction: A conjunction is a sentence that contains ∧ connectives such a, P ∧ Q. Example: Rohan is intelligent and hardworking. It can be written as, P = Rohan is intelligent, Q = Rohan is hardworking. →P ∧ Q. 3) Disjunction: A disjunction is a sentence with a connective ∨ , such as P ∨ Q, where P and Q are the propositions. Example: "Ritika is a doctor or Engineer", Here P = Ritika is Doctor. Q = Ritika is Engineer, so we can write it as P ∨ Q. 4) Implication: An implication is a statement such as P → Q. If-then rules are another name for implications. It can be expressed as follows: If it rains, the street is flooded. Because P denotes rain and Q denotes a wet street, the situation is written as P → Q 5) Biconditional: A sentence like P,Q for example, is a biconditional sentence. I am alive if I am breathing. P= I am breathing, Q = I am alive, it can be represented as P ⇔ Q.  FUNDAMENTALS OF AI Truth Table: Connectives Symbol Technical Term Word Example ^ Conjunction AND P^Q v Disjunction OR PvQ → Implication Implies P→Q ⇔ Bi-Conditional If and only If P⇔Q ¬ or ~ Negation Not P ¬ Q or P ~ Q We need to know the truth values of propositions in all feasible contexts in propositional logic. With logical connectives, we can combine all possible combinations, and the representation of these combinations in a tabular manner is known as a truth table. The truth table for all logical connectives is as follows: Nagation P ¬P TRUE FALSE FALSE TRUE Conjunction P Q P^Q TRUE TRUE TRUE TRUE FALSE FALSE FALSE TRUE FALSE FALSE FALSE FALSE Disjunction P Q PvQ TRUE TRUE TRUE TRUE FALSE TRUE FALSE TRUE TRUE FALSE FALSE FALSE Implication P Q P→Q TRUE TRUE TRUE TRUE FALSE FALSE FALSE TRUE TRUE FALSE FALSE TRUE Bi-Conditional P Q P⇔Q TRUE TRUE TRUE TRUE FALSE FALSE FALSE TRUE FALSE FALSE FALSE TRUE  FUNDAMENTALS OF AI Truth table with three propositions: You can build a proposition composing three propositions P, Q, and R. Precedence of connectives: Propositional connectors or logical operators, like arithmetic operators, have a precedence order. When evaluating a propositional problem, this order should be followed. The following is a list of the operator precedence order: Logical equivalence: One of the characteristics of propositional logic is logical equivalence. If and only if the truth table's columns are equal, two assertions are said to be logically comparable. Let's take two Propositions P and Q, so for logical equivalence, we can write it as P⇔Q. In the below truth table we can see that columns for ¬P ∨ Q and P→Q, are identical hence P is Equivalent to Q.  FUNDAMENTALS OF AI For Example: “If it is raining, then the ground is wet" and "If the ground is not wet, then it is not raining”. Here, the truth of one statement confirms the truth of the other which demonstrates logical equivalence. Properties of Operators: Commutativity: P ∧ Q= Q ∧ P, or P ∨ Q = Q ∨ P. Associativity: (P ∧ Q) ∧ R = P ∧ (Q ∧ R), (P ∨ Q) ∨ R= P ∨ (Q ∨ R). Identity element: P ∧ True = P, P ∨ True= True. Distributive: P ∧ (Q ∨ R) = (P ∧ Q) ∨ (P ∧ R). P ∨ (Q ∧ R) = (P ∨ Q) ∧ (P ∨ R). DE Morgan's Law: ¬(P ∧ Q) = (¬P) ∨ (¬Q), ¬(P ∨ Q) = (¬ P) ∧ (¬Q). Double-negation elimination: ¬(¬P) = P. Limitations of Propositional logic: This is not possible to represent relations like ALL, some, or none with propositional logic. Example: o All the girls are intelligent. o Some apples are sweet.  FUNDAMENTALS OF AI The expressive power of propositional logic is restricted. We can't explain propositions in propositional logic in terms of their qualities or logical relationships. 3.2. First-order logic First-order logic is another way of knowledge representation in artificial intelligence. It is an extension of propositional logic. FOL is sufficiently expressive to represent the natural language statements concisely. First-order logic is also known as Predicate logic or First-order predicate logic. First-order logic is a powerful language that develops information about objects in a more easy way and can also express the relationship between those objects. First-order logic (like natural language) does not only assume that the world contains facts like propositional logic but also assumes the following things in the world: Objects: A, B, people, numbers, colors, wars, theories, squares, pits, wumpus. Relations: It can be unary relation such as red, round, is adjacent, or n-any relation such as the sister of, brother of, has color, comes between Function: Father of, best friend, third inning of, end of, As a natural language, first-order logic also has two main parts: Syntax Semantics Syntax of First-Order logic: The syntax of FOL determines which collection of symbols is a logical expression in first- order logic. The basic syntactic elements of first-order logic are symbols. We write statements in short-hand notation in FOL. Basic Elements of First-order logic:  FUNDAMENTALS OF AI The following are the basic elements of FOL syntax: Atomic sentences: Atomic sentences are the most basic sentences of first-order logic. These sentences are formed from a predicate symbol followed by a parenthesis with a sequence of terms. We can represent atomic sentences as Predicate (term1, term2, term n). Example: Ravi and Ajay are brothers: => Brothers(Ravi, Ajay). Chinky is a cat: => cat (Chinky). Complex Sentences: Complex sentences are made by combining atomic sentences using connectives. First-order logic statements can be divided into two parts: Subject: Subject is the main part of the statement. Predicate: A predicate can be defined as a relation, which binds two atoms together in a statement. Consider the statement: "x is an integer.", it consists of two parts, the first part x is the subject of the statement and the second part "is an integer," is known as a predicate. Quantifiers in First-order logic: A quantifier is a language element that generates quantification, and quantification specifies the quantity of specimen in the universe of discourse. These are the symbols that permit to determine or identify the range and scope of the variable in the logical expression. There are two types of quantifiers: Universal Quantifier, (for all, everyone, everything) Existential quantifier, (for some, at least one). Universal Quantifier: A universal quantifier is a symbol of logical representation, which specifies that the statement within its range is true for everything or every instance of a particular thing. The Universal quantifier is represented by a symbol ∀, which resembles an inverted A. If x is a variable, then ∀x is read as:  FUNDAMENTALS OF AI For all x For each x For every x. Example: All men drink coffee. Let a variable x which refers to a cat so all x can be represented in UOD as below: ∀x man(x) → drink (x, coffee). It will be read as There are all x where x is a man who drinks coffee. Existential Quantifier: Existential quantifiers are the type of quantifiers, which express that the statement within its scope is true for at least one instance of something. It is denoted by the logical operator ∃, which resembles an inverted E. When it is used with a predicate variable then it is called an existential quantifier. If x is a variable, then the existential quantifier will be ∃x or ∃(x). And it will be read as: There exists a 'x.' For some 'x.' For at least one 'x.' Example:  FUNDAMENTALS OF AI ∃x: boys(x) ∧ intelligent(x) It will be read as There are some x where x is an intelligent boy. Properties of Quantifiers: In the universal quantifier, ∀x∀y is similar to ∀y∀x. In the Existential quantifier, ∃x∃y is similar to ∃y∃x. ∃x∀y is not similar to ∀y∃x. Some Examples of FOL using quantifiers: 1. All birds fly. In this question, the predicate is "fly(bird)." since all birds fly so it will be represented as follows. ∀x bird(x) →fly(x). 2. Every man respects his parent. In this question, the predicate is "respect(x, y)," where x=man, and y= parent. Since there is every man so will use ∀, and it will be represented as follows: ∀x man(x) → respects (x, parent). 3. Some boys play cricket. In this question, the predicate is "play(x, y)," where x= boys, and y= game. Since there are some boys we will use ∃, and it will be represented as: ∃x boys(x) → play(x, cricket). 4. Not all students like both Mathematics and Science. In this question, the predicate is "like(x, y)," where x= student, and y= subject. Since there are not all students, we will use ∀ negation, so the following representation for this: ¬∀ (x) [ student(x) → like(x, Mathematics) ∧ like(x, Science)]. 5.Anyone passing his history exams and winning the lottery is happy. ∀x [Pass(x,history) ^ win(x,lottery) -> happy(x)] Read as: For all x, if x passes history and x wins the lottery, then x is happy. 3.3. Representing knowledge using rules One way to represent knowledge is by using rules that express what must happen or what does happen when certain conditions are met. Rules are usually expressed in the form of IF THEN Statements, such as:  FUNDAMENTALS OF AI IF A THEN B this can be considered to have a similar logical meaning as the following: A→B A is called the antecedent and B is the consequent in this statement. In expressing rules, the consequence usually takes the form of an action or a conclusion. In other words, the purpose of a rule is usually to tell a system (such as an expert system) what to do in certain circumstances, or what conclusions to draw from a set of inputs about the current situation. In general, a rule can have more than one antecedent, usually combined either by AND or by OR (logically the same as the operators ∧ and ∨). Similarly, a rule may have more than one consequence, which usually suggests that there are multiple actions to be taken. In general, the antecedent of a rule compares an object with a possible value, using an operator. For example, suitable antecedents in a rule might be IF x > 3 If the name is “Bob” IF the weather is cold Here, the objects being considered are x, name, and weather; the operators are “>” and “is”, and the values are 3, “Bob,” and cold. Note that an object is not necessarily an object in the real-world sense—the weather is not a real- world object, but rather a state or condition of the world. An object in this sense is simply a variable that represents some physical object or state in the real world. An example of a rule might be IF the name is “Bob” And the weather is cold THEN tell Bob ‘Wear a coat’ This is an example of a recommendation rule, which takes a set of inputs and gives advice as a result. The conclusion of the rule is an action, and the action takes the form of a recommendation to Bob that he should wear a coat. In some cases, the rules provide more definite actions such as “move left” or “close the door,” in which case the rules are being used to represent directives. Rules can also be used to represent relations such as: IF temperature is below 0 THEN the weather is cold.  FUNDAMENTALS OF AI 3.4. Procedure versus Declarative Knowledge We can express the knowledge in various forms to the inference engine in the computer system to solve the problems. There are two important representations of knowledge namely, procedural knowledge and declarative knowledge. The basic difference between procedural and declarative knowledge is that procedural knowledge gives the control information along with the knowledge, whereas declarative knowledge just provides the knowledge but not the control information to implement the knowledge. Read through this article to find out more about procedural knowledge and declarative knowledge and how they are different from each other. Key Procedural Knowledge Declarative Knowledge Meaning Procedural knowledge provides the Declarative knowledge provides the knowledge of how a particular task can be basic knowledge about something. accomplished. Alternate name Procedural knowledge is also termed Declarative knowledge is also imperative knowledge. termed as functional knowledge. Basis Procedural knowledge revolves around Declarative knowledge revolves the "How" of the concept. around the "What" of the concept. Communication Procedural knowledge is difficult to Declarative knowledge is easily communicate. communicable. Orientation Procedural knowledge is a process- Declarative knowledge is data- oriented. oriented. Validation Validation is not very easy in procedural Validation is quite easy in knowledge. declarative knowledge. Debugging Debugging is not very easy in procedural Debugging is quite easy in knowledge. declarative knowledge. Use Procedural knowledge is less commonly Declarative knowledge is more used. general. Representation Procedural knowledge is represented by a Declarative knowledge is set of rules. represented by production systems. Source Procedural knowledge is obtained from Declarative knowledge is obtained actions, experiences, subjective insights, etc. from principles, procedures, concepts, processes, etc.  FUNDAMENTALS OF AI 3.5. Forward versus Backward Reasoning What is Forward Reasoning?  Forward reasoning is a process in artificial intelligence that finds all the possible solutions to a problem based on the initial data and facts. Thus, forward reasoning is a data-driven task as it begins with new data. The main objective of forward reasoning in AI is to find a conclusion that would follow. It uses an opportunistic type of approach. Forward reasoning flows from the incipient to the consequence. The inference engine searches the knowledge base with the given information depending on the constraints. The precedence of these constraints has to match the current state. In forward reasoning, the first step is that the system is given one or more constraints. The rules are then searched for in the knowledge base for every constraint. The rule that fulfills the condition is selected. Also, every rule can generate a new condition from the conclusion which is obtained from the invoked one. These new conditions can be added and processed again. The step ends if no new conditions exist. Hence, we can conclude that forward reasoning follows the top-down approach. What is Backward Reasoning? Backward reasoning is the reverse process of forward reasoning in which a goal or hypothesis is selected and it is analyzed to find the initial data, facts, and rules. Therefore, backward reasoning is a goal-driven task as it begins with conclusions or goals that are uncertain. The main objective of backward reasoning is to find the facts that support the conclusions. Backward reasoning uses a conservative type of approach and flows from the consequence to the incipient. The system helps to choose a goal state and reasons in a backward direction. The first step in backward reasoning is that the goal state and rules are selected. Then, sub-goals are made from the selected rule, which needs to be satisfied for the goal state to be true. The initial conditions are set such that they satisfy all the sub-goals. Also, the established states are matched to the initial state provided. If the condition is fulfilled, the goal is the solution, otherwise, the goal is rejected. Therefore, backward reasoning follows the bottom-up technique. Backward reasoning is also known as a decision-driven or goal-driven inference technique because the system selects a goal state and reasons in the backward direction.  FUNDAMENTALS OF AI Difference between Forward and Backward Reasoning in AI Forward Reasoning Backward Reasoning It is a data-driven task. It is a goal-driven task. It begins with new data. It begins with uncertain conclusions. The objective is to find a conclusion that would The objective is to find the facts that support follow. the conclusions. It uses an opportunistic type of approach. It uses a conservative type of approach. It flows from the incipient to the consequence. It flows from the consequence to the incipient. Forward reasoning begins with the initial facts. Backward reasoning begins with some goal (hypothesis). Forward reasoning tests all the rules. Backward reasons test some rules. Forward reasoning is a bottom-up approach. Backward reasoning is a top-down approach. Forward reasoning can produce an infinite Backward reasoning produces a finite several conclusions. several conclusions. In the forward reasoning, all the data is In the backward reasoning, the data is available. acquired on demand. Forward reasoning has a small number of Backward reasoning has a smaller number of initial states but a large number of conclusions. goals and a larger number of rules. In forward reasoning, the goal formation is In backward reasoning, it is easy to form a difficult. goal. Forward reasoning works in the forward direction Backward reasoning works in a backward to find all the possible conclusions from facts. direction to find the facts that justify the goal. Forward reason is suitable to answer problems Backward reasoning is suitable for diagnosis-like such as planning, control, monitoring, etc. problems.