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
Given: • A sequence of n arrival times t0, t1, ..., tn-1, • a library of mlogically equivalent gates {(d0, c0), (d1, c1), ..., (dm-1,cm-1)} where d is delay and c is cost • a

Mr. X's MMPI suggests that he either suppresses anger and hostility or has a naturally low level of anger and hostility (O-H=58, ANG=36, TPA=41, AGGR=36). His responses on the PAS

1. Click Tools > General Options, and then click the Object Mapping tab. 2. From the Object type list, select the standard object type that is associated with the object class

Businesses are interested in AI because of the characteristics it offers that no other systems type offers. That is AI ability to: a. Preserve Intelligence and Knowledge: C

Use of Typewriters for Multiple Copies : Offices frequently require copies of various letters and documents. The simplest method is to make the copies at the same time along with

What is a disk drive? The electro mechanical mechanism that spins the disk and moves the read/write heads known as disk drive.

A protocol is a formal description of message formats and the rules two or more machines must follow to exchange those messages. Because TCP (transmission control protocol) and IP

Q. Illustration of parallel programming environments? Let's discuss illustrations of parallel programming environments of Intel paragaon XP/S and Cray Y-MP software. The Cra

Q. Drawback of the system using disk caching? The main drawback of the system using disk caching is risking loss of updated information in event of machine failures like loss o

How do you create special files like named pipes and device files? The system call method forms special files in the following sequence. Kernel assigns new inode,