Composition-nominative logics are program-oriented logics. They are based on algebras of partial predicates which do not have fixed arity. The aim of this work is to present CNL as institutions. Homomorphisms of first-order CNL are introduced, satisfaction condition is proved. Relations with institutions for classical first-order logic are considered. Directions for further investigation are outlined.

A new class of program-oriented logical formalisms is investigated – renominative logics with extended renominations, equality predicates, and predicate complement composition. Composition algebras and languages of such logics are described; their semantic properties are investigated. For these logics, a number of logical consequence relations are proposed and investigated, in particular, the logical consequence relations with undefinedness conditions. Properties of these relations form the semantic basis for further construction of sequent-type calculi for the proposed logics.