نگارش صورت و الگوریتم آن در منطق

منطق و فرامنطق

درآمد به منطق

۱- سرآغاز	۱۴- شمای فرمول و زیرفرمول بی‌واسطه
۲- زبان صوری Pℓ: معرفی واژگان ابتدایی	۱۵- سه شمای فرمول
۳- نگارش صورت (تألیف لفظ)	۱۶- تعریف بازگشتی زیرفرمول
۴- روند نگارش صورت	۱۷- استقرای ساختاری (Structural induction) و خوانش یکتای فرمول
۵- تعریف بازگشتی صورت	۱۸- رتبه فرمول
۶- دنباله پیکربندی	۱۹- اثبات یکتایی شمای (خوانش یکتای) فرمول
۷- مثال: نگارش لفظ (دنباله پیکربندی)	۲۰- رابط اصلی فرمول
۸- فرمول‌ در منطق	۲۱- حذف پرانتز از فرمول
۹- فرمول شماتیک	۲۲- تصمیم پذیری فرمول خوش-ساخت در منطق گزاره‌ها
۱۰- فرمول اتمی	۲۳- الگوریتمِ تصمیم پذیری فرمول
۱۱- شمارایی مجموعه فرمول‌ها	۲۴- درخت پیکربندی فرمول
۱۲- درجه فرمول	۲۵- مثال برای درخت پیکربندی
۱۳- زیرفرمول	۲۶- شناسایی درخت فراکافت (Parse tree)

■ سرآغاز

هدف این یادداشت نگاه نزدیک به روند ساخت یک زبان صوری و نشان دادن تصمیم‌پذیری و خوانش یکتای آن است. به‌عبارت‌دیگر، ارائه الگوریتمی که بتواند برای هر عبارت دلخواه زبان به پرسش "آیا این عبارت یک عبارت خوش-ساخت در آن زبان است یا نه؟" به‌طور صحیح پاسخ آری یا نه دهد. بنابراین، موردتوجه این یادداشت صرفاً نگارش صورت (لفظ) در زبان صوری است. [برای تعریف دقیق "رشته‌"، "زبان" و "عبارت" اینجا را ببینید.]

یک زبان صوری مجموعه‌ای از‌ واژگان ابتدایی همراه با فهرست محدود از قواعد، موسوم به قواعد نحوی / Syntax rules (نیز قواعد ساخت / Construction rules) است، به قسمی که به‌موجب این قواعد بتوان یک و فقط یک زیرمجموعه‌ ناتهی و سره از عبارت‌های زبان — که به آنها فرمول‌های‌ خوش-ساخت گفته می‌شود — ساخت و متمایز گردد.

☚ مجموعه قواعد نحوی یک زبان صوری را نیز قواعد نگارش صورت (یا نحو زبان صوری) می‌نامند.

در بند بعد یک زبان صوری خواهیم ساخت و آن را Pℓ خواهیم ‌نامید.

■ زبان صوری Pℓ: معرفی واژگان ابتدایی

واژگان ابتدایی Pℓ اعضای سه مجموعه ازهم جدا (اتم‌ها - رابط‌ها - نمادهای ویژه) به‌قرار زیر است:

۱-	اتم‌ها: به هر یک از عناصر مجموعه: {p, q, r, s , t} یک اتم Pℓ (یا فقط اتم) می‌گوییم. گرچه در اینجا فقط پنج اتم معرفی شده است ولی در صورت لزوم می‌توان با کاربرد اندیس، مانند ,{p_۱, p_۲, . . ., p_n} به هر تعداد دلخواه از آن‌ها معرفی کرد. به‌طورکلی مجموعه اتم‌ها نامتناهی فرض می‌شود. گرچه شمارایی مجموعه اتم‌ها ضروری نیست ولی آن ‌را شمارا فرض می‌کنیم. بنابراین می‌توان مجموعه اتم‌ها را {p_۱, p_۲, . . ., p_n, . . .} نیز در نظر گرفت.
۲-	رابط‌ها: {~, ⊃, ∧, ∨} به عنوان رابط‌های ابتدایی. [بجای نماد "•" نماد "∧" را برای رابط عطف بکار برده‌ایم.]
۳-	نمادهای ویژه به قرار {) ,(} به‌عنوان ابزار وابسته زبانی برای پرهیز از چند خوانشی.

اجتماع سه مجموعه بالا را Σ^Pℓ نامیده و به رشته‌های‌ متناهی Σ^Pℓ عبارت‌های‌ زبان Pℓ می‌گوییم. بنابراین،

p)r ∧ p , p ∧ q , p

هر سه عبارت‌های Pℓ هستند.

☚: می‌توان هر نماد را با قرار دادن آن داخل دو گیومه نام‌گذاری کرد؛ مثل "~" (یا «~») و مانند آن.

■ نگارش صورت (تألیف لفظ)

همان‌طور که در بالا آمد، مراد ما در اینجا از نگارش صورت (تألیف لفظ) وضع قواعدی است تا به‌موجب آن‌ها یک و فقط یک زیرمجموعه‌ ناتهی و سره از عبارت‌های Pℓ، که ازاین‌پس آن را ƒ^Pℓ را می‌نامیم، متمایز گردد.

■ روند نگارش صورت

