BCC questions

Basic Computer Concept
FM: 50
Duration: 2 hrs


1. What is a computer? Classify it according to the operation, uses and capacity.
2. Describe the basic organization of a PC.
3. What is an operating system? Differentiate between uniproramming and multiprogramming. What is a time-sharing OS?
4. What is a network? What are the benefits of networking? Explain Ethernet and the cables and connectors used in this network.
5. Give brief explanations of
a. Compiler and Interpreter
b. Laser Printer

Artificial Intelligence

Lab sheet No:4

FOPL and Prolog

Introduction

First Order Predicate Logic (FOPL) is a generalisation of Propositional Logic. Logic Programs are written in a sub-language of FOPL and therefore derive their meaning and formal properties from it.

FOPL has two major extensions over Propositional Logic:

1. Propositions are renamed "predicates" and may possess an internal structure. In fact the predicates of FOPL have precisely the same syntactic structure as they have in Prolog - i.e. a predicate name with terms as arguments, each term being a

-constant,

-variable, or

-funcion with term(s) as argument(s).

2. Variables must be quantified by either

A meaning "for all" or

E " "there exists"

e.g Ex P(x) means "some unspecified constant has property P". Each quantifier has a SCOPE which is defined as the textual area in which it binds occurrences of its variable. This scope is usually delimited by brackets, unless it is obvious as in the example above.

These extensions critically extend the expressive power of logic. Consider the following sentences which are given a natural corresponding syntax in predicate calculus:

"John is the brother of Jim." brother_of(john,jim).

"Socrates is dead and buried." dead(socrates)&buried(socrates).

"All men are mortal." Ax (man(x) -> mortal(x)).

As an exercise try to express these in propositional logic!

Conversion of Prolog into FOPL:

Prolog clauses can be directly translated into FOPL, except for a few exceptions like write, !, is, assert, retract, ...

The three simple rules for conversion are:

- "," corresponds to "&"

- ":-" corresponds to "<-"

- All variables are universally quantified.

Examples

1. grandfather(X,Y) :- father(X,Z),parent(Z,Y).

In FOPL:

Ax,Ax,Az (grandfather(x,y) <- (father(x,z)&parent(z,y)))

2. uncle(X,Y) :- parent(Z,Y),brother(X,Z).

In FOPL:

Ax,Ay,Az ( uncle(x,y) <- (parent(z,y)&brother(x,z)))

3. member(X,[X|T]).

In FOPL:

Ax,Ay,At (member(x,[x|t]))

4. member(X,[Y|T]) :- member(X,T).

In FOPL:

Ax,Ay,At (member(x,[y|t]) <- member(x,t))

5. a :- b,c,d,e.

In FOPL:

a <- (b & c & d & e)

If we use the laws derived from the meaning of the logical connectives, we can simplify the expressions in 1, 2, 4, and 5:

1. AX,AY,AZ (grandfather(X,Y) <- (father(X,Z) & parent(Z,Y)) )

by "<-" simplification this becomes

= AX,AY,AZ (grandfather(X,Y) V ~(father(X,Z) & parent(Z,Y)) )

using "not" simplification this becomes

= AX,AY,AZ ( grandfather(X,Y) V ~father(X,Z) V ~parent(Z,Y) )

3. AX,AY,AT (member(X,[Y|T]) <- member(X,T))

by "<-" simplification this becomes

= AX,AY,AT (member(X,[Y|T]) V ~member(X,T))

4. AX,AY,AZ ( uncle(X,Y) <- (parent(Z,Y) & brother(X,Y)) )

by "<-" simplification this becomes

= AX,AY,AZ ( uncle(X,Y) V ~(parent(Z,Y) & brother(X,Y)) )

using "not" simplification this becomes

= AX,AY,AZ ( uncle(X,Y) V ~parent(Z,Y) V ~brother(X,Y) )

5. a <- (b & c & d & e)

