Logic and Reasoning in Prolog

Contents
1 Logic and Reasoning 2
1.1 Types of Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Key Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2 Logic Programs 2
2.1 Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

3 Prolog Syntax and Principal Primitives 3

3.1 Basic Syntax Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
3.2 Principal Primitives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

4 Important Techniques in Prolog 3

4.1 Accumulators in Prolog . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
4.2 Tail Recursion in Prolog . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
4.3 Difference Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

5 Summary Table 11

6 Applications 11

1
1 Logic and Reasoning
Logic is the study of reasoning — determining whether statements are true or false. It
forms the foundation of Artificial Intelligence, knowledge representation, and logic
programming.

1.1 Types of Logic

• Propositional Logic: Deals with simple true/false statements.
Example: “It is raining.” can be either True or False.

• Predicate Logic (First-Order Logic): Uses variables, functions, and quantifiers

to express relationships.
Example: ∀x(Human(x) → M ortal(x))

1.2 Key Concepts

• Facts: Known true statements.

• Rules: Conditional statements derived from facts.

• Queries: Questions asked to infer new information.

Example:
human ( socrates ) .
mortal ( X ) : - human ( X ) .

? - mortal ( socrates ) .
% Output : true .

This demonstrates reasoning — since Socrates is human, he must be mortal.

2 Logic Programs
Logic programs consist of a set of facts and rules that describe relationships between
objects.

2.1 Structure
• Facts: Basic assertions.

• Rules: Logical relationships using implication (:-).

• Queries: Ask questions to infer results.

Example: Family Relationships

2
parent ( john , mary ) .
parent ( mary , sam ) .
grandparent (X , Y ) : - parent (X , Z ) , parent (Z , Y ) .

? - grandparent ( john , sam ) .

% Output : true .

3 Prolog Syntax and Principal Primitives

3.1 Basic Syntax Rules
• Facts and rules end with a period .

• Variables start with a capital letter (X, Y, Person)

• Atoms (constants or symbols) start with lowercase (john, mary)

• Comments begin with % or /* ... */

3.2 Principal Primitives

Primitive Meaning Example
Fact Known true statement bird(sparrow).
Rule If-then relation can fly(X) :- bird(X).
Query Question ?- can fly(sparrow).
Conjunction (,) Logical AND parent(X, Y), parent(Y, Z)
Disjunction (;) Logical OR male(X); female(X)
Negation (\+) Logical NOT \+bird(fish)

Example:
bird ( sparrow ) .
bird ( pigeon ) .
can_fly ( X ) : - bird ( X ) , \+ penguin ( X ) .
penguin ( tux ) .

? - can_fly ( sparrow ) . % true

? - can_fly ( tux ) . % false

4 Important Techniques in Prolog

4.1 Accumulators in Prolog
Accumulators are extra arguments added to a recursive predicate to store interme-
diate results (partial computations). They are commonly used to make recursion more
efficient and often help convert normal recursion into tail recursion.
The idea is simple:

3
 • Pass along a variable (accumulator ) that keeps track of the computation so far.

• At each recursive step, update this accumulator.

• When the base case is reached, return the accumulator as the final result.

Accumulator Examples in Prolog

1. Sum of a list using an accumulator
% Base case : empty list , accumulator is the result
sum_acc ([] , Acc , Acc ) .

% Recursive case : add head to accumulator

sum_acc ([ H | T ] , Acc , Sum ) : -
Acc1 is Acc + H ,
sum_acc (T , Acc1 , Sum ) .

Example usage:
? - sum_acc ([1 ,2 ,3 ,4] , 0 , Sum ) .
Sum = 10.

Step-by-step:

1. Call: sum acc([1,2,3,4], 0, Sum) Acc = 0, H = 1, T = [2,3,4] Update Acc:

Acc1 = 0 + 1 = 1 Recurse: sum acc([2,3,4], 1, Sum)

2. Call: sum acc([2,3,4], 1, Sum) Acc = 1, H = 2, T = [3,4] Update Acc: Acc1 =

