On the expressive power of IF-logic with classical negation

Mostrar todas las versiones(3)

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

Guardado en:

Detalles Bibliográficos
Autores principales:	Figueira, S., Gorín, D., Grimson, R., Beklemishev L.D., Queiroz R.
Formato:	SER
Materias:	Computation theory Existential second-order logic Expressive power Non-trivial Prenex normal forms Second-order logic Computer circuits
Acceso en línea:	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	todo:paper_03029743_v6642LNAI_n_p135_Figueira
record_format	dspace
spelling	todo:paper_03029743_v6642LNAI_n_p135_Figueira2023-10-03T15:19:18Z On the expressive power of IF-logic with classical negation Figueira, S. Gorín, D. Grimson, R. Beklemishev L.D. Queiroz R. 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. SER info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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 Figueira, S. Gorín, D. Grimson, R. Beklemishev L.D. Queiroz R. 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.
format	SER
author	Figueira, S. Gorín, D. Grimson, R. Beklemishev L.D. Queiroz R.
author_facet	Figueira, S. Gorín, D. Grimson, R. Beklemishev L.D. Queiroz R.
author_sort	Figueira, S.
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
url	http://hdl.handle.net/20.500.12110/paper_03029743_v6642LNAI_n_p135_Figueira
work_keys_str_mv	AT figueiras ontheexpressivepowerofiflogicwithclassicalnegation AT gorind ontheexpressivepowerofiflogicwithclassicalnegation AT grimsonr ontheexpressivepowerofiflogicwithclassicalnegation AT beklemishevld ontheexpressivepowerofiflogicwithclassicalnegation AT queirozr ontheexpressivepowerofiflogicwithclassicalnegation
_version_	1807324537923043328

On the expressive power of IF-logic with classical negation

Ejemplares similares