منطق محمولات: نظریه‌های مرتبه اول
منطق و فرامنطق
درآمد به منطق
منطق محمولات:
نظریه‌های مرتبه اول
۱- مقدمه | ۵- قواعد استنتاج |
۲- تئوری‌های مرتبه اول | ۶- تعریف: مدل تئوری |
۳- بنداشت‌های منطقی | ۷- برخی توضیح برای بنداشت‌های (A۴) و (A۵) |
۴- بنداشت‌های سره / حساب محمول‌ها | ۸- نمونه‌های تئوری‌های مرتبه اول |
مگر در مواردی که با نماد "" مشخص شده باشد، محتوای ارائه شده در این یادداشت از مرجع زیر برگرفته و برگردان شده است.
Mendelson, Elliott. Introduction to mathematical logic. 6th, ed, CRC Press, Taylor & Francis Group. 2015. p. ۶۶-۶۹. ↜
■ مقدمه
در دو یادداشت (منطق محمولات: زبان، تعبیر و مدل ۱ و ۲) منطق محمولات را با رویکرد معنایی↝ (تعبیر / مدل) مرور کردیم. در این یادداشت و چند یادداشت بعد به منطق محمولات مرتبه اول با رویکرد برهانی می‌پردازیم و استواری و تمامیت محمولات مرتبه اول را نشان می‌دهیم.
■ (۲.۳) تئوری‌های مرتبه اول
در مورد حساب گزاره‌ای، روش جدول ارزش یک آزمون کارآمد برای تعیین توتولوژی بودن یک صورت گزاره‌ای ارائه شده است. اما، به نظر نمی‌آید که هیچ روند کارآمدی↝ برای تعیین اعتبار منطقی یک wff وجود داشته باشد، چرا که، به طور کلی، باید صدق‌پذیری یک wff را برای تعبیرهای با دامنه‌های↝↝ متناهی یا نامتناهی دلخواه بررسی کرد. در واقع، بعداً خواهیم دید که طبق تعریف قابل قبولی از «کارآمدی» می‌توان ثابت کرد که روندی کارآمد برای آزمون اعتبار منطقی وجود ندارد. بنابراین، رویکرد بنداشتی (اصل موضوعی)، که در حساب گزاره‌ها تشریفاتی به نظر می‌آید، در آزمون اعتبار منطقی wff هایی که شامل کمی‌سازها* (سور - سور عمومی - سور وجودی) هستند، یک ضرورت است. بنابراین اکنون به بررسی تئوری‌های مرتبه اول می‌پردازیم.
* دلیل دیگری نیز برای رویکرد بنداشتی صوری وجود دارد. مفاهیم و گزاره‌هایی که درگیر با انگاشت تعبیر و ایده‌های مرتبط مانند صدق و مدل هستند، اغلب معنایی (semantical) نامیده می‌شوند تا آنها را از مفاهیم نحوی (syntactical) متمایز کنند، که به روابط ساده میان نمادها و عبارات زبان‌‌های صوری دقیق اشاره دارد. از آنجایی که مفاهیم معنایی سرشت نظری-مجموعه‌ای (set-theoretic) دارند و از آنجایی که نظریه مجموعه‌ها، به دلیل پارادوکس‌ها، پایه‌ای نسبتاً متزلزل برای مطالعه منطق ریاضی در نظر گرفته می‌شود، بسیاری از منطق دانان یک رویکرد نحوی را که شامل مطالعه تئوری‌های بنداشتی صوری با استفاده از روش‌های ضعیف نظریه اعداد است، بسیار ایمن‌تر می دانند.⮫
برای بحث بیشتر، به پیشگام در معناشناسی تارسکی،
. Tarski, A. (1936) Der Wahrheitsbegriff in den formalisierten Sprachen. Stud. Philos., 1, 261–405 (English translation in Tarski, 1956).
و همچنین منابع زیر رجوع کنید:
. Kleene, S.C. (1952) Introduction to Metamathematics. Van Nostrand.
. Church, A. (1956) Introduction to Mathematical Logic. I. Princeton University Press.
. Hilbert, D. and P. Bernays (1934, 1939) Grundlagen der Mathematik, Vol. I (1934), Vol. II (1939). Springer (second edition, 1968, 1970).
فرض کنید ℒ یک زبان مرتبه اول باشد. یک تئوری مرتبه اول در زبان ℒ، یک نظریه صوری K است که نمادها و wfs های آن نمادها و wfs های ℒ هستند و بنداشت(ها) و قواعد استنتاج آن به صورت زیر مشخص می‌شوند.†⮫
† خواننده ممکن است بخواهد تعریف نظریه صوری را در بخش ۱.۴ مرور کند. ما از اصطلاحات (برهان، قضیه، نتیجه، اصول موضوع، ⊢ B، و غیره) و نماد (Γ ⊢ B، ⊢ B) که در آنجا معرفی شده است استفاده خواهیم کرد.
بنداشت‌های K به دو دسته تقسیم می‌شوند. : بنداشت‌های منطقی (Logical Axioms) و بنداشت‌های سره (Proper Axioms) [ یا بنداشت‌های غیرمنطقی].
■ (۲.۳.۱) بنداشت‌های منطقی
اگر β ،α و ς فرمول‌های ℒ باشند آنگاه (A۱) تا (A۵) در زیر بنداشت‌های منطقی (اصول موضوعه / Axioms) نظریه K هستند.
(A۱) `α ⇒ (β ⇒ α)`
(A۲) `((α ⇒ (β ⇒ ς)) ⇒ ((α ⇒ β) ⇒ (α ⇒ ς))`
(A۳) `(¬α ⇒ ¬β) ⇒ ((¬α ⇒ β) ⇒ α)`
(A۴) `(∀x_i)β(x_i)⇒β(t)`
در (A۴) `β(x_i)` فرمول ℒ و `t` ترم ℒ است و افزون بر این `t` در `β(x_i)` برای `x_i` آزاد است. [آزادی ترم برای متغییر۱ - آزادی ترم برای متغیر۲]
☜: توجه داشته باشید که `t` می‌تواند `x_i` باشد↝↝ و بنابراین به موجب بنداشت (A۴) همه فرمول‌های:
`(∀x_i)β(x_i)⇒β`
بنداشت هستند. [اینجا را ببینید.]
(A۵) `(∀x_i)((β⇒ς))⇒(β⇒(∀x_i)ς)`
به شرط آنکه `β` شامل رویداد آزاد `x_i` نباشد.
■ (۲.۳.۲) بنداشت‌های سره / حساب محمول‌ها
این گونه بنداشت‌ها را نمی‌توان مشخص کرد، زیرا از یک تئوری به تئوری دیگر متفاوت هستند [: پایین‌تر دو نمونه از این گونه تئوری‌ها را خواهیم دید]. به یک تئوری مرتبه اول که در آن بنداشت سره وجود ندارد، حساب محمولات مرتبه اول (First-order predicate calculus) گفته می‌شود.
■ (۲.۳.۳) قواعد استنتاج ↝، ↝، ↝
واعد استنتاج هر تئوری مرتبه اول به قرار زیر است:
۱- قیاس استثنایی (Modus ponens): `ς` از `β` و `β⇒ς` بدست می‌آید. (↝ - ↝) [با کوته‌نوشت: MP]
`β` , `β⇒ς`
———————————
`ς`
۲- تعمیم (Generalization): `(∀x_i)β` از `β` بدست می‌آید. (↝) [با کوته‌نوشت: Gen]
`β`
———————————
`(∀x_i)β`
[توجه: به `x_i` در قاعده تعمیم متغیر سوردار شده گفته می‌شود.]
برای نشان دادن کاربرد این دو قاعده به ترتیب از کوته نوشت‌های MP و Gen استفاده خواهیم کرد.
■ (۶۷.۳) تعریف: مدل تئوری
فرض کنید K یک تئوری مرتبه اول در زبان ℒ باشد. منظور ما از مدل K تعبیری از ℒ است که تمام بنداشت‌های K در آن تعبیر درست باشند.
از بند III و VI در صفحه ۵۷ می‌دانیم که، اگر قواعد قیاس استثنایی و تعمیم در مورد فرمول‌هایی که برای یک تعبیر معین درست است به کار برده شود، نتایج این کاربردها نیز درست هستند. بنابراین هر قضیه↝ K برای هر مدل K درست است.
همانطور که خواهیم دید، بنداشت‌های منطقی به گونه‌ای وضع شده‌اند که نتایج منطقی (به معنایی که در صفحه‌های ۶۳-۶۴ شرح داده شده است) بستار بنداشت‌های K دقیقاً قضایای K باشند. به ویژه، اگر K یک حساب محمول‌های مرتبه اول باشد، خواهیم دید که قضایای↝ K فقط آن فرمول‌های K هستند که منطقاً معتبر هستند.
■ (۶۷.۵) برخی توضیح برای بنداشت‌های (A۴) و (A۵)
برخی توضیح برای محدودیت‌های موجود در طرحواره‌های بنداشتی (A۴) و (A۵) نیاز است.
در مورد (A۴)، اگر `t` برای `x_i` در `β(x_i)` آزاد نباشد، نتیجه ناخوشایند زیر به وجود می‌آید: فرض کنید
`β(x_۱)`↝ به قرار `¬(∀ x_۲ )α_۱^۲ (x_۱ , x_۲ )`
و `t` به قرار `x_۲` باشد. توجه داشته باشید که `t` برای `x_۱` در `β(x_۱)` آزاد نیست [↝ - ↝]. مورد (pseudo-instance) زیر از (A۴) را در نظر بگیرید:
(▽): `(∀x_۱)(¬(∀x_۲)α_۱^۲(x_۱,x_۲))⇒¬(∀x_۲)α_۱^۲(x_۲,x_۲)`
اکنون (هر) دامنه‌ای با حداقل دو عضو را به عنوان دامنه تعبیر و `α_۱^۲` را رابطه اینهمانی در نظر بگیرید. در این صورت برای این تعبیر مقدم (▽) درست و تالی آن نادرست است. بنابراین، (▽) برای این تعبیر نادرست خواهد بود.
در مورد بنداشت (A۵)، ندیدن محدودیت مبنی بر آزاد نبودن `x_i` در `β` منجر به پیامد ناگوار زیر می‌شود. فرض کنید `β` و `ς` هر دو `A_۱^۱(x_۱)` باشند. بنابراین، `x_۱` در `β` آزاد است. مورد (pseudo-instance) زیر از (A۵) را در نظر بگیرید:
(▽▽): `(∀x_۱)(α_۱^۱(x_۱)⇒α_۱^۱ (x_۱))⇒`
`⇒((α_۱^۱) (x_۱)⇒(∀x_۱)α_۱^۱(x_۱))`
مقدم (▽▽) منطقاً معتبر است. اکنون دامنه را مجموعه اعداد صحیح و تعبیر `(∀x_۱)α_۱^۱(x_۱)` را زوج بود `x` بگیرید.
در این صورت `(∀x_۱)α_۱^۱(x_۱)` نادرست است. بنابراین، هر دنباله `s=(s_۱, s_۲, ...)` که در آن `s_i` زوج باشد تالی (▽▽) را برنمی‌آورد*. از اینجا (▽▽) برای این تعبیر درست نیست.
[*] چنین دنباله‌ای، از آنجاکه `s_۱` زوج است `α_۱^۱(x_۱)` را برمی‌آورد، اما `(∀x_۱)α_۱^۱(x_۱)` را برنخواهد آورد، زیرا هیچ دنباله‌ای `(∀x_۱)α_۱^۱(x_۱)` را بر نمی‌آورد.
■ نمونه‌های تئوری‌های مرتبه اول
| ۱. | ترتیب جزئی:↝ فرض کنید زبان ℒ فقط دارای یک حرف محمولی `A_۲^۲` و بدوت حرف تابعی و ثابت انفرادی باشد. به جای `A_۲^۲(x_i,x_j) ` می‌نویسیم `x_i<x_j`. تئوری K دارای بنداشت‌های سره زیر است: | ||
| پادمتقارن | `(∀x_۱)(¬x_۱<x_۱)` | .a | |
| ترایایی | `(∀x_۱)(∀x_۲)(∀x_۳)` `(x_۱<x_۲∧x_۲<x_۳⇒x_۱<x_۳)` | .b | |
| ۲. | تئوری گروه: فرض کنید زبان ℒ فقط دارای یک حرف محمولی `A_۱^۲`، یک حرف تابعی `f_۱^۲` و یک ثابت انفرادی `a_۱` باشد. برای مطابقت با نماد گذاری معمول `t=s` را بجای `A_۱^۲(t,s)`، `t+s` را بجای `f_۱^۲(t,s)` و ۰ را بجای `a_۱` می‌نویسیم. بنداشت‌های سره تئوری K از قرار زیر است: | ||
| انجمنی | `(∀x_۱)(∀x_۲)(∀x_۳)``(x_۱+(x_۲+x_۳)=``(x_۱+x_۲)+x_۳)` | a. | |
| یگانگی | `(∀x_۱)(۰+x_۱=x_۱)` | b. | |
| وارون | `(∀x_۱)(∃x_۲)(x_۲+x_۱=۰)` | c. | |
| بازتابی(=) | `(∀x_۱)(x_۱=x_۱)` | d. | |
| تقارن(=) | `(∀x_۱)(∀x_۲)``(x_۱=x_۲⇒x_۲=x_۱)` | e. | |
| ترایایی(=) | `(∀x_۱)(∀x_۲)(∀x_۳)=``(x_۱=x_۲∧x_۲=x_۳⇒``x_۱=x_۳)` | f. | |
| جانشینی(=) | `(∀x_۱)(∀x_۲)(∀x_۳)``(x_۲=x_۳⇒x_۱+x_۲` `=x_۱+x_۳∧x_۲+x_۱=``x_۳+x_۱)` | g. | |
مدلی از این تئوری که در آن تعبیر نماد = اینهمانی باشد گروه نامیده می‌شود. به یک گروه آبلی (abelian) گفته می‌شود اگر فرمول:
`(∀x_۱) (∀x_۲)(x_۱+x_۲=x_۲+x_۱)`
درست باشد.
تئوری‌های ترتیب جزئی و گروه‌ها هر دو بنداشتی هستند. به طور کلی، هر تئوری با تعداد متناهی بنداشت سره بنداشتی است، زیرا آشکار است که می‌توان به طور کارآمد تصمیم گرفت که آیا هر فرمول داده شده یک بنداشت منطقی است یا نه.↝
