Atlas: Decidability of t-tautologies by Petr Hajek

Atlas home || Conferences | Abstracts | about Atlas

First St.Petersburg Days of Logic and Computability
May 26-29, 1999
Steklov Institute of Mathematics
St. Petersburg, Russia

Organizers
Evgeny Dantsin, Gennadii Davydov, Dima Grigoriev, Eduard Karavaev, Nickolai Kossovskii, Vladimir Lifschitz, Maurice Margenstern, Yuri Matiyasevich (chairman), Grigori Mints, Vladimir Orevkov, Anatol Slissenko, Maxim Vsemirnov

View Abstracts
Conference Homepage

Decidability of t-tautologies
by
Petr Hájek
Institute of Computer Science of the Czech Republic, Prague

Each continuous t-norm * determines a fuzzy propositional calculus with * as the truth function of conjunctions, the residuum ===> of * as the truth function of implication and with the truth function (-) of negation defined by (-)x=x ===> 0. It is known that for each of the three most important t-norms - Lukasiewicz, Gödel and product t-norm - the set of * -tautologies (formulas having identically the value 1) is decidable, even NP-complete. (Note that Gödel propositional fuzzy logic is an intermediate logic - stronger than intuitionistic logic.)

A fomula is a t-tautology if it is a * -tautology for each continuous t-norm * .

Theorem. The set of all t-tautologies is recursive. A proof (using Hähnle's method based on mixed integer programming) will be sketched.

Remark. (1) A more detailed analysis shows that in fact the set of all t-tautologies is NP-complete; the full proof is planned to be published as a joint work of the present author with M. Baaz and H. Veith. (2) Note that deductive systems of fuzzy logic - both propositional and predicate - are elaborated in detail in my monograph Metamathematics of fuzzy logic, Kluwer 1998. The talk will start with a short survey of the main approach and basic notions.

Date received: February 19, 1999