[go: up one dir, main page]
Scribd
Upload
67 views18 pages

#14 Horn Clause

The document discusses logic programming and Horn clauses. It defines key concepts such as literals, clauses, conjunction, disjunction, and different types of Horn clauses. Specifically: - Literals are basic statements that can be true or false and are components of clauses. - Clauses are logical statements composed of one or more literals. There are Horn clauses and general clauses. - Conjunction implies both statements are true, while disjunction means at least one is true. - Horn clauses have at most one positive literal and are well-suited for rules. Types include definite, unit, and goal clauses depending on structure.

Uploaded by

Nishaa Latif
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
67 views18 pages

#14 Horn Clause

The document discusses logic programming and Horn clauses. It defines key concepts such as literals, clauses, conjunction, disjunction, and different types of Horn clauses. Specifically: - Literals are basic statements that can be true or false and are components of clauses. - Clauses are logical statements composed of one or more literals. There are Horn clauses and general clauses. - Conjunction implies both statements are true, while disjunction means at least one is true. - Horn clauses have at most one positive literal and are well-suited for rules. Types include definite, unit, and goal clauses depending on structure.

Uploaded by

Nishaa Latif
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 18

HORN

CLAUSE
139,148,150
LOGIC
PROGRAMMING
Logic programming involves defining a
set of logical rules, facts, and queries to
perform automated reasoning.
The rules, often written in the form of
Horn clauses that define relationships
and implications.
IMPORTANT
SYMBOLS

(or)

(and)

~ or
(Conditional)
LITERAL:
Literal is a statement that can be either true or
false
it can be represent by a variable.
A literal can be Positive (a simple fact) or
negative.
Examples of literals:
Positive Literal "It is raining" X
Negative Literal: "It is not raining" ~X

A literal is a basic component of a clause.


CLAUSE
A clause is a logical statement
that expresses a piece of
information or a rule. It's
composed of one or more literals.
There are two main types of
clauses:
Horn Clause
General Clause
CONJUNCTION &
DISJUNCTION

A conjunction implies that both


statements are true (and)
Disjunction implies that at least
one statement is true(or)
HORN CLAUSE
Horn clauses are a specific type of logical formula used
within logic programming.
∨
Horn clause is a disjunction( ) with at most one
positive literal
Horn clauses are well-suited for expressing rules and
implications in a concise and structured manner.
Example:
~X1 ∨ ~X2 ∨ ... ∨~Xn ∨Y
0r
¬X1 ∨ ¬X2 ∨ ... ∨¬Xn ∨Y
EXAMPLE QUESTION
Convert the Following into horn clause

Example 1: ∵ to remove (→) implies sign


(X1 ∧ X2 ∧...∧Xn)→Y negation(¬) sign is applied
that converts and∧ into or∨
¬(X1 ∧ X2 ∧...∧Xn)∨Y
¬X1 ∨ ¬X2 ∨...∨¬Xn∨Y Horn Clause (disjunction
function and one positive
literal)

Horn Clause to Prolog Programming (replace disjunction with


comma, sign)

¬X1 , ¬X2 ,...,¬Xn,Y


EXAMPLE QUESTION
Convert the Following into horn clause
Example 2: ∵ to remove (→) implies sign
∧
negation(¬) sign is applied
(A B)→C ∧
that converts and into or ∨
Step 1: ¬(A∧B)∨C
Step 2: ¬A∨¬B∨C Demorgan's law

Example 3:
∨
(X Y)→Z
Step 1: ¬(X∨Y)∨Z
Step 2: ¬X∧¬Y∨Z Distributed Property
Step 3: (¬X∨Z)∧(¬Y∨Z)
EXAMPLE QUESTION
Convert the Following into horn clause
Example 4: ∵ to remove (→) implies sign
∨B)→C
negation(¬) sign is applied
(A ∧
that converts and into or ∨
Step 1: ¬(A∨B)∨C
Step 2: ¬A∧¬B∨C
(¬A∨C)∧(¬B∨C)
Demorgan's law
Step 3:

Distributed Property
EXAMPLE QUESTION
Convert the Following into horn clause
Example 5: ∵ to remove (→) implies sign
∧B)→C
negation(¬) sign is applied
(¬A ∧
that converts and into or ∨
Step 1: ¬(¬A∧B)∨C
Step 2: (A∨¬B)∨C
Step 3: A∨¬B∨C This is not a horn clause because
in horn clause there may be
atmost one positive literal here
are two positive literals A and C
EXAMPLE QUESTION
Convert the Following into horn clause
Example 6: ∵ to remove (→) implies sign
∨¬B)→C
negation(¬) sign is applied
(A ∧
that converts and into or ∨
Step 1: ¬(A∨¬B)∨C
Step 2: (¬A∧B)∨C
Step 3: (¬A∨C)∧(B∨C) This is not a horn clause because
in horn clause there may be
atmost one positive literal here
are two positive literals B and C
TYPES OF
H0RN CLAUSE
Horn clauses can be categorized into several types
based on their structure and properties.

Definite clause / Strict Horn clause:


A definite clause is a Horn clause that has exactly one positive
literal.
This clause can be interpreted as the implication "If p is true, then
q and r are false.
Example 1: p ¬q ∨ ∨ ¬r
Example 2: A → B
TYPES OF
H0RN CLAUSE
all definite clauses are Horn clauses, but not all Horn clauses
are definite clauses.

Unit clause
A unit clause is a clause that has only one literal,
and that literal must be either positive or
negative.
It can be understood as an assertion that the
positive literal is true (or false, depending on the
literal)
TYPES OF
H0RN CLAUSE
Example of Unit Clause:
A (true)
¬B (false)
Goal Clause:
A goal clause is a Horn clause that has no positive
literals.
It can be understood as a query to prove that the
negative literals are false.
A Horn clause can have zero or more goal clauses.
TYPES OF
H0RN CLAUSE
Example 1 of Goal Clause:

p ∨ q ∨¬r
This clause states that either p or q is true, or r is
false. The goal clause is ¬r, which means that we
are trying to prove that r is false.
TYPES OF
H0RN CLAUSE
Another Example with 2 Goal Clause:

¬p ∨ ¬q ∨ s
This clause states that either p or q is false, or s is
true. The goal clauses are ¬p and ¬q, which means
that we are trying to prove that p and q are both
false.
THANK YOU!

You might also like