سوالات

فرض کنیم مدل M به‌صورت زیر تعریف شده است: دامنه‌ی M مجموعه‌ی ۰,۱,۲,۳,۴ است. نماد تابعی یک موضعی f به‌صورت به‌علاوه‌یک به پیمانه‌ی ۵ تغییر می‌شود. یعنی f(n) = n+۱ mod ۵ نماد رابطه‌ای دو موضعی R(x,y)…

فرض کنیم مدل M به‌صورت زیر تعریف شده است: دامنه M مجموعه α, β, γ است. ثابت C به α و ثابت d به β تعبیر می‌شود. نماد رابطه‌ای یک موضعی R به‌صورت R = α, γ است. نماد رابطه‌ای دو موضعی S به‌صورت S = (α…

فرض کنیم مدل M به‌صورت زیر تعریف شده است: دامنه M مجموعه ۰, ۱, ۲ است. ثابت C به صفر تغییر می‌شود. نماد تابعی یک موضعی f به‌صورت f(۲) = ۰, f(۱) = ۲, f(۰) = ۱ است. نماد رابطه‌ای دو موضعی R به‌صورت R =…

مثال زیر از استنتاج طبیعی برای سورها را درنظربگیرید:, 1. ∀ x P(x,x);, 2. P(u,u) (∀ E, 1);, 3. ∃ z P(u,z) (∃ I, 2);, 4. ∀ y ∃ z P(y,z) (?, 1-3);, 5. ∀ x P(x,x)→∀ y ∃ z P(y,z) (→ I, 1-4) به‌جای ؟ کدام…

…دیگر ارزش نادرست دارد: در به‌دست آوردن فرم نرمال عطفی (CNF) این فرمول از روی جدول ارزش، از دو عبارت زیر کدام ظاهر می‌شود؟ A B C α - - - - T T F T T F F T F T T T F F T T الف ــ (¬ A) ∨ (¬ B) ∨ (¬ C)…

دو عبارت زیر را درنظربگیرید: الف ــ قضیه ناتمامیت گودل نشان می‌دهد که هیچ سیستم استنتاجی کامل برای منطق مرتبه اول کلاسیک وجود ندارد. ب ــ اگر سیستم استنتاجی ناسازگار باشد می‌توان هر فرمولی را در آن…

مجموعه A را متعدی گوئیم هرگاه از x ∈ y ∈ A نتیجه شود x ∈ A . دو شرط زیر را در مورد مجموعه A در نظر بگیرید: الف) bigcup A ⊆ A ب) A ⊆ P(A) از این دو شرط کدام معادل متعدی بودن A است.

دو عبارت زیر را در نظر بگیرید: الف ــ کاردینال مجموعه اعداد حقیقی بین ۰ و ۱ با کاردینال مجموعه اعداد حقیقی برابر است. ب ــ کاردینال بازه (۰ ,۱) با کاردینال [۰ ,۱] برابر است. از این دو عبارت کدام درست…

فرض کنیم V_(∘) = φ ، V_(α+1) = P(V_α) و اگر β اوردینال حدی باشد V_β = bigcup_(α<β) V_α . دو عبارت زیر را در نظر بگیرید: الف ــ عدد طبیعی ۲ به‌عنوان یک اوردینال برابر V_2 است. ب ــ عدد طبیعی ۳…

فرض کنیم V_۰ = φ ، V_(α+1) = P(V_α) و اگر β اوردینال حدی باشد V_β = bigcup_(α<β) V_α . دو عبارت زیر را در نظر بگیرید: الف ــ عدد طبیعی n به‌عنوان یک اوردینال عضو V_(n+1) است. ب ــ ω = ۰, ۱, ۲, ... ∈…

می‌دانیم ω کوچک‌ترین اوردینال نامتناهی است. دو عبارت زیر را در نظر بگیرید: الف ـ ω + ۳ = ω ب ـ ۳ + ω = ω از این دو عبارت کدام درست است؟

دو عبارت زیر را در نظر بگیرید: الف ــ یک تابع دوسوئی (یک به یک و پوشا) بین مجموعه تمام زیرمجموعه‌های متناهی N و خود N وجود دارد. ب ــ اگر B subsetneq A و A نامتناهی باشد آنگاه هیچ تابع دوسوئی بین A و…

دو عبارت زیر را در نظر بگیرید: الف ــ با استفاده از اصل تصریح (Axiom Schema of Comprehension) در نظریه مجموعه‌ها می‌توان ثابت کرد که اشتراک دو مجموعه یک مجموعه است. ب ــ اصل نظم (Regularity) نتیجه…

۱۰۸- تابع f:(۰,۱)×(۰,۱)→(۰,۱) تعریف شده براساس بسط اعشاری نامتناهی منحصربه‌فرد اعداد حقیقی بین صفر و یک با ضابطه زیر تعریف شده است: کدام‌یک در مورد این تابع درست است؟ f(۰/a_۱ a_۲ …, ۰/b_۱ b_۲…

فرض کنیم A مجموعه همه توابع از مجموعه اعداد گویا Q به مجموعه ۰،۱،۲ ، یعنی مجموعه همه توابع f:Q→ ۰،۱،۲ ، باشد. دو عبارت زیر را در نظر بگیرید: الف ــ A با مجموعه اعداد گویا Q هم توان است. ب ــ A با…

فرض کنید ω^((ω)) مجموعهٔ توابع f:ω→ω باشد که در آن‌ها مجموعهٔ supp(f)= n f(n)≠ ۰ متناهی است. برای تابع ناصفر f∈ω^((ω)) قرار می‌دهیم s(f)=max(supp(f)) . سه تابع زیر را در نظر بگیرید: f(n)= ۴۲, n=۵…

اگر R یک رابطه روی مجموعه A= a ,b ,c با ماتریس متناظر M(R)= ۰, ۱, ۱; ۰, ۱, ۰; ۱, ۰, ۱ باشد، آنگاه رابطه R∘ R کدام خواص زیر را دارد؟

دنبالهٔ (a_n) با رابطهٔ بازگشتی a_n = b_n a_(n-1) به‌ازای n ≥ ۲ (با معلوم‌بودن a_۱ ) تعریف شده است. جملهٔ عمومی a_n کدام است؟

تعداد جواب‌های صحیح نامنفی دستگاه زیر کدام است؟ x_۱ + x_۲ + x_۳ = ۵ ; x_۱ + x_۲ + x_۳ + x_۴ + x_۵ = ۲۰

گزاره ~ p ⇒ (~ q ⇒ r) هم‌ارز کدام گزاره زیر است؟

در یک امتحان دانشجو باید به ۸ سوال از ده سوال پاسخ دهد، ولی شرطی گذاشته شده است که باید دست‌کم به چهار سوال از پنج سوال اول پاسخ دهد. این دانشجو به چند طریق می‌تواند به سوالات داده شده پاسخ دهد؟

یک قفل دارای رمز ۳ رقمی فرد با ارقام ۱ تا ۹ است. اگر رمز قفل را نداشته باشیم و امتحان کردن هر رمز ۲ دقیقه طول بکشد، حداکثر چند ساعت طول می‌کشد تا قفل باز شود؟

تابع مولد دنباله‌ی a_n که در آن a_n تعداد کدهای n رقمی از ارقام ۰ و ۱ و ۲ و ۳ است که دارای حداقل یک ۱، یک ۲ و یک ۳ می‌باشد، کدام است؟

فرض کنید 2n دیسک به قطرهای d_1 تا d_2n داریم بهطوریکه d_1 < d_2 < ⋯ < d_2n سه میله موجود است که دیسکهای با قطر d_1 و d_3 و ⋯ و d_(2n-1) روی یکی و دیسکهای با قطر d_2 و d_4 و ⋯ و d_2n روی دیگری قرار…

در گراف داده‌شده، اگر p تعداد رأس‌ها (مرتبه)، q تعداد یال‌ها (اندازه)، δ کمینهٔ درجه و Δ بیشینهٔ درجه باشد، آنگاه مقدار (δ^۲ - ۵Δ)pq^۲ برابر است با:

[کراپ ناقص — به یادداشت مراجعه شود] این تصویر شامل صورت سؤال ۱۲۰ نیست؛ نشانگر چاپی آن «۱۲۱-» (سؤال ۱۲۱) است. تنها بخشِ نمایان از سؤال ۱۲۰، انتهای یکی از گزینه‌هاست: dfrac ⋯ ۳! (n!)^۳ . صورت سؤال ۱۲۰…

فرض کنیم A = ۱/۱۰∑_(i=۳)^۷C(i, ۳)C(۷, i) ، در این صورت A در کدام بازه قرار دارد؟

چند تابع مانند f: 1,⋯,5 → 1,⋯,5 وجود دارد که در شرط i<j⇒ f(i)≤ f(j) صدق می‌کند؟

فرض کنیم A تعداد رشته‌های به‌طول ۳ و با نمادهای ۰، ۱، ۲، ۳ باشد که تعداد صفرهای آن زوج است. A در کدام بازه قرار دارد؟

فرض کنیم A تعداد توابع پوشای f: ۱,۲,⋯,۶ → ۱,۲,۳,۴ باشد. دراین‌صورت A/۳۰ در کدام بازه قرار دارد؟

فرض کنیم A ضریب x^۱۴ در عبارت (۱/x+x^۲)^۱۰ باشد. دراین‌صورت A/۵ در کدام بازه قرار دارد؟

دو عبارت زیر را در مورد گراف‌ها در نظر می‌گیریم: a) هر درخت حداکثر یک تطابق کامل دارد. b) فرض کنیم G گراف ساده با ۲n رأس باشد که درجه هر رأس آن بزرگ‌تر یا مساوی n+۱ است. دراین‌صورت G تطابق کامل دارد.…

فرض کنیم x(G) عدد رنگی گراف G باشد. دو عبارت زیر را درنظر می‌گیریم: a) اگر G گراف مسطح با حداقل ۳ رأس باشد، که K_3 زیر گراف G نیست، آنگاه x(G) ≤ ۴ . b) اگر G گراف مسطح با حداقل ۳ رأس باشد که K_4…

فرض کنیم G یک گراف همبند است که دور اویلری (Euler Tour) دارد. گزاره‌های زیر را درنظر می‌گیریم: a) اگر G تعداد زوج رأس داشته باشد، آنگاه تعداد زوج یال دارد. b) اگر e و f دو یال باشند که در رأسی مشترک…

فرض کنیم A تعداد جواب‌های صحیح نامنفی معادله a+b+c=۴۰ باشد که a زوج، b≤ ۴ و c≥ ۱ است. دراین‌صورت A/۱۶ در کدام بازه قرار دارد؟

۱۳۰- فرض کنیم C(x) تابع مولد دنباله زیر باشد: c_۰ = ۱ , c_(n+۱) = ∑_(i=۰)^n c_i (n ≥ ۰) اگر C(x) = (۱-x)/(۱-ax) ، آنگاه a برابر است با: