Representation of Boolean Functions Using Binary Trees

Initializing live version
Download to Desktop

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.

This Demonstration shows representations of Boolean functions of two, three or four arguments using binary trees.

[more]

Abbreviations: CNF = canonical normal form, DNF = disjunctive normal form, BDT = binary decision tree, ANF = algebraic normal form, BFF = Boolean function form.

[less]

Contributed by: Izidor Hafner (September 2016)
Open content licensed under CC BY-NC-SA


Snapshots


Details

The first use of binary trees to represent Boolean functions were Macfarlane's diagrams that he called "logical spectra" [5, p. 44]. The representation is more compact than using truth tables.

References

[1] R. Audi, ed., The Cambridge Dictionary of Philosophy, Cambridge: Cambridge University Press, 1995 pp. 780–782.

[2] L. Borkowski, Elementy logiki formalnej (Elements of Formal Logic, in Polish), 3rd ed., Warsaw: Wyd, 1976.

[3] L. Carroll, Symbolic Logic and the Game of Logic, New York: Dover, 1958.

[4] I. M. Copi and C. Cohen, Introduction to Logic, 9th ed., New York: Macmillan, 1994 pp. 214–218.

[5] M. Gardner, Logic Machines, Diagrams and Boolean Algebra, New York: Dover Publications, 1968.



Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.
Send