Horn clause and applications with detail

horn clauses and its application

1. Horn Clause and Definite
clause
BCA 6
th
AI

2. Contents
•Horn Clause and Definite clause
•Types of Horn clause
•Quantifiers
•Two forms of Horn Clause

3. Horn clause and definite clause
•Hornclauseanddefiniteclausearetheformsofsentences,which
enablesknowledgebasetouseamorerestrictedandefficientinference
algorithm.
•AHornclauseisaclause(adisjunctionofliterals)withatmostone
positive,i.e.unnegated,literal.Aclausewithatmostonepositive
(unnegated)literaliscalledaHornClause.

4. Types of Horn Clauses :
•Definite clause / Strict Horn clause :Has exactly one positive literal.
•Unit clause :Definite clause with no negative literals.
•Goal clause :Horn clause without a positive literal.
•In Datalog, rules are expressed as a restricted form of clauses called
Horn clauses, in which a clause can contain at most one positive literal.
•Clausal form:
In this form, the formula is made up of a number of clauses, where each
clause is composed of a number of literals connected by OR logical
connectives only.

5. Contd..
•Definiteclause:Aclausewhichisadisjunctionofliteralswithexactlyone
positiveliteralisknownasadefiniteclauseorstricthornclause.
•Hornclause:Aclausewhichisadisjunctionofliteralswithatmostone
positiveliteralisknownashornclause.Henceallthedefiniteclausesare
hornclauses.
•Example:(¬pV¬qVk).Ithasonlyonepositiveliteralk.
•It is equivalent to p ∧q → k.

6. Types of Quantifiers
•A formula can have following quantifiers:
•Universal quantifier –
It can be understood as –“For all x, P(x) holds”, meaning P(x) is true
for every object x in universe. For example, all trucks has wheels.
•Existential quantifier –
It can be understood as –“There exists an x such that P(x)”, meaning
P(x) is true for at least one object x of universe. For example, someone
cares for you.

7. Forms of Horn Clause
•Clausal form :
Literals can be positive literals or negative literals. For the forms of the
individual clauses where each of is a disjunction of literals. For the
clause form :
•The above clause has n negative literals and m positive literals. This
clause can be transformed into the following equivalent logical
formula :
•where ‘=>’ is the implies symbol.

8. Horn Clausal form :
•(i)The Horn clause,
•Can be transformed into the clause :
•P1 AND P2 AND … AND Pn=> Q
•which is written in Datalog as the following rules.
•The above Datalog Rule, is hence a Horn clause.

9. Contd…
•Meaning:IfthepredicatesP1ANDP2AND…ANDPn,arealltruefor
aparticularbindingtotheirvariablearguments,thenQisalsotrue
andcanhencebeinferred(concluded).
•(ii)TheHornclause,

10. Contd…
•Can be transformed into
•P1 AND P2 AND … AND Pn=>
which is written in Datalog as follows :
•TheaboveDatalogexpressioncanbeconsideredasanintegrity
constraint,whereallthepredicatesmustbetruetosatisfythequery.

11. •END OF THE PRESENTATION
•THANKS