Counting functions

DOI10.1305/NDJFL/1093634488MaRDI QIDQ689218zbMATH OpenOpenAlexFDO

Authors Fred Johnson

Publication date 14 June 1994

Published in Notre Dame Journal of Formal Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1305/ndjfl/1093634488

zbMATH Keywords

counting functions

Mathematics Subject Classification ID

Classical propositional logic (03B05)

Review text

The proof by \textit{F. J. Pelletier} and \textit{N. M. Martin} [ibid. 31, 462- 475 (1990; Zbl 0745.03007)] of Post's Functional Completeness Theorem contains a very complex argument that shows in effect that counting functions are closed under composition. The purpose of this note is to give a simple proof of this result.

Recommendations

• Post's functional completeness theorem
• scientific article; zbMATH DE number 4214083
• scientific article; zbMATH DE number 16458
• The completeness and closed classes of functions of Boolean algebra with direct and iterative variables

Cited in

(5)

• Post's functional completeness theorem
• Learning counting functions with queries
• Counting with symmetric functions
• scientific article; zbMATH DE number 6028114 (Why is no real title available?)
• scientific article; zbMATH DE number 5242341 (Why is no real title available?)

This page was built for publication: Counting functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q689218)