صورت‌های نرمال پرنکس و اسکولم

منطق محمولات و نظریه مدل

درآمد به منطق و رایانش

روند صورت‌های نرمال پرنکس و اسکولم - (Prenex and Skolem Normal Forms)

توجه: جز در مواردی که با نماد "توجه:" مشخص شده‌اند، محتوای یادداشت برگرفته و ترجمه شده از منبع زیر است.

Mendelson, Elliott. Introduction to mathematical logic. 6th, ed, CRC Press, Taylor & Francis Group. 2015; §2.10;. Pg 105-110.


۱- مراد از مجموعه شمارا (Denumerable Set) یک مجموعه شمارای نامتناهی است مگر آنکه صراحتاً خلاف آن ذکر شده باشد.

۲- در این بخش، برای خوانایی بیشتر، به جای فونت دست‌نویس (`ccA, ccB, ccC, ...`) از فونت (`ttA, ttB, ttC, ...`) برای نشان دادن فرمول‌ها استفاده می‌کنیم. این نمادها نشان‌دهنده فرمول خوش-ساخت به طور کلی هستند، نه حروف محمولی.

توجه: پیش‌درآمد به صورت‌های پرنکس (Prenex) و اسکولوم (Skolem)

در حساب محمولات، یک فرمول می‌تواند هم‌ارز با بی‌شمار صورت نحوی دیگر باشد. سورها درون زیرفرمول‌ها جای می‌گیرند و از دیده پنهان شوند. نقیض‌ها روی هم انبار شوند و پیوندها در هر عمقی قرار گیرند. این گوناگونی ویژگی زبان، چه زبان صوری و چه طبیعی، است. اما این ویژگی برای تحلیل ساختاری و برهان‌آوری بس دشواری می‌آورد. صورت‌های نرمال فرمول‌ها را به ساخت مشترک می‌برند. به ویژه در منطق محمولات فرمول‌ها را به جایی می‌برند که در آن ساختار سورها شفاف است و بدنه بدون ‌سور در دسترس است. این روند در متون منطق با دو رویکرد انجام میشود:

  1. در این رویکرد که در این قسمت خواهیم دید هدف تحلیل مسئله تصمیم‌پذیری و در نهایت قضیه‌های ناتمامیت گدل است. این هدف در کتاب مندلسون در بستری موجز و صوری برآورده شده است. در این مسیر، کمینه نگه داشتن زبان (همانطور که خواهیم دید، بدون حرف تابعی و ثابت انفرادی) دارای ارزش اثباتی است.
  2. از دیگر سو، در متون منطق و رایانش هدف بسیار متفاوت است و بر اثبات خودکار قضیه (Automated Theorem Proving) تمرکز دارد. در این رویکرد، زبان با آنچه توابع اسکولم نامیده می‌شود گسترش می‌یابد تا سورهای وجودی به کلی حذف شوند و مسیر به سوی قاعده واگشایی (Resolution rule) و برهان خودکار قضیه (Automated Theorem Proving) هموار گردد.

گام‌ بنیادین برای نرمال  سازی فرمول بازآرایی آن به «صورت نرمال پرنکس» (Prenex Normal Form) است. در این ساخت، همه سورها (عمومی `AA` و وجودی `EE`) به ابتدای فرمول منتقل می‌شوند و بخش بدون‌سور، به‌صورت یک فرمول گزاره‌ای درمی‌آید. به عبارت دیگر، هر فرمول خوش‌ساخت را می‌توان به صورت زیر برگردان کرد:

`Q_۱x_۱ Q_۲​ x_۲ ​ ⋯ Q_nx_n​ tt"A"`

که در آن هر `Q_i` یا `AA` یا `EE` است و `tt"A"` صورت بدون سور است.

برای مثال:

`\AA x \EE y``\ (P(x) \ vee Q(y))`

یک صورت پرنکس است، حال آن‌که:

`AAx ``(``P(x)^^``EEx` `Q(y)``)`

یک صورت پرنکس نیست، زیرا سور در میانه فرمول قرار دارد.

هر صورت نرمال پرنکس دارای دو بخش متمایز است:

  1. پیشوند (Prefix): بخش آغازین که فقط از سورها (`EE`) یا (`AA`) همراه با متغیرهای آنها تشکیل شده است. یعنی `Q_۱x_۱ Q_۲​ x_۲ ​ ⋯ Q_nx_n`.
  2. ماتریس (Matrix): بخش نهایی فرمول، یعنی بدنه یا هسته آن - که پس از پیشوند می‌آید و دارای هیچ سوری نیست. یعنی `tt"A"` در `Q_۱x_۱ Q_۲​ x_۲ ​ ⋯ Q_nx_n​ tt"A"`.

در ادامه این قسمت (قضیه ۲.۳۰) نشان داده خواهد شد که الگوریتمی برای برگردان هر فرمول به فرمولی منطقاً هم‌ارز به صورت نرمال پرنکس وجود دارد.

در گام بعدی نیاز است تا فرمول‌های درآمده به صورت نرمال پرنکس را به صورت نرمال اسکولم درآورد.

منظور از صورت نرمال اسکولم فرمولی است که:

  1. به صورت نرمال پرنکس باشد،
  2. همه سورهای وجودی (در صورت وجود) قبل از همه سورهای عمومی (در صورت وجود) قرار گرفته باشند.

در ادامه در قضیه ۲.۳۱ نشان داده خواهد شد که با معرفی حروف محمولی کمکی، الگوریتمی برای برگردان هر فرمول `tt"A"` به فرمولی به صورت نرمال اسکولم، `tt"S"`، وجود دارد، به قسمی که `tt"A"` و `tt"S"` هم-اثبات‌پذیر (Equi-provable) باشند.

مثال ۱. گیریم:

`tt"A" = AAx(F(x)=>EEyL(x,y))) ^^ EEz¬F(z)`

فرض می‌کنیم دامنه سخن انسان‌ها، تعبیر `F` دوست و تعبیر ‍`L` دوست بودن باشد.

تعبیر `tt"A"`: هر دوست کسی را دوست دارد، و کسی هست که دوست نیست:

صورت پرنکس:

`tt"P":``EEzAAxEEy[(F(x)=>L(x,y))∧¬F(z)]`

صورت اسکولم:

`tt"S":``EEzEEyAAx[(F(x)=>L(x,y))∧¬F(z)]`

تعبیر `tt"S"`: یکی که دوست نیست `(z)`، یکی هم `(y)` هست که هر دوستی او را دوست دارد.

در این مثال:

فرمول `tt"P"` صورت پرنکس فرمول `tt"A"` است و داریم (قضیه ۲.۳۰): `|--tt"A" <=>tt"P"`.

فرمول `tt"S"` صورت اسکولم فرمول `tt"P"` است و داریم (قضیه ۲.۳۱): `|--tt"P" <=> |--tt"S"`. بنابراین:

`|--tt"A" <=> |--tt"S"`


توجه: هم-اثبات‌پذیری (Equi-Provability) و هم-صدق‌پذیری (Equi-Satisfiability)

تعریف. هم-اثبات‌پذیری: دو فرمول `ttA` و `ttB` را هم-اثبات‌پذیر (Equi-Provable) گوییم اگر و تنها اگر اثبات‌پذیری یکی اثبات‌پذیری دیگری را نیز به دنبال داشته باشد. یعنی:

`vdash ttA iff vdash ttB`.

این یک گزاره فرامنطقی درباره وجود برهان است. این گزاره نمی‌گوید که `ttA` و `ttB` هم‌ارز منطقی هستند، دارای مدل‌های یکسان هستند با حتی به یک زبان تعلق دارند. فقط می‌گوید: یکی یک قضیه است اگر و تنها اگر دیگری هم قضیه باشد.

مثال ۱:

فرض کنید `tt"A" = p` و `tt"B" = q`، که در آن `p` و `q` متغیرهای گزاره‌ای متمایزند. هیچ‌یک توتولوژی نیستند، و از اینجا هیچ‌یک اثبات‌پذیر نیستند. بنابراین `|--tt"A" <=> |--tt"B"` برقرار است (هر دو طرف نادرست)، اما `⊬ (tt"A" <=> tt"B")`. آن‌ها هم-اثبات‌پذیر هستند اما منطقاً هم‌ارز نیستند.

مثال ۲:

فرض کنید:

`tt"A" = (AAx)P(x) => (EEy)Q(y)`

و

`tt"B" = (EEx)(∃y)(P(x) => Q(y))` باشد.

`tt"B"` صورت پرنکس `tt"A"` است و بنا بر قضیه ۲.۳۱ داریم

`⊢(A ↔ B)`.

بنابراین آنها هم-اثبات‌پذیر، نیز منطقاً هم‌ارز هستند.

مثال ۳:

فرض کنید:

`tt"A" = (EEy)(AAu)tt"C"(y,u)`.

در برگردانی به صورت نرمال اسکولم، نماد جدید `P` معرفی می‌شود:

`tt"S"=(EEy)[(AAu)(tt"C"(y,u)=>P(y,u))=>(AAu)P(y,u)]`,

که داریم:

`|-- tt"A" <=> |-- tt"S"`.

این فرمول‌ها هم-اثبات‌پذیرند، اما در `tt"S"` نمادی است که در `tt"A"` نیست، بنابراین نمی‌توانند منطقاً هم‌ارز باشند.

مثال ۴:

فرض کنید `tt"A" = p` و `tt"B" = q`، که در آن `p` و `q` متغیرهای گزاره‌ای متمایزند. هیچ‌یک توتولوژی نیستند، و از اینجا هیچ‌کدام اثبات‌پذیر نیستند. بنابراین `|--tt"A" <=> |--tt"B"` برقرار است (هر دو طرف نادرست)، اما `⊬ (tt"A" <=> tt"B")`. آن‌ها هم-اثبات‌پذیر هستند اما منطقاً هم‌ارز نیستند.

توجه: هم-اثبات‌‌پذیری و هم‌ارزی منطقی

اگر `ttA` و `ttB` منطقاً هم‌ارز باشند آنگاه هم-‌اثبات‌پذیر هم هستند. یعنی:

`vdash(ttA <=> ttB) => (vdash ttA <=> vdash ttA)`.

اما وارون آن الزاماً برقرار نیست. یعنی وقتی `vdash ttA <=> ttB ` داریم:

  • `ttA iff ttB` خودش اثبات‌پذیر است.

  • فرض کنید `tt"A" = P(c)` و `tt"B" = (EEx)P(x)` باشد. در این‌صورت، اگر `|-- P(c)`، آنگاه `|-- (EEx)P(x)`، اما وارون آن برقرار نیست. از این رو، آنها هم-اثبات‌پذیر نیستند.

چند نکته:

  • مفهوم هم-اثبات‌پذیری از بنیاد نحوی است.

  • هم-اثبات‌پذیری سازگاری را حفظ می‌کند. یعنی، `|-- A <=> |-- B` نتیجه می‌دهد که A سازگار است اگر B سازگار باشد.

  • وقتی `ttA` و `ttB` اثبات‌پذیری یکسان دارند: برای یافتن برهان `ttA`، کافی است یک `ttB` هم-اثبات‌پذیر با `ttA` را در یک صورت آسان‌تر ساخت و برای آن برهان بسازیم.

  • معمولا برای ساختن برهان برای `ttB` وقتی `ttA` و `ttB` هم-اثبات‌پذیراند نیاز به معرفی نمادها (حروف محمولی جدید) است. اضافه کردن این نمادهای جدید پایستار هستند (بسط پایستار تئوری) - هیچ قضیه جدیدی در دستگاه اصلی ایجاد نمی‌شود.

توجه: هم-صدق‌پذیری (Equi-Satisfiability)

تعریف. هم-صدق‌پذیر: دو فرمول `ttA` و `ttB` را هم-صدق‌پذیر (Equi-satisfiable) گوییم اگر و تنها اگر `ttA` دارای مدل باشد، `ttB` نیز دارای مدل باشد.

به عبارت دیگر `ttA` و `ttB` هم-صدق‌پذیرند اگر و تنها اگر:

`text{Mod}(A) ne \emptyset \iff \text{Mod}(B) \ne \emptyset`

که در آن `text{Mod}(A)` و `text{Mod}(B)` به ترتیب کلاس‌های مدل‌های `A` و `B` هستند

مفهوم هم-صدق‌پذیری ماهیتی معنایی و مدل ‌محور دارد. یعنی هر دو فرمول در دست‌کم یک مدل درست‌اند، در حالی‌ که هم-اثبات‌پذیری مفهومی نحوی و استنتاجی است.


■ ۲.۱۰ صورت‌های نرمال پرنکس (Prenex Normal Form) [با کوتاه‌نویسی PNF]

گوییم فرمول `(Q_1y_1) … (Q_ny_n) tt"B"`، [که در آن هر `(Q_iy_i)` یا `(AAy_i)` یا `(EEy_i)` است و `y_i` برای `i ≠ j` با `y_j` متفاوت است و `B` شامل هیچ سوری نیست] به صورت نرمال پرنکس است. (حالت `n = 0` را برای وقتی نظر می‌گیریم که هیچ سوری وجود نداشته باشد). نشان خواهیم‌داد که برای هر فرمول، می‌توانیم یک صورت نرمال پرنکس هم‌ارز بسازیم.

برای مثال دو فرمول زیر در PNF هستند.

۱. `exists x \, \forall y \, \exists z \, ( P(x, y) => Q(y, z) `

۲. `\forall x \, \exists y \, \forall z \, \exists w \, \forall u \ ``( R(x, y, z) \ ^^ \neg S(w, u) )`


■ ۲.۲۹ لم: برخی روابط بین سورها سور‌ها.

در هر تئوری، اگر `y` در `tt"D"` آزاد نباشد، و `tt"C"(x)` و `tt"C"(y)` یک‌جور باشند، آنگاه رابطه‌های زیر برقرار است:

a. `⊢ ((AAx)tt"C" (x) => tt"D") <=> (EEy)(tt"C" (y) => tt"D")`

b. `⊢ ((EEx)tt"C" (x) => tt"D") <=> (AAy)(tt"C" (y) => tt"D")`

c. ⊢ `(tt"D" => (AAx)C (x)) <=>``(AAy)(tt"D" => tt"C" (y))`

d. `¬(tt"D" ⇒ (EEx)tt"C" (x)) ⇔ (EEy)(tt"D" ⇒ tt"C" (y))`

e. ⊢ `¬(AAx)tt"C" <=> (EEx) ¬tt"C"`

f. ⊢ `¬(EEx)tt"C" <=> (AAx) ¬tt"C"`

برهان (a):

فرض

۱. `(AAx)tt"C"(x)=>tt"D"`

فرض

۲. `¬(EEy)(tt"C"(y)=>tt"D")`

۲ و کوتاه نویسی

۳. `¬¬(AAy)¬(tt"C"(y)=>tt"D")`

۳ و حذف نقیض دوگانه

۴. `(AAy)¬(tt"C"(y)=>tt"D")`

۴، توتولوژی و قضیه ۲.۹.c

۵. `(AAy)(tt"C"(y)^^¬tt"D")`

۵ و قاعده A۴

۶. `tt"C"(y)^^¬tt"D"`

۶ و حذف عطفی

۷. `tt"C"(y)`

۷ و تعمیم

۸. `(AAy)tt"C"(y)`

۸، لم و حذف دو شرطی

۹. `(AAx)tt"C"(x)`

۱، ۹ و MP

۱۰. `tt"D"`

۶ و حذف عطفی

۱۱. `¬tt"D"`

۱۰، ۱۱ و حذف عطفی

۱۲. `tt"D"^^¬tt"D"`

۱ - ۱۲

۱۳. `(AAx)tt"C"(x)=>tt"D"`,
`¬(EEy)(tt"C"(y)=>tt"D")⊢tt"D"^^¬tt"D"`

۱-۱۳ و برهان از روش تناقض

۱۴. `(AAx)tt"C"(x)=>tt"D"`
`⊢(EEy)(tt"C"(y)=>tt"D")`

۱ - ۱۴ و نتیجه ۲.۶

۱۵. `⊢(AAx)tt"C"(x)=>`
`tt"D"=>(EEy)(tt"C"(y)=>tt"D")`

وارون به شیوه زیر اثبات می‌شود

فرض

۱. `(EEy)(tt"C" (y) => tt"D")`

فرض

۲. `(AAx)tt"C" (x)`

۱ و قاعده C ۳. `tt"C" (b) => tt"D"`
۲ و قاعده A۴ ۴. `tt"C" (b)`
۳ و ۴ و MP ۵. `tt"D"`
۱ - ۵ ۶. `(EEy)(tt"C" (y) => tt"D"), (AAx)tt"C" (x) |--``tt"C"`
۶ و قضیه ۲.۱۰ ۷. `(EEy)(tt"C" (y) => tt"D"), (AAx)tt"C" (x) |-- tt"D"`
۱ - ۷ و دوبار نتیجه ۲.۶ ۸. `|-- (EEy)(tt"C" (y) => tt"D") =>`` ((AAx)tt"C" (x) => tt"D")`


