Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-23T07:05:10.393Z Has data issue: false hasContentIssue false

Weak simplest normal truth functions

Published online by Cambridge University Press:  12 March 2014

Raymond J. Nelson*
Affiliation:
Owego, New York

Extract

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.

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1955

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Nelson, R. J., Simplest normal truth functions, this Journal, vol. 20 (1955), pp. 105108.Google Scholar
[2]Quine, W. V., The problem of simplifying truth functions, American mathematical monthly, vol. 69 (1952), pp. 521531.CrossRefGoogle Scholar