Semantic and Declarative Technologies

AIT Budapest, 2025 fall

Péter Szeredi
László Kabódi
Péter Tóth

The 711 problem

One day, a customer bought four items at a 711 store. The cashier said:

"That will be $7.11, please."
"Is it $7.11 because this is a 711 store?"
"No, I multiplied the prices together and got $7.11."
"But you are supposed to add them, not multiply them."
"Oh, you’re right! Let me recalculate … that will be $7.11."

What were the four prices? (No rounding)

Topics and layout of the course

Duration Topic
2 weeks Propositional & First Order Logic
5 weeks Logic Programming:
the Prolog programming language
5 weeks CLPFD:
Constraint Logic Programming (on Finite Domains)
2 weeks Description Logics for Semantic Web

Requirements

  • Two programming assignments:
    Prolog (Sudoku solver), CLPFD (Skyscraper sudoku solver)
    15% each, total 30%


  • Two tests: mid-term & final 20% each, total 40%


  • Many small exercises + class activity 30%

Prolog — Programming in logic

  • A Prolog program consists of simple logic statements
  • The slogan of Prolog: WHAT rather than HOW
  • A Prolog program describes WHAT to do, but it is also important to know HOW Prolog executes the program
  • A sample logic statement (also called predicate): 
                                    
                                has_gp(GC, GP) :-
                                    has_p(GC, P),
                                    has_p(P, GP).
                                
                            
                                    
                                    % GC has grandparent GP if
                                    % GC has parent P and
                                    % P has parent GP.
  • Prolog is a symbolic language: 1+1 is a tree structure, not evaluated to 2 by default

Prolog task: Check if a number is prime

  • Let’s write a predicate prime(P) to determine if P is a prime
  • A non-recursive executable specification, first in English, then in Prolog: 
                                
                            prime(P) :-
                                integer(P), P > 1,
                                P1 is P-1,
                                \+
                                    (
                                        between(2, P1, I),
                                        P mod I =:= 0
                                    ).
                            
                        
                                
                            % P is a prime if
                            %   P is an integer and P > 1 and
                            %   P1 = P-1 and
                            %   it is not the case that
                            %     ( there exists an I such that:
                            %       2 =< I =< P1 and
                            %       P is divisible by I
                            %     ).
  • X is Expr is a built-in predicate (BIP):
    it evaluates the arithmetic expression Expr, and assigns its value to X
  • The BIP Expr1 =:= Expr2 evaluates both Expr1 and Expr1, and succeeds iff the values are equal; analogously for Expr1 > Expr2, etc.
  • Library predicate between(From, To, Int) enumerates in Int all integers between From and To.

Constraint Logic Programming (CLP)

  • CLP is an extension of Prolog with special reasoning techniques for a given domain
  • In this course we will cover CLP(FD) for reasoning on integer domains
  • Example cryptarithmetic puzzle: AT + RAT = ART, where letters represent different digits, no initial 0’s allowed
  • A solution using CLP(FD): 
    
                            art(A, R, T) :-
                                domain([A,R,T], 0, 9),      % A, R and T are digits
                                A #> 0, R #> 0,             % A and R can not be 0
                                all_distinct([A,R,T]),      % A, R and T are all different
                                (10*A + T) + (100*R + 10*A + T) #= (100*A + 10*R + T).
    → R = 8, A = 9, T = 0

711 solution


                    problem711(Vs) :-
                        Vs = [A,B,C,D],             % prices of the 4 items
                        domain(Vs, 1, 711),         % prices are in cents
                        A+B+C+D #= 711,             % prices add up to 711 cents
                      % A*B*C*D/100^4 = 711/100,    % prices in $s multiply to 7.11
                        A*B*C*D #= 711*100^3,       % multiply both sides by 100^4
                        A #=< B, B #=< C, C #=< D,  % increasing order
                        labeling([ff], Vs).         % search
→ A = 120, B = 125, C = 150, D = 316

The Semantic Web (SW)

  • Math side — Description Logics: decidable subsets of First Order Logic
  • Software side — the Web Ontology Language OWL from World Wide Web Consortium, and the Protegé knowledge editor from Stanford University
  • An example puzzle:
    There is an island where some people are optimistic.
    The following statements hold on this island:
    • Someone having an optimistic parent is bound to be optimistic.
    • Someone having a non-optimistic friend is also bound to be optimistic.
    • Susan's father has her mother as a friend.
  • Can you prove that Susan has to be optimistic (opt.)? Protegé can!

Why should you attend this course?

  • Learn a very different programming paradigm, which you can also use in other languages.
  • Learn techniques to quickly and concisely solve difficult algorithmic problems
  • Learn Description Logics – the maths behind the next generation “intelligent” knowledge base
  • Learn from one of the 15 Founders of Logic Programming (as recognized by the Association for Logic Programming)
  • Enjoy the PLWIN (Prolog Web Interface) based practice apps, developed by the authors of this course https://ait.plwin.dev/

Slides and further content at:

ait-sdt.hu

Slides and further content at:

ait-sdt.hu