(a) از دو برهان بالا با مقدمه دو شرطی نتیجه می‌شود. (b) تا (f) به راحتی اثبات می‌شوند و به عنوان تمرین باقی می‌مانند. ((f) بدیهی است و (e) از تمرین (a) ۲.۳۳ نتیجه می‌شود؛ (c) و (d) به ترتیب از (b) و (a) نتیجه می‌شوند.)

لم ۲.۲۹ امکان انتقال سورهای درونی به ابتدای یک فرمول را فراهم می‌کند. این فرایند برای برهان قضیه زیر ضروری است.


■ قضیه ۲.۳۰: وجود الگوریتم تبدیل فرمول به صورت پرنکس

یک روند کارآمد (الگوریتم) برای تبدیل هر فرمول `tt"B"` به فرمول `tt"C"` به صورت نرمال پرنکس وجود دارد به قسمی که `|-- tt"B" <=> tt"C"`.

برهان:

ما با استقرا روی تعداد `k` رابط و سور در `B` پیش می‌رویم. طبق تمرین ۲.۳۲ (a,b)، می‌توانیم فرض کنیم که متغیرهای سوردار در پیشوند حاصل متمایز هستند. اگر `k = 0` باشد، فرض کنید `C = B`.

اکنون فرض کنید که برای هر فرمول خوش‌ساخت با کمتر از `n` تکرار رابط و سور، یک `C"` متناظر وجود دارد و `B` دارای `n` تکرار از این نوع است.

حالت ۱.

فرض کنید `\(B\)` در صورت `\(\neg D\)` باشد. طبق فرض استقرا، یک فرمول `\(E\)` به صورت نرمال پرنکس وجود دارد به قسمی که `\(\vdash D \Leftrightarrow E\)`. با نقیض دوشرطی، `\(\vdash \neg D \Leftrightarrow \neg E\)`، بنابراین `\(\vdash B \Leftrightarrow \neg E\)`.

با اعمال بند‌های (e) و (f) از لم ۲.۲۹ و قضیه جایگزینی (قضیه ۲.۹-b)، یک فرمول خوش-ساخت `\(C\)` به صورت نرمال پرنکس به دست می‌آوریم به قسمی که `\(\vdash \neg E \Leftrightarrow C\)`. بنابراین، `\(\vdash B \Leftrightarrow C\)`.

حالت ۲.

اگر `\(B\)` در صورت `\(D \Rightarrow E\)` باشد، آنگاه بنا بر فرض استقرا، می‌توان صورت‌های صورت‌های نرمال پرنکس `\(D_1\)` و `\(E_1\)` وجود دارند به قسمی که `\(\vdash D \Leftrightarrow D_1\)` و `\(\vdash E \Leftrightarrow E_1\)`.

از اینجا، با یک توتولوژی مناسب قیاس استثنایی `\(\vdash (D \Rightarrow E) \Leftrightarrow (D_1 \Rightarrow E_1)\)`، یعنی، `\(\vdash B \Leftrightarrow (D_1 \Rightarrow E_1)\)`.

اکنون با کارزدن بند‌های (a) تا (d) از لم ۲.۲۹ و قضیه جایگزینی (قضیه ۲.۹-b)، می‌توانیم سورها را در پیشوندهای `\(D_1\)` و `\(E_1\)` به جلو منتقل کنیم و فرمول `\(C\)` به صورت نرمال پرنکس به دست آوریم به قسمی که `\(\vdash B \Leftrightarrow C\)`.

حالت ۳.

اگر `B` در صورت `(AAx)D` باشد، آنگاه طبق فرض استقرا، فرمول `D_1` به صورت نرمال پرنکس وجود دارد به قسمی که `|-- D <=> D_1`.

از اینجا، بنا به Gen، لم ۲.۸ و MP `⊢ B ⇔ (AAx)D_1`.

اما `(AAx)D_1` به صورت نرمال پرنکس است. [پایان برهان]


■ مثال‌ها:

مثال ۱. `tt"B"` را فرمول (۱) زیر بگیرید:

۱. `(AA x)(A_1^1(x) => (AA y)(A_2^2(x, y) =>`` not (AA z)(A_3^2(y, z))))`

۲. پس از کارزدن بند (e):

`(AA x)(A_1^1(x) => (AA y)[A_2^2(x, y) =>`` (EE z) not A_3^2(y, z)])`

۳. پس از کارزدن بند (d):


`(AA x)(A_1^1(x) => (AA y)(EE u)[A_2^2(x, y) =>`` not A_3^2(y, u)])`

۴. پس از کارزدن بند (c):


`(AA x)(AA v)(A_1^1(x) => (EE u)[A_2^2(x, v) =>`` not A_3^2(v, u)])`

۵. پس از کارزدن بند (d):

`(AA x)(AA v)(EE w)(A_1^1(x) => (A_2^2(x, v) =>`` not A_3^2(v, w)))`

۶. تغییر متغیرهای پابند

`(AA x)(AA y)(EE z)(A_1^1(x) => (A_2^2(x, y) =>`` not A_3^2(y, z)))`


مثال ۲.

۱. `tt"B"`:: `A_1^2(x, y) => (EE y)[A_1^1(y) =>`` ((EE x) A_1^1(x) => A_2^1(y))]`

۲. پس از کارزدن بند (b):


`A_1^2(x, y) => (EE y)(A_1^1(y) => (AA u)[A_1^1(u) =>`` A_2^1(y)])`

۳. پس از کارزدن بند (c):

`A_1^2(x, y) => (EE y)(AA v)(A_1^1(y) => [A_1^1(v) =>`` A_2^1(y)])`

۴. پس از کارزدن بند (d):

`(EE w)(A_1^2(x, y) => (AA v)[A_1^1(w) => (A_1^1(v) =>`` A_2^1(w))])`

۵. پس از کارزدن بند (c):

