Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am working on an inference system for infinite valued Łukasiewicz logic, using standard MV-algebras.

As a pre-processing step, I would like to perform (non-exhaustive) simplification of formulae. So I am wondering what simplifying equivalences hold in the algebra of this logic. I know that the usual lattice axioms hold:

$$a \lor a = a$$ $$a \land a = a$$ $$ \vdots$$ $$ \text{etc.}$$

The absorption laws listed above would are good examples of simplifying formulae.

Anybody know of some other good simplifying algebraic identities for Łukasiewicz logic?

share|improve this question
    
Any examples of formulas in particular that you want to simplify? –  Doug Spoonwood Mar 10 '13 at 19:15
add comment

3 Answers 3

For a convenient set of identities, have you checked the usual axioms of MV-algebras? For normal forms, have you had a look at McNaughton's theorem? The answer to these questions may be found in the work by Antonio Di Nola and by Daniele Mundici. Have you checked the proof-theoretic approach proposed by George Metcalfe?

share|improve this answer
    
Well, I want to simplify expressions prior to converting to McNaughton Normal Forms. Yeah, I've looked at the usual axioms, but honestly apart from absorption rules it doesn't appear that there are many good candidates for simplification rules, so I was hoping an expert would chime in. As for Metcalfe's stuff: my decision procedure involves solving SAT problems over McNaughton Normal Forms, so I've pretty much married myself to using semantics over proof theory... –  Matt W-D Mar 9 '13 at 5:31
add comment

An infinite valued logic on [0, 1] with max(x, y)=(x$\lor$y), min(x, y)=(x$\land$y), (1-x)=$\lnot$x has the same theorems as a three-valued logic on {0, 1/2, 1} with max for $\lor$, min for $\land$, and (1-x) for $\lnot$. So, we just need to check the three-valued cases for any proposed simplifying equivalence. See Walker and Nguyen's A First Course in Fuzzy Logic, the section on the logical aspects of fuzzy sets, for an outline of a proof. Unfortunately, I don't know if we have a similar situation for the richer structure you've referenced.

share|improve this answer
    
That doesn't seem right. In Łukasiewicz logic a → b = min(1,1-a+b); you can define a + b := ¬a → b. It is not generally true that (a+a+a) → (a+a) (for instance, where a = 1/3), however in a three valued logic that would be a tautology. I'm now a little skeptical that your source is treating the same fuzzy logic I'm studying. –  Matt W-D Mar 10 '13 at 18:54
    
Thanks for pointing out that strong disjunction "+" isn't similar in 3-valued and infinite-valued logic. That said, for any formula which uses only $\lor$, $\land$, and $\lnot$, the above still should apply. –  Doug Spoonwood Mar 10 '13 at 19:13
add comment

To give a few that I've come up with, we have the absorption rules I mentioned:

$$ a \land a = a$$ $$ a \lor a = a$$

We also have some other common lattice rules:

$$ 0 \lor a = a$$ $$ 0 \land a = 0$$ $$ 1 \land a = a$$ $$ 1 \lor a = 1 $$

In fact, all of these can be seen as instances of the general absorption pattern (particular to Łukasiewicz logic):

$$ (a \oplus b) \lor a = (a \oplus b) $$ $$ (a \oplus b) \land a = a $$

There's also double negation: $$ \neg\neg a = a $$

Here are some simplifying implication rules: $$ a \to a = 1$$ $$ a \to 0 = \neg a $$ $$ \neg a \to \neg b = b \to a $$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.