Simple characterization of functionally complete one-element sets of propositional connectives

✍ Scribed by Petar Maksimović; Predrag Janičić

• Publisher: John Wiley and Sons
• Year: 2006
• Tongue: English
• Weight: 110 KB
• Volume: 52
• Category: Article
• ISSN: 0044-3050
• DOI: 10.1002/malq.200610009

✦ Synopsis

Abstract

A set of propositional connectives is said to be functionally complete if all propositional formulae can be expressed using only connectives from that set. In this paper we give sufficient and necessary conditions for a one‐element set of propositional connectives to be functionally complete. These conditions provide a simple and elegant characterization of functionally complete one‐element sets of propositional connectives (of arbitrary arity). (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)