AI with Python – Logic Programming

AI with Python – Logic Programming Essentials

This chapter delves into logic programming, a paradigm where programs are written as a set of logical statements, and explores its application in Artificial Intelligence using Python.

Logic, in essence, is the study of reasoning and inference. It allows us to deduce new information from existing true statements. For example, if we know “All humans are mortal” and “Socrates is a human,” we can infer “Socrates is mortal.”

Concept of Logic Programming

Logic Programming combines ‘logic’ and ‘programming’. It’s a programming paradigm where problems are described by facts and rules within a system of formal logic. Instead of specifying how to achieve a goal (imperative programming), you specify what the goal is and the logical relationships involved (declarative programming). The system then uses an inference engine to find solutions that satisfy these logical conditions. Prolog is a well-known language in this paradigm; Python offers libraries like kanren to achieve similar functionality.

Solving Problems with Logic Programming

Logic programming relies on two fundamental building blocks: Facts and Rules. To solve a problem, you define these for your domain and specify a goal (a query).

Facts

Facts are unconditionally true statements about the problem domain. They assert known information. For example: capital('India', 'New Delhi'). or father('John', 'Peter'). These are the basic pieces of data your logic program works with.

Rules

Rules define relationships and allow the system to infer new facts from existing ones. They are conditional statements, typically written as logical clauses. For example, a rule defining an ancestor could be: ancestor(X, Y) :- parent(X, Y). (X is an ancestor of Y if X is a parent of Y).

Rules are crucial for complex problem-solving. The general syntax is often Head :- Body., which can be read as “Head is true if Body is true.” The Body can consist of one or more sub-goals (conditions) connected by logical AND (usually a comma) or OR (often separate rules for the same head).

Example of a more complex rule:

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

This reads: “X is an ancestor of Z if X is a parent of Y, AND Y is an ancestor of Z.” This is a recursive definition. The inference engine uses these rules to search for solutions to queries.

Essential Python Packages for Logic Programming

To implement logic programming concepts in Python, we’ll primarily use the kanren library. SymPy can also be useful for symbolic mathematics, which sometimes intersects with logic programming tasks.

Kanren

kanren is a Python library that enables relational and logic programming. It allows you to express logic using facts and rules and query for solutions. Install it via pip:

pip install kanren

SymPy

SymPy is a Python library for symbolic mathematics. While not strictly a logic programming tool, it’s useful for problems involving algebraic manipulation, which can be expressed declaratively. Install it via pip:

pip install sympy

Examples of Logic Programming in Python with Kanren

Let’s explore some practical examples using kanren.

1. Matching Mathematical Expressions

Logic programming can be used to find unknown values in expressions by matching patterns. This example demonstrates how kanren can match and solve for variables in algebraic expressions.

First, import necessary components from kanren:

from kanren import run, var, fact, conde,Relation, facts
from kanren.assoccomm import eq_assoccomm as eq_ac # For associative-commutative equality
from kanren.assoccomm import commutative, associative

Define mathematical operations as constants:

add = 'add'
mul = 'mul'

Specify that addition and multiplication are commutative and associative operations. These are facts for kanren:

fact(commutative, mul)
fact(commutative, add)
fact(associative, mul)
fact(associative, add)

Declare logic variables using var():

a, b = var('a'), var('b')
x, y, z = var('x'), var('y'), var('z')

Define an original pattern, for example, (5 + a) * b. In kanren, this is represented as nested tuples:

original_pattern = (mul, (add, 5, a), b) # Represents (5 + a) * b

Define expressions to match against this pattern:

exp1 = (mul, (add, 5, 3), 2)  # (5 + 3) * 2
exp2 = (mul, 2, (add, 5, 3))  # 2 * (5 + 3) (commutative)
exp3 = (add, 5, (mul, 8, 1))  # 5 + (8 * 1) (different structure)

Use run to find solutions. run(0, (a,b), goal) means find all solutions for a and b that satisfy the goal. eq_ac checks for equality considering associativity and commutativity.

print(f"Pattern: {original_pattern}")
print(f"Expression 1: {exp1} -> Solutions for (a,b): {run(0, (a,b), eq_ac(original_pattern, exp1))}")
print(f"Expression 2: {exp2} -> Solutions for (a,b): {run(0, (a,b), eq_ac(original_pattern, exp2))}")
print(f"Expression 3: {exp3} -> Solutions for (a,b): {run(0, (a,b), eq_ac(original_pattern, exp3))}")

Expected output:

