You get a bonus - 1 coin for daily activity. Now you have 1 coin

Equivalence and Feasibility

Lecture



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 1 ^ R 2 ^ R 3 ^ R 4 ^ R 5 ), 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.

The proof of the truth of the statement β on the basis of the truth of the statement a by checking the impracticability of the expression (α ^ ¬β) corresponds exactly to the standard mathematical method of proof by reduction to the absurdity (literally, “reduction to the absurd” - reductio ad absurdum). It is also called proof by refutation , or evidence by identifying contradictions . In this method of proof, the assumption is accepted that the statement β is false, and it is demonstrated that such an assumption leads to a contradiction with the known axioms α. Such a contradiction corresponds exactly to what is meant by the statement that the expression (α ^ ¬β) is impracticable.
created: 2014-09-23
updated: 2021-03-13
132466



Rating 9 of 10. count vote: 2
Are you satisfied?:



Comments


To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Logics

Terms: Logics