DATA STRUCTURE

 

 

                                                AI(Artificial Intelligence)

In AI , we discuss about Intelligence, both Machine and human. Machine Intelligence is popularly known as Artificial Intelligence.

 

***** Simple Definitions of AI.******

 

According to behviour- Oriented approach  “AI is the study of Making Computers smart ”

 

According to this  approach, AI is concerned  with programming computers to behave Intelligently.

 

“AI  is the study of making computer models of Human Intelligence.”

  “This definition is based on psychologists  point of view, where the purpose is to use computer as a tool to understand better the mechanisms of the human mind.”

 

****=> “AI is the study concerned with building machines , that simulate human behavior.

       This definition is based on robotic approach to AI ”

 

Definition by ELIANE RICH:->

  “AI is the study of how to make Computers do things, at which ,at the moment people are better. ”

              According to this definition is Idea that there are mental task that computer can do better than human beings and  vice Versa.

 

****Computer are better than human  beings in the matter of:-

Ø Numeric  Computations

Ø Information Storage

Ø Repetitive Task.

****Human beings are much better than machine in the matter of:-

§  Understanding including the capability of Expalining.

§  In the matter of Common Séance reasoning.

§  In drawing conclusion when available information is either incomplete, inconsistent.

§  In visual understanding or speech understanding.

§  In Essentially parallel processing.

 

Hence, we can say that, Computer are better than human beings :-

           in tasks requiring sequential but fast computations,

 And human beings are better than computers in tasks , requiring  essentially parallel processing.

 

As for Example there is a problem ,where require parallel processing for its solutions:-

Here, In this example on paper letter “C” is written on it and a card board with a pin hole in it. if paper is covered by card board and user only try to look at the paper through card board hole ,then some time letter C is look like letter O and some time looks like As C both.

 

 

 

Here, on the basis of contextual information or knowledge and on visual understanding , in this figure curved line represent a river and other curved line represent sides of the hills on the basis of simultaneous availability of information

 

 

Contextual information plays a very important role not only in visual understanding but also in the language and speech understanding.

For example.

 HERE the word “for a long time” has no of meaning.

 

·        He waited in the doctor’s room for a long time.

·        It has not rained for a long time.

·        Dinosaurs ruled the earth for a long time.

 

The advantage of human beings have in matter of parallel processing

 

Algorithmic method vs Non- Algorithmic Method:-

Algorithm is a step by step procedure with well defined starting and ending points, which is guaranteed to reach a solution to a specific problem. If any  problem  solved by algorithm is known as algorithmic solution

Limitation of algorithmic method:-

  Algorithmic solution is used to solve any small problem easily but when any problem is large and  we try to solve its through algorithmic method then  us require more time and space.

For example :-

        We consume less time to pay 1000 tax payers compare to one million tax payers.

To solve any problem an algorithmic approach is a limit approach.

 

For Ex:-

Consider the problem of crossing from one side over to the other side of a busy road on which a no. of vehicles are moving at different velocities.

       If we want to solve this problem by step by step (Algorithmic ) Method then:-

(i)                Knowing the distances of various vehicles from the path to be followed to cross over

(ii)              Also measure the velocities ,acceleration of various vehicles.

(iii)            Calculating the  time that would be taken by each of the various vehicles to reach the path.

(iv)            Adjusting dynamically our speeds on the path ,so that no collision taken place with any of vehicle moving on the road.

 

 

After follow upper step by step method we ensure hat no collision will be occurred, but how many of us can follow it?

 

 First of all , it is practically , impossible to measure distances ,velocities and accelerations of various vehicles on the road.

        Secondly ,w e  would not care to follow the above algorithm, because our past experience allowed us in the past , to cross over safely without  follow any systematic method

 

How ever , about to 1000 people in any one person guess is wrong and he hurt and killed.

 

After upper discussion we decide that ,instead of  Step by step  solution on a good guess provide guarantees of best  solutions.  In AI its type of guess is known as Heuristic Search.

 

 

                                    Propositional Logic (PL):-

         

                                To understand propositional logic ,first of all we try to understand about Logic.

 

Logic is the analysis and appraisal of arguments.

            An Argument is a set of statements consisting of a finite no of   assumed statements and conclusion.

For ex:-  Gopi  is begger.

Here we assume that if gopi is begger then   Gopi is not rich.(it’s a conclusions).

 

Symbolic Logic:-

         Symbolic logic is combination of philosophy, mathematics, linguistic and computer science.The discussion of symbolic ligic is depend upon Structure of Reasoning and information ..The study of symbolic logic is significant for academic pursuits.

 

 

Propositional Logic:-

In propositional Logic we intersested on declarative sentences. Declarative sentences means sentences that can be either true of False but not both.

 

for Ex:-

           “The sun rises in the west”

            “Suger is sweet”

            “Ram has a MCA degree”

 

This sentence is depend upon where Ram is actually a MCA or not.

 

“Here in this sentence, it may be known , where the statement is true or false, yet it is sure that the sentences is Either true or false and not both ”

 

For the given declarative sentences , its being ‘True’and  ’False’ is called Truth-Value.

 

In PL symbols are used to denote proposition.

 

For example we can represent upper declared declarative sentences as Symbolically.

P: The Sun rises in the west.

Q:  Sugar is Sweet.

R: Ram has a Ph.D degree.

 

These Symbols are known as :- Atoms.

By using these Atoms , we can easily Symbolize more complex proposition. These complex propositions are also known as Compound propositions. These complex propositions are solved by using logical operator(connectors).

 

These Five logical connectors  are:-   ~(not), ^(and), V(OR),

 ->(if…..Then),<-->(If and only if ) are used.

 

Now solve this problem:-

 

“If the wind speed is high and Temperature is low, then one does not fill comfortable”.

 

P: The wind speed is high.

Q: Temperature is low.

C: One fills Comfortable.

 

Its may be represented as Symbolically:-

 

((P^Q)à (~C))

 

This technique is also called Well Formed Formula.(WFF).

 

Express the following statements in propositional Logic.

(a)  If he campaigns hard, he will be elected.

Solution:-

  H: He campaigns hard.

  E : He will be elected.

         

                  H—˃E

                 

 (B) If the humidity is high, it will rain either today or tomorrow.

Solution:-

      H: Humidity is high.

      RTY:It will rain today.

      RTW: It will rain Tomorrow.

            H—˃ RTY  v  RTW

(2.)Let

      P: He needs a doctor,              Q: He needs a lawyer.

      R: He has an accident,             S: He is sick,

      U: He is injured.

 

(a)   (S —˃P) ^(R—˃Q)            

If he seak then he needs a doctor and if he has an accident then he needs a lawer.

 

                 (b)P—˃ (S  v   U)

                        if he needs a doctor then he must be either sick or injured.

(C)  (P^ Q) —˃ R

                  If he needs a doctor and a lawyer then he has an accident.                                 

                  (D) (P^Q) <--> (S^U)

                    He requires a doctor and also a lawyer if and only if he is sick and                 also injured.

                

 

         Valid Argument:-

 

A argument is known as valid argument in which contradictory for the premises to be true but conclusion is False.

     In logical studies  we are interested in valid argument.

 

Ex of valid argument:-

Ex:-

1.     (i) If you overslept , you will be late.

(ii) You are not Late.

 

So,  You did not oversleep.

                       Ex of Invalid argument:-

2.     (i)If you overslept , you will be late.

(ii) You did not oversleep.

 

 So,  you did not late.

 

(This Argument is invalid , because despite not having overslept, one may be late because of some other engagements or  laziness ).

 

Syntax of PL:-

 

A Well –Formed Formula.

 

1.     An atom is a WFF.

2.     If A is a WFF , then (~A) is WFF.

3.     If A  and   B are WFF then each of (A˄B),(A˅B),(A—˃B),(A˂—˃)is a WFF.

4.     Any WFF is obtained only by applying the above rules.

 

 

 

 

Validity through Truth –Table.

(i)                If I overslept, then I am late,  i.e., Symbolically

S —˃L

(ii)              I am not late, i.e., Symbolically

~L

                       To conclude

(iii)            I did not Oversleep, i.e.,  Symbolically

                    ~S

 

Now , We establish the validity/ Invalidity of the argument, Consider the Truth-Table.

 

S          L          S—˃L             ~L          ~S

F          F               T                 T          T

F          T               T                 T          F

T          F               F                 T          F

T          T               T                 F          F         

 

 

There is only one row, that is first row, in which both the premises   S—˃L  and ~L are True. But in this case the conclusion represented by ~S is also True. Hence, the conclusion is valid.

 

Invalidity through Truth –Table.

(i)                If I overslept, then I am late.

                S—˃L 

        (ii)                I did not oversleep, i.e.,

                                     ~S

                   To conclude

        (iii )I  would not  be  late,  i.e.,

               ~L (invalid conclusion)

 

S           L        (S—˃L  )             ~S         ~L

F            F             T                         T          T

F           T              T                         T          F

T           F             F                       F            T

T           T             T                          F          F

 

The invalidity of the argument is established , because, for validity last column must contain true in those rows for which all premises are true . But in the second row both  S—˃L   and ~S  are True but ~L  is False.

 

 

Limitation of PL:-

 

In PL we try to establish relations between given sentences and also can convert any given sentences in negation form, but its failure to explain any sentences.

            To overcome this problem new technology  generated as FOPL.

First Order Predicate Logic is represented as Real world facts can be represented as logical propositions written as WFF in PL.

FOPL is used to model world as an object. and object has available different different properties and basis of this properties FOPL try to distinguish from one object to another.

 

Why we study FOPL ?

 Because  PL is failure to represent some sentences Such as:-

 

FOPL contain/provide two types of Quantifiers.

 

(i)                Universal Quantifier(for all ’x’ such as ᵾ)

if ᵾ universal then its applicable for all variable.

and if its be in ɜ form then its applicable for some value.

 

 For example:-

 

           All dogs are brown.

(ii)Existensial Quantifier (For some ‘x’ such that ɜ)

 

 

For ex:-

(i)                All boys like football.

 

ᵾx: boys(x) à like(x,football)

 

for all x  and x is a boy then he like football

(ii)              Some boys like folltball.

 

ɜx: Boys(x) ^ Like(x,football)

(There exists some boys in if x is a boy he may like football)

 

 

Solve the following questions:-

(1)Let P(x) represent “X is a rational number”. and  Q(x) represent “x is a real number.” Then symbolize the following sentences.

 

(i)                Every rational number is  a real number.

(ᵾx)(p(x)àQ(x))

(ii)              Some real number are rational number.

(ɜX)(P(X)) ^ Q(x))

                        (III)     Not every real number is a rational number.

                                                ~(ᵾx) Q(x))à P(x).