Pattern: ('mul', ('add', 5, _a), _b)
Expression 1: ('mul', ('add', 5, 3), 2) -> Solutions for (a,b): ((3, 2),)
Expression 2: ('mul', 2, ('add', 5, 3)) -> Solutions for (a,b): ((3, 2),)
Expression 3: ('add', 5, ('mul', 8, 1)) -> Solutions for (a,b): ()

The output shows that exp1 and exp2 match the pattern, yielding a=3, b=2. exp3 does not match, so an empty tuple () is returned, indicating no solutions.

2. Checking for Prime Numbers

Logic programming can define properties like primality and then query for numbers satisfying this property. This example uses kanren along with sympy for its isprime function.

Import necessary modules:

from kanren import isvar, run, membero, conde, eq, var, Relation, facts
from sympy.ntheory.generate import prime, isprime
import itertools as it

Define a goal prime_check(x) that succeeds if x is prime. If x is a variable, it generates prime numbers. If x is a ground value, it checks if that value is prime.

def prime_check(x_var):
    if isvar(x_var):
        # If x_var is a variable, generate primes
        # conde takes a list of (goal_list) pairs
        return conde([(eq, x_var, p)] for p in map(prime, it.count(1)))
    else:
        # If x_var is a ground value, check if it's prime
        return conde([(eq, True, isprime(x_var))]) # Succeeds if isprime(x_var) is True

Declare a logic variable:

x = var()

Example 1: Find prime numbers within a given list.

number_list = (12, 14, 15, 19, 20, 21, 22, 23, 29, 30, 41, 44, 52, 62, 65, 85)
# Goal: x is a member of number_list AND x is prime
result_primes_in_list = run(0, x, membero(x, number_list), prime_check(x))
print(f"Prime numbers in {number_list}: {set(result_primes_in_list)}")

Example 2: Generate the first 10 prime numbers.

# Goal: x is prime (generate)
result_first_10_primes = run(10, x, prime_check(x)) # Get 10 solutions
print(f"First 10 prime numbers: {result_first_10_primes}")

Expected output:

Prime numbers in (12, 14, 15, 19, 20, 21, 22, 23, 29, 30, 41, 44, 52, 62, 65, 85): {19, 23, 29, 41}
First 10 prime numbers: (2, 3, 5, 7, 11, 13, 17, 19, 23, 29)

3. Solving Logic Puzzles (e.g., Zebra Puzzle Variant)

Logic programming excels at solving constraint satisfaction problems like Sudoku or the famous Zebra Puzzle. Here’s a simplified setup for a Zebra-like puzzle.

The puzzle statement (classic version, slightly adapted for brevity):

1. There are five houses, each of a different color and inhabited by men of different nationalities,
   with different pets, drinks, and cigarettes.
2. The Englishman lives in the red house.
3. The Spaniard owns the dog.
4. Coffee is drunk in the green house.
5. The Ukrainian drinks tea.
6. The green house is immediately to the right of the ivory house.
7. The Old Gold smoker owns snails.
8. Kools are smoked in the yellow house.
9. Milk is drunk in the middle house.
10. The Norwegian lives in the first house.
11. The man who smokes Chesterfields lives in the house next to the man with the fox.
12. Kools are smoked in a house next to the house where the horse is kept.
13. The Lucky Strike smoker drinks orange juice.
14. The Japanese smokes Parliaments.
15. The Norwegian lives next to the blue house.
Question: Who drinks water? Who owns the zebra?

Import kanren components:

from kanren import var, run, conde, membero, eq, lall # lall for ANDing multiple goals
import time

Helper functions to define spatial relationships like ‘next to’ or ‘right of’:

def right_of(item1, item2, items_list):
    # item1 is immediately to the right of item2
    # This means (item2, item1) must be a pair in the zipped list
    return membero((item2, item1), zip(items_list, items_list[1:]))

def next_to(item1, item2, items_list):
    # item1 is next to item2 (either left or right)
    return conde([right_of(item1, item2, items_list)], [right_of(item2, item1, items_list)])

Declare a logic variable houses to represent the list of 5 house configurations. Each house is a tuple: (nationality, pet, smoke, drink, color).

houses = var() # This will be a list of 5 house tuples

Define the rules (constraints) of the puzzle using lall (logical all). This is a simplified set of rules for illustration. A full solution is more verbose.

rules_zebra_puzzle = lall(
    # Rule 1: There are 5 houses. Each house is a tuple of 5 attributes.
    (eq, (var(), var(), var(), var(), var()), houses), # Ensures 'houses' is a list of 5 items
    # Each item in 'houses' is a (nationality, pet, smoke, drink, color) tuple.
    # We'll represent each house as a tuple of variables initially.
    (membero, ('Englishman', var(), var(), var(), 'red'), houses),            # Rule 2
    (membero, ('Spaniard', 'dog', var(), var(), var()), houses),              # Rule 3
    (membero, (var(), var(), var(), 'coffee', 'green'), houses),             # Rule 4
    (membero, ('Ukrainian', var(), var(), 'tea', var()), houses),            # Rule 5

    # Rule 6: Green house right of Ivory house.
    # Let house_g = (..., 'green') and house_i = (..., 'ivory')
    (right_of, (var(),var(),var(),var(),'green'),
                 (var(),var(),var(),var(),'ivory'), houses),

    (membero, (var(), 'snails', 'Old Gold', var(), var()), houses),         # Rule 7
    (membero, (var(), var(), 'Kools', var(), 'yellow'), houses),             # Rule 8

    # Rule 9: Milk in middle house. Houses is 0-indexed list [h0, h1, h2, h3, h4]
    # So middle house is houses[2]
    (eq, (var(), var(), (var(),var(),var(),'milk',var()), var(), var()), houses),

    # Rule 10: Norwegian in first house (houses[0])
    (eq, (('Norwegian',var(),var(),var(),var()), var(),var(),var(),var()), houses),

    # Rule 11: Chesterfields next to Fox owner
    (next_to, (var(), var(), 'Chesterfields', var(), var()),
                (var(), 'fox', var(), var(), var()), houses),

    # Rule 12: Kools next to Horse owner
    (next_to, (var(), var(), 'Kools', var(), var()),
                (var(), 'horse', var(), var(), var()), houses),

    (membero, (var(), var(), 'Lucky Strike', 'orange juice', var()), houses),# Rule 13
    (membero, ('Japanese', var(), 'Parliaments', var(), var()), houses),     # Rule 14

    # Rule 15: Norwegian next to blue house
    (next_to, ('Norwegian', var(), var(), var(), var()),
                (var(), var(), var(), var(), 'blue'), houses),

    # The queries: Who drinks water? Who owns the zebra?
    (membero, (var('water_drinker_nationality'), var(), var(), 'water', var()), houses),
    (membero, (var('zebra_owner_nationality'), 'zebra', var(), var(), var()), houses)
)

Run the solver. run(1, ...) asks for one solution. The variables water_drinker_nationality and zebra_owner_nationality will be bound in the solution.

print("Solving Zebra Puzzle (this might take a while)...")
start_time = time.time()
solutions = run(1, houses, rules_zebra_puzzle) # Request 1 solution for houses
end_time = time.time()
print(f"Solved in {end_time - start_time:.2f} seconds.")

# Extract and print the answers from the solution
if solutions:
    solution_env = solutions[0] # The environment binding variables
    # To get the values of 'water_drinker_nationality' and 'zebra_owner_nationality',
    # we need to re-run the query with the specific variables we want.

    # We need to find which house tuple contains 'water' and 'zebra'
    # and extract the nationality from that tuple.

    # This requires a more complex extraction or a re-run with specific query vars.
    # For simplicity, we'll manually inspect the full 'houses' solution if printed,
    # or use a refined query for specific variables.

    # Querying specifically for the nationalities using the solved 'houses'
    water_drinker_query = run(0, var('nationality'), membero((var('nationality'),var(),var(),'water',var()), solution_env))
    zebra_owner_query = run(0, var('nationality'), membero((var('nationality'),'zebra',var(),var(),var()), solution_env))

    if water_drinker_query:
        print(f"The {water_drinker_query[0]} drinks water.")
    else:
        print("Could not determine who drinks water from the solution.")

    if zebra_owner_query:
        print(f"The {zebra_owner_query[0]} owns the zebra.")
    else:
        print("Could not determine who owns the zebra from the solution.
Likely the rules provided were insufficient or there's an issue in the rule definitions for a complete solution.")

    # print("Full solution for houses:")
    # for house_detail in solution_env:
    #    print(house_detail)
else:
    print("No solution found for the Zebra Puzzle with the given rules.")

The actual Zebra puzzle is quite complex and requires all 15 rules to be correctly encoded. The output for the classic puzzle is typically that the Norwegian drinks water and the Japanese owns the zebra. The kanren solution can find this if all rules are correctly specified.

Logic programming is a powerful tool for problems that can be expressed in terms of objects and their relationships, particularly in areas like expert systems, database querying, and automated reasoning.