Maths - Horn Clause

It is useful, for certain types of reasoning, to have the things we know about a situation in the form of implications. For instance:

A -> B   A implies B

of even:

A /\ B /\ C -> D   A and B and C implies D

Deduction Using Implies

So if the following are true:

  • A -> B
  • B -> C
  • C -> D

then we can deduce:

A -> D

for example, by combining the implications (substituting).

Forward and Backward Chaining

Diagrams, such as the one above, give us a graphical guide.

As Meet and Join

We may need to express the implication in terms of meet and join ('or' and 'and') . To see how to do this lets look at a truth table for it:

A B A->B

Note: I've drawn the truth table as Boolean values but we can use constructive logic instead (law of excluded middle not required).































metadata block
see also:
  • Stanford - Development of Intuitionistic Logic
  • Stanford - Intuitionistic Logic
  • Youtube video

    Advanced Topics in Programming Languages Series: Parametric Polymorphism and the Girard-Reynolds Isomorphism. This talk is based on a series of papers by Philip Wadler, a principal designer of the Haskell programming language. Featured are a number of double-barreled names in computer science:

    • Hindley-Milner (Strong typing without having to type the types)
    • Wadler-Blott (Making ad-hoc polymorphism less ad-hoc with parametricity)
    • Curry-Howard (Isomorphism between types and theorems, terms and proofs)
    • Girard-Reynolds (Isomorphism between types and terms in the presence of parametricity)
  • or Djinn code see here.
  • Parametricity
  • "Propositions as Types" by Philip Wadler
Correspondence about this page

Book Shop - Further reading.

Where I can, I have put links to Amazon for books that are relevant to the subject, click on the appropriate country flag to get more details of the book or to buy it from them.

cover Modern Graph Theory (Graduate Texts in Mathematics, 184)

Commercial Software Shop

Where I can, I have put links to Amazon for commercial software, not directly related to the software project, but related to the subject being discussed, click on the appropriate country flag to get more details of the software or to buy it from them.


This site may have errors. Don't use for critical systems.

Copyright (c) 1998-2023 Martin John Baker - All rights reserved - privacy policy.