Post's functional completeness theorem

DOI10.1305/NDJFL/1093635508MaRDI QIDQ1173782zbMATH OpenOpenAlexFDO

Authors Francis Jeffry Pelletier, Norman M. Martin

Publication date 25 June 1992

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

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

zbMATH Keywords

elementary logicPost's functional completeness theorem

Mathematics Subject Classification ID

Classical propositional logic (03B05)

Review text

Post's functional completeness theorem is revisited. The paper provides a new proof, which is, by the authors' opinion, in a style accessible to modern logicians and teachers of elementary logic.

Recommendations

• On proving functional incompleteness in symbolic logic classes
• Counting functions
• A new version of the proof of completeness criterion for k-valued logic functions
• A note on generalized functional completeness in the realm of elementary logic

Cited in

(16)

• On proving functional incompleteness in symbolic logic classes
• Characterizations of closed classes of Boolean functions in terms of forbidden subfunctions and Post classes
• Characterization of zigzag De Morgan functions
• A new proof for Craig's theorem
• A post-style proof of completeness theorem for symmetric relatedness logic S
• Representing voting rules in Łukasiewicz's three-valued logic
• Aggregation of votes with multiple positions on each issue
• Results on functional completeness in logical calculi
• A note on generalized functional completeness in the realm of elementary logic
• Definability of Boolean functions in Kripke semantics
• Counting functions
• Expressive quantale-valued logics for coalgebras: an adjunction-based approach
• Boolean basis, formula size, and number of modal operators
• A note on the expressive completeness of LP in a metatheory without negation
• A functional completeness theorem for De Morgan functions.
• Schönfinkel-type operators for classical logic

This page was built for publication: Post's functional completeness theorem

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