Representation of Boolean Functions Using Binary Trees

Requires a Wolfram Notebook System

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

Requires a Wolfram Notebook System

Edit on desktop, mobile and cloud with any Wolfram Language product.

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