×
Urquhart, Alasdair

Enumerating types of Boolean functions. (English) Zbl 1181.03002

Bull. Symb. Log. 15, No. 3, 273-299 (2009).
Call two Boolean functions equivalent if they are the same up to permutations and complementations of variables. In 1874 Jevons posed the question of counting the equivalence classes of Boolean functions of a given set of variables. Pólya, in a 1940 Journal of Symbolic Logic article, presented a solution based on his enumeration theorem. Urquhart’s paper provides both an exposition of Pólya’s solution and a very interesting history of Jevons’ problem, which drew the attention of figures such as Clifford and Schröder, and resurfaced in the context of computer circuits in the work of Shannon and others.
Reviewer: Leon Harkleroad (Wilton)

Cited in 1 Document

MSC:

03-03 History of mathematical logic and foundations
01A55 History of mathematics in the 19th century
01A60 History of mathematics in the 20th century
03B05 Classical propositional logic
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)

Keywords:

Jevons; Pólya; Boolean functions; Pólya enumeration
PDF BibTeX XML Cite
\textit{A. Urquhart}, Bull. Symb. Log. 15, No. 3, 273--299 (2009; Zbl 1181.03002)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] Permutation groups (1999)
[2] Logical design of electrical circuits (1958) · Zbl 0090.44004
[3] Combinatorics: Topics, techniques, algorithms (1994) · Zbl 0806.05001
[4] DOI: 10.1007/BF02392038 · Zbl 0264.05119
[5] Combinatorial enumeration of groups, graphs and chemical compounds (1987)
[6] Applied combinatorial mathematics pp 144– (1964)
[7] Collected papers, volume IV: Probability; combinatorics; teaching and learning in mathematics (1984)
[8] DOI: 10.2307/2266862 · Zbl 0024.00102
[9] Mathematical papers (1968)
[10] Memoirs of the Literary and Philosophical Society of Manchester, Session 1876–1877 16 pp 88– (1877)
[11] DOI: 10.1007/BF02546665 · Zbl 0017.23202
[12] Graph theory 1736–1936 (1976)
[13] DOI: 10.2307/2964390 · Zbl 0085.00203
[14] Handbook of the history of logic, volume 1: Greek, Indian and Arabic Logic pp 397– (2004)
[15] Encyclopedia of mathematics and its applications (1998)
[16] DOI: 10.1090/S0002-9947-1942-0005739-6 · JFM 68.0039.01
[17] A course in enumeration (2007) · Zbl 1123.05001
[18] Classical invariant theory (1999) · Zbl 0971.13004
[19] DOI: 10.1007/s00407-003-0067-0 · Zbl 1033.01003
[20] DOI: 10.1007/BF01691615 · JFM 25.0101.01
[21] Stoic logic (1953)
[22] Combinatorics on words (1997)
[23] DOI: 10.1090/S0002-9904-1907-01509-4 · JFM 38.0230.02
[24] The development of logic (1962)
[25] Applied finite group actions (1999)
[26] Representations of permutation groups II (1975)
[27] Mitteilungen aus dem Mathemematischen Seminar Giessen 98 pp 5– (1973)
[28] The principles of science: A treatise on logic and scientific method (1877)
[29] Proceedings of the London Mathematical Society 31 pp 273– (1930)
[30] The principles of science: A treatise on logic and scientific method 1 (1874)
[31] Symbolic logic (1894)
[32] A history of Greek mathematics (1921)
[33] Core memory: A visual survey of vintage computers (2007)
[34] DOI: 10.1080/0161-119691884933 · Zbl 0877.94032
[35] DOI: 10.2307/2370675 · JFM 53.0106.03
[36] Formal logic: or, the calculus of inference, necessary and probable (1847)
[37] From error-correcting codes through sphere packings to simple groups (1983) · Zbl 0545.94016
[38] DOI: 10.1016/S0021-9800(68)80008-0 · Zbl 0246.20002
[39] DOI: 10.2307/2974582 · Zbl 0873.01002
[40] Introduction to switching and automata theory (1965) · Zbl 0196.51702
[41] Enumerative combinatorics 1 (1986) · Zbl 0608.05001
[42] The encyclopedia of integer sequences (1995)
[43] DOI: 10.1016/0016-0032(63)90456-3 · Zbl 0196.51701
[44] DOI: 10.1137/0111059 · Zbl 0119.01202
[45] DOI: 10.4153/CJM-1953-020-x · Zbl 0051.24802
[46] Graphical enumeration (1973) · Zbl 0266.05108
[47] Collected papers (1993)
[48] DOI: 10.2307/2309856 · Zbl 0089.01602
[49] DOI: 10.1002/j.1538-7305.1949.tb03624.x
[50] DOI: 10.2140/pjm.1958.8.743 · Zbl 0084.19402
[51] DOI: 10.1109/T-AIEE.1938.5057767
[52] DOI: 10.2307/3109806 · Zbl 0917.01011
[53] Vorlesungen über die Algebra der Logik (exakte Logik) I (1890)
[54] Moralia XIII (1976)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.