Equivalences & rewrite rules - artificial intelligence, Computer Engineering

Assignment Help:

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.


Related Discussions:- Equivalences & rewrite rules - artificial intelligence

Define the term- encryption, Define the term- encryption The user would ...

Define the term- encryption The user would then type in O P E and card purchase will be authorised. This extra protection is used as well as encryption. Some of the new syste

How do you traverse a btree in backward in-order, Put the node in the right...

Put the node in the right subtree Then, Put the root  Put the node in the left subtree

What do you mean by decoders, Q. What do you mean by Decoders? Decoder ...

Q. What do you mean by Decoders? Decoder transforms one kind of coded information to other form. A decoder has n inputs and one enable line (sort of selection line) and 2 n ou

How many octets does smallest possible ipv6 datagram contain, How many Octe...

How many Octets does the smallest possible IPV6 datagram contain? The maximum size of an Ipv6 datagram is 65575 bytes, with the 0 bytes Ipv6 header. Ipv6 also describe a minim

What are attributes, What are Attributes?  Attributes are declarative ...

What are Attributes?  Attributes are declarative tags in code that insert additional metadata into an assembly. There exist two types of attributes in the .NET Framework: Pred

Maximum size of a database, What is the maximum size of a database that can...

What is the maximum size of a database that can be opened in Microsoft Access? Ans) 1 Gigabyte

What is programming paradigm, a. Explain the Programming Paradigm? Discuss ...

a. Explain the Programming Paradigm? Discuss four major programming paradigms. b. State the three basic logic operators available in C++? Write a small program in C++ that uses

Define about classes of object oriented modelling, Define about classes of ...

Define about classes of object oriented modelling A class is a collection of things, or concepts that have the same properties. Each of these concepts or things is known an obj

Do you provide storage and destruction services, Do you provide storage and...

Do you provide storage and destruction services? We will assess your storage and destruction needs as part of our evaluation process. Our destruction services can be performed

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd