سوالات

همه موارد زیر صحیح‌اند، به‌جز:

فرض کنید تعبیرهای زیر را برای اعداد طبیعی در نظریهٔ مجموعه‌های ZFC داشته باشیم: ∅ := ، 1 := ∘ ، 2 := ∘,1 و ........ ، ⟨ x,y⟩ := x , x,y ، در این صورت چند تا از احکام زیر درست هستند؟ الف) bigcup(n+1)…

کدام‌یک از هم‌ارزی‌های منطقی ادعا شده زیر برقرار است؟

برای اثبات کدام‌یک از احکام زیر به اصل انتخاب نیاز نیست؟

کدام‌یک از مجموعهٔ ادواتِ معرفی شده، به‌طور تابعی کامل نیست؟

تابع بازگشتی f روی گزاره‌های منطق گزاره‌ها به‌صورت استقرایی تعریف می‌شود. برای هر P اتمی: −f(p) = ۱ −f(¬A) = ۲f(A) −f(A ∧ B) = ۳ × f(A) × f(B) −f(A → B) = ۷ × f(A) × f(B) −f(A ∨ B) = ۵ × f(A) × f(B)…

می‌خواهیم تابع f را به‌صورت استقرایی روی گزاره‌ها (فرمول‌های منطق گزاره‌ای که با اتم‌های P₁، P₂، ... و ادوات منطقی ∧، ∨، ¬، → ساخته شده‌اند) طوری تعریف کنیم که برای هر A که در فرم نرمال عطفی باشد…

فرض کنید A(p,q,r) یک گزاره باشد که در آن تنها از سه متغیر اتمی p و q و r استفاده شده و می‌دانیم (p → (q → r)) → A همانگو (راستگو، صادق) است. حداکثر چند گزارهٔ غیرمعادل A می‌تواند باشد؟

همهٔ احکام زیر صحیح‌اند، به‌جز:

فرض کنید Γ مجموعه‌ای از گزاره‌ها باشد. گوییم Δ یک پایه برای Γ است، اگر (۱) Δ ⊆ Γ و (۲) برای هر A ∈ Γ داریم Δ ⊢ A (۳) برای هر B ∈ Δ داریم Δ ∖ B nvdash B . کدام‌یک از احکام زیر درست است؟

اگر برای مجموعهٔ X مجموعهٔ توانی X را با P(X) نشان داده و برای هر n قرار دهید: P^((n))(X)=P(P^((n-1))(X)) . در این صورت عدد اصلی مجموعهٔ P^۵(φ) کدام است؟

فرض کنید که S ساختاری در یک زبان مرتبهٔ اول شامل نماد تساوی و با جهان ۱,۲ باشد. S چه تعداد از جملات زیر را برآورده می‌کند؟ ∃ x_1 ∃ x_2 x_1 ≠ x_2 ∃ x_1 ∃ x_2 ∀ x (x = x_1 ∨ x = x_2) ∀ x_1 ∀ x_2 (x_1 ≠…

چند مورد از گزاره‌های زیر معتبر است؟ p → (q → p) ((p → q) ∧ ¬ q) → ¬ p (p → q) → ((p → ¬ q) → ¬ p) p → (q → (p ∧ q))

فرض کنید Σ مجموعه‌ای از گزاره‌هایی باشد که از اتم‌هایی که از اتم‌های (نمادهای گزاره‌ای ساده) A_1, …, A_n تشکیل شده‌اند. کدام‌یک از ادعاهای زیر همواره درست است؟

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

فرض کنید X یک مجموعه نامتناهی و P یک افراز X باشد. اصل انتخاب میگوید یک زیرمجموعه X مانند R وجود دارد بهطوریکه:

در یک قطعه از یک برنامه کامپیوتری، n متغیری صحیح است و آرایه ‎A[1] ، ...، A[20]‎ به‌صورت زیر تعریف شده است: for n := 1 to 20 do A[n] := n n - n کدام‌یک از گزاره‌های زیر صحیح است؟

نقیض سور (∃x)[p(x) → (q(x) ∧ r(x)) ] کدام است؟

کدام‌یک از گزاره‌های زیر همواره درست است؟

اگر نظریه Γ ∪ φ → ψ سازگار باشد، آنگاه کدام مورد صحیح است؟

همه استنتاج‌های زیر درست‌اند، به‌جز:

به چند طریق می‌توان ۷ مهره رُخ یکسان را در یک صفحه شطرنجی ۸×۸ قرار داد به‌طوری که هیچ دوتایی از آن‌ها همدیگر را تهدید نکنند؟ (یعنی هیچ دو مهره‌ای در یک سطر یا در یک ستون نباشند)

گراف G به‌صورت «هر زیر مجموعه ۳ عضوی از ۱,۲,...,۱۰ را یک رأس گراف در نظر می‌گیریم. دو رأس A و B را به هم وصل می‌کنیم هرگاه A ∩ B = φ » تعریف می‌شود. این گراف چند یال دارد؟

حداقل چه تعداد عدد متمایز دلخواه از مجموعهٔ 1,2,…,10 باید برداریم تا مطمئن باشیم که در بین اعداد انتخاب‌شده، دو عدد با ب.م.م بزرگتر از ۱ وجود دارد؟

به چند طریق رئوس گراف زیر را با ۵ رنگ مختلف رنگ‌آمیزی کرد به‌طوری که هیچ دو رأس مجاوری هم رنگ نباشند؟ (امکان دارد از بعضی از رنگ‌ها استفاده نشود.)

اگر تابع مولد دنباله‌ی a_n _(n=0)^(∞) برابر A(x) و تابع مولد دنباله‌ی b_n _(n=0)^(∞) برابر B(x) باشد، آنگاه اگر C_n _(n=0)^(∞) دنباله‌ی متناظر با تابع مولد A(x^2)+xB(x^2) باشد، C_2019 برابر است با:

تعداد راه‌های افراز 1,…,8 به زیر مجموعه‌های ۲ یا ۴ عضوی برابر است با:

می‌خواهیم با شرایط زیر ۲۰ عدد میوه بخریم: (۱) تعداد سیب‌ها زوج باشد. (۲) تعداد موزها مضرب ۳ باشد. (۳) حداکثر ۱ هندوانه بخریم. (۴) حداکثر ۲ طالبی بخریم. چند روش برای انجام خرید فوق وجود دارد؟

تعداد جایگشت‌های (Π_1, …, Π_10) از مجموعهٔ 1, …, 10 به‌طوری‌که به‌ازای هر 1 ≤ k ≤ 10 داشته باشیم π_k - k ≤ 1 ، برابر است با:

برای هر جایگشت π = (π_1, π_2, …, π_n) از اعضای X = 1, 2, …, n ، f_k(π) برابر تعداد زیرمجموعه‌های k عضوی A از X تعریف می‌شود به‌طوری که A = π(a) a ∈ A . به‌عنوان مثال برای جایگشت π = (231564) از X =…

می‌خواهیم سه مجموعه‌ی A ، B و C از زیرمجموعه‌های مجموعه‌ی X= 1,2,3,4,5 انتخاب کنیم به‌طوری که A⊆ B⊂ C و A≠ B و B≠ C باشد به چند طریق این کار امکان‌پذیر است؟

گراف مسطح و همبند G از مرتبه ۱۰، دقیقاً ۴ وجه مثلث شکل دارد. حداکثر تعداد یال‌های G چقدر است؟

رابطهٔ R روی گراف‌های متناهی از مرتبه ۴ به‌صورت زیر تعریف می‌شود: GRH ⇔ q(G) = q(H), Δ(G) = Δ(H) چند کلاس هم‌ارزی تحت این رابطه، ایجاد می‌شود؟

کمترین مقدار n را بیابید بهطوری که گزاره زیر همیشه درست باشد: «یال‌های K_n را به هر شکل دلخواه با دو رنگ قرمز و آبی رنگ کنیم حداقل یک مسیر تک‌رنگ به طول ۳ وجود دارد.»

گراف زیر دارای چند درخت فراگیر است؟

تعداد درخت‌های فراگیر گراف برچسب‌گذاری شدهٔ K_5 با Δ ≤ 3 برابر است با (منظور از Δ ماکزیمم درجهٔ درخت مورد نظر است.)

تعداد n بیضی در صفحه رسم شده‌اند به‌طوری که هر دو بیضی یکدیگر را در ۲ نقطه قطع می‌کنند و هیچ ۳ بیضی از یک نقطه نمی‌گذرند. اگر تعداد نواحی ایجاد شده در صفحه را r_n بنامیم، مقدار r_۱۰۰ برابر است با:

تعداد رابطه‌های پادمتقارن روی مجموعه A = ۱,۲,۳,۴ که شامل (۱,۲) باشد اما شامل (۳,۴) نباشد، چندتاست؟

متحرکی در نقطه (۰،۰) از صفحه مختصات قرار دارد، این متحرک می‌تواند دو نوع حرکت به‌صورت S : (x,y) → (x+۱,y+۱) و R : (x,y) → (x+۱,y) انجام دهد. این متحرک به چند طریق می‌تواند به نقطه (۱۶،۱۰) برسد…

دو دور C_5 و C_6 که از طریق یک یال به هم چسبانده‌ایم به چند طریق می‌توان رئوس این گراف را با ۳ رنگ، رنگ کرد به‌طوری که هیچ دو رأس مجاوری همرنگ نباشند؟