by "<-" simplification and "not" simplification this becomes

= a V ~b V ~c V ~d V ~e

The following should be obvious from the examples:

Any Prolog clause which is translated into FOPL has exactly one positive (i.e. non-negated) predicate - originally the head of the Prolog clause.

Assignments

PREMISES 1

1. Horses, cows, pigs are mammals.

2. An offspring of a horse is a horse.

3. Bluebeard is a horse.

4. Bluebeard is Charlie’s parent.

5. Offspring and parent are inverse relations.

6. Every mammal has a parent.

QUERY

1. Is Charlie a horse?

PREMISES 2

2. every American who sells weapons to hostile nations is a criminal.

3. every enemy of America is a hostile.

4. iraq has some missiles.

5. all missiles of iraq were sold by george.

6. george is an American

7. iraq is a country.

8. iraq is the enemy of America.

9. missiles are weapons.

QUESTION

1. Is George a criminal ?

PREMISES 3

1. All pompeians are romans.

2. all romans were either loyal to Caesar or hated him.

3. everyone is loyal to someone.

4. people only try to assassinate rulers they are not loyal to.

5. marcus tried to assassinate Caesar.

6. marcus was Pompeian.

QUESTION

1. did marcus hate Caesar?

PREMISES 4

Bhogendra likes all kinds of food. Oranges are food. Chicken is food. Anything anyone eats and isn’t killed by is food. If a person likes a food means that person has eaten it. Jogendra eats peanuts and is still alive. Shailendra eats everything Bhogendra eats.

QUESTION

Does Shailendra like chicken.

PREMISES 5

Dave and Fred are members of a dancing club in which no member can both waltz and jive. Fred"s dad can"t waltz and Dave can do whatever fred can"t do. If a child can do something, then their parents can do it also.

PROVE that there is a member of the dancing club who can"t jive.

1

Artificial Intelligence

Lab sheet No:3

Constraint satisfaction problems

Introduction

Constraint programming is a useful tool in formulating and solving problems that can be defined in terms of constraint among a set of variables. In fact real world problems are constraint satisfaction problems defined in terms of some variables that bear some constraints. Finding a set of variables, that are within the constraints given(or observed) is a solution to that problem.

Let us consider a problem, that can be represented by some relations of the variables x, y and z. We have a domain Dx, Dy, Dz from where the variables can take a value. The constraint is given by a set C and may have a number of constraints C₁,C₂,C₃,etc each relating some or all of the variables x,y and z. Now a solution (or solutions) to the problem is a set dx,dy,dz such that dx Dx, dy Dy and dz Dz and all the constraints of the set C are satisfied.

Eight queens problem

Eight queens problem is a constraint satisfaction problem. The task is to place eight queens in the 64 available squares in such a way that no queen attacks eachother. So the problem can be formulated with variables x₁,x₂,x₃,x₄,x₅,x₆,x₇,x₈ and y₁,y₂,y₃,y₄,y₅,y_6, y₇,y₈; the xs represent the rows and ys the column. Now a solution for this problem is to assign values for x and for y such that the constraint is satisfied.

The problem can be formulated as

P={(x₁,y₁),(x₂,y₂),……………………..(x₈,y₈)}

where (x₁,y₁) gives the position of the first queen and so on.

So it can be clearly seen that the domains for x_i and y_i are

Dx = {1,2,3,4,5,6,7,8}and Dy ={1,2,3,4,5,6,7,8} respectively.

The constraints are

1. No two queens should be in the same row,

i.e y_i≠y_j for i=1 to 8;j=1 to 8;i≠j

2. No two queens should be in the same column,

i.e x_i≠x_j for i=1 to 8;j=1 to 8;i≠j

3. There should not be two queens placed on the same diagonal line

i.e (y_i-y_j) ≠ ±(x_i-x_j).

Now a solution to this problem is an instance of P wherein the above mentioned constraints are satisfied.

PREDICATES

DOMAINS

cell=c(integer,integer)

list=cell*

int_list=integer*

PREDICATES

solution(list)

member(integer,int_list)

nonattack(cell,list)

CLAUSES

solution([]).

solution([c(X,Y)|Others]):-

solution(Others),

member(Y,[1,2,3,4,5,6,7,8]),

nonattack(c(X,Y),Others).

nonattack(_,[]).

nonattack(c(X,Y),[c(X1,Y1)|Others]):-

Y<>Y1,

Y1-Y<>X1-X,

Y1-Y<>X-X1,

nonattack(c(X,Y),Others).

member(X,[X|_]).

member(X,[_|Z]):-

member(X,Z).

GOAL

solution([c(1,A),c(2,B),c(3,C),c(4,D),c(5,E),c(6,F),c(7,G),c(8,H)]).

Assignment 1). Observe the result of the above program and discuss on the result. Test the goal by placing a few queens explicitly.

(Try goals like solution ([c(1,1),c(2,B),c(3,C),c(4,8),c(5,E),c(6,F),c(7,G),c(8,H)] etc).

Assignment 2). Try to solve the above problem using C or C++.

Assignment 3). Create a DLL file using prolog and use it in any of the available languages java or .NET to depict the solution. Make it interactive. (You may want to set a queen in the fifth row of the first column).

Crypto arithmetic problem

Crypto arithmetic problem is yet another constraint satisfaction problem. We have to assign numeric values(0 through 9) to the alphabets in the given words in such a way that the sum of the two words equals the third.

For example: SEND+MORE=MONEY

We have to assign values to the individual alphabets in such a manner that the arithmetic rules are followed, a trivial solution will be to assign 0s to all, but we have a constraint, no two alphabets should be assigned with the same number.

C₄ C₃ C₂ C₁

S E N D

+ M O R E

M O N E Y

So, by now we have the problem in hand. The domain for the alphabets is

S,E,N,D,M,O,R,Y€ {0,1,2,3,4,5,6,7,8,9}.

The constraints are

D+E=Y+10C₁

N+R+C₁=E+10C₂

E+O+C₂=N+10C₃

S+M+C₃=O+10C₄

M=C₄

C₁,C₂,C₃,C₄€{0,1}

And we have the constraint that no two alphabets should be assigned with the same number.

Assignment 4) Write a module in prolog to solve the crypto arithmetic problem.

1

Artificial Intelligence

Lab sheet No:2

Introduction to Prolog contd…

Backtracking

As has already been seen prolog has built in backtracking mechanism. It tries to prove a goal with all possible instantiations. Automatic backtracking is a useful programming concept because it reveals the programmer of the burden of backtracking explicitly. However in some cases this feature degrades the efficiency of the program.

For example in cases where one solution is sufficient, backtracking to find all the solutions is not a good idea. Similarly, in case of mutually exclusive rules(clauses) when one rule has been proved then it is known in advance that no other rules can succeed. So this backtracking can be controlled by the use of ‘cut’, (“!”).

The disadvantage of using cut is that we tend to move away from the declarative nature of the prolog because when we have used the cut the order of the clauses may make difference in the result we get.

Consider the function shown in the above figure. The relation between X and Y can be specified by the following three rules.

Rule 1: if X<3 then Y=0

Rule 2: if 3=<X <6 then Y=2

Rule 3: if 6<X then Y=4

This can be programmed as

PREDICATES

f(integer,integer)

CLAUSES

f(X,0):-

X<3.

f(X,2):-

3<=X,X<6.

f(X,4):-

6<X.

GOAL

f(2,X).

Assignment 1.) Now modify the program using cut and observe the difference between the two modules. Comment on the difference.

Assignment 2.) Define the relation min(X,Y,Z) where Z returns the smaller of the two given numbers X and Y. Do it with and without the use of cut and comment on the result.

Structure revisited

In prolog we can use structures to define data types of our requirement. For example if we want to use date as an structure we can define date as a structure in the domains section as follows

date=d(integer,symbol,integer)

We can then on use date as a data type to contain the date.

DOMAINS

date=d(integer,symbol,integer)

PREDICATES

inquire

display(symbol)

date_of_birth(symbol,date)

CLAUSES

date_of_birth(ram,d(12,july,1983)).

date_of_birth(shyam,d(15,august,1976)).

date_of_birth(hari,d(26,may,1994)).

date_of_birth(sita,d(29,september,1991)).

display(X):-

date_of_birth(X,Y),

write(X),nl,

write(Y).

inquire:-

write("Enter the name"),

readln(X),

display(X).

GOAL

inquire.

Here the goal so proceeds as to ask a name from the user and to display the date of birth of the person with that name. With a little modification we can write goals which can find out persons with age below or above certain value, persons born in a month etc as in a relational database.

So the facts of the prolog can be thought of as a database. In fact we use structures to define certain relations and for all purposes of integrity this can be used similar to a table in a relational database. We call it the prolog’s internal database. We can update this database during the execution of the program by using the following keywords.

assert(C) – this keyword can be used to assert a data in the facts base as

asserta(C) and assertz( C) can be used to control the position of insertion, the two asserts at the beginning and the end respectively.

retract( C) –deletes a clause that matches C.

An example

DOMAINS

date=d(integer,symbol,integer)

works=w(symbol,integer)

FACTS

person(symbol,symbol,date,works).

PREDICATES

start

load_name

evalans(integer)

display

search

dispname(symbol)

delete

CLAUSES

person(shyam,sharma,d(12,august,1976),w(ntv,18000)).

person(ram,sharma,d(12,august,1976),w(ntv,18000)).

person(ram,singh,d(13,may,2001),w(utl,12000)).

start:-

write("*************MENU**************"),nl,

write("Press 1 to add new data"),nl,

write("Press 2 to show existing data"),nl,

write("Press 3 to search"),nl,

write("Press 4 to delete"),nl,

write("Press 0 to exit"),nl,

write("*************MENU**************"),nl,

readint(X),

evalans(X).

evalans(1):-

load_name,

start.

evalans(2):-

display,

evalans(2).

evalans(3):-

search,

evalans(3).

evalans(4):-

delete,

evalans(4).

evalans(0):-

write("Thank You").

delete.

/* write clauses delete a fact from the facts base */

search.

/*write clauses to search a fact from the facts base */

dispname(N):-

person(N,C,d(D,M,Y),w(O,S)),

write("Name:",N," ",C),nl,

write("Date of Birth:",D,"th"," ",M," ",Y),nl,

write("Organisation:",O),nl,

write("Salary:",S),nl,nl.

display:-

retract(person(N,X,d(D,M,Y),w(O,S))),

write("Name:",N," ",X),nl,

write("Date of Birth:",D,"th"," ",M," ",Y),nl,

write("Organisation:",O),nl,

write("Salary:",S),nl,nl.

load_name:-

write("Enter the name n"),

readln(N),

write("Enter the surname n"),

readln(S),

write("Date of Birth n Day:"),

readint(D),nl,

write("Month:"),

readln(M),nl,

write("Year:"),

readint(Y),nl,

write("Enter the organisation:"),

readln(O),

write("Enter the salary:"),

readint(Sl),nl,nl,

asserta(person(N,S,d(D,M,Y),w(O,Sl))).

GOAL

start.

We may not use prolog to handle databases but the use of prologs internal database makes problem solving with prolog lot more easy.

Assignment: Observe the above program. Add clauses for search and delete and extend your module as much as you like 3.

Simple application

Let us now see how the features of prolog can be used to simulate a non-deterministic automata which would have been a cumbersome task using other programming languages.

A nondeterministic finite automaton is an abstract machine that reads a string of symbols as input and decides whether to accept or to reject the input string. An automaton has a number of states and it is always in one of the states. The automata can change from one state to another upon encountering some input symbols. In a non deterministic automata the transitions can be non deterministic meaning that the transition may take place with a NULL character or the same character may result in different sitions

A non deterministic automaton decides which of the possible moves to execute, and it chooses a move that leads to the acceptance of the string if such a move is available.

Let us simulate the given automata.

DOMAINS

Symb_list=symbol*

PREDICATES

Trans(symbol,symbol,symbol)

Silent(symbol,symbol)

Final(symbol)

CLAUSES

final(s3).

trans(s1,a,s1).

trans(s1,a,s2).

trans(s1,b,s1).

trans(s2,b,s3).

trans(s3,b,s4).

silent(s2,s4).

silent(s3,s1).

accepts(S,[]):-

final(S).

accepts(S,[H|T]):-

trans(S,H,S1),

accepts(S1,T).

accepts(S,X):-

silent(S,S1),

accepts(S1,X).

GOAL

Accepts(S,[a,b]).

Assignment 4.) Check the automaton with various input strings and with various initial states. ( The initial state need not necessarily be s1.) Observe the result and comment on how the simulation works.

Use the following goals

• accepts(s1,[a,a,b]).

• accepts(s1,[a,b,b]).

• accepts(S,[b,a,b]).

• accepts(s1,[X,Y,Z]).

• accepts(s2,[b]).

• accepts(s1,[_,_,_,_|[a,b]]).

1

Artificial Intelligence

Lab sheet No:1

Introduction to Prolog

Prolog is a very important tool in programming artificial intelligence applications and in the development of expert systems. By allowing the programmer to model the logical relationships among objects and processes, complex problems are inherently easier to solve, and the resulting program is easier to maintain through its lifecycle. With Visual Prolog, applications such as customized knowledge bases, expert systems, natural language interfaces, and smart information management systems are easy to develop. Prolog is what is known as a declarative language. This means that given the necessary facts and rules, Prolog will use deductive reasoning to solve the programming problems. This is in contrast to traditional computer languages, such as C, BASIC and Pascal, which are procedural languages. We can also use prolog as any other programming languages in a procedural manner.

So prolog can be viewed as a tool to solve problems in the field of artificial intelligence or it can be very well used a general programming language.

Prolog enforces a different problem solving paradigm complementary to traditional programming languages so it is believed that a student of computer should learn programming in prolog.

Data types in prolog

• Atoms and numbers

• Variables

• Structures

Atoms and numbers

Atoms can be constructed in three different ways

1. strings of letters, digits, and the underscore character ‘_’ starting with a lower case letter.

for example:

man, ram, comp_students, pc_ct_059.

2. strings of special characters

for example:

<------->

:::::::::::

Care should be taken not to use the character combination that may have some built in meaning.

3. strings of characters enclosed in quotes

for example

‘Ram’

‘Bird’

Numbers used in prolog are integers and real numbers.

Variables

Variables are strings of letters digits and underscore that start with an underscore or an upper-case letter. The scope of a variable is one clause only. So the same variable used in different clauses mean different thing.

For example:

X, Ram, _weight etc.

Note here that Ram is a variable unlike the earlier use ‘Ram’ where it was a constant, an atom.

An underscore ‘_’ also known as anonymous variable is used in clauses when a variable need not be inferred to more than once.

Structures

Structures are objects that have different components. The components can be atoms or yet some other structures. A functor is used to construct a structure as follows.

family(father, mother, children)

Here family is a structure that has father, mother and the children as its elements. The father and mother may be atoms while the children may be yet another structure or a list of atoms. List is a special built in structure in prolog.

A list is a built in structure in prolog. It can be thought of as a sequence of elements ordered linearly however it is internally represented as a binary tree.

For example:

[ram,shyam,hari,sita]

The representation is as follows

The list as such can be broken down into two parts, the HEAD and the TAIL. The head is the first element of the list and the tail is the remaining list. The above list can be broken down as

[H| T]

Where H= ram

and T= [shyam, hari,sita]

List is one of the most useful structure in prolog.

Writing programs in prologs

All prolog programs start from the goal. It then uses the facts and clauses to break down the goal to sub-goals and tries to prove the subgoals. A clause is said to have succeeded if there is a combination of facts and clause(s) that holds true.

Prolog has built in backtracking mechanism i.e. whenever there are multiple paths, it chooses one tries to prove it, and comes back to the other choices whether the first one succeeds or fails.

Program 1: A typical prolog program

PREDICATES

bigger(integer,integer,integer)

CLAUSES

bigger(X,Y,Z):-

X>Y,Z=X.

bigger(X,Y,Z):-

X<Y,Z=Y.

GOAL

bigger(5,7,X).

In program 1 we have defined a predicate that gives us the larger of the two given integers. The predicate bigger is defined in the PREDICATES section and the relation is defined in the CLAUSES section. It is customary to put together the predicate definition and clause definition for each predicate but it is not necessary. However all the clauses for a predicate have to be written together.

The predicates section defines what types of relations or facts we are going to use. It is somewhat like declaring functions in programming languages like C. The clauses section holds the relation and facts and can be compared to function definition.

Program 2: A program combining facts and rules.

PREDICATES

husband(STRING,STRING)

father(STRING,STRING)

mother(STRING,STRING)

son(STRING,STRING)

CLAUSES

mother("Kaushalya","Ram").

mother("Kaikai","Bharat").

mother("Sumitra","Laxman").

mother("Sumitra","Satrughan").

husband("Dasarath","Kaushalya").

husband("Dasarath","Kaikai").

husband("Dasarath","Sumitra").

son(A,C):-mother(C,A).

son(A,C):-husband(C,B),mother(B,A).

father(A,B):-husband(A,C),mother(C,B).

Goal

son(X,"Kaikai").

Here the predicate mother is used to assert facts. There are four facts in that section. Similarly the predicate husband is used to assert more facts. The predicates son and father are used to define rules. We could have defined rules even with mother and husband but we bet that conciseness for program clarity at this stage.

The goal can be checked with

son( “Ram”,X).

father(X,”Ram”).

Program 3: A program to find the length of a list

DOMAINS

int_list=integer*

PREDICATES

length(int_list,integer)

CLAUSES

length([],0).

length([H|T],L):-

length(T,L1),

L=L1+1.

GOAL

length([1,2,5,2,1,6,7],X).

Program 4 A program to read integers into a list and display them.

DOMAINS

list=integer*

PREDICATES

start

read_a_list(list)

insert(integer,list,list)

display(list)

CLAUSES

start:-

write("enter the numbers"),

nl,

write("enter 0 to stop"),nl,

read_a_list([]).

read_a_list(Y):-

readint(X),

insert(X,Y,Z),

read_a_list(Z).

insert(0,Y,_):-

write("these were the elements you inserted"),

nl,

write("["),

display(Y).

insert(X,Y,[X|Y]).

display([ ]):-

write(" ]"),nl.

display([H|T]):-

write(H),write("t"),display(T).

GOAL

start.

Assignments

1. Write a program to find the hcf of two numbers.

Hint: use a predicate like hcf(no1,no2,result).

2. Write a program to find the factorial of a given number.

3. Write a program of your choice. Give some facts and use some rules to make a few deductions.

4. Write a program to add the content of an integer list and display it.

5. Write a program to find the length of a list.

6. Write a program to append two lists.

7. Write a program which takes a list of integers and displays only 1s and 2s. ( If the input is [1,2,4,5,2,4,5,1,1] the solution list should be [1,2,2,1,1]. )

8. Write a program to delete a given element from the list.

1