1 + 2 = 3 Recurse: sum acc([3,4], 3, Sum)

3. Call: sum acc([3,4], 3, Sum) Acc = 3, H = 3, T = [4] Update Acc: Acc1 = 3 +

3 = 6 Recurse: sum acc([4], 6, Sum)

4. Call: sum acc([4], 6, Sum) Acc = 6, H = 4, T = [] Update Acc: Acc1 = 6 + 4

= 10 Recurse: sum acc([], 10, Sum)

5. Base case reached: Sum = 10

Reversing a List Using an Accumulator in Prolog

Prolog Code
% Helper predicate with accumulator
reverse_acc ([] , Acc , Acc ) .
reverse_acc ([ H | T ] , Acc , Rev ) : -
reverse_acc (T , [ H | Acc ] , Rev ) .

% Wrapper predicate
my_reverse (L , Rev ) : -
reverse_acc (L , [] , Rev ) .

4
Explanation
1. Helper Predicate: reverse acc(List, Accumulator, Result) is a tail-recursive
predicate that builds the reversed list by accumulating elements in Acc.

• Base Case:
reverse_acc ([] , Acc , Acc ) .

If the input list is empty, the accumulator already contains the reversed list. So the
result is simply the accumulator.
• Recursive Case:
reverse_acc ([ H | T ] , Acc , Rev ) : -
reverse_acc (T , [ H | Acc ] , Rev ) .

- ‘[H—T]‘ splits the list into head ‘H‘ and tail ‘T‘. - ‘[H—Acc]‘ prepends the head
to the accumulator. - Recursively call reverse acc on the tail T with the updated
accumulator Acc.

2. Wrapper Predicate:
my_reverse (L , Rev ) : -
reverse_acc (L , [] , Rev ) .

- Starts recursion with an empty accumulator ‘[]‘. - ‘L‘ is the list to reverse, and ‘Rev‘
will be the reversed result.

3. Example Execution
? - my_reverse ([1 ,2 ,3] , R ) .

Step-by-step evaluation:

1. my reverse([1,2,3], R) calls reverse acc([1,2,3], [], R)

2. reverse acc([1,2,3], [], R): H = 1, T = [2,3], Acc = [] Calls reverse acc([2,3],
[1], R)
3. reverse acc([2,3], [1], R): H = 2, T = [3], Acc = [1] Calls reverse acc([3],
[2,1], R)
4. reverse acc([3], [2,1], R): H = 3, T = [], Acc = [2,1] Calls reverse acc([],
[3,2,1], R)
5. reverse acc([], [3,2,1], R): Base case reached → R = [3,2,1]

4. Why Use an Accumulator?

A normal recursive reverse:
my_reverse ([] , []) .
my_reverse ([ H | T ] , Rev ) : -
my_reverse (T , RevT ) ,
append ( RevT , [ H ] , Rev ) .

5
- Uses append in each step → O(n²) complexity.
Using an accumulator: - Builds the list as we go → O(n) complexity - Tail-recursive
→ more efficient.

4.2 Tail Recursion in Prolog

Tail recursion is a special form of recursion where the recursive call is the last operation
in the clause. This means that once the recursive call is made, there is no further
computation required in that clause. Tail recursion is more memory-efficient because
the Prolog interpreter can reuse the same stack frame instead of creating a new one for
each call.

Example: Factorial using Normal Recursion

factorial(0, 1).
factorial(N, F) :-
N > 0,
N1 is N - 1,
factorial(N1, F1),
F is N * F1.

Explanation: In this example, after the recursive call factorial(N1, F1), Pro-
log still needs to compute F is N * F1. Hence, it is not tail-recursive — Prolog must
remember the pending multiplication at each recursion level.

Detailed Explanation Tail recursion with Accumulator Example

The following Prolog code computes the sum of a list using an accumulator:

sum_acc([], Acc, Acc).

sum_acc([H|T], Acc, Sum) :-
Acc1 is Acc + H,
sum_acc(T, Acc1, Sum).

Explanation:

1. The predicate sum acc has three arguments:

• The first argument is the input list.

• The second argument is the accumulator that stores the partial sum.
• The third argument is the final result (the total sum).

2. Base Case:

sum_acc([], Acc, Acc).

When the list is empty, there are no more elements to add. At this point, the
current value of the accumulator (Acc) already contains the total sum. So, the final
result (Acc) is unified with the third argument.

6
3. Recursive Case:

sum_acc([H|T], Acc, Sum) :-

Acc1 is Acc + H,
sum_acc(T, Acc1, Sum).

Here’s what happens step by step:

(a) [H|T] splits the list into:
• H — the head (first element of the list)
• T — the tail (remaining list)
(b) The new accumulator value (Acc1) is computed as:
Acc1 = Acc + H
(c) The predicate then recursively calls itself with the tail of the list and the new
accumulator:
sum acc(T, Acc1, Sum)
This process continues until the list becomes empty, at which point the base case
is triggered.
4. Example Execution:

?- sum_acc([1,2,3], 0, Sum).

Step-by-step execution:
(a) First call: sum acc([1,2,3], 0, Sum)
Acc1 = 0 + 1 = 1
Recursive call: sum acc([2,3], 1, Sum)
(b) Second call: sum acc([2,3], 1, Sum)
Acc1 = 1 + 2 = 3
Recursive call: sum acc([3], 3, Sum)
(c) Third call: sum acc([3], 3, Sum)
Acc1 = 3 + 3 = 6
Recursive call: sum acc([], 6, Sum)
(d) Base case: sum acc([], 6, Sum)
Sum = 6
5. Final Output:
Sum = 6
6. Key Idea: At every recursive step, the accumulator keeps track of the running to-
tal. This makes the recursion tail-recursive, since there are no pending operations
after the recursive call.

7
4.3 Difference Lists
Definition: A Difference List is a pair of lists written as List1-List2, where the
difference between the two represents the actual content of the list.
It is a clever representation of lists that allows efficient concatenation (append) and
building of lists in constant time, avoiding the repeated traversal of elements.

Normal Lists vs Difference Lists

In normal Prolog lists, concatenating two lists using append takes time proportional to
the length of the first list, because Prolog must traverse it to attach the second.

append([], L, L).
append([H|T], L2, [H|R]) :- append(T, L2, R).

?- append([1,2,3], [4,5], Result).

Result = [1,2,3,4,5].

But for large lists, this is inefficient.

—

Difference List Representation

A difference list is represented as:

[L1 , L2 , . . . , Ln |X] − X

Here:

• The first list ([L1, L2, ..., Ln | X]) represents the partial list.

• The second (X) represents the yet-to-be-filled “tail”.

Example:
[1, 2, 3|X] − X
represents the actual list [1, 2, 3].
If later we instantiate X = [4,5], the pair becomes:

[1, 2, 3, 4, 5] − [4, 5]

and the full list now represents [1, 2, 3, 4, 5].

—

Example: Appending with Difference Lists

append_dl(A-B, B-C, A-C).

Explanation:

• A-B is the first difference list.

• B-C is the second difference list.

8
 • The result is A-C, which represents the concatenation.
Example Query:
?- append_dl([1,2,3|X]-X, [4,5|Y]-Y, Result).
Result = [1,2,3,4,5|Y]-Y.
The result represents the list [1, 2, 3, 4, 5] as a difference list.
—

Example: Building a List Efficiently

Let’s use a difference list to collect all numbers from 1 to 3.
% Base case
build_list (0 , L - L ) .

% Recursive case
build_list (N , [ N | T ] - Rest ) : -
N > 0,
N1 is N - 1 ,
build_list ( N1 , T - Rest ) .

Example Query
? - build_list (3 , L -[]) .
L = [3 , 2 , 1].

Step-by-Step Explanation
Step 1: Initial call
build_list (3 , L -[])

- N = 3 > 0, recursive clause applies: [N |T ] − [] = [3|T ] − [] - Recursive call:

build_list (2 , T -[])

- At this point: L = [3|T ]