قواعد عضویت در ƒ^Pℓ و به‌عبارت‌دیگر، تعریف ƒ^Pℓ را به روش بازگشتی بیان می‌کنیم. این روش به طور گسترده در ریاضیات، منطق و دانش کامپیوتر استفاده می‌شود. ویژگیِ این‌گونه تعریف که به آن تعریف سازنده هم می‌گویند، پیدایش مصداق‌های معرَف (تعریف‌شده) در روند تعریف است.

هر تعریف بازگشتی در سه‌گام انجام می‌شود. بنابراین ƒ^Pℓ را در سه گام به شرحی که خواهد آمد تعریف خواهیم کرد. ولی قبل از آن باید یک نکته را یادآوری کرد. و آن اینکه، قرار است یک زبان (زبان موضوع) تعریف شود و این به‌وسیله زبان ناظر (فرازبان) که همین جمله در آن است، انجام می‌شود. بنابراین باید در زبان ناظر در باره "چیزهایی" در زبان موضوع سخن گفت. به‌عبارت‌دیگر، نیاز است تا در زبان ناظر این "چیزها" را نام برد و به آن‌ها ارجاع داد. در این موارد می‌توان با قرار دادن عناصر زبان موضوع درون جفت گیومه آنها را متمایز کرد.

بعلاوه نیاز است چیزهایی را نام ببریم که گرچه در دامنه مصداقی مشخص هستند اما اشاره به مورد خاصی در این دامنه ندارند. مثل آنکه می‌خواهیم بگوییم «فرض کنید شئ‌ای یک عبارت Pℓ باشد، ...» یا «اگر شئ‌ای عضو ƒ^Pℓ باشد، آنگاه....». در این موارد به‌جای «شئ‌ای" از حروف کوچک الفبای یونانی به‌قرار β ،α ،γ و λ با اندیس و بی اندیس استفاده خواهیم کرد. به این‌ها، که درواقع عناصر فرازبان‌ هستند متغیرهای فرازبانی، گفته می‌شود.

■ تعریف بازگشتی صورت

در گام یکم (I) عبارت‌های معینی از Pℓ را به صراحت به عضویت ƒ^Pℓ درمی‌آوریم. به این نحو که می‌گوییم:

I: اتم‌ها و ثابت‌های منطقی عضو ƒ^Pℓ هستند. (بنابراین ƒ^Pℓ تهی نخواهد بود.)

در گام دوم (II) ƒ^Pℓ را با یک پیوست چهار قاعده‌ای به شرحی که خواهد آمد گسترش می‌دهیم (با این چهار قاعده، عبارات بیشتری را برای ƒ^Pℓ بر پایه عبارات موجود می‌سازیم).

پس می‌گوییم:

II.۱: اگر α عضو ƒ^Pℓ باشد آنگاه ~α نیز عضو ƒ^Pℓ است.

مثال: بنا بر I، اتم p عضو ƒ^Pℓ است و بنا بر II.۱ عبارت ~p نیز عضو ƒ^Pℓ خواهد بود. و ازآنجاکه p~ عضو ƒ^Pℓ است، مجدداً بنا بر II.۱ عبارت p~~ نیز عضو ƒ^Pℓ است. (با تکرار روند II.۱ به هر تعداد دلخواه می‌توان برای ƒ^Pℓ عضو ساخت.)

گام دوم را با وضع چهار قاعده دیگر تمام می‌کنیم و می‌گوییم:

اگر α و β عضو ƒ^Pℓ باشند، آنگاه:

(α ∧ β) :II.۲
(α ∨ β) :II.۳
(α ⊃ β) :II.۴

عضو ƒ^Pℓ هستند.

آنچه می‌ماند اینکه این تعریف هنوز نهایی نیست (جامع است ولی مانع نیست). یعنی، آیا عبارت‌های دیگر، غیر ازآنچه در این دو گام به عضویت ƒ^Pℓ درآمده‌اند، هستند که عضو ƒ^Pℓ باشند؟ پس، گام آخر (سوم) نهایی کردن (بستن) تعریف (وضع قوانین تألیف لفظ) است.

بنابراین، در گام سوم(III)، می‌گوییم:

فقط آن عبارات از Pℓ عضو ƒ^Pℓ هستند که به‌وسیله (I) و (II) ساخته‌شده باشند.

☚	سه‌گانه بالا را قواعد نگارش Pℓ می‌نامیم.
☚	همیشه حرف آغازین اعضای ƒ^Pℓ یک اتم یا "~" یا ")" است.

■ دنباله پیکربندی

به دنباله‌ای متناهی از عبارت‌های Pℓ دنباله پیکربندی گوییم اگر و تنها اگر هر یک از عناصر آن اتم (فرمول اتمی) باشند یا از عناصر قبلی و بناشده بر یکی از قواعد ساخت باشند. اکنون می‌توان گفت:

α در Pℓ یک فرمول است اگر و تنها اگر یک دنباله پیکربندی که آخرین عنصر آن α باشد وجود داشته باشد.

دنباله پیکربندی یک فرمول الزاماً یکتا نیست. برای مثال:

☚	≺p, q, (p ∧ q)≻ و ≺q, p, (p ∧ q)≻ هر دو دنباله ساخت فرمول (p∧q) هستند.

■ مثال: نگارش لفظ (دنباله پیکربندی)

نشان دهید عبارت‌های زیر عضو ƒ^Pℓ هستند.

۱- α = (~~ p ⊃ p)

