Equivalences & rewrite rules - artificial intelligence, Computer Engineering

Equivalences & Rewrite Rules - artificial intelligence:

Along with allowing us to verify trivial theorems, tautologies make us able to establish that definite sentences are saying the same thing. In precise, if we can show that A <-> B is a tautology then we knows B and A are true for exactly the same models, for example they will have identical columns in a truth table. We say that B and A are logically equivalent, written as the equivalence A ≡ B.

(Clearly ↔ it means the same thing here, so why use 2 different symbols? It is a technical difference: A<->B is a sentence of propositional logic, whereas A B is a claim we make outside the logic.)

In natural language, we could replace the phrase in sentences "There is only 1 Tony Blair" by "Tony Blair is unique",because the phrases mean the similar thing in actual. We can do just the similar in logical languages, with an advantage: because in the sense of beingmore formal, we will have mathematically proved that 2 sentences are equivalent.  This means that no doubt there is not any situation in which  1sentence would be interpreted in a different way to another, which is surely possible with natural language sentences about Tony Blair.

Similaritiesallow us to change 1 sentence into another without changing the meaning, because we know that replacing 1 side of an equivalence with the other will have no effect whatsoever on the semantics: yet it will be true for the same models. Imagine we have a sentence S with a sub expression A, which we write as S[A]. If we know A ≡ B then we maybe sure the semantics of S is not affected if we replace A with B, for instance S[A] ≡ S[B].

Moreover, we may also use A≡B to replace any sub expression of S which is an instance of A. for an example of a propositional expression A is a 'copy' of A where some  of  the  propositions  of  have  been  consistently  replaced  by  new  sub expressions, for example every P has been replaced by Q. We call this replacement a substitution this is a mapping from propositions to expressions. By applying a substitution U to a sentence S, we get a new sentence S.U which is acase of S. It is simple to show that if A ≡ B then A.U ≡ B.U for any substitution For example a case of equivalence is also equivalence. Hence an equivalence A  B allows us to change a sentence S[A'] to a logically equivalent one S[B'] if we have substitution U such as A' = A.U and B' = B.U.

The power to replace sub expressions allows utilize to verify theorems with equivalences: in the above example, given a theorem S[A'] S[B'] we may use the equivalence A ≡ B to rewrite the theorem to the equivalent S[A'] <-> S[A'], which we know to be true. Given a set of equivalences we may prove (or disprove) a complicated theorem by rewriting it to something logically equivalent thatalready we know to be true (or false).

The fact that we may rewrite case of A to case of B is expressed in the rewrite rule A => B. We, of course, can also rewrite Bs to As, so we could use the rewrite rule B => A instead. However, it is easy to see that having an agent use both rules is dangerous, as it could get stuck in a loop A => B => A => B => ... and so on. Hence, we typically utilize just one of the rewrite rules for a specific equivalence (we 'orient' the rule in a single direction). If we do use both then we have to make sure we do not get stuck in a loop.

Apart from proving theorems directly, the other use for rewrite rules is to prepare a statement for use before we find for the proof. This is because some automated deduction techniques require a statement to be in a specific format, and in these cases, we may use a set of rewrite rules to convert the sentence we want to show into a logically equivalent 1 which is in the correct format.

Below are some common equivalence which automated theorem proves can use as rewrite rules. Remember that the rules may be read both ways, but that in practice either (i) just one direction is used or (ii) a loop-check is employed. Notice that also these are true of sentences in propositional logic, so they may also be used for rewriting sentences in first order logic, which is only an extension of propositional logic.

Posted Date: 10/2/2012 7:40:55 AM | Location : United States

Related Discussions:- Equivalences & rewrite rules - artificial intelligence, Assignment Help, Ask Question on Equivalences & rewrite rules - artificial intelligence, Get Answer, Expert's Help, Equivalences & rewrite rules - artificial intelligence Discussions

Write discussion on Equivalences & rewrite rules - artificial intelligence
Your posts are moderated
Related Questions
A 4-bit synchronous counter uses flip-flops with propagation delay times of 15 ns each.  The maximum possible time required for change of state will be ? Ans. 15 ns since in sy

Q. Explain Functional Roles of Information System? Functional Roles of Information System 1 Lower Costs - a) Use IT to significantly reduce the cost of business proce

Q Develop a program that accepts decimal number and converts it into given base. Fractional numbers are allowed and negative numbers are not allowed. Also check that entered number

Background, Examples and Hypothesis: Now we will switch off with three logic programs. So very firstly, we will have the logic program representing a set of positive examples

Given the following interface public interface WordSet extends Iterable { public void add(Word word); // Add word if not already added public boolean contains(Word word);

The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which one of the following is the postorder traversal sequence of the same tree?

What is Double entry - Verification In this approach, data is entered twice (using two different people); data is only accepted if both versions match up. Generally used to ve

8:1 Mux for a given function, f=S (0, 1,5,7,9, 13)..