A crash course in logic for Prolog programmers

Nice to know
1

Edit I’ve put a neatened up version of this with Venn diagrams on the wiki I started with more emphasis on Prolog and less on classical maths.

I’ve been reading a couple of the classics on logic and struggling to fit the theory into Prolog semantics. Judging from various discussions here, gather I’m not alone, so thought I’d put up some notes.

Sets and Logic

Set-builder notation is something that seems have been invented since my formal education way back in the last century, and is a very handy way of combining logic and sets which I’ll get to shortly. But first a quick refresher on basic logic and set theory.

Using copula notation p∧q for and, p∨q for or, and my own invention p ≤ q rather than p ⇒ q for implication is a handy mnemonic that these are related to P ∩ Q for intersection, P ∪ Q for union, and P⊆ Q for subset. Equivalence p ⇔ q and P ≡ Q for most problems need to be expanded into p ≤ q ∧q ≤ p, and P⊆ Q ∩ Q ⊆P which I’ll elaborate on later.

The set equivalent of negation ¬p is complement Pc, and while we tend to think of De Morgan’s laws as the logic substitution rules ¬(p∧q) ⇔ ¬p∨¬q and ¬(p∨q) ⇔ ¬p∧¬q, interestingly he discovered them from writings on set theory in ancient Indian texts, which in our notation would be (P ∩ Q)c ≡ Pc ∪ Qc and (P ∪ Q)c ≡ Pc ∩ Qc

To show how to use the above maths in Prolog, I’m going to use examples I’ll use are taken from my translation of Jennifer Widom’s SQL basics examples which I’ve translated into Prolog SWISH -- SWI-Prolog for SHaring

I’ll be using these two tables in my examples

%! student(?SID:text, ?SName:text, ?GPA:float, ?SizeHS:integer) is nondet 
student(123, 'Amy',    3.9, 1000).
student(234, 'Bob',    3.6, 1500).
student(345, 'Craig',  3.5, 500).
student(456, 'Doris',  3.9, 1000).
student(567, 'Edward', 2.9, 2000).
student(678, 'Fay',    3.8, 200).
student(789, 'Gary',   3.4, 800).
student(987, 'Helen',  3.7, 800).
student(876, 'Irene',  3.9, 400).
student(765, 'Jay',    2.9, 1500).
student(654, 'Amy',    3.9, 1000).
student(543, 'Craig',  3.4, 2000).

%! apply(?SID:integer, ?CName:text, ?Major:text, ?Decision:text) is nondet
apply(123, 'Stanford', 'CS',             'Y').
apply(123, 'Stanford', 'EE',             'N').
apply(123, 'Berkeley', 'CS',             'Y').
apply(123, 'Cornell',  'EE',             'Y').
apply(234, 'Berkeley', 'biology',        'N').
apply(345, 'MIT',      'bioengineering', 'Y').
apply(345, 'Cornell',  'bioengineering', 'N').
apply(345, 'Cornell',  'CS',             'Y').
apply(345, 'Cornell',  'EE',             'N').
apply(678, 'Stanford', 'history',        'Y').
apply(987, 'Stanford', 'CS',             'Y').
apply(987, 'Berkeley', 'CS',             'Y').
apply(876, 'Stanford', 'CS',             'N').
apply(876, 'MIT',      'biology',        'Y').
apply(876, 'MIT',      'marine biology', 'N').
apply(765, 'Stanford', 'history',        'Y').
apply(765, 'Cornell',  'history',        'N').
apply(765, 'Cornell',  'psychology',     'Y').
apply(543, 'MIT',      'CS',             'N').

Students IDs of those who have applied for CS

Basic set builder notation looks like P = {p|Φ(p)} where Φ(p) in this case is the boolean test Major == ‘CS’.

A simple way to do this is in Prolog is:

apply(SID, _, 'CS', _).

The above works, though it’s a little unelegant in that students 123 and 987 get listed twice because they applied for ‘CS’ at both Stanford and Berkeley. One way to sort that out is using distinct(SID, apply(SID, _, 'CS', _)).

Students IDs of those who have not applied for CS

A trap is to think this query is simply not ‘CS’ as in:

apply(SID, _, _Major, _), _Major \== 'CS'.

This gives the wrong answer because students 123 and 345 applied for ‘EE’ besides ‘CS’. The next mistake is to think \+apply(SID, _, 'CS', _). will give us the complement of the apply(SID, _, 'CS', _). whereas all it will return is false.

The way to make this work is

student(SID, _, _, _), \+apply(SID, _, 'CS', _).

In set-builder builder notation, Pc = {p ∈ E|p ∉ P}. When querying which students had applied for ‘CS’, we didn’t have to think of set E, which in this example is the student table. If we don’t include it in the not ‘CS’, we’ll fail to find the four students who are not in the apply table.

An important quirk of Prolog is that negation is not associative, ie we can’t rewrite our query \+apply(SID, _, 'CS', _), student(SID, _, _, _). This crops up in implication shortly which is commonly written as ¬p∨q, which will only work in Prolog written q ∨¬p.