۲- β = (((p ⊃ q) ∧ (q ∨ r)) ⊃ (p ∨ r)) ⊃ ~(q ∨ s)))

حل ۱: با توجه به فهرست زیر، α عضو ƒ^Pℓ است.


توجیه ساخت	عبارات ساخته
اتم‌ها عضو ƒ^Pℓ هستند. (I)	p	۱.
۱ و II.۱.	~p	۲.
۲ و II.۱.	~~p	۳.
۳ و II.۴.	(~~ p ⊃ p)	۴.

دنباله‌ای که عناصر آن عبارات ستون ۱ و به ترتیب از سطر ۱ تا ۴ است روند پیدایش (نگارش) اعضای ƒ^Pℓ است. هر عضو این دنباله یک اتم است یا از عضوهای قبل بنا بر یک قاعده حاصل‌شده است. مراحل ۱ تا ۴ در بالا را می‌توان به‌صورت یک دنباله نشان داد:
≺p, ~p, ~~p, (~~p ⊃ p)≻

حل ۲: با توجه به فهرست زیر، β عضو ƒ^Pℓ است.


توجیه ساخت	عبارات ساخته
I	p	۱.
I	q	۲.
I	r	۳.
I	s	۴.
۱، ۲ و II	(p⊃q)	۵.
۲، ۳ و II	(q∨r)	۶.
۵، ۶ و II	((p⊃q) ∧ (q∨r))	۷.
۱، ۳ و II	(p∨r)	۸.
۲، ۴ و II	(q∨s)	۹.
۷، ۸ و II	(((p⊃q)∧(q∨r)) ⊃(p∨r))	۱۰.
۹ و II	~(q∨s)	۱۱.
۱۰، ۱۱ و II	((((p⊃q)∧(q∨r)) ⊃(p∨r))⊃~(q ∨s))	۱۲.

در زیر روند ۱ تا ۱۲ در بالا به‌صورت یک دنباله نشان داده‌شده:
≺ p, q, r, s, (p⊃q), (q ∨r), ((p⊃q)∧(q∨r)), (p∨r), (q∨s), (((p⊃q)∧(q ∨r))⊃(p ∨r)), ~(q∨s), ((((p⊃q)∧(q∨r))⊃(p∨r)⊃~(q∨s)) ≻

■ فرمول‌ در منطق

زبان Pℓ را می‌توان با معرفی عناصر جدید (برای مثال رابط‌ها و اتم‌ها از گونه‌های جدید) گسترش داد و زبان صوری بزرگ‌تری را ساخت. این همان چیزی است که در تئوری سورها (فصل 11 کتاب) انجام شد و اتم‌های «ثابت‌های انفرادی»، «حروف محمولی» و همچنین سه رابط «سور عمومی»، «سور وجودی» و «متغیر انفرادی» معرفی ‌شدند. در این زبان‌ها الفاظ تألیفی فقط "صورت‌های گزاره‌ای" آن‌گونه که در فصل‌ نه کتاب معرفی شدند نیستند، بلکه صورت‌های دیگر نیز به میان می‌آیند. منطق ‌دان‌ها به این صوَر «Well-Formed Formula» (با کوته‌سازی wff) می‌گویند. ازآنجاکه در متون ریاضی به زبان فارسی عباراتی مانند «Well Defined» و «Well Ordered» به ترتیب به «خوش-تعریف» و «خوش-ترتیب» برگردانده شده است، ما نیز به پیروی «پیکره / پیکرک(ها)ی خوش-ساخت» یا آسان‌تر فرمول خوش-ساخت را با همان کوته‌سازی، wff، بکار می‌بریم. و وقتی از زمینه مشخص است، فقط از "فرمول" یاد می‌کنیم. مراد از "خوش-ساخت" نابسته بودن آن‌ها به هر تعبیری هستند که ممکن است به آن‌ها منتسب گردد. حاصل کلام آنکه به عضوهای مجموعه ƒ^Pℓ فرمول‌های (خوش-ساخت) Pℓ می‌گوییم و فقط عضوهای این مجموعه را فرمول‌های ƒ^Pℓ می‌نامیم.

⦁ طول فرمول

هر فرمول یک "عبارت" است. و ازاینجا، اگر α فرمول باشد طول آن ر طول عبارت α می‌گیریم و آن را با |α| نشان می‌دهیم.

برای مثال |((p∧q)⊃p)|=۹ و |p|=۱.

■ فرمول شماتیک

به فرمولی که در آن حداقل یک متغیر فرازبانی به‌کاررفته، یک فرمول شماتیک گفته می‌شود. یک فرمول شماتیک معرفی تعداد نامتناهی فرمول است. برای مثال فرمول (p∨α) معرف (p∨(p∧q)) یا (p∨q) و مانند آن‌ها است.

■ فرمول اتمی

به یک فرمول غیر شماتیک که در آن رابطی‌ بکار نرفته باشد فرمول اتمی و در غیر این صورت به آن فرمول غیر اتمی گفته می‌شود. بنابراین همه اتم‌ها فرمول اتمی هستند.

■ شمارایی مجموعه فرمول‌ها

• یادآوری از حساب (شماره گذاری گودل):

هر عدد طبیعی بزرگ‌تر از یک را به‌طور یکتا می‌توان به عوامل اول تجزیه کرد. به‌عبارت‌دیگر، برای هر n∈ℕ ; n>۱ اعداد متمایز اول

p_۱, p_۲ , . . . , p_r [و تنها نیز آنها]

وجود دارند به قسمی که:

n = (p_۱)^a۱ × (p_۲)^a۲ × . . . × (p_r)^ar

که در آن:

r_i ∈ ℕ; r_i > ۱; a_۱ ∈ ℕ; a_۱ > ۰.

برای مثال:

۱۶,۵۲۹,۹۴۰,۸۶۴ = ۲^۷ × ۳^۱۷;
۱۰۰ = ۲^۲ × ۵^۲;
۶۳ = ۳^۲ × ۷^۱

و مانند آن‌ها.

اکنون تابع g را طوری تعریف می‌کنیم که به نماد‌های ابتدایی Pℓ اعداد زیر را نظیر کند:

g(()=۱ , g())=۲, g(~)=۳ , g(∧)=۴,

g(∨)=۵ , g(⊃)=۶ , g(p)=۷ , g(q)=۸,

g(r)=۹ , g(s)=۱۰ , g(t)=۱۱.

سپس به هر عبارت در Pℓ، مانند e → c_۱c_۲...c_m، عدد:

۲^g(c۱) × ۳^g(c۲) × . . . × p_r^g(cr)

را نظیر کرده به قسمی که در آن c_i حرف iام در e و امینr ،p_r عدد اول باشد. برای مثال، برای عبارت '(~∨~)' داریم:

(~∨~) ↔ ۲^۱×۳^۳×۵^۵×۷^۳×۱۱^۲= ۷۰۰۳۶۳۱۲۵۰

به این ترتیب، یک رابطه ۱:۱ بین زیرمجمو‌عه‌ای از اعداد طبیعی و عبارات Pℓ پدید می‌آید. و ازاینجا مجموعه عبارات Pℓ شمارا است؛ و چون مجموعه فرمول‌های Pℓ، یعنی، ƒ^Pℓ، زیرمجموعه عبارات آن است آنگاه ƒ^Pℓ نیز شمارا است. اگر اتم‌های Pℓ را نامتناهی و شمارا در نظر بگیریم، با توجه به نامتناهی بودن اعداد اول، هنوز ƒ^Pℓ شمارا خواهد بود.

شمارایی ƒ^Pℓ امکان برشمردن آن را میسر می‌سازد. به‌عبارت‌دیگر، می‌توان اعضای آن را به گونه زیر فهرست کرد:

α_۱, α_۲, α_۳, . . . α_k, . . .

به قسمی که هر عضو ƒ^Pℓ در این فهرست باشد و هر α_i یک عضو ƒ^Pℓ باشد.

■ درجه فرمول

به تعداد رابط‌های یک فرمول درجه فرمول می‌گویند. این عدد برابر با تعداد کار زدن قواعد II.1 تا II.4 در دنباله پیکربندی آن فرمول است. در مثال‌های بالا رابط‌های رنگی شده کار زدن یکی از قواعد ساخت II.1 تا II.4 را نشان می‌دهند.

■ زیرفرمول

فرض کنید α فرمول باشد. یک زیرفرمول (Subformula) α یک زیرعبارت α است اگر خود فرمول باشد. برای مثال اگر α فرمول ((p∨q)⊃p) باشد آنگاه همه زیرفرمول‌های α عبارت‌اند از:

p, q, (p∨q), ((p∨q)⊃p)

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

در ادامه، ما در پی یک روند کارآمد برای یافتن زیرفرمول‌های یک فرمول، به قسمی که ساختن دنباله ساخت آن را میسر کند خواهیم بود. در این راه و در قدم اول نیازمند به یک تعریف سازنده (بازگشتی) برای زیرفرمول هستیم. قبل از آوردن چنین تعریفی باید زیرفرمول بی‌واسطه را تعریف کنیم.

■ شمای فرمول و زیرفرمول بی‌واسطه

فرض ‌کنید α یک wff غیر اتمی باشد. با توجه به قواعد پیکربندی درمی‌یابیم که α به یکی از سه شمای زیر است:

۰ اتم (یکی از اعضای {p, q, r, s, t})،

یا

۱ ~β (~ موسوم به رابط یکتایی /Unary است)،

یا

۲ (γ b λ)؛ b یکی از رابط‌های •, ∨, ⊃, ≡ (موسوم به رابط‌های دوتایی /Binary است).

در شمای ۱، β را زیرفرمول بی‌واسطه α و در شمای ۲، γ و λ را زیرفرمول‌های بی‌واسطه α می‌نامیم. بنابراین یک فرمول اتمی (شمای ۰) زیرفرمول بی‌واسطه ندارد و افزون بر آن یک فرمول زیرفرمول بی‌واسطه خود نیست.

■ سه شمای فرمول

با توجه به آنچه درباره زیرفرمول گفته شد، شمای یک فرمول Pℓ و زیرفرمول(های) بی‌واسطه آن را می‌توان به‌صورت زیر نیز نشان داد.

■ تعریف بازگشتی زیرفرمول

فرض کنید α یک wff باشد آنگاه:

۱.	α یک زیرفرمول α است؛
۲.	اگر β یک زیرفرمول α باشد، آنگاه همه زیرفرمول‌های بی‌واسطه β زیرفرمول α هستند؛
۳.	فقط عباراتی که از ۱ یا ۲ به دست می‌آیند زیرفرمول‌های α هستند.

■ استقرای ساختاری (Structural induction) و خوانش یکتای فرمول

در بند قبل دیدیم هر فرمول در Pℓ به یکی از سه شمای (۰، ۱، ۲) است. آیا این شما یکتا است؟ به‌عبارت‌دیگر، اگر فرمول α دارای دو شمای (γbλ) و (εbρ) باشد، آنگاه باید: ε= γ ،λ=ρ ؟

جواب این پرسش آری است و برای اثبات آن ابتدا باید با گونه‌ای تکنیک برهان (در فرازبان) به نام استقرای ساختاری آشنا شد. در واقع، استقرای ساختاری گونه‌ای تکنیک استدلال (تعمیم استقرای ریاضی) است که می‌توان از آن برای اثبات ویژگی‌های عناصر مجموعه‌هایی که به روش استقرایی تعریف شده‌اند (مانند مجموعه فرمول‌های Pℓ، یعنی ƒ^Pℓ) به کار زد.

یک استقرای ساختاری در دو گام انجام می‌یابد. در گام نخست نشان می‌دهیم ویژگی مورد نظر، به فرض P()، برای همه ساختارهای کمینه‌ای در ƒ^Pℓ برقرار است. در گام دوم نشان می‌دهیم که اگر ویژگی P() برای زیرساختار‌های بی‌واسطه (ساختارهای کمینه‌ای) آن ساختار برقرار باشد، آنگاه برای همه عناصر ƒ^Pℓ نیز برقرار است.

⦁ استقرای ساختاری طولی (۱)

فرض کنید P() یک ویژگی (برای مثال زوج بودن تعداد پرانتز‌های اعضای ƒ^Pℓ) باشد. می‌خواهیم نشان دهیم این ویژگی برای همه اعضای ƒ^Pℓ برقرار است. در چنین موارد کار زدن موفق استقرای طولی فرمول‌ که بر اصل آمده در زیر استوار است برای شمول P() به همه اعضای ƒ^Pℓ کافی است.

اگر P() یک ویژگی در ƒ^Pℓ و داشته باشیم:

۱	آ. P() بری هر فرمول اتمی در ƒ^Pℓ برقرارباشد؛
	و
۲	ب. اگر P() برای فرمول α برقرار است آنگاه برای ~α برقرار باشد؛ ج. اگر P() برای فرمول‌های α و β برقرار است آنگاه برای (αbβ) برقرار باشد؛

آنگاه P() برای هر عضو ƒ^Pℓ برقرار است.

⦁ مثال: زوج بودن تعداد پرانتزها در فرمول

اگر P ویژگی زوج بودن پرانتزها در ƒ^Pℓ باشد، نیز x∈ƒ^Lp باشد آنگاه داریم:

آ. P(x) برای هر {p, q, r, s, t} ∋ x؛

ب. اگر (فرمول λ و γ) P(λ) و P(γ) آنگاه P(~λ) و P(γbλ).

بنابراین، بنا به اصل استقرای ساختاری P برای همه اعضای ƒ^Pℓ برقرار است.

⦁ مثال: تعریف طول فرمول به روش بازگشتی

در بالا↥ طول یک فرمول را برابر طول عبارت آن گرفتیم. در زیر تعریف طول یک فرمول به شیوه تعریف بازگشتی آمده است. به شیوه استقرای طولی فرمول می‌توان نشان داد مقدار طول فرمول در هر دو تعریف یکی است.

تابع len:ƒ^𝓅ℓ →ℕ، آن‌گونه که در زیر تعریف‌شده را به‌عنوان طول فرمول α می‌گیریم:

	len(α) = ۱ اگر α اتمی باشد؛
	len(α) = l+۱ اگر α به شمای ~β و len(β)=l باشد؛
	len(α) = l_۱+ l_۲+۳ اگر α به شمای (γbλ) و len(λ)=l_۲, len(γ)=l_۱ باشد؛

برای مثال:

۱- len(((p∧q)⊃r)) = len((p∧q)) + len(r) + ۳ = len(p) + len(q)+ ۳ + len(r) + ۳ = ۱ + ۱ + ۳ + ۱ + ۳ = ۹

۲- len((p∧q))=len(p) +len(q)+۳=۱+۱+۳=۵

⦁ استقرای ساختاری طولی (۲)

در زیر، بازآرایی دیگری از تعریف استقرای طولی فرمول‌ آمده است که به آسانی می‌توان نشان داد که با تعریف آمده در بالا↥ معادل است.

فرض کنید α فرمول و P() یک ویژگی آن باشد. می‌گوییم:

اگر P() برای هر فرمول با طول کوچک‌تر از |α| برقرار باشد آنگاه برای α نیز برقرار است. آنگاه P() برای هر عضو ƒ^Lp برقرار است.

■ رتبه فرمول

رتبه فرمول معیاری برای اندازه‌گیری درجه ترکیب (پیچیدگی) یک فرمول است. در زیر تعریف رتبه فرمول به روش بازگشتی آمده است.

اگر α فرمول اتمی باشد؛	۱
اگر α به شمای ~β باشد؛	Rank(β)+۱			Rank(α) =
اگر α به شمای (γbλ) باشد.	Max(Rank(γ), Rank(λ))+۱

تعریف تابع Max(a, b)		اگر a>b	a	Max(a, b)=
		وگرنه	b	Max(a, b)=

برای مثال:

۱- Rank(p)=۱

۲- Rank((p⊃q)) = Max(Rank(p), Rank(q)) + ۱ =
= Max(۱, ۱) + ۱=۱+۱ = ۲

۳- Rank(((p∧q)⊃r)) = Max(Rank((p∧q)), Rank(r)) +۱ =
= Max(۲, ۱) +۱ = ۲+۱=۳

۴- Rank(((p⊃q)⊃(p∧r))) = Max(۲, ۲) + ۱ = ۲+۱ = ۳

۵- Rank((((p∧(q∨r))⊃r)∨(p∧r))) = ۵

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

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

حل:

برای اثبات، فرض استقرا را "رتبه هر زیرفرمول بی‌واسطه یک فرمول کوچک‌تر از رتبه خود آن فرمول است" گرفته و اثبات را ادامه می‌دهیم.

⦁ مثال: پاره آغازی سره (۱)

نشان دهید اگر پاره(ها) آغازی سره یک فرمول صرفاً شامل رابط "~" نباشد آنگاه تعداد پرانتز باز آن از تعداد پرانتز بسته آن بیشتر است.

⦁ مثال: پاره آغازی سره (۲)

نشان دهید پاره آغازی سره یک فرمول، خود فرمول نیست.
برای مثال فرمول (p∨q) را در نظر بگیرید. هیچ‌یک از پاره(ها) آغازی سره آن، یعنی:

(, (p, (p∨, (p∨q

فرمول نیستند.

حل:

فرض کنید α فرمول باشد، نیز P() ویژگی "قطعه‌های آغازی‌ سره همه فرمول‌های با طول کوچک‌تر از |α| فرمول نیستند" باشد. P() را درست فرض می‌کنیم و می‌گوییم: α باید به یکی از سه شمای زیر باشد:

۰- α فرمول اتمی است و در این صورت قطعه آغازی سره ندارد.

۱- α به شمای ~β است. چنین فرض می‌کنیم ~β دارای قطعه آغازی سره است که فرمول است. این قطعه ~ نیست زیرا ~ فرمول نیست. پس قطعه آغازی ~β باید به‌صورت ~β' باشد. این یعنی β' قطعه آغازی سره β است. اما طول β کوچک‌تر از طول ~β است و بنا بر P()، β' فرمول نیست. و ازآنجاکه قاعده‌‌ ساختی β' را فرمول نمی‌کند، پس بنا به گام (III) در تعریف فرمول، ~β' فرمول نیست.

۲- α به شمای (γbλ) است. مانند حالت ۱ فرض می‌کنیم (γbλ) دارای پاره آغازی سره است که فرمول است. سپس به روش (۱) اثبات را ادامه می‌دهیم.

■ اثبات یکتایی شمای (خوانش یکتای) فرمول

فرض کنید α دارای دو شمای متفاوت (γbλ) و (εbρ) باشد ( γ و ε و نیز λ و ρ متفاوت از یکدیگرند و می‌دانیم ،γ ،ε λ و ρ فرمول هستند.) در این صورت ε باید قطعه آغازی سره γ یا برعکس باشد که هر دو حالت ممکن نیست. برای بقیه حالت‌ها نیز به همین ترتیب است.

⦁ معرفی ⏉""، "⏊" و "≡":

۱- نمادهای "⏉"، "⏊" را به عنوان دو شمای فرمول مطابق زیر تعریف می‌کنیم [ χ متغیری است که دامنه آن متغیرهای لفظی است]:

۱- ⏉ ≝ (χ ∨ ~χ) ۲- ⏊ ≝ (χ ∧ ~χ)

۲- "≡" را برای کوتاه نویسی (یک رابط تعریف‌شده) مطابق تعریف زیر به کارخواهیم برد:

α ≡ β ≝ (α ⊃ β) ∧ (β ⊃ α)

توجه داریم که این نماد‌ها هیچ‌یک از نمادهای بنیادی زبان Pℓ نیست، بلکه هر یک طبق تعریف در Pℓ حاضرشده‌اند.

■ رابط اصلی فرمول

فرض کنید α یک فرمول غیر اتمی، آنگاه α به یکی از دو شمای:

۱- ~β یا ۲- (γ b λ)

است. در شمای ۱ به ~ و در شمای ۲ به b رابط اصلی فرمول α گفته می‌شود. با توجه به یکتایی شمای فرمول، رابط اصلی فرمول نیز یکتاست. بنابراین، هر فرمول غیر اتمی دارای یک و فقط یک رابط ‌اصلی است.

⦁ شناسایی رابط اصلی

فرض کنید α به شمای (γbλ) باشد. ازآنجاکه γ فرمول است پس باید تعداد پرانتزهای چپ و راست آن برابر و درنتیجه تعداد پرانتزهای چپ در "(γ" یک واحد بیشتر از پرانتزهای راست آن است. اما هیچ رابط دوتایی دیگر در " (γ" دارای این ویژگی نیست. بنابراین رابط اصلی یک فرمول به شمای (γbλ) اولین رابط دوتایی است که در زیر-عبارت بلافاصله مقدم آن (سمت چپ) دقیقاً دارای یک پرانتز چپ بیشتر از پرانتزهای راست‌ آن باشد.

■ حذف پرانتز از فرمول

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

قبل از معرفی سطح اولویت رابط‌ها گفته باشیم که طبق قرارداد همیشه می‌توان بیرونی‌ترین جفت پرانتز فرمول را حذف کرد. برای مثال p∨q به‌جای (p∨q) و مانند آن.

در جدول زیر سطح الویت رابط‌ها آمده است.

شرکت‌پذیری	رابط	سطح الویت
راست به چپ	~	۰
چپ به راست	∧	۱
چپ به راست	∨	۲
چپ به راست	⊃	۳
چپ به راست	≡	۴

جدول آ.۱۰.۱ سطح الویت رابط‌

در مثال‌های زیر نحوه کار زدن سطح الویت رابط‌ها برای حذف و نیز بارگذاری پرانتز آمده است.

۱.	~~p ↔ ~(~p) ↔ (~(~p))
۲.	p⊃q⊃p ↔ (p⊃q)⊃p ↔ ((p⊃q)⊃p)
۳.	p∨~(q ⊃p∨q) ↔ p∨~(q⊃(p ∨q)) ↔ ↔ p∨(~(q⊃(p ∨q))) ↔ ↔ (p ∨(~(q⊃(p ∨q))))
۴.	p⊃~q⊃r ↔ q⊃(~q)⊃r ↔ ↔ (q⊃(~q))⊃r ↔ (q⊃(~q))⊃r

باید توجه داشت که نمی‌توان با استفاده از مفهوم سطح الویت همه پرانتزهای هر فرمولی را حذف کرد. برای مثال حذف پرانتزهای p⊃(q⊃p) به فرمول p⊃q⊃p منجر می‌شود. بارگذاری پرانتزهای فرمول اخیر با توجه به سطح اولویت رابط‌ها فرمول ((p⊃q)⊃p) را به دست می‌دهد که متفاوت از فرمول اول است. البته با بهره‌گیری از روش نگارش موسوم به پولیش /لهستانی/Polish می‌توان به‌تمامی از پرانتز در نوشتن فرمول استفاده نکرد. در جای لازم از این روش بهره خواهیم برد. در نگارش به روش پولیش وقتی یک طول یک فرمول حتی کم هم باشد خواندن و نوشتن آن برای آدمی‌زاده با دردسر همراه است و البته خواندن آن برای ماشین بسی بی‌دردسر است.

■ تصمیم پذیری فرمول خوش-ساخت در منطق گزاره‌ها

در اینجا می‌خواهیم بدانیم آیا مسئله فرمول بودن در L^C تصمیم‌پذیر است؟ به‌عبارت‌دیگر اگر ρ یک عبارت دلخواه L^C و |ρ|>۰ باشد آنگاه الگوریتمی هست که ورودی آن ρ و خروجی آن پاسخ آری یا نه درباره فرمول بودن (خوش-ساخت بودن / به قاعده ساخت) ρ باشد؟

برای مثال وقتی ورودی این الگوریتم هر یک از عبارات زیر باشد؛

۱- ((
۲- ((~p)
۳- )p(
۴- (p⊃((p⊃p)⊃(p⊃p)⊃(p⊃p))))

خروجی الگوریتم باید "نه" باشد؛ و برای ورودی‌های زیر و مانند آن‌ها؛

۱- (p⊃~q)
۲- p
۳- (p⊃((p⊃r)⊃((q•~p)⊃(p⊃s))))

باید "بله" باشد.

■ الگوریتمِ تصمیم پذیری فرمول

توجه: همزمان با ارائه الگوریتم، اجرای آن را برای:

ρ::(p⊃(~p⊃q))

پی خواهیم گرفت.

۰- z را اتمی می‌گیریم که در ρ نباشد؛ [مجموعه اتم‌ها را شمارش پذیر نامتناهی فرض کرده‌ایم و بعلاوه هر نماد در یک عبارت که پرانتز و رابط نباشد اتم خواهد بود.]

۱- z را جایگزین هر مورد اتم‌های ρ کرده و حاصل را A_۱ نامیده. این عمل ر f_۱ می‌نامیم. بنابراین:

A_۱=f_۱(ρ) =f_۱((p⊃(~p⊃q)))=(z⊃(~z⊃z)

۲- z را جایگزین هر رویداد ~z در A_۱ کرده و حاصل ر A_۲ نامیده. این عمل ر f_۲ می‌نامیم. روشن است که: |A_۲|≤|A_۱|.

A_۲ =f_۲(A_۱)=(z⊃(z⊃z))

۳- A_۲ را از چپ به راست ‌کاویده و اولین زیرعبارت یافته در آن به شمای (zbz) را با z جایگزین کرده. حاصل را A_۳ نامیده. روشن است که: |A_۳|≤|A_۲|. این عمل ر f_۳ می‌نامیم.

A_۳ =f_۳(A_۲)= (z⊃z)

۴- دستورالعمل ۲ و ۳ را به ترتیب (یعنی، f_۳ºf_۲ که آن را f_۴ می‌نامیم) برای A_۳ تکرار می‌کنیم و حاصل ر A_۴ نامیده. این کار را تا جایی که، به فرض دربار nام، نتیجه به‌دست‌آمده روی A_n با خود A_n یکی شود، یا به‌عبارت‌دیگر داشته باشیم f_۳ºf_۲(A_n)=A_n ادامه می‌هیم. روشن است که در هر بار |A_n|<|A_n-۱| و دربار آخر |A_n+۱|=|A_n|.

A_۴ =f_۳ºf_۲(A_۳)=f_۳ºf_۲((z⊃z))=z
A_۵ =f_۳ºf_۲(A_۴)=A_۴

۵- اگر A_n=z آنگاه ρ فرمول و در غیر این صورت فرمول نیست.

چون برای n=۴ داریم: A_۴ =z پس ρ یعنی عبارت(p⊃(~p⊃q)) فرمول است.

توضیح: برای اثبات کارآمدی روند بالا (یعنی الگوریتم بودن آن) باید نشان داد اگر ρ فرمول باشد آنگاه عدد طبیعی n به قسمی که A_n=z وجود دارد (یعنی، اجرای الگوریتم در زمان محدود پایان می‌پذیرد که با توجه متناهی بودن طول عبارت ثابت می‌شود) و بعلاوه نیز نشان‌داد که اگر عدد طبیعی n به قسمی که A_n=z باشد وجود داشته باشد آنگاه ρ فرمول است و در غیر این صورت ρ فرمول نیست (یعنی اثبات صحت الگوریتم، که این نیز یا توجه به خوانش یکتای فرمول اثبات می‌شود).

مثال بیشتر:

ρ :: (p⊃((p⊃p)⊃~(p⊃p)⊃(p⊃~p))))
A_۱ =f_۱(ρ)=(z⊃((z⊃z)⊃~(z⊃z)⊃(z⊃~z))))
A_۲=f_۲(A_۱)=(z⊃((z⊃z)⊃~(z⊃z)⊃(z⊃z))))
A_۳=f_۳(A_۲)=(z⊃(z⊃~(z⊃z)⊃(z⊃z))))
A_۴=f_۳(A_۳)=(z⊃(z⊃~z⊃(z⊃z))))
A_۵=f_۲(A_۴)=(z⊃(z⊃z⊃(z⊃z))))
A_۶=f_۳(A_۵)=(z⊃(z⊃z⊃z)))
A_۷=f_۳ºf_۲(A_۶)=(z⊃(z⊃z⊃z)))=A_۶
فرمول نیست. ρ پس A_۶=A_۷≠z چون

ρ :: (p⊃((p⊃~p)⊃(p • p)⊃(p∨~p))))
A_۱=f_۱(ρ)=(z⊃((z⊃~z)⊃((z • z)⊃(z∨~z))))

A_۲=f_۲(A_۱)=(z⊃((z⊃z)⊃((z • z)⊃(z∨z))))
A_۳= f_۳(A_۲)=(z⊃(z⊃((z • z)⊃(z∨z))))

A_۴= f_۴(A_۳)=(z⊃(z⊃(z⊃(z∨z))))
A_۵= f_۴(A_۴)=(z⊃(z⊃(z⊃z)))
A_۶= f_۴(A_۵)=(z⊃(z⊃z))
A_۷= f_۴(A_۶)=(z⊃z)
A_۸=f_۴(A_۷)=z
A_۹=f_۴(A_۸)=A_۸
فرمول است. ρ پس A_۸=A_۹=z چون

■ درخت پیکربندی فرمول:

در این بند به نگارش و خوانش فرمول (wff) در یک ساختار درختی (نمودار درختی) می‌پردازیم. به چنین ساختاری درخت پیکربندی (یا درخت فراکافت - Parse tree) گفته می‌شود. فرض می‌کنیم α فرمول باشد. درخت پیکربندی α یا Tree_α - را به گونه بازگشتی مطابق زیر تعریف می‌کنیم:

آ- اگر α اتمی باشد آنگاه؛

Tree_α=۰ α

ب- اگر α به شمای ~β باشد آنگاه؛

Tree_α=

ج- اگر α به شمای (γbλ) باشد آنگاه؛

Tree _(γbλ)=

■ مثال برای درخت پیکربندی

درخت فراکافت (تجزیه) در منطق

☚	فرض کنید α یک فرمول و Tree_α درخت پیکربندی آن باشد، آنگاه محتوی هر گره‌ Tree_α یک زیرفرمول α است و بعلاوه محتوی هر گره تالی زیرفرمول-بی‌واسطه گره مقدم خود است.

■ شناسایی درخت فراکافت (Parse tree)

فرض کنید T یک درخت دودویی باشد به‌گونه‌ای که؛

۱- محتوی هر برگ (گره‌ انتهایی) یک اتم باشد؛

۲- محتوی هر گره ساده T یک فرمول به شمای ~β بوده و بعلاوه فرزند این گره دارای محتوی β باشد؛

۳- محتوی هر گره انشعاب در T فرمولی به شمای (γbλ) بوده و بعلاوه فرزندان چپ و راست این گره به ترتیب دارای محتوی γ و λ باشد؛

در این صورت به T یک درخت پیکربندی می‌گوییم. می‌توان نشان داد که T متناظر با درخت پیکربندی فرمولی است که محتوای ریشه T است.

درخت تحلیل فرمول منطق

اینجا بحث درباره صورت (فرمول خوش-ساخت) را تمام می‌کنیم و یادآور می‌شویم الگوریتم‌های آمده در این قسمت را با داشتن مهارت میانه با یک زبان برنامه نویسی می‌توان به آسانی پیاده سازی کرد. افزون براین، این الگوریتم‌ها برای عبارت‌های ریاضی (جبری) نیز قابل کاربرد هستند.