Equivalence and Feasibility

Before proceeding to the presentation of detailed information about the algorithms of inference, it is necessary to consider some additional concepts relating to the logical consequence. Like the very concept of the consequence, these concepts apply to all forms of logic, but they are best shown by the example of a particular variant of logic, such as propositional logic.

The first concept is logical equivalence : two statements, α and β, are logically equivalent if they are true in the same set of models. This statement is written as α <=> β. For example, one can easily show (using truth tables) that the statements P ^ Q and Q ^ P are logically equivalent; other equivalences are shown in the listing. They play almost the same role in logic as arithmetic equalities play in ordinary mathematics. An alternative definition of equivalence is as follows: for any two statements α and β

α ≡ β if and only if α | = β and β | = α

(Once again we remind that | = means a logical consequence.)

The second concept that we need is admissibility. The statement is valid if it is true in all models. For example, the statement P v ¬ P is valid. Valid statements are also known as tautologies - they are necessarily true and therefore redundant. Since the statement True is true in all models, any valid statement is logically equivalent to True.

What can valid statements be used for? From the definition of a logical consequence, we can derive the deduction theorem , which was known in ancient Greece:

For any statements α and β, α | = β, if and only if the statement (α => β) is admissible.

The inference algorithm shown in the listing can be considered as a test of the admissibility of a statement (KB => α). And vice versa, each admissible statement in the form of an implication describes an acceptable variant of a logical inference.

The last concept that we need is feasibility. Some statement is feasible if and only if it is true in some model. For example, the above knowledge base, (R ₁ ^ R ₂ ^ R ₃ ^ R ₄ ^ R ₅ ), is feasible because there is not even one, but three models in which it is true. If some statement a is true in the model m, then the expression that "m performs α" or that "m is a model α" is used to denote this. The feasibility can be checked by going through all possible models until at least one of them is found that performs this statement. The first task in propositional logic, for which it was proved that it is NP-complete, was the task of determining the feasibility of statements.

Many tasks in computer science really represent the tasks of determining feasibility. For example, in all problems of satisfying constraints, in essence, it was necessary to find an answer to the question of whether these constraints are satisfied with some assignment. In addition, with the help of appropriate transformations according to the method of verifying the feasibility, we can also solve search problems. Of course, the concepts of admissibility and feasibility are related to each other: a statement a is admissible if and only if the statement - ¬α is impracticable, and vice versa, the statement a is feasible if and only if the statement ¬α is unacceptable. On this basis, the following useful result can also be obtained:

The statement α | = β is true if and only if the statement (α ^ ¬β) is impracticable.