—
Step 2: Second call
build_list (2 , T -[])

- N = 2 > 0, recursive clause: [2|T 1] − [] - Recursive call:

build_list (1 , T1 -[])

- At this point: T = [2|T 1], so L = [3, 2|T 1]

—
Step 3: Third call
build_list (1 , T1 -[])

9
 - N = 1 > 0, recursive clause: [1|T 2] − [] - Recursive call:
build_list (0 , T2 -[])

- At this point: T 1 = [1|T 2], so L = [3, 2, 1|T 2]

—
Step 4: Base case
build_list (0 , T2 -[])

- N = 0, matches base case: T 2 − [] = L − L → T 2 = []

- Resolving all:

T 2 = [] ⇒ T 1 = [1] ⇒ T = [2, 1] ⇒ L = [3, 2, 1]

Step-by-Step Summary Table

Call N Difference List List so far
1 3 [3|T ] − [] [3|?]
2 2 [2|T 1] − [] [3, 2|?]
3 1 [1|T 2] − [] [3, 2, 1|?]
4 0 [] − [] [3, 2, 1]
—

Key Points
• Difference lists allow **efficient list construction** without traversing the list.

• The **tail variable** is instantiated only in the base case.

• The final list is obtained by closing the difference list (‘T2 = []‘).

Advantages of Difference Lists

• Faster concatenation and list building.

• Useful in grammar rules (Definite Clause Grammars, DCGs).

• Reduces memory and stack usage.

• Keeps code declarative while improving performance.

Analogy:
Think of a difference list as an “open-ended train” — the last coach (X) is still open and
can easily attach more coaches (elements) without walking back through the entire train.

10
5 Summary Table
Concept Purpose Example
Logic and Reasoning Express relationships mortal(X) :- human(X).
Logic Program Facts, rules, queries Family relationships
Prolog Syntax Define structure can fly(X) :- bird(X).
Tail Recursion Efficient recursion Sum of list
Accumulators Intermediate storage Factorial
Difference Lists Fast concatenation [1,2|X]-X

6 Applications
• Expert Systems (e.g., medical diagnosis)

• Natural Language Processing

• Knowledge Representation

• Automated Reasoning

• Symbolic AI

Prolog Example Programs

1. Family Relationships Example

Listing 1: Family Relationships

% Facts
parent ( john , mary ) .
parent ( john , david ) .
parent ( susan , mary ) .
parent ( susan , david ) .
parent ( mary , lily ) .

% Rules
father (X , Y ) : - parent (X , Y ) , male ( X ) .
mother (X , Y ) : - parent (X , Y ) , female ( X ) .

male ( john ) .
male ( david ) .
female ( susan ) .
female ( mary ) .
female ( lily ) .

% Grandparent rule
grandparent (X , Y ) : - parent (X , Z ) , parent (Z , Y ) .

Sample Queries:

11
? - parent ( john , mary ) .
? - grandparent ( john , lily ) .
? - father ( john , X ) .

2. Even and Odd Numbers

Listing 2: Even and Odd Numbers

even ( X ) : - 0 is X mod 2.
odd ( X ) : - 1 is X mod 2.

Sample Queries:
? - even (10) .
? - odd (7) .

3. Student Marks Example

Listing 3: Student Marks

% Facts
marks ( rahul , 85) .
marks ( rita , 92) .
marks ( amit , 74) .
marks ( neha , 60) .

% Rules
passed ( X ) : - marks (X , M ) , M >= 40.
distinction ( X ) : - marks (X , M ) , M >= 75.

Sample Queries:
? - passed ( rita ) .
? - distinction ( amit ) .
? - distinction ( neha ) .

4. Simple Arithmetic Example

Listing 4: Arithmetic Operations

add (X , Y , Z ) : - Z is X + Y .
multiply (X , Y , Z ) : - Z is X * Y .

Sample Queries:
? - add (5 , 3 , R ) .
? - multiply (4 , 6 , R ) .

12
5. Animal Classification Example

Listing 5: Animal Classification

