Truth Maintainance System

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

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

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

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.

Get more Joomla!® Templates and Joomla!® Forms From Crosstec