کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430237 | 687934 | 2014 | 17 صفحه PDF | دانلود رایگان |
• We study Independence Friendly logic extended with Hodge's flattening operator.
• We prove that this logic corresponds to a weak syntactic fragment of second order.
• We prove that this logic is equivalent to the logic of Henkin quantifiers.
• We argue that Hodge's notion of negation is adequate.
It is well-known that Independence Friendly (IF) logic is equivalent to existential second-order logic (Σ11) 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 Δ21. In this article we consider SL(↓)SL(↓), IF-logic extended with Hodges' flattening operator ↓, which allows to define a classical negation. SL(↓)SL(↓) contains Extended IF-logic and hence it is at least as expressive as the Boolean closure of Σ11. We prove that SL(↓)SL(↓) corresponds to a weak syntactic fragment of SO which we show to be strictly contained in Δ21. The separation is derived almost trivially from the fact that Σn1 defines its own truth-predicate. We finally show that SL(↓)SL(↓) is equivalent to the logic of Henkin quantifiers, which shows, we argue, that Hodges' notion of negation is adequate.
Journal: Journal of Computer and System Sciences - Volume 80, Issue 6, September 2014, Pages 1102–1118