Some decades ago, V. Klee and G.-C. Rota introduced a lattice-theoretic analogue of the Euler characteristic, the celebrated topological invariant of polyhedra. Using the Klee-Rota de nition, we introduce the Euler characteristic of a formula in G odel logic (an extension of intuitionistic logic, or, equivalently, a many-valued logic). We then prove that the Euler characteristic of a formula \phi coincides with the number of Boolean assignments that satisfy the formula \phi. Building on this, we generalise this notion to other invariants of \phi that provide additional information about the satis ability of \phi in G odel logic. Specifically, while the Euler characteristic does not determine non-classical tautologies, these new invariants do. Finally, if time allows, we sketch a similar analysis for other many-valued logics.

The Euler characteristic of a formula in many-valued logic / P. Codara. ((Intervento presentato al convegno Combinatorics tenutosi a Verbania, Italy nel 2010.

The Euler characteristic of a formula in many-valued logic

P. Codara
Primo
2010-07

Abstract

Some decades ago, V. Klee and G.-C. Rota introduced a lattice-theoretic analogue of the Euler characteristic, the celebrated topological invariant of polyhedra. Using the Klee-Rota de nition, we introduce the Euler characteristic of a formula in G odel logic (an extension of intuitionistic logic, or, equivalently, a many-valued logic). We then prove that the Euler characteristic of a formula \phi coincides with the number of Boolean assignments that satisfy the formula \phi. Building on this, we generalise this notion to other invariants of \phi that provide additional information about the satis ability of \phi in G odel logic. Specifically, while the Euler characteristic does not determine non-classical tautologies, these new invariants do. Finally, if time allows, we sketch a similar analysis for other many-valued logics.
Settore INF/01 - Informatica
Settore MAT/01 - Logica Matematica
http://www.mate.polimi.it/comb2010/
The Euler characteristic of a formula in many-valued logic / P. Codara. ((Intervento presentato al convegno Combinatorics tenutosi a Verbania, Italy nel 2010.
Conference Object
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2434/169265
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact