Hostname: page-component-78c5997874-g7gxr Total loading time: 0 Render date: 2024-11-09T08:55:27.216Z Has data issue: false hasContentIssue false

On simplifying truth-functional formulas

Published online by Cambridge University Press:  12 March 2014

Kurt Bing*
Affiliation:
Rensselaer Polytechnic Institute

Extract

The following are some consequences of a recent result concerning the prime implicants of disjunctive normal formulas.

I. Introduce the void fundamental formula λ, and define the consensus of αϕ and as in [5], but allowing ϕ or ψ or both to be λ. Then a normal formula Φ is valid if and only if the operations of dropping subsuming clauses and adjoining consensus formulas end by transforming Φ into the single formula λ. (For under the notions of fundamental formula and consensus as now extended, λ is a (unique) prime implicant of all valid formulas and of no others; and the argument of [5] now shows that the operations mentioned transform every normal formula, whether valid or not, into the disjunction of its prime implicants.)

II. A normal formula ψ implies a normal formula Φ if and only if every clause of ψ subsumes one of the prime implicants of Φ, which are found as in I above. (The condition is clearly sufficient. It is necessary, for if ψ implies Φ, then every clause of ψ implies Φ and subsumes a shortest fundamental formula implying Φ.) In this condition, the prime implicants of Φ may be replaced by the clauses of the result of merely adjoining, as long as possible, consensus formulas to Φ.

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1956

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]Bing, Kurt, On simplifying propositional formulas (abstract), Bulletin of the American Mathematical Society, vol. 61 (1955), p. 560.Google Scholar
[2]Nelson, Raymond J., Simplest normal truth functions, this Journal, vol. 20 (1955), pp. 105108.Google Scholar
[3]Quine, W. V., The problem of simplifying truth functions, American mathematical monthly, vol. 59 (1952), pp. 521531.CrossRefGoogle Scholar
[4]Quine, W. V., Two theorems about truth functions, Boletin de la Sociedad Matemdtica Mexicana, vol. 10 (1953), pp. 6470.Google Scholar
[5]Quine, W. V., A way to simplify truth functions, American mathematical monthly, vol. 62 (1955), pp. 627631.CrossRefGoogle Scholar
[6]Samson, Edward W. and Mills, Burton E., Circuit minimization: algebra and algorithms for new Boolean canonical expressions, AFCRC technical report 54-21 (a United States Air Force memorandum of 04 1954).Google Scholar