• propositional logic
• we have logical variables and constant and connectives such as and , or, not, implication
• We really don't need a lot of connectives any two can do the job
  • if we use only and and not
  • x or y can be written as not(not x and not y)
  • x=>y can be written as not x or y. Another way to write the same thing is not(x and not y).

x	y	x => y	not x or y
T	T	T	T
T	F	F	F
F	T	T	T
F	F	T	T

• We only need two connectives but we use more to make our sentences more readable.
• Can we use propositional logic for serious programming?
• It is too restrictive. We need to go to the next level which is predicate logic.

• Predicate logic builds on the propositional logic by providing predicates
• Predicates are relations or functions
  • Relations
  • father(john,jacob).
  • relations define relationship between two different objects
  • function
  • right_hand_of(john).
  • specifies a new object, saves us from creating new object for right_hand of every person
  • We will concentrate more on relations
  • Predicate logic also provides quantifiers.

• for all x, x is a mammal implies that there exists a y such that y is a parent of x.
• All of the english language sentences that make sense can be translated to logical statements. We may have to go to higher order logic in some cases (beyond the scope of this class)
• x is a parent of y if x is mother of y or x is father of y
• 
• Above logical representation will not be possible with propositional logic.
• horses, cows, and pigs are mammals

• an offspring of a horse is a horse

• Bluebeard is a horse
• Horse(Bluebeard)
• Bluebeard is Charlie's parent
• Parent(Bluebeard,Charlie).
• Offspring and parent are inverse relations

• Every mammal has a parent

• We want to write programs that use logical sentences and do the reasoning on their own
• Prolog is one of the most popular languages for logic programming
• It uses slightly restrictive type of predicate logic called Horn Clause Logic
• In Horn Clause logic, all the sentences are of the form

• These sentences can be easily written in conjunctive normal form CNF
• Every sentence in conjunctive normal form is a disjunction

• can be easily converted to a CNF as
• Substitution and resolution to do the reasoning
• If a sentence has P(x) and another sentence has not P(A)
• then we can substitute x/A and resolve the two sentences by eliminating P as well as not P
• read the example from the Blackboard that proves that Charlie is mammal
• In Prolog, we write as
• a :- x,y,....,z
• The implication operands are written in reverse order
• comma corresponds to the and operator
• semicolon corresponds to or operator
• :- is <=
• Prolog deviates from another convention in Logic
• constants in prolog start with a lower case letter
• variables in prolog start with an upper case later

horse(blue).

parent(blue,charlie).

mammal(X) :- horse(X).

mammal(X) :- horse(Y),offspring(X,Y).

offspring(X,Y):-parent(Y,X).

• The program does identify charlie and blue as mammals, but goes into infinite recursion looking for third mammal.
• This is a frequent problem in prolog programs
• The order of the rules matters.

ancestor(X,Y):-parent(X,Y).

ancestor(X,Y):-ancestor(X,Z),parent(Z,Y).

• If you reverse the order of the two statements above, you will get into an infinite loop.
• List processing in prolog
• Prolog is used for AI programming. Needs symbolic manipulations
• [a,b,c]
• we can separate the list as:
• [a,b|[c]]
• [a|[b,c]]
• [a,b,c|[]]
• [H|T]=[a,b,c]