LoginSignup
0

More than 1 year has passed since last update.

Prolog Barber Paradox in JavaScript/Python

Last updated at Posted at 2022-01-04

The Dogelog Runtime goes now by the name Dogelog Player. It is a Prolog interpreter which is written in 100% Prolog itself. Means it is based on a small native kernel, but most of it is written in Prolog itself, like clause compilation, clause indexing and term input/output.

bertrandrussell3.png

To demonstrate some of its capabilities we made a series of experiments in rendering Jens Ottens Lean Prover proofs with the help of Dogelog Player. We started with propositional logic and walked our ways into first order logic. As a demo we can automatically render a proof of the Barber Paradox.

Lean Prover

On a Cade19 tutorial website Jens Otten has published a couple of automated theorem provers written Prolog. They might be considered lean, since they do not require some difficult staging such as having files with the desired theorems, and then files with their conjunctive normal form. One can directly call a predicate prove0/1 in a Prolog top-level and experiment with different theorems.

The provers can be further considered lean since they don't demand much from the underlying Prolog system. A couple of the ISO core standard predicates such as unify_with_occurs_check/2 and copy_term/2 do the job. Lets look at a prenex normal form Q1x1…QnxnM, the provers mainly work according to the following principle:

  • Qj=∀: is handled by a Skolem function.
  • Qj=∃: is handled by fresh variable and contraction.

The FOL matrice M is then solved by unification and backtracking. Phil Zucker recently posted a website where he showed how to display a reduction tree in the propositional logic case. We took up the idea and extended it towards the first order logic case.

Build Your Own First-Order Prover | Tutorial at CADE 2019
http://jens-otten.de/tutorial_cade19/

Automated Propositional Sequent Proofs in Your Browser with Tau Prolog
https://www.philipzucker.com/javascript-automated-proving/

JavaScript MathJax

There is a nativer JavaScript kernel for Dogelog Player that allows running it in the browser. To display first order logic proofs we took leanseq_v5.pl and added returning a proof tree. We also modified the TPTP syntax slightly, so as to have names of bound variables.

TPTP Syntax without modification:

?- prove0((![X]:p(X) => ![Y]:(p(Y) & p(f(Y)))), 1).

TPTP Syntax with modification:

?- prove0((![X='x']:p(X) => ![Y='y']:(p(Y) & p(f(Y)))), 1).

Unlike Phil Zuckers take, we wrote the MathJax generation completely in Prolog itself using DCGs. We also saw to it that an LK calculus proof is extracted from the found reduction tree. LK calculus proofs are more readable, since they omit unnecessary formulas in the sequents:

1_sUqksHLWDT1o8XI4Cje0Eg.png

Live demo available here:

Dogelog MathJax Herbrand
http://www.xlog.ch/izytab/doclet/en/docs/18_live/40_bin2021/paste06/package.html

Python Unicode

Although we were happy with our LK calculus MathJax rendering here, the latex itself is not very E-mail friendly. The commands are verbose and the markup is without numbering. So we explored the alternative of Unicode. We did this first in the browser but it also runs from within Python. The below shows a first order logic proof of the Barber Paradox.

1_JclT58Zo5AuDOLZDdkEh2g.png

Paradoxically there exists no Barber that shaves everybody s(x,y) that cannot shave himself ~s(y,y) and vice versa. The first order logic prover allows experimenting with other queries, like the formula from ex_barber.pl on Jens Ottens homepage. For running the Python version, we found choosing a certain font, like for example NSimSum, helps.

Live demo available here:

Dogelog Unicode List
http://www.xlog.ch/izytab/moblet/en/docs/18_live/40_bin2021/paste07/package.html

Conclusions

We gave the end-user more control by a predicate prove0/2 where the second integer parameter gives the desired contraction depth. We could also provide an alternative output to MathJax by using the Unicode features of Dogelog Player. We can then even run the first order logic prover from within a Python interpreter using the Dogelog Player top-level.

The Dogelog Player top-level delivers a similar interactive experience like the JavaScript sandbox. As a logic example, we could show the Barber Paradox, but other toy examples are also possible. To move away from toy examples we might explore in the future the other first order logic provers that are also found on Jens Ottens tutorial page.

Follow us on Twitter or Facebook:

Dogelog Twitter Account
https://twitter.com/dogelogch

Dogelog Facebook Account
https://www.facebook.com/groups/dogelog

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0