On the expressive power of IF-logic with classical negation

It is well-known that Independence Friendly (IF) logic is equivalent to existential second-order logic ((formula presnted)) and, therefore, is not closed under classical negation. The boolean closure of IF sentences, called Extended IF-logic, on the other hand, corresponds to a proper fragment of (f...

Descripción completa

Detalles Bibliográficos
Publicado: 2011
Materias:
Computation theory
Existential second-order logic
Expressive power
Non-trivial
Prenex normal forms
Second-order logic
Computer circuits
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v6642LNAI_n_p135_Figueira
http://hdl.handle.net/20.500.12110/paper_03029743_v6642LNAI_n_p135_Figueira
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_03029743_v6642LNAI_n_p135_Figueira
record_format dspace
spelling paper:paper_03029743_v6642LNAI_n_p135_Figueira2023-06-08T15:28:39Z On the expressive power of IF-logic with classical negation Computation theory Existential second-order logic Expressive power Non-trivial Prenex normal forms Second-order logic Computer circuits It is well-known that Independence Friendly (IF) logic is equivalent to existential second-order logic ((formula presnted)) and, therefore, is not closed under classical negation. The boolean closure of IF sentences, called Extended IF-logic, on the other hand, corresponds to a proper fragment of (formula presnted). In this paper we consider IF-logic extended with Hodges’ flattening operator, which allows classical negation to occur also under the scope of IF quantifiers. We show that, nevertheless, the expressive power of this logic does not go beyond (formula presnted). As part of the proof, we give a prenex normal form result and introduce a non-trivial syntactic fragment of full second-order logic that we show to be contained in (formula presnted). © 2011, Springer-Verlag Berlin Heidelberg. 2011 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v6642LNAI_n_p135_Figueira http://hdl.handle.net/20.500.12110/paper_03029743_v6642LNAI_n_p135_Figueira
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic Computation theory
Existential second-order logic
Expressive power
Non-trivial
Prenex normal forms
Second-order logic
Computer circuits
spellingShingle Computation theory
Existential second-order logic
Expressive power
Non-trivial
Prenex normal forms
Second-order logic
Computer circuits
On the expressive power of IF-logic with classical negation
topic_facet Computation theory
Existential second-order logic
Expressive power
Non-trivial
Prenex normal forms
Second-order logic
Computer circuits
description It is well-known that Independence Friendly (IF) logic is equivalent to existential second-order logic ((formula presnted)) and, therefore, is not closed under classical negation. The boolean closure of IF sentences, called Extended IF-logic, on the other hand, corresponds to a proper fragment of (formula presnted). In this paper we consider IF-logic extended with Hodges’ flattening operator, which allows classical negation to occur also under the scope of IF quantifiers. We show that, nevertheless, the expressive power of this logic does not go beyond (formula presnted). As part of the proof, we give a prenex normal form result and introduce a non-trivial syntactic fragment of full second-order logic that we show to be contained in (formula presnted). © 2011, Springer-Verlag Berlin Heidelberg.
title On the expressive power of IF-logic with classical negation
title_short On the expressive power of IF-logic with classical negation
title_full On the expressive power of IF-logic with classical negation
title_fullStr On the expressive power of IF-logic with classical negation
title_full_unstemmed On the expressive power of IF-logic with classical negation
title_sort on the expressive power of if-logic with classical negation
publishDate 2011
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v6642LNAI_n_p135_Figueira
http://hdl.handle.net/20.500.12110/paper_03029743_v6642LNAI_n_p135_Figueira
_version_ 1768546675352141824

Ejemplares similares