کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
430237 687934 2014 17 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Independence friendly logic with classical negation via flattening is a second-order logic with weak dependencies
ترجمه فارسی عنوان
منطق دوستی استقلال با نفی کلاسیک از طریق مسطح کردن، یک منطق مرتبه دوم با وابستگی های ضعیف است
کلمات کلیدی
منطق اطلاعات نامناسب، منطق دوستانه استقلال، قدرت بیانگر منطق مرتبه دوم، اپراتور مسطح
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی


• 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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 80, Issue 6, September 2014, Pages 1102–1118
نویسندگان
, , ,