Weak simplest normal truth functions

Abstract

In certain applications of truth-functional logic it is of interest to determine classes of formulas equivalent to a given formula Φ under the hypothesis that certain conjunctions of letters of Φ are always false. Of especial interest is the case where the class to be determined is that of simplest normal truth functions. The problem of giving a calculation procedure for this question is evidently a more general form of the simplification problem as considered in [1] and [2]. The purpose of this note is to indicate how the procedure of [1] applies.Let Π, Π′, Π″, … be fundamental formulas, in the sense of [2], such that every literal of Π, etc., is a literal of Φ and such that Π, Π′, Π″, … are all false for all values of the constituent literals. Then we say that Ψ is a weak simplest disjunctive normal equivalent of Φ if and only if Ψ ≡ Φ, under the hypothesis, and there is no Ψ′ such that Ψ′ is simpler than Ψ and Ψ′ ≡ Φ, under the hypothesis. Similarly, under exactly the same hypothesis, we say that X is a weak simplest conjunctive normal equivalent of Φ. When the class of always false fundamental formulas is empty, as in [1] and [2], we may speak of strong simplest forms and hence of the more general problem of strong simplification.