Mini-Max Algorithm in Artificial Intelligence © Mini-max algorithm is a recursive or backtracking algorithm which is used in decision-making and game theory. It provides an optimal move for the player assuming that opponent is also playing optimally. © Mini-Max algorithm uses recursion to search through the game-tree. Min-Max algorithm is mostly used for game playing in Al. Such as Chess, Checkers, tic-tac-toe, go, and various tow-players game. This Algorithm computes the minimax decision for the current state. © In this algorithm two players play the game, one is called MAX and other is called MIN. © Both the players fight it as the opponent player gets the minimum benefit while they get the maximum benefit. © Both Players of the game are opponent of each other, where MAX will select the maximized value and MIN will select the minimized value. © The minimax algorithm performs a depth-first search algorithm for the exploration of the complete game tree. © The minimax algorithm proceeds all the way down to the terminal node of the tree, then backtrack the tree as the recursion. Pseudo-code for MinMax Algorithm: . function minimax(node, depth, maximizingPlayer) is . if depth or node is a terminal node then . return static evaluation of node . if MaximizingPlayer then _// for Maximizer Player . maxEva= -infinity for each child of node do eva= minimax(child, depth-1, false) 9. maxEva= max(maxévaeva) _//gives Maximum of the values 10. return maxEva an 12.else 11 for Minimizer player 13. minEva= +infinity 14, for each child of node do PNAMAWHNS15, eva= minimax(child, depth-1, true) 16. minEva= min(minEva, eva) //gives minimum of the values 17. return minEva Initial call: Minimax(node, 3, true) Working of Min-Max Algorithm: © The working of the minimax algorithm can be easily described using an example. Below we have taken an example of game-tree which is representing the two-player game. o. Inthis example, there are two players one is called Maximizer and other is called Minimizer. © Maximizer will try to get the Maximum possible score, and Minimizer will try to get the minimum possible score. ‘© This algorithm applies DES, so in this game-tree, we have to go all the way through the leaves to reach the terminal nodes. o At the terminal node, the terminal values are given so we will compare those value and backtrack the tree until the initial state occurs. Following are the main steps involved in solving the two-player game tree: Step-1: In the first step, the algorithm generates the entire game-tree and apply the utility function to get the utility values for the terminal states. In the below tree diagram, let's take A is the initial state of the tree. Suppose maximizer takes first turn which has worst-case initial value =- infinity, and minimizer will take next tum which has worst-case initial value = +infinity.‘Maximizer Minimizer Maximizer Terminal node Terminal values Step 2: Now, first we find the utilities value for the Maximizer, its initial value is -e0, 50 we will compare each value in terminal state with initial value of Maximizer and determines the higher nodes values. It will find the maximum among the all ° For node D For Node E For Node F For node G max(-1,- -00) => max(-1,4)= 4 max(2, -00) => max(2, 6)= 6 max(-3, -09) => max(-3,-5) = -3 max(0, -c0) = max(0, 7) = 7Maximizer Maximizer Terminal node Terminal values Step 3: In the next step, it's a turn for minimizer, so it will compare all nodes value with +00, and will find the 3” layer node values. © For node B= min(4,6) = 4 © Fornade C= min (-3, 7) =wirwandroid.universityupdates.in / www.amniversityupdates.in | huips:/telegram.ne nth ‘Maximizer Minimizer Maximizer Terminal node Terminal values Step 4: Now it's a turn for Maximizer, and it will again choose the maximum of all nodes value and find the maximum value for the root node. In this game tree, there are only 4 layers, hence we reach immediately to the root node, but in real games, there will be more than 4 layers. © Fornode A max(4, -3)= 4‘Maximizer ‘Minimizer Maximizer Terminal node Terminal values That was the complete workflow of the minimax two player game. Properties of Mini-Max algorithm: ‘o Complete- Min-Max algorithm is Complete. It will definitely find a solution (if exist), in the finite search tree. © Optimal-Min-Max algorithm is optimal if both opponents are playing optimally. o. Time complexity- As it performs DFS for the game-tree, so the time complexity of Min-Max algorithm is O(b™), where b is branching factor of the game-tree, and mis the maximum depth of the tree, ‘© Space Complexity- Space complexity of Mi DFS which is O(bm). i-max algorithm is also similar to Limitation of the minimax Algorithm: The main drawback of the minimax algorithm is that it gets really slow for complex. games such as Chess, go, etc. This type of games has a huge branching factor, and the nwmsandroidpreviousuestionpapers.com [ssww.previousquestionpepers.eont | Intps:/telegram.me taht sain J wewamiversitypdates.in {huips:/telegramane ath vwovwrcandroidaniversinvnp player has lots of choices to decide. This limitation of the minimax algorithm can be improved from alpha-beta pruning which we have discussed in the next topic.Alpha-Beta Pruning ‘© Alpha-beta pruning is a modified version of the minimax algorithm. It is an optimization technique for the minimax algorithm, ‘© As we have seen in the minimax search algorithm that the number of game states it has to examine are exponential in depth of the tree. Since we cannot eliminate the exponent, but we can cut it to half, Hence there is a technique by which without checking each node of the game tree we can compute the correct minimax decision, and this technique is called pruning. This involves two threshold parameter Alpha and beta for future expansion, so it is called alpha- beta pruning. It is also called as Alpha-Beta Algorithm. © Alpha-beta pruning can be applied at any depth of a tree, and sometimes not only prune the tree leaves but also entire sub-tree. © The two-parameter can be defined as: a, Alpha: The best (highest-value) choice we have found so far at any point along the path of Maximizer. The initial value of alpha is -2», b. Beta: The best (lowest-value) choice we have found so far at any point along the path of Minimizer. The initial value of beta is +e, © The Alpha-beta pruning to a standard minimax algorithm returns the same move as the standard algorithm does, but it removes all the nodes which are not really affecting the final decision but making algorithm slow. Hence by pruning these nodes, it makes the algorithm fast. | __ Note: To better understand this topic, kindly study the minimax algorithm. Condition for Alpha-beta pruning: The main condition which required for alpha-beta pruning is: 1. a>=B Key points about alpha-beta pruning: © The Max player will only update the value of alpha. © The Min player will only update the value of beta. © While backtracking the tree, the node values will be passed to upper nodes instead of values of alpha and beta. ssnarcanidroid previousguestio ars Jousquestionpapers.com (hnps:/tetegranaae jurul pers.comt | wwn:previousquestionpapers.c " ji oid aniversityupdates.in { www.universityupdates.in | lutps:/telegram.mesjutalt Weill only pass the alpha, beta values to the child nodes.Pseudo-code for Alpha-beta Pruning: . function minimax(node, depth, alpha, beta, maximizingPlayer) is ._ if depth ==0 or node is a terminal node then . return static evaluation of node maxEva= -infinity for each child of node do eva= minimax(child, depth-1, alpha, beta, False) 9. maxEva= max(maxEva, eva) 10. alpha= max(alpha, maxéva) 11. if beta<=alpha 12. break 13, return maxEva 14. 15.else // for Minimizer player 16. minEva= +infinity 17. for each child of node do 18, eva= minimax(child, depth-1, alpha, beta, true) 19. minEva= min(minEva, eva) 20. beta= min(beta, eva) 21. if beta<=alpha 22. break 23, return minEva 1 2. 3. 4, 5. if MaximizingPlayer then —_// for Maximizer Player 6. 7. 8. Working of Alpha-Beta Pruning: Let's take an example of two-player search tree to understand the working of Alpha- beta pruning Step 1: At the first step the, Max player will start first move from node A where and B= +09, these value of alpha and beta passed down to nade B where again and B= +00, and Node 8 passes the same value to its child D.Step 2: At Node D, the value of a will be calculated as its turn for Max. The value of a is compared with firstly 2 and then 3, and the max (2, 3) = 3 will be the value of a at node D and node value will also 3. Step 3: Now algorithm backtrack to node B, where the value of B will change as this is a turn of Min, Now B= +, will compare with the available subsequent nodes value, ie. min (co, 3) = 3, hence at node B now a= 09, and B= 3In the next step, algorithm traverse the next successor of Node B which is node E, and the values of a= -co, and B= 3 will also be passed. Step 4: At node E, Max will take its turn, and the value of alpha will change. The current value of alpha will be compared with 5, so max (-02, 5) = 5, hence at node E a= § and B= 3, where a>=B, so the right successor of E will be pruned, and algorithm will not traverse it, and the value at node E will be 5.Step 5: At next step, algorithm again backtrack the tree, from node B to node A. At node A, the value of alpha will be changed the maximum available value is 3 as max (- ©, 3)= 3, and B= +00, these two values now passes to right successor of A which is Node C. At node C, a=3 and B= +c, and the same values will be passed on to node F. Step 6: At node F, again the value of a will be compared with left child which is 0, and max(3,0)= 3, and then compared with right child which is 1, and max(3,1)= 3 still a remains 3, but the node value of F will become 1.Step 7: Node F returns the node value 1 to node C, at C a= 3 and B= +00, here the Value of beta will be changed, it will compare with 1 so min (c, 1) = 1, Now at C, a=3 and B= 1, and again it satisfies the condition a>=B, so the next child of C which is G will be pruned, and the algorithm will not compute the entire sub-tree G.Step 8: C now returns the value of 1 to A here the best value for A is max (3, 1) = 3. Following is the final game tree which is the showing the nodes which are computed and nodes which has never computed. Hence the optimal value for the maximizer is 3 for this example.wevamdroidaniverseepdatsin J wvsuniversitpdatenin [aps ramen Move Ordering in Alpha-Beta pruning: The effectiveness of alpha-beta pruning is highly dependent on the order in which leach node is examined. Mave orders an important aspect of alpha-bets pruning, can be of two types 12. Worst ordering: In some case, alpha-beta pruning algorithm doesnot prune any ofthe leaves of the tree, and works exactly as minimax algorithm. In this ase it so consumes more time because of alpha-bets factors, such 3 move ‘of pruning i called worst ordering. n this case, the best move occurs on the right side of the tre. The time complexity for such an order is OC") 16 Ideal ordering: The idea! ordering for alphs-beta pruning occurs when lots of pruning happens in the tee, and best moves occur atthe lft side of the te, ‘We apply DFS hence it fist search eft ofthe tree and go deep twice as minimax algorithm inthe same amount of time. Comply in ideal ordering is O19") wevanroldaniverseepdatesnj wwncenbverssupdesd {ps nh Rules to find good ordering: Following are some nies to find goo ordering in alphabets pruning ‘© Occur the best move from the shalomest node. ‘© Onder the nodes in the tree such thatthe best nades ae checked fist ©. Use domain knowledge while finding the best move. x for Chess try order captures fist then threats then forwart moves, backward moves. ‘2 Wecan bookkesp the state, a there is 2 possiblity that states may repeat. Ill O° “AwWhat is a Constraint Satisfaction Problem (CSP)? A Constraint Satisfaction Problem is a mathematical problem where the solution must meet a number of constraints. In a CSP, the objective is to assign values to variables such that all the constraints are satisfied. CSPs are used extensively in artificial intelligence for decision-making problems where resources must be managed or arranged within strict guidelines.Common applications of CSPs include: ¢ Scheduling: Assigning resources like employees or equipment while respecting time and availability constraints. Planning: Organizing tasks with specific deadlines or sequences. e Resource Allocation: Distributing resources efficiently without overuse.Components of Constraint Satisfaction Problems CSPs are composed of three key elements: 1. Variables: The things that need to be determined are variables. Variables in a CSP are the objects that must have values assigned to them in order to satisfy a particular set of constraints. Boolean, integer, and categorical variables are just a few examples of the various types of variables, for instance, could stand in for the many puzzle cells that need to be filled with numbers in a sudoku puzzle. 2. Domains: The range of potential values that a variable can have is represented by domains. Depending on the issue, a domain may be finite or limitless. For instance, in Sudoku, the set of numbers from 1 to 9 can serve as the domain of a variable repres¢ming a problem cell.3. Constraints: The guidelines that control how variables relate to one another are known as constraints. Constraints in a CSP define the ranges of possible values for variables. Unary constraints, binary constraints, and higher-order constraints are only a few examples of the various sorts of constraints. For instance, in a sudoku problem, the restrictions might be that each row, column, and 3x3 box can only have one instance of each number from 1 to 9. Types of Constraint Satisfaction Problems CSPs can be classified into different types based on their constraints and problem characteristics: 1. Binary CSPs: In these problems, each constraint involves only two variables. For example, in a scheduling problem, the constraint could specify that task A must be completedbefore task B.2. Non-Binary CSPs: These problems have constraints that involve more than two variables. For instance, in a seating arrangement problem, a constraint could state that three people cannot sit next to each other. 3. Hard and Soft Constraints: Hard constraints must be strictly satisfied, while soft constraints can be violated, but at a certain cost. This distinction is often used in real-world applications where not all constraints are equally important.Representation of Constraint Satisfaction Problems (CSP) In Constraint Satisfaction Problems (CSP), the solution process involves the interaction of variables, domains, and constraints. Below is a structured representation of how CSP is formulated: 1. Finite Set of Variables (V,, V2,...,V,): The problem consists of a set of variables, each of which needs to be assigned a value that satisfies the given constraints. . Non-Empty Domain for Each Variable (Di, Do,...,Dn): Each variable has a domain—a set of Ny possible values that it can take. For example, in a Sudoku puzzle, the domain could be the numbers 1 to 9 for each cell. . Finite Set of Constraints (C,, C2,...,Cm)* Constraints restrict the possible values that variables can take. Each constraint defines a rule or relationship between variables. w{Te WMITIOU GEER NO PICOClhauvil. Each constraint c; is represented as a Pair , where: ¢ Scope: The set of variables involved in the constraint. ¢ Relation: A list of valid combinations of variable values that satisfy the constraint. 5. Example: Let's say you have two variables ¥, and Vy. A possible constraint could be 4 4 V4, which means the values assigned to these variables must not be equal. Detailed Explanation: o Scope: The variables and 13. o Relation: A list of valid value combinations where VY; is not equal to V2. Some relations might include explicit combinations, while others may rely on abstract relations that are tested for validity dynamically. CSP AlgorithmpsSolving = oO <Constraint Propagation Constraint propagation is a fundamental concept in constraint satisfaction problems (CSPs). A CSP involves variables that must be assigned values from a given domain while satisfying a set of constraints. Constraint propagation aims to simplify these problems by reducing the domains of variables, thereby making the search for solutions more efficient. Key Concepts 1. Variables: Elements that need to be assigned values. 2. Domains: Possible values that can be assigned to the variables. 3. Constraints: Rules that define permissible combinations of values for the variables. How Constraint Propagation Works Constraint propagation works by iteratively narrowing down the domains of variables based on the constraints. This process continues until no more values can be eliminated from any domain. The primary goal is to reduce the search space and make it easier to find a solution. Steps in Constraint Propagation 1. Initialization: Start with the _ initial domains of all variables. 2. Propagation: Apply constraints to reduce the domains of variables. 3. Iteration: Repeat the propagation step until a stable state is reached, where no further reduction is possible.Example Consider a simple CSP with two variables, X and Y, each with domains {1, 2, 3}, and a constraint X # Y. Constraint propagation will iteratively reduce the domains as follows: e If X is assigned 1, then Y cannot be 1, so Y's domain becomes {2, 3}. e If Y is then assigned 2, X cannot be 2, so X's domain is reduced to {1, 3}. e This process continues until a stable state is reached. e Applications of Constraint Propagation Constraint propagation is widely used in various AI applications. Some notable areas include: Scheduling In scheduling problems, tasks must be assigned to time slots without conflicts. Constraint propagation helps by reducing the possible time slots for each task based on constraints like availability and dependencies. Planning AI planning involves creating a sequence of actions to achieve a_ goal. Constraint propagation simplifies the planning process by reducing the possible actions at each step, ensuring that the resulting plan satisfies all constraints. Resource Allocation In resource allocation problems, resources must be assigned to tasks in a way that meets all constraints, such as capacity limits and priority rules. Constraint propagation helps by narrowing down the possible assignments, making the sea’ g \ an optimal allocation more efficient. 7Concept of Backtracking Search Constraint Satisfaction Problems (CSPs) are a fundamental topic in artificial intelligence and computer science. They involve finding a solution that meets a set of constraints or conditions. Backtracking search is a powerful technique used to solve these problems. Backtracking Search Backtracking search is a depth-first search algorithm that incrementally builds candidates for the solutions, abandoning a candidate (backtracks) as soon as it determines that the candidate cannot possibly be completed to a valid solution. Steps in Backtracking 1. Initialization: Start with an empty assignment. 2. Selection: Choose an unassigned variable. 3. Assignment: Assign a value to the chosen variable. 4. Consistency Check: Check if the current assignment is consistent with the constraints. 5. Recursion: If the assignment is consistent, recursively try to assign values to the remaining variables. 6. Backtrack: If the assignment is not consistent, or if further assignments do not lead to a solution, undo the last assignment (backtrack) and try the next eh ee 4>INVIC Ul DGACALIGOCAINY Hl OUIVITIG Vors Advantages 1. Simplicity: The algorithm is easy to implement and understand. 2. Effectiveness: It works well for many practical CSPs, especially when combined with heuristics. 3. Flexibility: Can be adapted and optimized with various strategies like variable ordering and constraint propagation. Optimization Techniques 1. Forward Checking: After assigning a value to a variable, eliminate inconsistent values from the domains of the unassigned variables. 2. Constraint Propagation: Use algorithms like AC-3 (Arc Consistency 3) to reduce the search space by enforcing constraints locally. 3. Heuristics: Employ heuristics such as MRV (Minimum Remaining Values) and LCV (Least Constraining Value) to choose the next variable to assign and the next value to try. Limitations 1. Inefficiency for Large Problems: The algorithm can be slow for large or highly constrained problems. 2. Redundancy: Without optimization techniques, the search might redundantly explore many invalid paths. 3. Space Complexity: It requires significant memory for storing the state of the search tree.winicandroid previousguestionpapers.com / www,previousquestionpapers.com [ huips://telegramane/jntuh wirw.android.universityupdates.in | www.tniversityupdates.in | hutps://telegram.me/jntuh Knowledge-Based Agent in Artificial intelligence © Anintelligent agent needs knowledge about the real world for taking decisions and reasoning to act efficiently. © Knowledge-based agents are those agents who have the capability of maintaining an internal state of knowledge, reason over that knowledge, update their knowledge after observations and take actions. These agents can represent the world with some formal representation and act intelligently. o Knowledge-based agents are composed of two main parts: © Knowledge-base and © Inference system. A knowledge-based agent must able to do the following: © Anagent should be able to represent states, actions, etc. Anagent Should be able to incorporate new percepts 2 Anagent can update the internal representation of the world Anagent can deduce the internal representation of the world Anagent can deduce appropriate actions. The architecture of knowledge-based agent:Environment Input from Environment The above diagram is representing a generalized architecture for a knowledge-based agent. The knowledge-based agent (KBA) take input from the environment by perceiving the environment. The input is taken by the inference engine of the agent and which also communicate with KB to decide as per the knowledge store in KB. The learning element of KBA regularly updates the KB by learning new knowledge. Knowledge base: Knowledge-base is a central component of a knowledge-based agent, itis also known as KB. Itisa collection of sentences (here ‘sentence’ isa technical term and it is not identical to sentence in English). These sentences are expressed in a language which is called a knowledge representation language. The knowledge-base of KBA stores fact about the world, Why use a knowledge base? knowledge-base is required for updating knowledge for an agent to leam with experiences and take action as per the knowledge. Inference system Inference means deriving new sentences from old. Inference system allows us to add a new sentence to the knowledge base. A sentence is a proposition about the world. Inference system applies logical rules to the KB to deduce new information, Inference system generates new facts so that an agent can update the KB. An inference system works mainly in two rules which are given as: wwewsanudroid previousquestionpapers.com / www: previousquestionpapers.cews | heips:(telegram.mezjutul wiewandrotd.universitvupdates.in [ wwne.aniversityupdates.in | hitps://telegram.me/jntud © Forward chaining o Backward chainitVarious levels of knowledge-based agent: ‘A knowledge-based agent can be viewed at different levels which are given below: 1. Knowledge level Knowledge level is the first level of knowledge-based agent, and in this level, we need to specify what the agent knows, and what the agent goals are. With these specifications, we can fix its behavior. For example, suppose an automated taxi agent needs to go from a station A to station B, and he knows the way from A to B, so this, comes at the knowledge level 2. Logical level At this level, we understand that how the knowledge representation of knowledge is, stored, At this level, sentences are encoded into different logics. At the logical level, an encoding of knowledge into logical sentences occurs. At the logical level we can expect to the automated taxi agent to reach to the destination B. 3. Implementation level: This is the physical representation of logic and knowledge. At the implementation level agent perform actions as per logical and knowledge level. At this level, an automated taxi agent actually implement his knowledge and logic so that he can reach to the destination. Approaches to designing a knowledge-based agent: There are mainly two approaches to build a knowledge-based agent: 1. 1. Declarative approach: We can create a knowledge-based agent by initializing with an empty knowledge base and telling the agent all the sentences with which we want to start with. This approach is called Declarative approach. id previousquestionpapers.com (www previousquestionpapers.con | hups:/telegr wuwandroidwuniversityupdates.in { wiew.amiversityupdates.in | huips:/Atelegram,mefjatuh 2. 2. Procedural approach: In the procedural approach, we directly encode desired behavior as a program code. Which means we just need to write a program that already encodes the desired behavior or agent. However, in the real world, 2 successful agent can be built by combining both declarative and procedural approaches, and declarative knowledge can often be compilad into more efficient procedural code.Propositional Theorem Proving © We show how entailment can be done by theorem proving - applying rules of inference directly to the sentences in our. knowledge base to construct a proof of the desired sentence: without consulting models Logical equivalence: two sentences a and 8 are logically equivalent if they are true in the same set of models. We write this as a = 8. For example, we can easily show (using truth tables) that PA Q and Q a P are logically equivalent; other equivalences are shown in following figure. DOIAGIQIS)Standard logical equivalences. The symbols a, B and ¥ stand for arbitrary sentences of propositional logic. Two sentences are logically equivalent iff true in same models: @=6 ifandonlyif a Band Bea (aAB) = (8Aa) commutativity of A (a VB) = (8Va) commutativity of V ((@AB) Ay) = (aA(BAY)) associativity of A ((aV 8) V7) = (aV(BV ¥)) associativity of V =(-a) = a double-negation elimination (a => 8) = (=8 > -a) contraposition (a = 8) = (-aV 8) _ implication elimination (a & 8) = ((a > B)A(B => a)) _ biconditional elimination A(a AB) = (na V8) de Morgan a(a VB) = (7a A78) de Morgan (@A(BV7)) = ((@AB)V(aA7y)) distributivity of A over V (av (8A7)) = ((aV8)A(aV 7) distributivity of V over APropositional Logic - Reasoning Patterns Inference Rules * Standard patterns of inference that can be applied to derive chains of conclusions that lead to the desired goal. These patterns of inference are called inference rules. * The useful inference rules are 1. Modus Ponens 2. And Elimination *¢ These rules can then be used in any particular instances where they apply, generating sound inferences without the need for enumerating models.Inference Rules — AND Elimination * And Elimination * From a conjunction, any of the conjuncts can be inferred aap a * Example * (WumpusAhead ~ WumpusAlive), WumpusAlive can be inferred.Inference Rules — Modus Ponens * Modus Ponens * Given: $1 > S2 and S1, derive $2 * Whenever sentences of the form o = B and o are given, then sentence B can be inferred a>B,na B * (WumpusAhead A WumpusAlive) => Shoot And (WumpusAhead A WumpusAlive), * Shoot can be inferredInference Rules — Biconditional Elimination ¢ The equivalence for biconditional elimination yields the two inference rules as B a (PBA = a) @=>AAG>a ™ as BpInference and Proofs ‘Sample Rules of Inference Sample Proof ‘Modus Ponens: {a= B.a} FB If John isnot married he isa bachelor. -P = Q) John is mora Bachelor. (4Q) “Therefore he is matied. (P) ‘And Elimination: (0B) I-05 {0.0 B} P=Q ‘And Introduction: (4, B}- aD {Implication elimination Or introduction: {ay Fav B Double negation elimi ‘Double negation Elimination: {a} Fa ‘Unit resolution Implication Eumination: {a= B}}--avB Could also check validity of: ‘Unit resolution: {av BB} Fa (P>Qa-QsP Resolution: {av P,Bv Lavy Form of modus tollens reasoningCONJUNCTIVE NORMAL FORM (CNF) In propositional logic, the resolution method is applied only to those clauses which are disjunction Coy Neel oe There are following steps used to convert into CNF: 1) Eliminate bi-conditional implication by replacing A = B with (A> B)A(B—>A) 2) Eliminate implication by replacingA —> Bwith7AVB. 3) In GNF, negation(=) appears only in literals, therefore we move it Nz TK SF-1 3 ( 7A) = A (double-negation elimination) 7(AAB A V 7B) (De Morgan's law) (A V B) =( 7A A 7B) (De Morgan ‘s law) 4) Finally, using distributive law on the sentences, and formsthe GNF Ey (A, VB,) A(A, VB.) A-A RESOLUTION ALGORITHM In resolution method, we use Proof by Refutation/Proof by Contradiction technique to prove the given statement Idea: to show that KB |= a, we show that (KB A =a) is unsatisfiable. Step 1: Convert all sentences to CNF OMe eM cca Step 2: Negate the desired conclusion (converted to CNF) * add negated clause as a premise Step 3: Apply resolution rule until either, * Derive false (a contradiction) ONC io NI liY Resolution refutation is sound.and/completeDefinite Clause and Horn Clause @ Hom clause and definite clause are the forms of sentences, which enables knowledge base to use a more restricted and efficient inference algorithm Definite clause: A clause which is a disjunction of literals with exactly one positive literal is known as a definite clause or strict horn clause. Dacre He ee Mis Puree mie RL) at most one positive literal is known as horn clause. Hence ENT ae ET ETB ie ero © Example: (+ p V 7 q Vk). It has only one positive literal k.