Definability of Boolean Functions in Kripke Semantics
Naosuke Matsuda · Notre Dame Journal of Formal Logic · 2023
A set F of Boolean functions is said to be functionally complete if every Boolean function is definable by combining functions in F. Post clarified when a set of Boolean functions is functionally complete (with respect to classical semantics). In this paper, by extending Post’s theorem, we clarify when a set of Boolean functions is functionally complete with respect to Kripke semantics.