Students who have applied for both ‘CS’ and ‘EE’

This is the intersection of two sets of student IDs, which is easily done like so:

distinct(SID, (apply(SID, _, 'CS', _), apply(SID, _, 'EE', _))).

Students who have applied for both ‘CS’ or ‘EE’

In this example students who applied for ‘EE’ are a subset of students who applied for ‘CS’, so the union is the same as the ‘CS’ set.

There are two ways to or things in Prolog. One is to use a semicolon as in

distinct(SID, (apply(SID, _, 'CS', _); apply(SID, _, 'EE', _))).

The other way is to write the alternatives we want as separate rules.

How subsets and material implication are related

The implication rule in classical logic (sometimes called material implication) was something I really struggled to understand, and I had an “aha” moment recently when I grasped p ⇒ q is the same as p ≤ q which equates in sets to P⊆ Q.

In the example here, since the only two students who have applied for ‘EE’ have also applied for ‘CS’, applying for ‘EE’ implies applying for ‘CS’.

A search for ‘EE’ students who have not applied for ‘CS’ returns false:

apply(SID, _, 'EE', _), \+apply(SID, _, 'CS', _).

This is a clue that the trick to finding if one set is a subset of another, a statement like the one above will return false, so it’s negation will true.

I’m going to turn this into a general query to find all majors in the example database which are subsets to other majors. A quick diversion into logic manipulation first since it’s an interesting application of De Morgan’s law: if we abstract the above Prolog query to ¬(p ∧ ¬q) it can be rewritten the conventional way ¬p ∨ q. The truth table for p ⇒ q is more easily understood as p ≤ q in my opinion.

p ⇒ q is equivalent to ¬p ∨ q, which using De Morgan’s Law can be rewritten ¬(p ∧ ¬q)

A way to find all supersets and their subsets in this example looks like so:

distinct([Superset, Subset], 
          (    apply(_, _, Subset, _), apply(_, _, Superset, _), 
               \+ (apply(_SID, _, Subset, _), \+apply(_SID, _, Superset, _)), 
               Subset \== Superset
          )).

Equality

Two sets are equal if they are subsets of each other. There aren’t any in this example.

1 Like
3

A good union example could be something like

apply(SID, _, 'CS', _); apply(SID, _, 'Computer Science', _).

with any number of more ors added.

5

re: material implication

I was reading a logic theory book recently where there was a short discussion about material implication vs. logic implication …

I am still mulling over things but it then occurred to me that an analog difference could be seen between logic programming and theorem proving.

Logic programming such as in Prolog is “material” in that a goal proves “by example” – hence a goal that succeeds is “material” in this sense, whereas theorem proving is about validity – i.e. an inference about all possible material answers (models).

Hence, logic programming is in this sense rather weak …

Not sure if my musing here makes sense …

Dan

7

I am mulling over the meaning of “material” vs. logical … and what a symbolic prove system does vs. a logic language with a resolution system – which, i think would apply to predicate logic as well …

9

I’ll just expand on this in a new post here because the way p ⇔ q is derived from p ⇒ q∧q ⇒ p illustrates quite a lot of interesting basics, especially the tautology rules which @ j4n_bur53 mentioned.

p ⇔ q is commonly expanded to (p ∧ q) ∨ (¬p ∧ ¬q), and the way it gets derived from (¬p ∨ q) ∧ (¬q ∨ p) ie what p ⇒ q∧q ⇒ p expand to I found interesting.

The easiest way to do the required algebraic substitution is rather than use copula notation, lets go back to George Boole’s original two value algebra. Instead of false and true, we use 0 and 1 (a bit of historical trivia I found interesting was Boole started with probability values ranging from 0 to 1, and logic grew from that. A lot of people seem to want to go back to square one from two value algebra to an infinite range of probabilities).

and is multiplication and or is addition, and it works exactly the same as normal arithmetic except 1 clocks as in 1 + 1 = 1. My initial reaction to and not being addition was that seems weird, but after a couple of exercises it all makes sense. The Victorians wrote a lot about how maths should become all ideograms so people didn’t get confused with word associations.

So we rewrite (¬p ∨ q) ∧ (¬q ∨ p) as (¬p + q)(¬q + p) which normal algebra expands to

¬p¬q + ¬pp + q¬q + qp

Now multiplying ¬p by p is always going to result in zero, as will multiplying q by ¬q, so we can rewrite it

¬p¬q + 0 + 0 + qp which can be simplified further to qp + ¬p¬q

Replace multiplication with ∧ and addition with ∨, and voila

(q ∧ p) ∨ (¬q ∧ ¬p)

The need in set-theory to say two sets are equal if they are reciprocally subsets of each other may seem long winded, but since sets are often not enumerable, it’s often the only way to do it.

11

If you run the query I provided above, you’ll get this;

Superset Subset
‘CS’ ‘EE’ 1
‘CS’ bioengineering 2
‘EE’ bioengineering 3
‘CS’ ‘marine biology’ 4
biology ‘marine biology’ 5
history psychology 6

The easiest way to show how equality is related to implication is probably creating rules

implies(P, Q) :- 
    distinct( [P, Q], 
          (    apply(_, _, P, _), apply(_, _, Q, _), 
               \+ (apply(SID, _, P, _), \+apply(SID, _, Q, _)), 
               P \== Q
          )).

equality(P, Q) :-
    implies(P, Q),
    implies(Q, P).

Then to get two equal sets, lets add

apply(678, 'Stanford', 'psychology',     'Y').

so that both history and psychology contain 678 and 765.

equality(P, Q).

P Q
history psychology 1
psychology history 2
13

I’ve neatened my ramblings here up at ClassicLogic - SWI-Prolog Wiki which hopefully make more sense.

As always, comments and suggested corrections welcome.

1 Like
14

Perhaps a short comment.

I found the predicate name ‘apply’ a bit confusing – first i though its some kind of predefined goal.

Also, I read it as a verb whereas it should probably be term that specifies a relation or, in these cases, an observable relational state, e.g.

applied_course(123, ‘Stanford’, ‘CS’, ‘Y’).

or perhaps simply:

course(123, ‘Stanford’, ‘CS’, ‘Y’).

with the number of relational arguments implying the course a studied is taking, given the student id as argument, rather than a description of the course only.

16

Thanks for the feedback.

I’ve added a line to explain apply/4 is just me lazily cutting and pasting Jennifer Widom’s original SQL example, and has nothing to do with the builtin apply/2

I don’t think it’s a good idea to rename the table since overcoming preconceived ideas of what words mean is a key skill to mastering logic.

Firstly, there’s and means multiplication, which is obvious once one does a few exercises, but I for one strongly associate the word and with addition.

The worst misuse of language in classic logic is probably implication which as I’ve tried to explain means something fairly obvious: if p belongs to a subset of a larger set containing q, it implies p is also a member of that larger set.

The Victorians spent a lot of time arguing about classical logic’s implication rule, whereas modern textbooks just seem to tiptoe around it. At one stage implication got mangled up with causation, prompting one of my favourite Bertrand Russel quotes:

Causation, like much that passes muster among philosophers, is a relic of a bygone age, surviving, like the monarchy, only because it is erroneously supposed to do no harm.

18

re: p ⇒ q — Which majors are subsets of others

I guess looking p is a subset of q as a necessary and sufficient condition for p implies q to hold makes a lot of sense. Since only a subset can hold such a guarantee …

Dan

20

Can you explain what this means … i.e. what is the intuition behind it

21

Which part do you not understand? Did you get a chance to look at this page: Łukasiewicz logic - Wikipedia

22

Nothing – right now its squibbles on paper with some abstract descriptions …

Here is a sample from there …

Propositional infinite-valued Łukasiewicz logic can also be axiomatized by adding the following axioms to the axiomatic system of monoidal t-norm logic:

Divisibility
    ( A ∧ B ) → ( A ⊗ ( A → B ) ) {\displaystyle (A\wedge B)\rightarrow (A\otimes (A\rightarrow B))} (A\wedge B)\rightarrow (A\otimes (A\rightarrow B))
Double negation
    ¬ ¬ A → A . {\displaystyle \neg \neg A\rightarrow A.} \neg \neg A\rightarrow A.

That is, infinite-valued Łukasiewicz logic arises by adding the axiom of double negation to basic t-norm logic BL, or by adding the axiom of divisibility to the logic IMTL.

Finite-valued Łukasiewicz logics require additional axioms.

Wonder whether there is a description with examples – what is offered, how its used in practice with examples …

Dan

24

thanks but how is this put to use in knowledge based reasoning

26

What would be an example of an impasse – and i guess, the idea is to use one argument that holds the resulting truth values that are passed around …

28

Thanks.

But, this is still too abstract for me – how is this used in a real life example … in what context, in what case and for what purpose.

30

While in Toronto, I loved going to the library – UofT library system was incredible.

Libraries here in Israel aren’t so well stocked and yes, its about limiting mobility also, in particular in corona times …

Most books on logic I looked at academic in nature, and I am wondering how practitioners use such features in their day to day work – and on this list, I presume that there are practitioners present as well.

Dan

32

I’ve updated ClassicLogic - SWI-Prolog Wiki to explain better what I mean by two value algebra and how and is analogous to multiplication and or to addition:

It’s most easily explained by the truth tables:

p q p ∧ q p * q
1 1 1 1
1 0 0 0
0 1 0 0
0 0 0 0
p q p ∨ q p + q
1 1 1 1
1 0 1 1
0 1 1 1
0 0 0 0

As far as I recall, when I did ‘EE’ way back in the last century, we were taught this trick to quickly simplify boolean equations, so I’m not sure if this is more or an ‘EE’ than maths thing.