توابع منطقی

در این مسئله با توابع اندیس‌دار که مقدار برگشتی آن‌ها $True$ یا $False$ است سر و کار داریم. مثلا ممکن است تابع اندیس‌دار $F$‌را به صورت زیر تعریف کنیم:

$$f_i(x) = \begin{cases} True & \text{i+x=2k} \\ False & \text{o.w.} \end{cases}$$

برای معرفی چنین تابعی از زبانی با ساختار خاص استفاده می‌کنیم که در آن سه نماد $i$، $n$ و $p$‌ به شرح زیر معرفی می‌شوند:

• $i$‌ مقدار صفر
• $n$‌ مقدار بعدی
• $p$‌ مقدار قبلی

به عنوان مثال $inn$‌نشان‌گر ۲ و $ip$ نشان‌گر مقدار $-1$ است.

در این زبان یک تابع اندیس‌دار به این صورت مشخص می‌شود که در سمت چپ با نشانه‌های گفته شده‌ی $i,n,p$ پارامتر را مشخص کرده و سپس یک حرف الفبای لاتین به نشانه‌ی نام تابع و سپس با همان نشانه‌ها اندیس می‌آوریم. به عنوان مثال $F_2(-1)$ با $ipFinn$‌مشخص می‌شود. همچنین یک برنامه‌ی مفسر، تابع‌های مورد نظر خود را با دو نوع گزاره معرفی می‌کند:

• گزاره‌ی اولیه که با مشخص کردن یک تابع با ندیس و پارامتر آن نوشته می‌شود و به معنای درست بودن آن است! مثلا $inFi$ یعنی $F_0(1)=True$.
• گزاره‌ی شرطی که به فرم یک ترکیب شرطی است و نشان می‌دهد اگر تابع سمت چپ درست باشد تابع سمت راست نیز درست است. در ضمن اگر در تابع سمت چپ، اندیس یا پارامتر مشخص نشود، می‌توان در سمت راست مقدار آن را با $n,p$ تغییر داد و یک گزاره‌ی سوری ساخت! مثلا $Fi\rightarrow nGin$ معادل $\forall x :F_0(x) \rightarrow G_1(x+1)$ و $G\rightarrow iGpp$‌به معنای $\forall x,y :G_x(y) \rightarrow G_{x-2}(0)$ است.

اگر در برنامه‌ای $F_0(x)$‌درست باشد، می‌گوییم برنامه، $x$‌را تولید می‌کند. به عنوان مثال برنامه‌ی زیر اعداد زوج را تولید می‌کند:

1. برنامه‌ای بنویسید که در آن $F_i(x)=True$ اگر و فقط اگر $x+i$ مضرب مثبت ۳ باشد.
2. برنامه‌ای بنویسید که توان‌های مثبت ۲ را تولید کند.

• سوال بعد
• سوال قبل