Premium
Simple characterization of functionally complete one‐element sets of propositional connectives
Author(s) -
Maksimović Petar,
Janičić Predrag
Publication year - 2006
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.200610009
Subject(s) - arity , propositional variable , propositional formula , mathematics , element (criminal law) , simple (philosophy) , propositional calculus , well formed formula , set (abstract data type) , atomic formula , characterization (materials science) , discrete mathematics , algebra over a field , pure mathematics , computer science , artificial intelligence , programming language , intermediate logic , philosophy , materials science , epistemology , political science , description logic , nanotechnology , law
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)