% Facts
animal ( cat ) .
animal ( dog ) .
animal ( cow ) .

mammal ( cat ) .
mammal ( dog ) .
mammal ( cow ) .

has_fur ( cat ) .
has_fur ( dog ) .

% Rule
is_pet ( X ) : - animal ( X ) , has_fur ( X ) .

Sample Queries:
? - is_pet ( dog ) .
? - is_pet ( cow ) .

Additional Prolog Example Programs

1. Factorial (Recursive Example)

Listing 6: Factorial Calculation

% Base case
factorial (0 , 1) .

% Recursive case
factorial (N , F ) : -
N > 0,
N1 is N - 1 ,
factorial ( N1 , F1 ) ,
F is N * F1 .

Sample Queries:
? - factorial (5 , F ) .
F = 120.

2. Fibonacci Series

Listing 7: Fibonacci Numbers

% Base cases
fibonacci (0 , 0) .

13
fibonacci (1 , 1) .

% Recursive case
fibonacci (N , F ) : -
N > 1,
N1 is N - 1 ,
N2 is N - 2 ,
fibonacci ( N1 , F1 ) ,
fibonacci ( N2 , F2 ) ,
F is F1 + F2 .

Sample Queries:
? - fibonacci (6 , F ) .
F = 8.

3. Finding Member in a List

Listing 8: List Membership Check

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

Sample Queries:
? - member (3 , [1 ,2 ,3 ,4 ,5]) .
true .
? - member (9 , [1 ,2 ,3]) .
false .

4. Length of a List

Listing 9: List Length Calculation

length_list ([] , 0) .
length_list ([ _ | T ] , N ) : -
length_list (T , N1 ) ,
N is N1 + 1.

Sample Queries:
? - length_list ([ a ,b ,c , d ] , L ) .
L = 4.

5. Concatenation of Two Lists

Listing 10: Concatenating Lists

concatenate ([] , L , L ) .

14
concatenate ([ H | T ] , L2 , [ H | R ]) : -
concatenate (T , L2 , R ) .

Sample Queries:
? - concatenate ([1 ,2 ,3] , [4 ,5] , L ) .
L = [1 ,2 ,3 ,4 ,5].

6. Reverse of a List

Listing 11: Reversing a List

reverse_list ([] , []) .
reverse_list ([ H | T ] , R ) : -
reverse_list (T , RevT ) ,
concatenate ( RevT , [ H ] , R ) .

Sample Queries:
? - reverse_list ([ a ,b , c ] , X ) .
X = [c ,b , a ].

7. Greater Than Comparison

Listing 12: Compare Two Numbers

greater (X , Y ) : - X > Y .

Sample Queries:
? - greater (10 , 5) .
true .
? - greater (3 , 8) .
false .

8. Animal Sounds Knowledge Base

Listing 13: Animal Sounds

sound ( dog , bark ) .
sound ( cat , meow ) .
sound ( cow , moo ) .
sound ( lion , roar ) .

makes_sound ( Animal , Sound ) : - sound ( Animal , Sound ) .

Sample Queries:

15
? - makes_sound ( dog , What ) .
What = bark .
? - makes_sound ( lion , roar ) .
true .

9. Temperature Classification

Listing 14: Classifying Temperature

temperature ( cold ) : - write ( ’ Temperature is below 20 C . ’) .
temperature ( warm ) : - write ( ’ Temperature is between 20 C and 30
,→ C . ’) .
temperature ( hot ) : - write ( ’ Temperature is above 30 C . ’) .

Sample Queries:
? - temperature ( hot ) .
Temperature is above 30 C .
true .

10. Simple Knowledge Base (Countries and Capitals)

Listing 15: Country-Capital Database

capital ( india , delhi ) .
capital ( france , paris ) .
capital ( japan , tokyo ) .
capital ( italy , rome ) .

% Query Rule
get_capital ( Country , Capital ) : - capital ( Country , Capital ) .

Sample Queries:
? - get_capital ( india , X ) .
X = delhi .
? - get_capital ( france , paris ) .
true .

16