Correspondences between definability of Boolean functions and frame definability in modal logic

Abstract

We establish a connection between term definability of classes of Boolean functions and definability of finite modal frames. We define a bijective translation between functional terms and uniform degree-1 formulas and show that a class of Boolean functions is defined by functional terms if and only if the corresponding class of finite Scott-Montague frames is defined by the translations of these functional terms, and vice versa. Since clones in particular are term definable, we obtain for each clone a corresponding class of Scott-Montague frames which is defined by uniform degree-1 formulas. As a special case, we get that the clone of all conjunctions and constant functions with the value 1 corresponds

to the class of all Kripke frames. We get further correspondences by restricting the binary relation in Kripke frames in a natural way and considering Kripke frames with non-normal worlds. Furthermore, by modifying Kripke semantics, we extend our results to correspondences between linear clones and classes of Kripke frames equipped with modified Kripke semantics. Using these methods, we give, by means of Kripke semantics or modified Kripke semantics, the

characterizations of the classes of Scott-Montague frames corresponding to each subclone of the clone of all conjunctions and constants, the clone of all disjunctions and constants,

and the clone of linear functions.

Key words: modal logic, Kripke frames, Scott-Montague frames, Boolean functions, functional terms, clones