`(EE w)(AA z)(A_1^2(x, y) => [A_1^1(w) => (A_1^1(z) =>`` A_2^1(w))])`


■ تمرین - ۲.۴۸

۲.۴۸ صورت نرمال پرنکس هم‌ارز با صورتول‌های زیر را بیابید.

a. `[(AA x)(A_1^1(x) =>`` A_1^2(x, y))] =>``([(EE y) A_1^1(y)] => (EE z) A_1^2(y, z))`
b. `(EE x) A_1^2(x, y) => (A_1^1(x) =>``not (EE u) A_1^2(x, u))`


■ حساب محمولات محض (Pure Predicate Calculus)

اگر در یک حساب محمولات هیچ حرف تابعی یا ثابت انفرادی وجود نداشته باشد و برای هر عدد صحیح مثبت `n`، نامحدود حرف محمولی `n` جایبانی وجود داشته باشد، آنگاه آن را حساب محمولات محض می‌نامند. از


■ صورت نرمال سکولم (Skolem Normal Form) [با کوتاه نویسی SNF]

به یک فرمول در حساب محمولات محض که به صورت نرمال پرنکس باشد یک فرمول به صورت نرمال سکولم (Skolem Normal Form) گفته می‌شود اگر همه سورهای وجودی (در صورت وجود) قبل از همه سورهای عمومی (در صورت وجود) قرار گیرند.

برای مثال دو فرمول زیر در SNF هستند.

1- `(\forall y) (\exists z) (P(c, y) => Q(y, z))`

2. `(\forall x) (\forall z) (\forall u) (R(x, u, z) \ ^^ \neg S(x, u) )`


توجه: ■ رتبه فرمول

رتبه فرمول (صورت نرمال پرنکس) `ttF` عبارت است از تعداد سورهای عمومی که قبل از سورهای وجودی در پیشوند قرار دارند.

برای مثال رتبه فرمول:

`[AA x EE y AA z EE w] (ttA)`

۳ است، زیرا `AA x`، در پیشوند، قبل از هر دو سور وجودی قرار دارد، نیز `(AA z)` قبل از `(EE w)` قرار دارد.

اگر رتبه `0` باشد، هیچ `(AA)` قبل از `(EE)` روی نمی‌دهد. بنابراین همه سورهای وجودی اول می‌آیند. برای نمونه:

`[EE x_1 cdots EE x_n AA y_1 cdots AA y_k] (ttA)`.

از این روی، هر فرمول به صورت نرمال پرنکس یک صورت نرمال اسکولم نیز است.

■ قضیه ۲.۳۱: وجود الگوریتم اسکولم‌سازی برای هر فرمول

در حساب محمولات محض، یک روند کارآمد وجود دارد که به هر فرمول `ttB`، فرمول دیگر `ttS` به صورت نرمال اسکولم را نظیر می‌کند، به قسمی که:

`|-- ttB` اگر و تنها اگر `|-- ttS` باشد. [به‌عبارت دیگر،

 `ttB` و `ttS` هم‌اثبات‌پذیر باشند.]

(یا به طور هم‌ارز، بنا بر قضیه تمامیت گودل، به قسمی که:

`ttB` منطقاً معتبر است اگر و تنها اگر `ttS` منطقاً معتبر باشد).

برهان:

در آغاز می‌توان فرض کرد `ttB` یک فرمول بسته است، زیرا یک فرمول اثبات‌پذیر است اگر و تنها اگر بستار آن اثبات‌شدنی باشد [Gen و (A۴)]. بنا به قضیه ۲.۳۰، نیز می‌توان فرض کرد `ttB` به صورت نرمال پرنکس است.

اکنون فرض کنید رتبه فرمول `ttB` برابر `r` باشد. [مراد از رتبه فرمول (صورت نرمال پرنکس) در اینجا عبارت است از تعداد سورهای عمومی در آن فرمول که قبل از سورهای وجودی قرار دارند.]

با استقرا روی رتبه، روند یافتن صورت‌های نرمال اسکولم را شرح خواهیم داد.

گام پایه استقرا: `(Rank = k > 0)`

آشکار است که وقتی رتبه 0 است، صورت نرمال اسکولم را از قبل داریم. یعنی: `\vdash ttB iff \vdash ttS`.

گام استقرایی: `(Rank = k > 0)`

فرض کنید می‌توانیم صورت‌های نرمال اسکولم را برای رتبه کوچکتر از `r` بسازیم، نیز فرض می‌کنیم `r` رتبه `ttB` باشد.

`ttB` را می‌توان به صورت زیر نوشت:

`ttB=(EEy_1) … (EEy_n) (AAu)ttC (y_1, …, y_n, u)`,

که در آن `ttC (y_1, …, y_n, u)` فقط `y_1, …, y_n, u` را به‌عنوان متغیرهای آزاد خود دارد. [و بقیه سورها اگر باشند در ادامه پیشوند فرمول آمده باشند.]

فرض کنید `A_j^(n+1)` اولین حرف محمولی `n + 1` جایبانی باشد که در `ttB` وجود ندارد.

اکنون فرمول `ttB_1` را مطابق زیر بسازید که در آن `bar y` کوتاه شده `y_1,\ldots,y_n` است:

img(ttB_1):

B1 Formula

`(ttB_1): `

`(\exists y_1)\cdots(\exists y_n)``[`` (\forall u)``(``ttC(\bar y,u) => ``A_j^(n+1)(\bar y,u)``)`` => (\forall u)A_j^(n+1)(\bar y,u)``]```

نشان می‌دهیم:

۱: `|-- ttB` اگر و تنها اگر `|-- ttB_1`

فرض می‌کنیم `|-- ttB_1`. [از آنجا که `ttB_1` را قضیه فرض کرده‌ایم، پس دارای برهان است.]

در برهان `ttB_1`، همه رویدادهای `A_j^(n+1)(z_1, …, z_n, w)` را با `ttC^(***)(z_1, …, z_n, w)` جایگزین کنید، آنگونه که `ttttC^(***)` از `ttC` با جایگزینی همه متغیرهای پابند که در برهان رویداد آزاد دارند با متغیرهای جدیدی که در برهان رخ نمی‌دهند، به دست می‌آید [تغییر متغیرهای پابند]. حاصل یک برهان برای

img

`(EE y_1) cdots (EE y_n) ( ( ( AA u ) ( ttC(\bar y, u) =>` `ttC^***(\bar y, u) ) ) => ( AA u ) ttC^***(\bar y, u) )`

است.

(`ttC^***` جایگزین `ttC` شده است تا کاربردهای بنداشت (A۴) همچنان کاربردهای همان بنداشت باقی بمانند.) اکنون، با تغییر مجدد متغیرهای پابند [به صورت اولیه]، خواهیم دید:

`(EE y_1) cdots (EE y_n) ( [ ( AA u ) (ttC(\bar y, u) =>``ttC(\bar y, u) ) ] => ( AA u )ttC(\bar y, u) )`

از آنجا که:

 `|-- (AA u)(ttC(bar y, u) =>ttC(\bar y, u) )`,

با استفاده از قضیه جایگزینی، خواهیم داشت:

`|-- (EE y_1) ... (EE y_n)(AA u)(ttC(\bar y, u) )`،

این یعنی، `|-- ttB`.

برعکس، فرض کنید که `|-- ttB`.

با استفاده از قاعده C، داریم:

`(AA u)(ttC(b_1, ..., b_n, u) )`.

اما، برای هر فرمول `ttD` و `ttE` داریم:

`|-- (AA u)ttD => ((AA u)( ttD=> ttE ) => (AA u) ttE )`.

(تمرین ۲.۲۷.a را ببینید).

ازاینجا:

`|--_ttC (AA u)``(``ttC(b_1, ..., b_n, u) =>`` A_j^(n+1)(b_1, ..., b_n, u)``)``=>` `(AA u) A_j^(n+1)(\bar y, u)`.

بنابراین، از قاعده E۴ داریم:

`|--_ttC (EE y_1) ... (EE y_n)``(``[ (AA u)``(ttC(b_1, ..., b_n, u) ) =>`` A_j^(n+1)(\bar y, u)``]`` => ``(AA u) A_j^(n+1)(\bar y, u)``)```,

یعنی، `|--_ttC ttB_1`. و بنابر قضیه ۲.۱۰، `|-- ttB_1`.

پس ثابت شد: `|-- ttB <=> |-- ttB_1`

یک صورت نرمال پرنکس از `ttB` دارای صورت `ttB_2` از قرار زیر است:

`ttB_2:``(EE y_1) ... (EE y_n)(EE u)(Q_1 z_1) ... (Q_s z_s)(AA v)ttC`,

که در آن `ttC` بدون سور (ماتریس) است و `(Q_1 z_1) ... (Q_s z_s)` پیشوند `ttC` است.

[در استخراج صورت نرمال پرنکس، ابتدا طبق لم ۲.۲۹، اولین `(AA u)` را بیرون می‌کشیم که به `(EE u)` تغییر می‌کند؛ سپس از اولین شرطی، سور‌های موجود در پیشوند `ttC` را استخراج می‌کنیم.

بنابه لم ۲.۲۹-(a,b) این کار سور‌های وجودی و عمومی را جابجا می‌کند، اما سپس دوباره این‌ها را از شرطی دوم در `ttB_1` بیرون می‌کشیم که پیشوند را به شکل اصلی خود برمی‌گرداند. سرانجام، از لم ۲.۲۹-(c)، دومین `(AA u)` را به پیشوند منتقل می‌کنیم و آن را به یک سور جدید `(AA v)` تغییر می‌دهیم.]

آشکارا، رتبه `ttB_2` یک واحد کمتر از رتبه `ttB` است و بنابر قضیه ۲.۳۰: `|-- ttB_1 <=> ttB_2`.

اما، `|-- ttB` اگر و تنها اگر `|-- ttB_1`. از این رو، `|-- ttB` اگر وتنها اگر `|-- ttB_2`. اکنون با توجه به فرض استقرا، می‌توانیم یک صورت نرمال اسکولم برای `ttB_2` پیدا کنیم که آن نیز یک صورت نرمال اسکولم برای `ttB` است. ■


توجه: ■ بازآرایی برهان قضیه ۲.۳۱

با توجه به کاربرد بنیادین قضیه ۲.۳۱ و از آنجا که برهان آن در کتاب مندلسون (که یک برهان ساختی است) به‌گونه‌ای موجز و فشرده بیان شده، در ادامه شرحی گام‌به‌گام بر آن ارائه می‌کنیم که دربردارنده آشکارتر الگوریتم گذار از صورت پرنکس به صورت اسکولم است.

صورت قضیه (۲.۳۱‍'):

گیریم `ttA` یک فرمول بسته به صورت نرمال پرنکس باشد. در این صورت، یک روند کارآمد وجود دارد که به `ttA` فرمول `ttS` را به صورت نرمال سکولم نظیر می‌کند به قسمی که:

`vdash ttS` اگر و تنها اگر `vdash ttA`.

برهان:

یک فرمول تنها فقط وقتی رتبه `0` دارد که پیشوند آن به صورت زیر باشد:

`[ (\exists x_1)\cdots(\exists x_m) (\forall z_1)\cdots(\forall z_n) \]`.

بنابراین هر فرمول با رتبه `0` از پیش در صورت SNF است.

با استقرا روی رتبه `ttA` نشان می‌دهیم که فرمول `ttS` که به صورت نرمال اسکولم است وجود دارد به قسمی که:

`\vdash ttA iff \vdash ttS`.

گام پایه:

اگر رتبه `ttA` برابر با `0` باشد، آنگاه `ttA` از قبل به صورت نرمال اسکولم است.

گام استقرایی: `(Rank = k > 0)`

فرض می‌کنیم قضیه برای همه فرمول‌های با رتبه کمتر از `k` برقرار است. نیز رتبه `ttA` برابر با `k>0` است. پس می‌توان نوشت:

`ttA=``(\exists y_1)\cdots(\exists y_n)(\forall u) ttC(y_1,\ldots ,y_n,u), `

که در آن `ttC` یک زیرفرمول است که خود می‌تواند هنوز شامل سور باشد. [در این حالت اولین بلوک سور عمومی نابجا (که موجب می‌شود `ttA` در SNF نباشد) را یافته و آن را جدا کرده و `ttA` را به شیوه زیر به صورت `ttA_1` در می‌آوریم.] برای این کار حرف محمولی جدید `(n+1)`-جایبانی `P` را انتخاب کنید که در فرمول `ttA` وجود نداشته باشد. اکنون فرمول `ttA_1` را مطابق زیر را می‌سازیم:

`ttA_1= ``(\exists y_1)\cdots(\exists y_n) \left[ (\forall u)``(``ttC(\bar y,u) => ``P(\bar y,u)``)`` => (\forall u)P(\bar y,u) \]`

که در آن `bar y` کوتاه شده `y_1,\ldots,y_n` است.

{برای شکستن رتبه سور، یک حرف محمولی کاملاً جدید `P` با شمارِ جایبان‌های `(n+1)` معرفی کرده که در `ttA` هرگز روی نداده باشد. از این حرف محمولی برای ساخت فرمول `ttA_1` که نقش واسط را خواهد داشت، استفاده می‌کنیم.}

{به `P(\bar y, u)` به عنوان یک متغیر موقت و خالی فکر کنید که قرار است رفتار `C(\bar y, u)` را کپی کند. به عبارت دیگر می‌گوید: "اگر `C` آنگاه `P`، پس اگر `C` برای هر `u` برقرار باشد، `P` نیز باید برای هر `u` برقرار باشد."}

اکنون به شیوه نحوی نشان خواهیم داد که:

`\vdash ttA\quad\ iff \quad\vdash ttA_1`.

آ. `vdash ttA_1` => `vdash ttA`:

از آنجاکه `vdash ttA_1` پس `ttA_1` یک قضیه است و دارای برهان است. در برهان `ttA_1` هر رویداد

`P(t_1,\ldots ,t_n,t)`

را با یک واریانت `C^{***}(t_1,\ldots,t_n,t)` از `C` جایگزین کنید. متغیرهای پابند در `C^***` به عنوان متغیرهای جدید انتخاب می‌شوند، بنابراین هیچ متغیری ربایش نمی‌شود.

{در واقع ما یک برهان صوری معتبر از `ttA_1` داریم و باید آن را به یک برهان معتبر از `ttA` تبدیل کنیم. از آنجا که `P` یک نماد کاملاً جدید و دلخواه بود، می‌توانیم بدون مسئله‌ای آن را با تعریف مورد نظر آن `C` جایگزین کنیم.}

روند جایگزینی

۱- یافتن: هر مورد رویداد `P(t_1, \ldots, t_n, t)` را در برهان `ttA_1` بیابید.

۲- تغییر نام: `C^{***}` را بسازید یعنی رونوشتی از `C` که در آن نام همه متغیرهای پابند داخلی به نام‌های جدید درآمده‌اند.

۳- جایگزینی: `P(t_1, \ldots, t_n, t)` را با `C^{***}(t_1, \ldots, t_n, t)` جایگزین کنید.

چرا واریانت `C^{***}` الزامی است؟ اگر `C` شامل سور‌های داخلی خود باشد (مثلاً `AA x`)، و یکی از ترم‌ها `t_{i}` اتفاقاً از نام متغیر `x` استفاده کند، جایگزینی مستقیم باعث ربایش متغیر می‌شود. ترم بیرونی به طور تصادفی توسط سور داخلی `C` پابند می‌شود و معنای فرمول را تغییر می‌دهد و قواعد برهان را می‌شکند. تغییر نام، ایمنی ساختاری را تضمین می‌کند.

طبق قضیه جایگزینی، این برهانی برای:

`(\exists\bar y) \left[ (\forall u)\(C(\bar y,u)\ => ``C^***(\bar y,u)\) => (\forall u)C^***(\bar y,u)]`.

را به دست می‌دهد.

• از آنجا که `C^***` فقط در نام متغیرهای پابند با `C` متفاوت است،

`vdash(\forall u) (C(\bar y,u) => C^***(\bar y,u))`.

• با کار زدن قیاس استثنایی سمت چپ `=>` را حذف می‌کنیم:

`vdash(\exists\bar y)(\forall u)C^***(\bar y,u)`.

• با نام‌گذاری مجدد متغیرهای پابند به نام‌های اصلی آنها، داریم:

`vdash(\exists\bar y)(\forall u)C(\bar y,u)`

و از اینجا:

`vdash ttA.`

ب. `vdash ttA` => `vdash ttA_1`:

گیریم:

`vdash(\exists\bar y)(\forall u)C(\bar y,u)`.

با کار زدن قاعده سور وجودی با متغیرهای جدید `b_1,\ldots,b_n`، کافی است از `(AAu)C(\bar b,u)` استدلال کنیم.

فرمول زیر یک توتولوژی است:

`p => ((p => q) => q)`.

`p` و `q` را از قرار زیر می‌گیریم:

`p=C(\bar b,u), \qquad q=P(\bar b,u)`,

نیز با کار زدن قواعد سورها [۲.۲۹ لم] خواهیم داشت:

`(\forall u)C(\bar b,u) =>`` [ (\forall u) (C(\bar b,u) =>`` P(\bar b,u)) => (\forall u)P(\bar b,u)]`.

قاعده تعمیم سور وجودی `b_1,\ldots ,b_n` فرمول `A_1` را بدست می‌دهد و از اینجا داریم:

`vdash A\quad =>\quad\vdash A_1`.

در نتیجه

`vdash A iff\vdash A_1`.

اکنون از قضیه‌ صورت نرمال پرنکس (قضیه ۲.۳۰) برای برگردان `A_1` به یک فرمول بسته صورت نرمال پرنکس `A_2` استفاده می‌کنیم و خواهیم دشت:

`vdash A_1\iff\vdash A_2`.

وقتی سورها به جلو منتقل می‌شوند، `A_2` رتبه کوچکتری نسبت به `A` دارد. بنا فرض استقرا، `A_2` را می‌توان با فرمول اسکولم-نرمال `S` جایگزین کرد به طوری که:

`vdash A_2\iff\vdash S`.

بنابراین داریم:

`vdash A\iff\vdash S`.


■ مثال: برگردان فرمول به صورت نرمال اسکولم

`ttB:``(AAx)(AAy)(EEz) ttC(x, y, z)```
`ttB_1``: (AAx)(((AAy)(EEz) ttC(x, y, z) => A_j^1(x)) =>``(AAx) A_j^1(x))`
`(EEx)([((AAy)(EEz) ttC(x, y, z) => A_j^1(x))] =>``(AAx) A_j^1(x))` 2.9.a
`(EEx)((EEy)[[EEz] ttC(x, y, z) => A_j^1(x)] =>``(AAx) A_j^1(x))` 2.9.a
`(EEx)((EEy)(AAz) ttC(x, y, z) => A_j^1(x)] =>``(AAx) A_j^1(x))` 2.9.b
`(EEx)(AAy)[(AAz) ttC(x, y, z) => A_j^1(x)] =>``(AAx) A_j^1(x)]` 2.9.b
`(EEx)(AAy)(EEz)[ttC(x, y, z) => A_j^1(x)] =>``(AAx) A_j^1(x)]` 2.9.a
`(EEx)(AAy)(EEz)(AAv)[ttC(x, y, z) =>A_j^1(x)] => A_j^1(v)]` 2.9.c

این روند را دوباره تکرار می‌کنیم: فرض کنید `ttD(x, y, z, v)` به صورت `(ttC(x, y, z) =>A_j^1(x)) =>A_j^1(v)` باشد.

فرض کنید `ttC(x, y, z, v)` از قرار `(ttC(x, y, z) =>A_j^1(x)) =>`` A_j^1(v)` باشد.
`(EEx)([(AAy)[(EEz)(AAv) ttD(x, y, z, v) => A_k^2(x, y)]] =>``(AAy) A_k^2(x, y))`
`(EEx)(EEy)[[EEz)(AAv) ttC(x, y, z, v) =>A_k^2(x, y)] =>`` (AAy) A_k^2(x, y)]` 2.9.a
`(EEx)(EEy)(EEz)(EEv)[[ttD(x, y, z, v) =>``A_k^2(x, y)] => (AAy) A_k^2(x, y)]` 2.9. (a, b)
`(EEx)(EEy)(EEz)(AAv)(AAw)[ttD(x, y, z, v) =>A_k^2(x, y)] =>``A_k^2(x, w)]` 2.9.c

بنابراین، یک صورت نرمال اسکولم `ttB` به صورت زیر است:

`(EEx)(EEy)(EEz)(AAv)(AAw)[[ttC(x, y, z) =>A_j^1(x)] => A_j^1(v)] =>``A_k^2(x, w)]`

■ تمرین ۲.۸۵ - ۲.۸۷

:۲.۸۵

a. `not(EEx)A_1^1(x)=>``AA(u)(EEy)AA(x )A_1^3(u,( , x, y)`

b. `(AAx)(EEy)(AAu)(EEv)A_1^4(x, y, u, v)`

:۲.۸۶

نشان دهید که یک روش کارآمد وجود دارد که برای هر فرمول `tt"B"` از یک حساب محمولات محض، فرمول `tt"D"` دیگری را در این حساب با صورت `(AAy_1) … (AAy_n)(EEz_1) … (EEz -m)tt"C"` به‌دست می‌دهد (`n, m ≥ 0` و `tt"C"` بدون سور)، به قسمی که `tt"B"` صدق‌پذیر است اگر و تنها اگر `tt"D"` صدق‌پذیر باشد. [راهنمایی: قضیه ۲.۳۱ را برای `not tt"B"` بکار بزنید.]

:۲.۸۷

یک صورت نرمال اسکولم `ttS` برای `(AAx)(EEx)A_1^2(x, y)` پیدا کنید و نشان دهید که چنین نیست که `|-- ttS <=> (AAx)(EEx)A_1^2(x, y)` باشد. بنابراین، یک صورت نرمال اسکولم برای فرمول `ttB` لزوماً هم‌ارز منطقی با `ttB` نیست، برخلاف صورت نرمال پرنکس که در قضیه ۲.۳۰ ارائه شده است.

حل:

`tt"S"` به صورت:

`(EEx)(EEy)(AAz)([A_1^2(x, y) => A_1^1(x)] => A_1^1(z))`

است. فرض کنید دامنه تعبیر `D` برابر با `{1, 2}` باشد، نیز تعبیر `A_1^ 2` عبارت از < [یعنی `x< y`] و تعبیر `A_1^1(u)` عبارت از `u = 2` باشد. در این صورت `tt"S"` در این تعبیر درست است [زیرا مقدم شرطی نادرست است]، اما `(AAx)(EEy)A_1^2(x, y)` نادرست است.


■ ■ ■ ■ ■




◄ توجه: