Handbook practical logic

Of course, we can only split up a disjunction if it contains no free variables, but this is quite often the case. We can now easily solve some quite interesting problems that were barely feasible before, e. To avoid repeating work, we split the clauses into two lists, used and unused. The main loop consists of taking one given clause cls from unused, moving it to used and generating all possible resolvents of the new clause with clauses from used including itself , appending the new clauses to the end of unused.

The idea is that, provided used is initially empty, every pair of clauses is 3. On the other hand, once they have participated, both clauses are moved to used and will never be used together again.

This organization, used in various resolution implementations at the Argonne National Lab, is often referred to as the given clause algorithm. Often, many apparently pointless clauses such as tautologous ones. We might expect tautologies to make no useful contribution to the search for a refutation. In the propositional case, we said that a clause C subsumes a clause D if C logically implies D, which is equivalent to the syntactic condition that C is a subset of D.

So even if logical entailment were decidable, it might be undesirable to use it as a subsumption test. Logically, this is irreproachable since the latter is indeed a logical consequence of the former and not vice versa, but it can be pragmatically unappealing since unit clauses tend to be more useful.

But why is discarding subsumed clauses First-order logic permissible without destroying refutation completeness? There are now two cases to consider. So one can deduce this directly as a corollary of the previous theorem.

Proof By Theorem 3. In the latter case we are done. In the former case, use Corollary 3. By transitivity of subsumption, the result follows. Using this result, we can at least show that we can restrict ourselves, without losing refutation completeness, to derivations where no clause C is subsumed by any of its ancestors, i.

Proof By induction on the structure of the proof. Otherwise, suppose C is derived by resolving on C1 and C2. And if it is, simply take the subproof of that ancestor. In particular, if the empty clause is derivable, it is derivable without ever deriving an intermediate clause subsumed by one of its ancestors.

Moreover: Lemma 3. Proof Suppose a proof of a non-tautology involves a tautology. As for discarding subsumed clauses, we still need to take care, because the relationship between the way in which clauses are generated and used in the proof search algorithm and the ancestral relation in any eventual proof is not trivial. Intuitively, forward deletion should be safe since anything one could generate from the newly generated clause will earlier be generated from existing clauses. However, if the subsuming clause is in used, this is not quite so clear, since the newly generated clause would be put on unused and so eventually have the opportunity to be resolved with another clause from used, whereas because of the way the enumeration is structured, two clauses from used are never resolved together.

Accordingly, we will only discard newly generated clauses if they are subsumed by a clause in unused. Backward deletion is also fraught with problems. Proper subsumption will automatically be enforced if we check for forward subsumption before back subsumption. Thus, it seems that the policy of replacement, where the subsumed clause is replaced by the subsuming one at the original point in the unused list, is probably better, and this is what we will do.

First we check if cl is a tautology using trivial or subsumed by either gcl or something already in unused, and if so we discard it. Otherwise we perform the replacement, which if no back-subsumption is found will simply put the new clause at the back of the list. All the problems solved by tableaux, and more besides, are now quickly solved by resolution.

In order to state the invariants simply, we will also extend the notion of subsumption from pairs of clauses to pairs of sets of clauses. This is trivially true at the beginning, since Sub 0 is empty and there are no resolvents. Hence the invariant is maintained. Consequently, if a resolution refutation of those clauses exists, the empty clause will be derived in some level. Moreover, assuming that the empty clause was not in Unused 0 , it can only have got into a level by being one of the newly generated resolvents, and hence will be detected.

It would be much better if we could cut down on this redundancy in the search space, for example by systematically preferring one kind of proof tree whenever there are many alternatives. Linear resolution In fact, we can regard the duplication above as indicating a possible proof transformation. Considering this, it turns out that we can always apply such a rotation, but we may need an additional step where one of the earlier clauses on the trunk is re-used.

In particular, if a set of clauses has a refutation, it has a linear refutation. The idea of searching just for linear refutations gives linear resolution Loveland ; Luckham ; Zamov and Sharanov Although this greatly reduces redundancy, compatibility with subsumption and elimination of tautologies becomes more complicated. We will not go into more detail, since we will not actually implement linear resolution. However it is useful to understand the First-order logic concept of linear resolution since it is related to material covered in the following two sections on Prolog and Model elimination.

Positive resolution Another way of imposing restrictions on resolution proofs was introduced by Robinson a very soon after his original paper on resolution. He showed that refutation completeness is retained if each resolution operation is restricted so that one of the two hypothesis clauses is all-positive, i.

This often cuts down the search space quite dramatically. Robinson referred to resolution subject to this restriction as P1 -resolution, though it is more often nowadays referred to simply as positive resolution. We will now demonstrate the refutation completeness of this restriction, following Robinson. We start with the following. Proof Partition the set S into two disjoint sets, the all-positive clauses P and the clauses with at least one negative literal N. Let K be some clause from N that is false in v and has the minimal number of negative literals among such clauses; i.

This contains fewer negative literals than K, since J is all-positive. Thus R has fewer negative literals than K and is false in v. This contradicts the minimality of K unless R is actually empty and therefore belongs to P. However by hypothesis the empty clause was not in S and so the result is proved.

Remember that we work at the propositional level and treat clauses as sets of literals, so repetitions of a literal do not give distinct clauses. Proof The usual lifting argument. By the previous theorem, there is a derivation of the empty clause by positive resolution.

Now we simply repeatedly apply the lifting Lemma 3. It is easy to see using the same argument as above that positive resolution is compatible with our subsumption and replacement policies. Thus we will modify the resolution prover with subsumption to perform positive resolution. Essentially the same argument can be used to establish refutation completeness in each case. All these can be seen as special cases of a more general technique of semantic resolution Slagle Proof As usual, we will perform lifting.

By the previous theorem, there is a refutation of the set of ground instances by resolution where at least one hypothesis is false in v. Positive resolution, for example, is the special case where the interpretation sets RI a1 ,. However, it First-order logic might be easier if we did not need to spell out an appropriate interpretation, but only kept it implicitly at the background.

In the main resolution setup above, we started with the used list empty, ensuring that all pairs of clauses had the opportunity to be resolved. However, it may be that we would do better to forbid resolutions entirely among some particular subset of the initial clauses. The idea is that by this means, resolution can be focused away from deducing valid but irrelevant conclusions, and towards deducing those that contribute to the problem at hand.

This is the basic principle of the set of support strategy Wos, Robinson and Carson Now we simply impose the requirement on resolution refutations that no two clauses of U are resolved together. By the refutation completeness of semantic resolution, there is therefore a resolution refutation in which at least one of the clauses that is resolved does not hold in I.

To implement the set-of-support restriction, we need no major changes to the given clause algorithm: simply set the initial used to be the unsupported clauses rather than the empty set. This precisely ensures that two unsupported clauses are never resolved together.

Recall that 3. One satisfactory choice for the set of support is the collection of allnegative input clauses. Although this may not be optimal, it often works quite well. However, resolution experts usually like to make a particular choice of set of support themselves rather than using the simple syntactically-based default we have adopted.

Suppose, for example, one is trying to use a standard set of mathematical axioms A together with special additional hypothesis B to prove a conclusion C. Note that simply imposing negative resolution would be more restrictive than set-of-support proofs starting with all-negative clauses as the set of support, but in many cases the set-of-support restriction allows shorter proofs that compensate for the larger search space.

Every step in a positive resolution refutation involves one all-positive clause, and in order for resolution to be possible, there must be at least one negative literal in the other clause. In general, a clause containing n negative literals, if it participates in a positive resolution derivation, must be repeatedly resolved with positive clauses until all the negative literals have disappeared. This might, because factoring merges some of the Li together, take fewer than n resolution steps.

We can imagine combining all these successive resolutions into a single hyperresolution step. We will not actually implement hyperresolution, but later Section 4. The set of all atomic ground formulas in a language is often called the Herbrand base. Our observation sets up a natural bijection between Herbrand interpretations and subsets of the Herbrand base, viz. Let S be a set of clauses. Accordingly, if M so constructed is in fact a model of S, we say that it is the least or minimal Herbrand model of S.

But under what circumstances is it indeed a model of S? Since neither P 0 nor Q 0 holds in all Herbrand models, M makes neither of them hold, and so is not a model of S. However, in a precise sense, a disjunction of more than one positive literal in S is the only case where things go wrong. We want to show that this holds in M for any valuation v. But if each PM t1 ,. Let M be the least Herbrand model of D, whose existence is guaranteed by the previous lemma. We claim that it is in fact a model of N as well.

For if a clause P 1 t11 ,. But this means that each PHk tk1 ,. By expanding the language if necessary, we can assume that all the Ai are ground cf. Proof Combine Theorems 3. We claim that the set B of ground atoms that can form the root of such a tree is exactly the subset of the Herbrand base corresponding to the least model. Conversely, it is clear that any model of the ground instances of the clauses in S must include B, since if each Pi holds in a model, so does Q.

We will exploit this feature when we consider Prolog below. To see this, take a set S of Horn clauses, and introduce a new nullary predicate symbol F that does not occur in S.

Conversely, we claim that any model of S can be extended to a model 3. Variable instantiations are kept globally, and backtracking is initiated when a given instantiation does not lead to a complete solution. If the list of goals is empty, it simply succeeds and returns the current instantiation env, unpacked into a list of pairs for later manipulation, while if n, which is a limit on the maximum number of rule applications, is zero, it fails.

As well as the instantiations, the necessary size bound is returned. First, however, it is worth noting another interesting feature of the present setup. Even though it is limited as a theorem prover, it can actually be used as a programming language. Prolog To ensure completeness, we performed iterative deepening over the total number of rule applications. Other approaches are possible, e.

We could also store the possible 3. Besides, as pointed out by Korf , the additional load of recalculation is usually relatively small because the number of possibilities tends to expand exponentially with depth, making the latest level dominate the runtimes anyway. A radical alternative is simply to abandon any kind of bound. Only by placing a limit on the number of rule applications did backtracking force hornprove to consider the second rule. However, when it does succeed, the unlimited search is often quicker, because it avoids the wasteful duplication and excessive search space exploration that can result from iterative deepening.

Application of this rule amounts to calling Q which in its turn will call the sub-procedures Pi. This is perhaps best understood by implementing it and demonstrating a few simple examples. For each polynomial p in the list pols we perform appropriate case-splits. But if any of the polynomials is a constant with respect to the top variable, we recurse to a delconst function to remove it. If the list of polynomials is empty, then trivially the empty sign matrix is the right answer, so we call the continuation on that.

Note the exception trap, though! Because of our rather naive case-splitting, we may reach situations where an inconsistent set of sign assumptions is made — for example a 0 or just a2 5. So we may elect to do no logical normalization of the formula at all, certainly not a full DNF transformation.

One way is to switch on tracing; e. The other required property, being an integer, is preserved by addition and multiplication. In practice, such a course is completely hopeless. One particularly notable failing of our algorithm is that it does not exploit equations in the initial problem to perform cancellation by pseudo-division, yet in many cases this would be a dramatic improvement — see Exercise 5.

In the purely linear case, where the language does not include multiplication except by constants, things are better still: we can slightly elaborate the DLO procedure from Section 5. We just put the variable to be eliminated alone on one side of each equation or inequality e.

For Decidable problems this, the classic simplex method Dantzig often works well in practice, and more recent interior-point algorithms following Karmarkar even have provable polynomial-time bounds. Word problems Suppose K is a class of algebraic structures, e.

However, the implicit algorithm was seldom competitive with simplex in practice. See Grotschel, Lovsz and Schrijver for a detailed discussion of the ellipsoid algorithm and its remarkable generality.

Many familiar structures are rings, e. However, it is important to realize that these values may not all be distinct. Theorem 5. Intuitively we think of i1 ,.

Intuitively, the arithmetic operations correspond to expanding out and collecting like terms, e. We will implement the ring Q[x1 ,. The zero polynomial is represented by the empty list. Let us note the following closure properties. Note that for a principal ideal, i. However, we emphasize a Decidable problems Theorem 5. By the results of Section 3. For the inner nodes, we need to verify that the property is preserved when using equality and congruence rules, and all those follow immediately from the closure properties of ideals noted above.

In the special case of the free word problem we have: Theorem 5. In a more general direction, the Horn nature of the ring axioms allows us to relate the validity of an arbitrary universal formula in the language of rings to the special case of the word problem. If there is exactly one qj x then we have the word problem.

We can arrive at a satisfying ideal membership equivalence for the word problem in torsion-free rings Simmons Proof A minor adaptation of the proof of Theorem 5.

In the other direction, note that the axioms T are still Horn, and in the same way we can prove the result by induction on a Prolog-style proof. The converse is not true in general, though it is true in integral domains, considered next.

As with rings, we will consider a proof of such a statement, and show by recursion on proofs that it implies a corresponding ideal membership property. But this time we have a non-Horn axiom I, so we need a more general proof format than Prolog-style trees; roughly following Lifschitz , we use binary resolution. This is refutation complete, so if the assertion above holds there is a proof of it by resolution. We may assume that all hypotheses are instantiated and consider a refutation of the instantiations by propositional resolution.

The same is true of the equivalence and congruence properties of equality, as we can check systematically. Applying the property deduced above to the empty clause yields the result. Several results on word problems are corollaries, most straightforwardly: Theorem 5. Proof Combine Theorem 5. Proof As usual, the right-to-left direction is straightforward. As we will see later, this is equivalent to a famous theorem in algebraic geometry, the strong Hilbert Nullstellensatz.

In the special case of characteristic zero: Theorem 5. This means that we can replace negated equations by unnegated ones, at the cost of adding new variables.

This method of replacing negated equations by unnegated ones is known as the Rabinowitsch trick. A Nullstellensatz in this special case of triviality is referred to as a weak Nullstellensatz. For example: 5.

Similarly: Theorem 5. This also shows that one can treat the Rabinowitsch trick as a purely formal transformation without reference to inverses. As it is an extension, it necessarily has the same characteristic. The proof is not too hard but uses a certain amount of algebraic machinery Lang ; for a sketch of an alternative proof using Decidable problems results of logic see Exercise 5. Combining all our results we see that all the following are equivalent for a universal formula in the language of rings.

Thus, despite the lengthy detour into general algebraic structures, we have arrived back at the complex numbers. We can proceed towards structures with fewer axioms as well. Similarly we have: Theorem 5. Proof Every ring is in particular an abelian monoid with respect to its multiplication operation, since the ring axioms include the abelian monoid axioms.

So if any formula holds in all abelian monoids it holds in all rings. Conversely, every abelian monoid M can be extended, given any starting ring R such as Z, to a ring R M called the monoid ring. We leave it to the reader to check that all details of the construction generalize straightforwardly.

Indeed, we could have regarded the polynomial ring as a special case of a monoid ring, based on the monoid of monomials. Corollary 5. Proof Combine the previous theorem and Theorem 5. We will once again argue that the word problems for abelian groups and rings in the common additive language are equivalent. One can prove this similarly based on the fact that every abelian group can be embedded in the additive structure of a ring Exercise 5.

But how do we solve such ideal membership questions? To be explicit, given multivariate polynomials q x , p1 x ,. But a serious defect is the need to place a bound on the monomials considered in the cofactors. One special case where this is unproblematical is solving the word problem for abelian groups: as noted we only need to consider constant cofactors. In fact there are theoretical bounds on the multidegrees we need to consider, and this formed the basis of early decision procedures for the problem Hermann This approach was originally developed by Buchberger in his PhD thesis — see also Buchberger — and in retrospect it has much in common with Knuth—Bendix completion, which it predated by some years.

We will present it emphasizing this connection and re-using some of the general theoretical results about abstract reduction relations from Section 4. We show the actual reductions followed by a restoration of the canonical polynomial representation with like monomials collected together, to make it easier to grasp what is happening. Abstractly, though, we consider these folded together in the reduction relation.

Moreover, x appears only linearly in the result, so no further reductions are possible. Indeed, we will show that polynomial reduction is always terminating, whatever the set S and the initial polynomial.

It follows at once from the wellfoundedness of the multiset ordering see Appendix 1 that the reduction process is terminating. Suppose that a polynomial p can be reduced in one step either to q1 or to q2.

Rather as with rewriting, we can distinguish two distinct possibilities. Thus q1 and q2 are joinable. Although this new relation does not coincide with joinability, it does imply it. The converse is not true in general, as the example F above shows.

We lead up to this via a few lemmas. Lemma 5. By Lemma 5. But by Lemma 4. Again appealing to Lemma 4. Since 0 is in normal form w. Now we can arrive at an analogous theorem to Theorem 4. Since this monomial m is a multiple both of m1 and m2 , it must be a multiple of LCM m1 , m2. However, by Theorem 5. Proof Using Theorem 5. Now we will prove the other implications.

Note that the relation on the right is trivially transitive, by the closure of ideals under addition. Moreover, Theorem 5. Thus, the following algorithm maintains the invariant that all S-polynomials of pairs of polynomials from basis are joinable by the reduction relation induced by basis except possibly those in pairs.

And in fact, we are in the happy situation, in contrast to completion, that termination is guaranteed. Note that each S-polynomial is reduced with the existing basis before it is added to that basis. Consequently, each polynomial added to basis has no monomial divisible by the head monomial of any existing polynomial in basis. Let a0 be such a number. This is the minimal bad sequence.

However, the existence of a minimal bad sequence ai , si is contradictory. For the negative equations, we will use the Rabinowitsch trick. New variables rvs are created for the Rabinowitsch transformation of the negated equations, and the negated polynomials are appropriately transformed.

There are also various criteria that justify ignoring many S-polynomials, e. For each point p in the original assertion we consider its coordinates, two real numbers px and py for two-dimensional geometry. Geometrical assertions about the points can then be translated into equations in the coordinates.

It has even been suggested Wildberger that geometry should be phrased in terms of quadrance and spread instead of length and angle, precisely to stick with algebraic functions of the coordinates. Moreover, the geometric properties are also unchanged under rotation about the origin. Intuitively we think of s and c as the sine and cosine of the angle of rotation, but we treat it purely algebraically. Similarly, we might want to use shearing invariance to justify taking three of the points as 0, 0 , x, 0 and 0, y , but this is problematic if the three points may be collinear.

For some time after this, the subject of automated geometry theorem proving received little attention. Nevertheless, it turns out in practice that most geometrical statements remain valid in the extended interpretation; see Exercise 5. Another drawback is that we cannot express ordering of points using the complex numbers, which places some restrictions on the geometric problems we can formulate. Degenerate cases We can successfully prove a few simple geometry theorems based on this idea.

Suppose we assume the equations in such a triangular set as hypotheses. Given another polynomial p x1 ,. First we pseudo-divide p x1 ,. Given pm x1 ,. We can then proceed to replace each ci x1 ,. The user is expected to list the variables in elimination order in vars, and specify which coordinates are to be set to zero in zeros.

The last is trivially true. The others do indeed express various nondegeneracy conditions: the points B and C are distinct, the points B and A are distinct, and the points C and A are distinct. Remember that A is the origin in this coordinate system. However, this is not in general the case over the complex numbers, and indeed there are non-Euclidean geometries e. Minkowski geometry in which non-trivial isotropic lines lines perpendicular to themselves may exist.

The others assert that the points A1 and A2 are not in fact the origin of the clever coordinate system we chose, i. Our examples above closely follow Chou , and numerous other examples can be found in Chou For example, instead of proving over N that n Decidable problems Limitations Unfortunately, the freedom to generalize existing decision procedures by introducing new symbols is quite limited. For example, consider the theory of reals with addition and multiplication, which we know is decidable Section 5.

This holds for logic with equality and logic without equality, and we will prove both forms below. The starting-point is the analogous result for propositional formulas, which is relatively easy to prove. Robinson First: Lemma 5. Q[y1 ,. Q[x1 ,. Again we can express the proof as an algorithm, for simplicity using the Davis—Putnam procedure from Section 3. However, c contains the unshared function symbols 0 and f , and indeed combinations of the two, so is not yet a full interpolant.

To show how we can always eliminate unshared function symbols from our partial interpolants, we note a few lemmas. C[x1 ,. But note that since there are no terms in C[x1 ,. We lift this to general formulas using Skolemization. If there are none, then the result follows from the previous lemma.

Suppose it is not yet an interpolant, i. In order to apply replacement repeatedly, we need to be careful over the order in which we eliminate terms. Now, since h is non-shared, there are two cases. If h occurs in P [x1 ,. Dually, if h occurs in Q[y1 ,. We can now iterate this step over all terms involving unshared function symbols, existentially or universally quantifying over the new variable depending on which of the starting terms the top function appears in.

Eventually we will eliminate all such terms and arrive at an interpolant. If we try this on our current example, we now get a true interpolant as expected. Once again we use Skolemization. Thus we can apply uinterpolate to obtain an interpolant. First, note that interpolation applies equally to logic with equality, where now the interpolant may contain the equality symbol even if only one of the formulas p and q does.

Form the conjunctions of their universal closures p and q and apply the basic result for logic with equality. The Nelson—Oppen method To combine decision procedures for theories T1 ,.

All the information is packaged up into a triple. Note that we still include multiplication though not exponentiation in the language though its application is strictly limited; this can be considered just the acceptance of syntactic sugar rather than an expansion of the language.

The following takes an explicit list of languages langs and adds on another one that treats all other functions as uninterpreted and handles equality as the only predicate using congruence closure. This could be extended to treat other predicates as uninterpreted, either by direct extension of congruence closure to the level of formulas or by using Exercise 4.

Homogenization The Nelson—Oppen method starts by assuming the negation of the formula to be proved, reducing it to DNF, and attempting to refute each disjunct. Note that in the case of an equation there may be a choice of which topmost function symbol to choose, e. Note also that in the case of an equation between variables we need a language including the equality symbol in our list e.

The following homogenizes a term, Decidable problems given a language with its function and predicate discriminators fn and pr. In the case of a variable, we apply the continuation to the current state.

If we have more than two theories, we need an iterated version of the same procedure. The interpolation theorem assures us that an interpolant exists, and that it is built from variables using the equality relation.

We would prefer to assume only component decision procedures for universal formulas, and indeed this is all we have for the theory of uninterpreted functions and equality.

We will use this below. Recall that our general problem is to decide whether T1 ,. Let us consider all possible ways in which an interpretation can set them equal or unequal to each other, i. For each partitioning P of the x1 ,. This gives us, in principle, a decision method. Now let us justify the claim. Otherwise we have T2 ,. Note that since the arrangements only need to be able to decide the nominal interpolants considered above, we may restrict ourselves to considering variables that appear in at least two of the homogenized conjuncts Tinelli and Harandi After homogenization, we repeatedly try the following.

To generate the disjunctions, we could simply enumerate all subsets of the set of equations. The corrected method has been used as the basis for a real implementation of the combined procedure called Yices. Cost, power, speed, and communication are a few of the many considerations when choosing the right PLC for the job.

Don't Miss Our Updates. Be the first to get exclusive content straight to your email. We promise not to spam you. You can unsubscribe at any time. Recommended Articles. More Articles. PLC Software a. Understanding Ladder Logic b. Basic Instructions c. Ladder Logic in Action. Automated reasoning Handbook. Logic in computer science Reasoning - publishing subsection.

Citation Type. Has PDF. Publication Type. More Filters. Revising basic theorem proving algorithms to cope with the logic of partial functions. Highly Influenced. View 4 excerpts, cites background and methods. It has been pointed out by a number of authors that partial terms i. Furthermore, earlier … Expand. View 1 excerpt, cites methods.

A Survey of Interactive Theorem Proving. Fully formally verified mathematics and software are long-standing aims that became practically realizable with modern computer tools. Reasoning can be reduced to several basic logical principles, … Expand.