منطق ریاضی و جبر مجموعه‌ها

مقدمه: زبان ریاضی را بیاموزیم

منطق ریاضی مانند دستور زبان ریاضیات است؛ برای درک و اثبات قضایای ریاضی باید قواعد آن را بشناسیم. این فصل پایه‌ای‌ترین مفاهیم ریاضیات را می‌سازد.

بخش اول: منطق ریاضی

گزاره جمله‌ای خبری است که دقیقاً یکی از دو ارزش «درست» یا «نادرست» را دارد؛ مثال: «عدد ۲ زوج است» (درست). جملات استفهامی، تعجبی و امری گزاره نیستند.

نقیض گزاره $p$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی را با $\sim p$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی نشان می‌دهیم: «چنین نیست که $p$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی». قانون نقیض مضاعف:

گزاره‌نما (گزاره باز) جمله‌ای با یک یا چند متغیر است که با جایگذاری مقادیر از دامنه $D$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی به گزاره تبدیل می‌شود؛ مجموعه جواب $S \subseteq D$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی زیرمجموعه‌ای است که گزاره‌نما را درست می‌کند.

ترکیب گزاره‌ها

• عطفی (AND) $p \wedge q$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی: فقط وقتی درست که هر دو درست باشند.
• فصلی (OR) $p \vee q$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی: فقط وقتی نادرست که هر دو نادرست باشند («یا»ی شامل).
• شرطی $p \Rightarrow q$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی («اگر $p$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی آنگاه $q$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی»؛ $p$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی مقدم، $q$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی تالی): فقط وقتی نادرست که مقدم درست و تالی نادرست باشد. هم‌ارزی مهم: $p \Rightarrow q \equiv \sim p \vee q$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی. عکس نقیض $p\Rightarrow q \equiv \sim q \Rightarrow \sim p$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی همیشه با اصل هم‌ارز است.
• دوشرطی $p \Leftrightarrow q$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی: درست وقتی $p,q$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی ارزش یکسان دارند؛ $p \Leftrightarrow q \equiv (p\Rightarrow q)\wedge(q\Rightarrow p)$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی.

سورها: $\forall$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی (سور عمومی، «به ازای هر») و $\exists$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی (سور وجودی، «وجود دارد»).

قوانین طلایی نقیض سورها: $\sim(\forall x; P(x)) \equiv \exists x; \sim P(x)$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی و $\sim(\exists x; P(x)) \equiv \forall x; \sim P(x)$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی — نقیض «همه» می‌شود «بعضی نیستند»، نقیض «بعضی» می‌شود «هیچ». مثال: نقیض «هر آسیایی ایرانی است» = «بعضی از آسیایی‌ها ایرانی نیستند».

بخش دوم: جبر مجموعه‌ها

$A \subseteq B \Leftrightarrow \forall x; (x\in A \Rightarrow x\in B)$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی. قضیه طلایی: اگر $A$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی دارای $n$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی عضو باشد، $2^n$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی زیرمجموعه دارد؛ مجموعه توانی $|P(A)| = 2^{|A|}$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی (هر عضو یا در زیرمجموعه هست یا نیست، پس $2^n$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی حالت).

مثال: اگر با افزودن ۲ عضو به $A$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی، زیرمجموعه‌هایش ۴۸ واحد اضافه شود: $3\times 2^n=48 \Rightarrow n=4$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی.

$A=B \Leftrightarrow (A\subseteq B)\wedge(B\subseteq A)$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی. برای اثبات $A\subseteq B$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی از روش عضوگیری دلخواه استفاده می‌شود: عضو دلخواه $x\in A$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی می‌گیریم و نشان می‌دهیم $x\in B$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی؛ مثلاً $x\in A\cap B \Rightarrow x\in A\wedge x\in B \Rightarrow x\in A$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی، پس $A\cap B\subseteq A$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی.

قوانین جبر مجموعه‌ها: جابه‌جایی/شرکت‌پذیری اجتماع و اشتراک؛ توزیع‌پذیری $A\cup(B\cap C)=(A\cup B)\cap(A\cup C)$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی؛ جذب: $A\cup(A\cap B)=A$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی.

قوانین دمورگان (بسیار مهم):

تفاضل: $A-B = A\cap B'$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی؛ توجه: $A-B \neq B-A$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی.

ضرب دکارتی: $A\times B=\{(x,y)\mid x\in A \wedge y\in B\}$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی؛ $|A\times B|=|A|\times|B|$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی و عموماً $A\times B \neq B\times A$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی.

نکات کنکوری

هم‌ارزی گزاره‌ها را با جدول ارزش بسنجید؛ برای ساده‌سازی عبارات مجموعه‌ای از دمورگان و $A-B=A\cap B'$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی کمک بگیرید؛ نمودار ون فقط برای حدس اولیه مفید است، نه اثبات رسمی.

جمع‌بندی فرمول‌های طلایی