# Bengal Engineering and Science University 2006 B.E Computer Science and Engineering Symbolic Logic and Artificial Intelligence - Question Paper

the ques. paper is with the attachment.

Ex/BESUS/ CST-802/ 06

B.E. (CST) Part-IV 8th Semester Examination, 2006

Symbolic Logic and Artificial Intelligence (CST-802)

Time : 3 hours Full Marks : 100

Answer SIX questions Four marks are reserved for neatness.

W4

Wl

W3

W2

Fig.-l

The above logic circuit in Fig.-l has four wires, Wl, W2, W3 and W4. It has an "and gate", A, and an "inverter" B. The input wires, Wl and W2, can be either "on" or not. If the and gate, A, is functioning properly (OK), wire W3 is "on" if and only if wires Wl and W2 both are "on". If the inverter, B, is functioning properly (OK), wire W4 is "on" if an only if wire W3 is not "on".

a) Use expressions like OK(A), ON(W1) and so on to describe the functioning of the circuit as defined.

b) Using the formulas describing the functioning of the circuit, and assuming that all components are functioning properly and that wires Wl and W2 are "on" use resolution to show that wire W4 is not "on". [6+10]

2. a) What is answer extraction problem in FOPL? How is it solved?

b) Victor has been murdered. Arthur, Bertram and Carleton are suspects. Arthur says he did not do it. He says that Bertram was the victim's friend but Carleton hated the victim. Bertram says he was out of town on the day of the murder and besides this, he did not even know the victim. Carleton says he is innocent and he saw Arthur and Bertram with the victim just before the murder. Assuming that everyone, expect the possible murder, is telling the truth, use answer extraction to solve the crime. |(3+3)+lO]

3. a) Consider the game oftic-tac-toe (also known as noughts and crosses). Define X_{n} as the number of rows, columns, or diagonals with exactly nX's and no

b) Use accumulators to write Prolog programs

i) to remove duplicate elements from a list

ii) to find factorial of a number

iii) to perform Quick sort. [(2+2)+(3+3+6)]

8. a) Write Iterative Deepening search algorithm.

b) Explain the key idea of Means-Eds-Analysis. Explain Means-Ends-Analysis with an example. [6+(5+5)|

9. a) What is an expert system? What is the role of a knowledge engineer in the

development of an expert system? What are the application areas of an expert system? How is an expert system software different from a traditional software?

b) Draw an expert system architecture and explain its different components.

l(2x4)+8]

10. a) Write ID3 algorithm for induction of decision tree from records of solved cases, b} Consider the following set of training example :

Attributes |
Class |

A B | |

T T |
+ |

T T |
+ |

T F | |

F F |
+ |

F T | |

FT |

What are the entropies of the attributes A and B? [8+8]

O's. Similarly, O_{n} is the number of rows, columns or diagonals with just n O's and no X's. The utility function assigns +1 to any position with X_{3} = 1 and -1 to any position with O3 = 1. All other terminal positions have utility 0. For nonterminal position use a linear evaluation function defined as

Eval (s) = 3X2(s) + X,(s) - (3O2(s) + O, (s)).

i) Draw the game tree from empty board to depth 2 (i.e., one X and one O

on the board) taking symmetry into account.

ii) Mark on your tree the backed up values for positions at depth 1 and 0

using the minimax algorithm, and use them to choose the starting move.

iii) Circle the nodes at level 2 that would not be evaluated if alpha-beta

pruning were applied assuming the nodes are generated in the optimal order for alpha-beta pruning.

b) Why two-person games are difficult to solve than the games like 8-puzzle? Is the minimax search a BFS or DFS? [lO+(3+3)|

4. a) Write an algorithm for an automated theorem prover in PL.

b) Take the following statement as true from the definition of God :

"Godsaves those who can 't save themselves'

Write this as a Prolog rule whose left and right side both refer to 'saves' predicate of two arguments. Suppose the person saved is God. Show the bindings in the rule and explain what the rule becomes in this case. Does this prove that God doesn't exist? Why? [9+7]

5. a) How a tree search procedure can be converted into a graph search procedure?

What are the advantages of a graph search?

b) In the AND-OR graph, the desired path is not always the lowest cost path. Justify this statement.

c) AND-OR algorithm fails to take into account any interaction between subgoals. Give an example of this failure phenomena. [(5+3)+4+4]

6. a) Write A* algorithm for a graph and explain it with an example.

b) Prove that A* algorithm will always find optimal path to a goal, if the heuristic function is optimistic at each node. [(8+3)+5]

What is an accumulator? What is its advantage?

7. a)

Attachment: |

Earning: Approval pending. |