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
Question: (a) Primary and secondary memory differs in their way they access data: (i) Mention the four generic access methods usually present in a computer system. (ii) E

What is OO Development? OO development is a way of thinking about software based on abstractions that exist in the actual world. Development refers to software lifecycle, desig

What are the properties which a data item should possess to implement a critical section? The Critical Section Problem Solution should satisfy the following conditions: 1.

This question can be answered either with respect to English or with respect to a language other than English. (If you you are not a native speaker of the language of your choice,

Opening Files for Reading Only     : A data file is a file that you can open and read its contents visually - for example, C source files, .dat files, HTML etc - anything that look

Hyper cube or multidimensional cube forms the core of OLAP system. This having of measures which are arranged according to dimensions. Hyper cube Meta data is formed by star or sno

I need help to create test cases for the MIPS Instruction set architecture

i want the matlab code for the following events 1. face detection 2. video to frame conversion 3.video shot boundary detection

Q. How to make frames for web documents? Intelligent use of frames can give your pages a cleaner look and make easier to navigate. The fundamental concept goes like this: Every

In a two stage network there are 512 inlets and outlets, r=s=24. If the probability that a given inlet is active is 0.8, calculate: Blocking probability Given: N =M =512,