# Uncategorised

## Truth Maintainance System

- Details
- Written by Administrator
- Category: Uncategorised

In logics, truth can "change" over time. What I mean with this concept :

*Obama is the president of the United States.*

In time the truth value of this sentence might change. In 2056 we will probably have it false. During the life of our logic reasoning facts can change from true to false and so forth. The purpose of a **Truth Maintainance System** is too keep track of the truth values of the sentences, complying with the fact that facts are generated from already existing facts that might change truth value.

For example we know that

*P*

and

*P->Q*

In this case we can add to the knowledge base the fact

*Q*

because *P* is true and we know that *P->Q*.

However if later on we need to retract *P* and assert *~P* (eg. P is now false), the truth value for *Q* is wrong, because it was based on the assertion of P. In this case we have either to rollback all statements that were asserted after asserting P, or recheck them. A truth maintainance system ensures all this.

A simple method of keeping tracks of true and untrue values is keeping a list of *IN *and *OUT *facts. Each fact has a list of facts that have to be *IN *so that the fact itself is *IN*. This is the *IN *list. Also each fact has to have a list of facts that are *OUT *so that the fact is *IN*. This is called the *OUT *list.

This method creates a graph of facts each dependent on others, and it''s easy to propagate modifications from leafs ( that are basic assumptions) to the end of the tree to see what states changed.

For example in our* P->Q* statement, the node is *Q*, and it''s *IN* list is *P*. The *OUT *list is empty. If *P* becomes *OUT*, then *Q* becomes *OUT *as well. If we had a statement like *P ^ ~R -> Q* then the *IN *list was *P* and the *OUT *list was *R*. Any change in this facts would change *Q* as well.

## Prenex Normal Form

- Details
- Written by Administrator
- Category: Uncategorised

In First Order Predicate Logic ( FOPL ), one can represent an expression using the operators

*For any X, Expression*

*Exists X such that Expression.*

Where Expression is a logic expression , either a predicate or a combination of logic operators and other expressions.

In order to represent an Expression in **Prenex Normal Form**, one must do some transformation. For an expression to be in Prenex Normal Form, all the "Any" and "Exists" Logical operators must precede a whole stand-alone expression. For example, expression

*(Any X in P(X) ) Or ( Exists Y in Q(Y))* it''s not in Prenex Normal Form.

Expression

*(Any X in ( P(X) and Q (Y) ) )* **is** in Prenex Normal Form .

Prenex Normal Form is useful in Knowledge representation for obvious reasons: memorizing in computer memory, specific attributes: We evaluate first the "Any"/"Exists" operators and the following expression can be substituted to simple expression.

To convert a normal expression to Prenex Normal Form, we consider the following transformation rules:

*( Any X in Expr) or (Another_Expr) *changes to *(Any X in ( Expr or Another_Expr )) *with mentioning the fact that X has no **free **appearances in Another_Expr ( if free they are renamed to another **free **variable )

*( Any X in Expr) and (Another_Expr)* changes to *(Any X in (Expr and Another_Expr ))* with same mentioning.

The same rules apply to *Exists *operator.

## Association rule Mining

- Details
- Written by Administrator
- Category: Uncategorised

Let''s say we want to mine some data for our supermarket, given as example previously.

A customer from a supermarket buys several products. This are categorical data. Let''s say he buys *Honey, Milk, Sugar, Bread*. We want to determine if other customers buy these items ( or part of them ), and if it''s possible to tell that one or more of these products determines the others. In other words, if for example a customer buys Milk and Sugar, it will also buy Honey and Bread.

First of all let''s see what other customers bought:

*Customer 2: Milk, Paper, Honey*

*Customer 3: Sugar, Honey, Milk, Beer*

*Customer 4: Beer, Chips, Bread*

*Customer 5: Milk, Honey, Bread*

We define an **association rule** as two related parts of an item set, such that first part determines the second part.

Example : Milk -> Sugar, Honey.

An **itemset **is a set of items such that each item is present only once.

For a given itemset, one can create multiple association rules.

An association rule has a *support *and a *confidence*. The support is defined as the number of customers ( transactions ) that bought all the items in the item set divided by the total number of transatctions. The confidence is defined as the number of transactions that include the first part of the association rule and the second part divided by total number of transactions that include the first part.

The support for our rule Milk -> Sugar, Honey is 2/5 e.g. 40 %. This is because Customer 1 and 3 have in their itemsets all the 3 items from our rule, and the total number of transactions is 5.

The confidence for our rule is 2/4 e.g. 50 % , because there are 4 customers that have Milk and only 2 which have Milk **and** Sugar, Honey.

For our rule we can say that buying Milk **determines **the buying of Sugar and Honey with a *support *of 40 % and a *confidence *of 50 %.

## Parameter evaluation in programming languages

- Details
- Written by Administrator
- Category: Uncategorised

How does parameter evaluation influences programming?

First of all how are possible evaluations?

Method 1: Evaluate each parameter *at a time* and then pass the result to the next level ( called function for example ). In this case parameters are send **by value**.

Method 2: Send the parameters *as they are*, and let the next level evaluate them, *if necessary*. In this case parameters are send **by name**.

At first glance, there is not an important difference, however, looking closer we may notice:

- Sending parameters by name implies a bigger stack because all calls need to store partial results and all unapplied parameters

- Sending parameters by name implies having evaluation at a later time, which in state-full programming languages/environments this may bring up some problems. On stateless situations evaluation time is non significant.

- Sending parameters by value may bring unnecessary computations because we may not need the evaluation of certain parameters.

Here is an example written in C programming language

*int myFunc( int parameter)*

*{*

*return 0;*

*}*

In this case the evaluation of parameter, in the case of the call *myFunc( someOtherFunc(some params ))*, computing the parameter value is useless.

Lets say *someOtherFunc *does the following:

*int someOtherFunc( some params )*

*{*

*while (1) ;*

*return 0;*

*}*

In this case, evaluation** by value** will have a serious problem because program will never end.

However, evaluation **by name** will end in a normal fashion because there is no need to call *someOtherFunc*.

*Stateless *programming languages can fully take advantage of this **lazy-evaluation**, but on *state-full *situations, *someOtherFunc *may change environment so it''s evaluation can become mandatory.

The C programming language uses *applicative evaluation*, which is by *value*, while functional programming languages like Haskell use** lazy-evaluation**.