سوالات

فرض کنید در یک مسئله عدد α_ij به‌ازای هر i و j که 1 ≤ i ≤ j ≤ n تعریف شده است و همچنین داریم: (∀ i) α_ii = 1 (∀ i < j) α_ij = min_(i ≤ k ≤ j) α_ik + α_kj + f(i,j,k) که در آن f یک تابع است که برای هر…

فرض کنید: L_1 = 0^2n1^n n ≥ 0 L_2 = a^i b^j c^k i + j = k کدام گزینه در مورد این دو زبان درست است؟

موارد زیر را در نظر بگیرید: I) کلاس زبان‌هایی که توسط NFA ها تشخیص داده می‌شوند تحت مکمل بسته‌اند. II) فرض کنیم D یک DFA باشد و C = L(D). در این صورت یک DFA دیگر مانند D̄ وجود دارد که زبان مکمل L(D)…

گرامر G با قوانین زیر را در نظر بگیرید که در آن S متغیر شروع است: S → 0S0 0S1 1S0 1S1 0 کدام رشته در زبان این گرامر قرار ندارد؟

فرض کنید: L_1 = a^n w w^R a^n : n ≥ 0, w ∈ ∘, ! ^ L_2 = a^n b^j a^n b^j : n, j ≥ 0 کدام‌یک در مورد این دو زبان درست است؟

فرض کنیم M یک DFA برای زبان زیر باشد: ‏ L = w ∈ a,b ^() : ‏ w با b شروع می‌شود با b تمام می‌شود و تعداد فردی a دارد M حداقل چند حالت دارد؟

فرض کنیم L زبان عبارت منظم زیر باشد: R = (۰+۱)^() ∘ ((۰+۱)(۰+۱)(۰+۱))^() ∘ (۰+۱)^() به‌ازای کدام مقدار برای x عبارت w = ۰۱۰۱۱۱۱x۰ در L قرار می‌گیرد؟

فرض کنیم Q یک اتوماتای شبیه به PDA باشد با این تفاوت که به جای پشته مجهز به یک نوار باشد. به عبارت دیگر، Q ماشینی متناهی‌الحالت است که با توجه به نماد ورودی فعلی، حالت فعلی و نماد جلویی نوار حرکت…

گوییم زبان L عضو کلاس C است هرگاه گرامر مستقل از متن برای آن وجود داشته باشد که همهٔ قوانین آن به‌ صورت A → xBy یا A → x باشد که x و y رشته‌های پایانی (احتمالاً تهی) هستند. این گزاره‌ها را در نظر…

کدام رشته در زبان اتوماتای زیر نیست؟

NFA زیر را در الفبای a = ∑ به DFA معادل تبدیل می‌کنیم DFA حاصل حداقل چند حالت دارد؟ (گراف: حالت شروع S، با گذارهای ε از S به A و از S به E. شاخه بالا: A با a به B، B با a به C، به‌علاوه C با ε به A و…

کدام موارد قضیه هستند؟ (الف) ((p ∧ q) ⇒ r) ⇔ ((p ⇒ r) ∧ (q ⇒ r)) (ب) ((p ∨ q) ⇒ r) ⇔ ((p ⇒ r) ∨ (q ⇒ r))

موارد زیر مفروض است: p= هوا سرد است. q= باران می‌بارد. r= نیاز به پوشیدن کلاه است. s= نیاز به پوشیدن بارانی است. کدام گزینه بیان‌گر گزاره زیر است؟ «اگر نه هوا سرد باشد نه باران ببارد، نه نیاز به…

برای یک مجموعهٔ x، منظور از P(x)، مجموعهٔ توانی x است. A و B دو مجموعهٔ دلخواه هستند. کدام گزینه ممکن است نادرست باشد؟

اعضای مجموعه‌ی ۰ ∪ℕ را به‌طور استقرایی چنین تعریف می‌کنیم: ∘ = ∅ n = (n-1) ∪ n-1 (∀ n ∈ N) در این‌صورت ۱ و ۲ به‌ترتیب چند عضوی هستند؟

اثبات کدام یک از گزاره‌های زیر نیازمند اصل انتخاب است؟ (الف) برای هر مجموعه‌ی x، رابطه‌ی ترتیب کلی ≤ روی x وجود دارد به‌طوری که برای هر y ⊆ x با y ≠ ∅ ، مجموعه‌ی y دارای بزرگ‌ترین عضو است. (ب) فرض…

A یک مجموعه سازگار و غیر ماکسیمال از گزاره‌هاست. چند تا از گزاره‌های زیر الزاماً درست است؟ (الف) گزاره‌ای مانند P وجود دارد که P ∉ A و مجموعه A ∪ P سازگار است. (ب) برای هر گزاره مانند P ، یکی از دو…

چه تعدادی از عبارت‌های زیر به‌عنوان فرمولی در منطق مرتبه اول درست هستند؟ الف) ∀ x[p(x) → Q(x)] ∧ ∀ x p(x) → ∀ x Q(x) ب) ∀ x ∃ y p(x,y) → ∃ y p(y,y) ج) ∀ y[p(x) → Q(x,y)] → [p(x) → ∀ y Q(x,y)]

کدام گزینه در مورد استدلال زیر درست است؟ فرض ۱: همه پدرها مرد هستند. فرض ۲: بعضی مردها مهربان هستند. حکم: بعضی پدرها مهربان هستند.

فرض کنید: H: خوشحال بودن من C: دقیق‌بودن منشی من T: پیداکردن شغل بهتر کدام گزینه بهترین ترجمه برای گزاره مرکب زیر با نمادهای فوق است؟ «من خوشحال می‌شوم فقط اگر منشی من دقیق باشد، اما اگر منشی من دقیق…

«هر کسی که از همهٔ بسکتبالیست‌ها بلندقدتر است از همهٔ فوتبالیست‌ها بلندقدتر است.»

کدام گزینه در مورد دو استدلال زیر درست است؟ (الف) مقدمه‌ها: ¬(s∧ t) ، ¬ w→ t . نتیجه: ∴ s→ w . (ب) مقدمه‌ها: ¬(¬ p∨ q) ، ¬ z→¬ s ، (p∧¬ q)→ s ، ¬ z∨ r . نتیجه: ∴ r .

فرض کنیم A و B دو مجموعه باشند و a ∈ A و b ∈ B . با توجه به تعریف زوج مرتب (a,b) در نظریهٔ مجموعه‌ها کدام گزینه در مورد عبارت‌های زیر درست است؟ (الف) (a,b) ∈ P(P(A ∪ B)) (ب) a,b ∈ bigcup (a,b)

فرض کنیم X یک مجموعه استقرائی باشد، تعریف می‌کنیم: A_1 = x ∈ X : x ⊆ X A_2 = x ∈ X : x متعدی است کدام گزینه صحیح است؟

فرض کنیم γ اوردینال ناصفر باشد که برای هر β < γ و α داشته باشیم α+β < γ . کدام یک از عبارت‌های زیر درست است؟ (الف) برای هر α < γ داریم α + γ = γ . (ب) γ اوردینال تالی است.

فرض کنیم P یک نماد محمولی یک‌موضعی باشد. بخش زیر از یک استنتاج در سیستم استنتاج طبیعی را در نظر بگیرید. کدام گزینه درست است؟ ⋮ ; hline P(y), z = y ⊢ P(z) ; hline P(y) ⊢ z = y → P(z) ; hline P(y) ⊢ ∀…

فرض کنیم A مجموعه همه توابع یک‌به‌یک و پوشا از [۰،۱] به [۰،۱] باشد. یعنی A = f : [۰،۱] → [۰،۱] یک‌به‌یک و پوشا است f. کدام گزینه در مورد مجموعه A صحیح است؟

در زبان L_<= < شامل یک رابطه دوتایی، فرض کنیم نظریه ترتیب‌های خطی چگال بدون نقاط انتهایی باشد و σ_۱ و σ_۲ دو جمله به‌طوری باشند که DLO∪ σ_۱ و DLO∪ σ_۲ هر دو سازگار باشند. فرض کنیم ساختارهای U_۱ و U_۲…

عبارت‌های زیر را در منطق گزاره‌ها در نظر می‌گیریم: (الف) هر مجموعه ارضاء شدنی (Satisfiable) از فرمول‌ها سازگار است. (ب) برای هر مجموعه از فرمول‌ها مانند Σ و فرمول φ اگر Σ ⊢ φ آنگاه Σ ⊨ φ . کدام گزینه…

فرض کنیم θ یک فرمول بدون سور در زبان منطق مرتبه اول باشد و ψ_1 = ∀ x_1 … ∀ x_n θ و ψ_2 = ∃ x_1 … ∃ x_n θ . فرض کنیم U زیرساخت B و s : V → U یک مقداردهی به متغیرها باشد. چه تعداد از موارد زیر درست…

فرض کنیم A مجموعه همه توابع از ...,۰,۱,۲ = w به w، B مجموعه همه توابع یک‌به‌یک و پوشا از w به w باشند و C=P(w). از مجموعه‌های A و B و C چه تعدادی از آن‌ها با مجموعه P(w)×P(w) هم‌توان (هم‌عدد) هستند؟

مقدار عبارت ∑_(k=0)^5C(6, k)C(7, 5-k) چقدراست؟

از ۱۳۶ دانشجوی یک دانشکده ۷۸ دانشجو علاقه‌مند به زبان فرانسوی، ۳۲ دانشجو علاقه‌مند به زبان آلمانی و ۵۷ دانشجو علاقه‌مند به زبان انگلیسی هستند. همچنین ۱۳ دانشجو علاقه‌مند به هر دو زبان آلمانی و…

یک مثلث متساوی‌الاضلاع که طول هر ضلع آن ۲۷ است را درنظر می‌گیریم. در مرحله اول هر ضلع آن را به سه قسمت مساوی تقسیم نموده و به جای بخش وسطی یک مثلث متساوی‌الاضلاع جدید (مطابق شکل) قرار می‌دهیم. در…

فرض کنید C صفحه شطرنجی خانه‌های هاشور نخورده (شامل ۲۴ خانه) باشد. ضریب x^3 در چند جمله‌ای رخی صفحه C چقدر است؟

فرض کنیم x تعداد رشته‌هایی به طول هشت با ارقام ۰٬۱٬...٬۹ باشد به‌طوری‌که رقمی در آن رشته وجود داشته باشد که حداقل سه بار ظاهر شده است. اگر قرار دهیم y = x / ۱٬۰۰۰٬۰۰۰ در این‌صورت y در کدام بازه قرار…

تابع مولد دنباله ۲, ۳, ۴, ۵,... کدام است؟

تعداد زیردرخت‌های فراگیر گراف مقابل چند است؟

چند مکعب مستطیل ۱×۲×۳ درون یک مکعب ۵×۵×۵ قرار دارد؟

مجموع اعداد ۵ رقمی با ارقام فرد متمایز (مثلاً ۳۱۹۷۵)، یک عدد چند رقمی است؟