۱۰۰ هزار تومان هدیهٔ ثبت‌نام، تا ۱ میلیونبا ثبت‌نام گردونهٔ هدیه را بچرخان: دست‌کم ۱۰۰٬۰۰۰ تومان و تا ۱٬۰۰۰٬۰۰۰ تومان اعتبار هدیه، بدون کارت بانکیگردونهٔ هدیه۱ میلیون برای تو، ۱ میلیون برای دوستتدوستانت را دعوت کن: برای هر دوستی که فعال شود ۱٬۰۰۰٬۰۰۰ تومان اعتبار هدیه می‌گیری و خودش هم ۱٬۰۰۰٬۰۰۰ تومانجوایز
1xAi

خلاصه درس فصل ۱ آمار و احتمال یازدهم؛ درسنامه و نکات مهم

«آشنایی با مبانی ریاضیات»: ۱۲ درس، هر کدام با توضیح مفاهیم، مثال حل‌شده و نکات مهم.

  • آمار و احتمال
  • پایهٔ یازدهم
  • صفحهٔ ۱ تا ۳۴

این درسنامه را هوش مصنوعی 1xAi از روی صفحه‌های همان درس در کتاب درسی نوشته است (برچسب «تولید هوش مصنوعی»). کنار توضیح‌ها شمارهٔ صفحهٔ کتاب آمده تا با کتاب مقایسه کنی، و مثال حل‌شدهٔ هر درس یک بار دیگر جداگانه حل و بررسی شده؛ مثالی که درست درنیامده حذف شده است.

درس ۱ · صفحهٔ ۱ تا ۴ · حدود ۱۵ دقیقه · تولید هوش مصنوعی

درس ۱: آشنایی با منطق ریاضی

در این درس یاد می‌گیری ارزش گزاره و نقیض آن را بررسی کنی، با جای‌گذاری در گزاره‌نما و در یک دامنۀ داده‌شده مجموعۀ جواب را پیدا کنی و رابط‌های گزاره‌ای و ترکیب عطفی را بشناسی.

پیش از شروع

اگر کسی بگوید «چنین نیست که حرفت نادرست باشد»، حرفت را تأیید کرده یا رد کرده است؟

حرفت را تأیید کرده است! با یک بار نقیض‌کردن، ارزش گزاره عوض می‌شود؛ با بار دوم، به ارزش اولیه برمی‌گردیم. در این درس یاد می‌گیری این جور جمله‌ها را دقیق و مرحله‌به‌مرحله بررسی کنی.

دو ارزش، چهار حالت

دو ارزش، چهار حالت

در منطق، به جمله‌ای خبری که راست یا دروغ باشد، گزاره می‌گوییم. درست یا نادرست بودن آن هم ارزش گزاره است. هر گزاره فقط یکی از این دو ارزش را دارد؛ ندانستنِ پاسخ، ارزش سومی ایجاد نمی‌کند!

مثلاً «عدد 88 زوج است» ارزش درست دارد و «عدد 99 زوج است» ارزش نادرست. برای کوتاه‌نویسی، گزاره‌ها را با حرف‌هایی مانند pp و qq نشان می‌دهیم.

حالا دو گزارۀ روزمره را در نظر بگیر: pp یعنی «چراغ اتاق روشن است» و qq یعنی «در اتاق باز است». روشن بودن چراغ، باز یا بسته بودن در را تعیین نمی‌کند. پس برای ارزش این دو گزاره، همۀ حالت‌های ممکن چنین‌اند:

ارزش ppارزش qq
درستدرست
درستنادرست
نادرستدرست
نادرستنادرست

پس برای دو گزاره، چهار حالتِ ارزش در نظر می‌گیریم. هر ردیف، یک حالت ممکن است؛ نه اینکه هر دو گزاره هم‌زمان چند ارزش داشته باشند.

کتاب درسی، صفحهٔ ۲

نقیض و برگشت به آغاز

نقیض و برگشت به آغاز

فرض کن دوستت می‌گوید: «چنین نیست که حرفت نادرست باشد.» او در واقع درست‌بودن حرفت را تأیید می‌کند! برای فهمیدن این جمله، باید اثر «نقیض» را بشناسیم.

نقیض یک گزاره، ارزش آن را برعکس می‌کند. نقیضِ گزارۀ pp را با ∼p\sim p نشان می‌دهیم و «چنین نیست که pp» می‌خوانیم. اگر pp درست باشد، نقیضش نادرست است؛ اگر pp نادرست باشد، نقیضش درست است.

حالا اگر دوباره نقیض بگیریم، ارزش یک بار دیگر برعکس می‌شود و به حالت آغاز برمی‌گردد:

pp∼p\sim p∼(∼p)\sim(\sim p)
درستنادرستدرست
نادرستدرستنادرست

دو گزاره‌ای که در تمام حالت‌ها ارزش یکسان دارند، «هم‌ارز» نامیده می‌شوند. پس می‌نویسیم:

p≡∼(∼p)p \equiv \sim(\sim p)

دقت کن: نقیض گرفتن همیشه به معنی نادرست‌کردن نیست؛ یعنی عوض‌کردن ارزش.

کتاب درسی، صفحهٔ ۳

جای خالیِ متغیر

جای خالیِ متغیر

جملۀ «aa عددی فرد است» را در نظر بگیر. تا وقتی مقدار aa مشخص نشده، نمی‌توانیم ارزش این جمله را تعیین کنیم؛ درست مثل جای خالی‌ای که منتظر پر شدن است. چنین جملۀ خبری‌ای گزاره‌نما نام دارد: متغیر دارد و با جای‌گذاری مقدار به جای متغیر، به گزاره تبدیل می‌شود.

اگر a=3a=3 بگذاریم، جملۀ «33 عددی فرد است» به دست می‌آید که درست است. اگر a=4a=4 بگذاریم، گزارۀ حاصل نادرست است. پس جای‌گذاری، گزاره می‌سازد؛ نه لزوماً گزارۀ درست!

گزاره‌نما ممکن است بیش از یک متغیر داشته باشد. مثلاً x+y=7x+y=7 دو متغیر دارد؛ برای تعیین ارزش گزارۀ حاصل، باید به جای هر دو متغیر مقدار بگذاریم. تعداد متغیرهاست که مشخص می‌کند گزاره‌نما یک‌متغیره، دومتغیره یا بیشتر است.

کتاب درسی، صفحهٔ ۳

دامنه با جواب فرق دارد

دامنه با جواب فرق دارد

در یک گزاره‌نما، دامنۀ متغیر مجموعهٔ مقدارهایی است که اجازه داریم به جای متغیر بگذاریم؛ آن را با DD نشان می‌دهیم. اما قرار نیست همۀ این مقدارها گزاره را درست کنند! مجموعۀ جواب، با نماد SS، فقط عضوهایی از دامنه را در بر می‌گیرد که با جای‌گذاری آن‌ها، گزاره‌ای درست به دست می‌آید.

مثلاً برای گزاره‌نمای «xx عددی زوج است»، دامنۀ داده‌شده را D={1,2,3,4}D=\{1,2,3,4\} در نظر بگیر. همۀ این عددها اجازۀ ورود دارند، ولی فقط 22 و 44 گزاره را درست می‌کنند؛ پس S={2,4}S=\{2,4\} است.

دامنه مثل فهرست مهمان‌های یک جشن است و مجموعۀ جواب مثل فهرست همان مهمان‌هایی که لباس آبی پوشیده‌اند: فهرست دوم نمی‌تواند کسی بیرون از فهرست اول داشته باشد. بنابراین همیشه داریم:

S⊆DS\subseteq D

یعنی هر عضو مجموعۀ جواب، عضو دامنه هم هست؛ ولی هر عضو دامنه لزوماً عضو مجموعۀ جواب نیست.

کتاب درسی، صفحهٔ ۴

ساختن گزاره‌های مرکب

ساختن گزاره‌های مرکب

فرض کن دو خبر داری: «امروز هوا سرد است» و «امروز باران می‌بارد». می‌توانی آن‌ها را با یک رابط کنار هم بگذاری و بگویی: «امروز هوا سرد است و باران می‌بارد». این جملۀ تازه، یک گزارۀ مرکب است.

رابط‌هایی مانند «و»، «یا» و «اگر ــ آنگاه» برای ساختن گزاره‌های مرکب به کار می‌روند. انتخاب رابط مهم است؛ مثلاً «هوا سرد است و باران می‌بارد» همان حرفِ «اگر هوا سرد باشد، آنگاه باران می‌بارد» نیست.

اگر گزارۀ اول را pp و گزارۀ دوم را qq بنامیم، ترکیب آن‌ها با «و» به شکل p∧qp \wedge q نوشته می‌شود و آن را «pp و qq» می‌خوانیم. نام این ترکیب، ترکیب عطفی است. پس هنگام تبدیل جمله به نماد، اول دو گزارۀ سازنده و بعد رابط بین آن‌ها را پیدا کن.

کتاب درسی، صفحهٔ ۴

مثال حل‌شده

گزاره‌نمای x2=4x^2=4 را با دامنۀ D={−2,0,2,3}D=\{-2,0,2,3\} در نظر بگیر. مجموعۀ جواب را پیدا کن؛ سپس ارزش گزارۀ حاصل و نقیض آن را برای x=0x=0 مشخص کن.

  1. هر عضو دامنه را جای‌گذاری می‌کنیم و بررسی می‌کنیم که آیا تساوی برقرار می‌شود یا نه.

  2. برای x=−2x=-2 داریم (−2)2=4(-2)^2=4 و برای x=2x=2 داریم 22=42^2=4؛ پس هر دو مقدار، گزاره را درست می‌کنند.

  3. برای x=0x=0 داریم 02=0≠40^2=0\ne4 و برای x=3x=3 داریم 32=9≠43^2=9\ne4؛ پس گزاره در این دو حالت نادرست است.

  4. فقط مقدارهای درست‌کننده را در مجموعۀ جواب می‌گذاریم: S={−2,2}S=\{-2,2\}؛ همان‌طور که انتظار داریم، S⊆DS\subseteq D است.

  5. در حالت x=0x=0، گزارۀ 02=40^2=4 نادرست است؛ بنابراین نقیض آن، یعنی 02≠40^2\ne4، درست است.

جواب: مجموعۀ جواب برابر است با S={−2,2}S=\{-2,2\} و برای x=0x=0، گزارۀ حاصل نادرست و نقیض آن درست است.

نکات مهم

  • هر گزاره یکی از دو ارزش درست یا نادرست را دارد؛ نقیض ارزش آن را برعکس می‌کند و نقیضِ نقیض با خود گزاره هم‌ارز است.
  • با جای‌گذاری مقدارهای دامنۀ داده‌شده در گزاره‌نما، گزاره به دست می‌آید و فقط مقدارهایی که آن را درست می‌کنند در مجموعۀ جواب قرار می‌گیرند.
  • رابط‌های گزاره‌ای، گزاره‌های مرکب می‌سازند و ترکیب با رابط «و» را ترکیب عطفی می‌نامیم و با p∧qp\wedge q نشان می‌دهیم.

تمرین تعاملی این درس (رایگان)تمرین تعاملی این درس

درس ۲ · صفحهٔ ۴ تا ۵ · حدود ۱۲ دقیقه · تولید هوش مصنوعی

ترکیب عطفی دو گزاره

در این درس یاد می‌گیری ترکیب عطفی دو گزاره را با نماد p∧qp \wedge q بنویسی، ارزش آن را تعیین کنی و از برقرار بودن هم‌زمان دو شرط در حل یک مسئله کمک بگیری.

پیش از شروع

برای شرکت در مسابقه نوشته‌اند: «دانش‌آموز باید عضو تیم مدرسه باشد و رضایت‌نامه داشته باشد.» اگر فقط یکی از این دو شرط را داشته باشی، می‌توانی شرکت کنی؟

نه؛ اینجا «و» یعنی هر دو شرط باید هم‌زمان برقرار باشند. در منطق هم وقتی دو گزاره را با «و» ترکیب می‌کنیم، درست‌بودن یکی از آن‌ها کافی نیست.

دو گزاره با رابط «و»

دو گزاره با رابط «و»

فرض کن روی برگهٔ مسابقه نوشته‌اند: «دانش‌آموز عضو تیم مدرسه است و رضایت‌نامه دارد.» این جمله از دو گزاره ساخته شده است که هرکدام به‌تنهایی می‌توانند درست یا نادرست باشند:

  • pp: دانش‌آموز عضو تیم مدرسه است.
  • qq: دانش‌آموز رضایت‌نامه دارد.

رابط «و» این دو گزاره را به هم وصل می‌کند و یک گزارهٔ مرکب می‌سازد. به این نوع ترکیب، ترکیب عطفی می‌گوییم و آن را به‌شکل p∧qp \wedge q می‌نویسیم؛ بخوان: «pp و qq».

پس نماد ∧\wedge همان رابط منطقی «و» است و عاطف نام دارد. برای نمادگذاری یک جملهٔ عطفی، ابتدا دو گزارهٔ سازنده‌اش را مشخص کن، سپس نماد عاطف را میان نام آن‌ها بگذار. دقت کن که نام هر گزاره نمایندهٔ تمام آن گزاره است، نه فقط یک کلمه از آن.

کتاب درسی، صفحهٔ ۴

هر دو باید درست باشند

هر دو باید درست باشند

برای درست‌بودنِ p∧qp \wedge q، درست‌بودنِ فقط یکی از گزاره‌ها کافی نیست؛ هر دو گزاره باید درست باشند. حتی اگر یکی از آن‌ها نادرست باشد، کل ترکیب عطفی نادرست می‌شود.

مثلاً این جمله را در نظر بگیر: «سارا کتابش را آورده است و تکلیفش را انجام داده است.» اگر سارا کتابش را آورده باشد، اما تکلیفش را انجام نداده باشد، این جملهٔ مرکب نادرست است؛ چون یکی از دو بخش آن برقرار نیست.

هر گزاره می‌تواند درست یا نادرست باشد؛ پس برای دو گزاره، چهار حالت داریم:

ppqqp∧qp \wedge q
درستدرستدرست
درستنادرستنادرست
نادرستدرستنادرست
نادرستنادرستنادرست

برای خواندن هر سطر، اول ارزش دو گزاره را ببین و بعد بپرس: «آیا هر دو درست‌اند؟» فقط اگر پاسخ مثبت باشد، ستون آخر «درست» می‌شود.

کتاب درسی، صفحهٔ ۵

مثال حل‌شده

مقادیر حقیقی xx و yy را بیاب که (3x−y)2+(x−2)2=0(3x-y)^2+(x-2)^2=0 باشد.

  1. هر دو عبارت مربع‌اند؛ بنابراین (3x−y)2≥0(3x-y)^2\geq0 و (x−2)2≥0(x-2)^2\geq0.

  2. مجموع دو عبارت نامنفی فقط زمانی صفر است که هر دو صفر باشند؛ پس [(3x−y)2=0]∧[(x−2)2=0][(3x-y)^2=0]\wedge[(x-2)^2=0].

  3. مربع یک عدد فقط وقتی صفر است که خود آن عدد صفر باشد؛ بنابراین [3x−y=0]∧[x−2=0][3x-y=0]\wedge[x-2=0].

  4. از شرط x−2=0x-2=0 به دست می‌آوریم x=2x=2؛ با جای‌گذاری در شرط دیگر داریم 3×2−y=03\times2-y=0، پس y=6y=6.

  5. برای بررسی، جای‌گذاری می‌کنیم: (3×2−6)2+(2−2)2=0(3\times2-6)^2+(2-2)^2=0؛ پس هر دو شرط هم‌زمان برقرارند.

جواب: x=2x=2 و y=6y=6

نکات مهم

  • ترکیب دو گزاره با رابط «و» را ترکیب عطفی می‌نامیم و به‌صورت p∧qp\wedge q می‌نویسیم.
  • ترکیب عطفی فقط وقتی درست است که هر دو گزاره درست باشند و در سه حالت دیگر نادرست است.
  • اگر مجموع دو مربع حقیقی صفر باشد، هر دو مربع باید هم‌زمان صفر باشند؛ پس دو شرط را با رابط عطفی به هم پیوند می‌دهیم.

تمرین تعاملی این درس (رایگان)تمرین تعاملی این درس

درس ۳ · صفحهٔ ۵ تا ۷ · حدود ۱۳ دقیقه · تولید هوش مصنوعی

ترکیب فصلی دو گزاره

در این درس یاد می‌گیری ترکیب فصلی دو گزاره را بنویسی، ارزش آن را با جدول تعیین کنی، تفاوتش را با ترکیب عطفی تشخیص بدهی و با قانون‌های دمورگان نقیض ترکیب‌ها را بسازی.

پیش از شروع

مدرسه می‌گوید: «پدر یا مادر برای گرفتن کارنامه بیاید.» اگر هر دو بیایند، آیا این گزاره در منطق ریاضی نادرست می‌شود؟

نه؛ در منطق ریاضی، «یا» حالتِ درست‌بودن هر دو گزاره را هم می‌پذیرد. کافی است دست‌کم یکی از دو گزاره درست باشد؛ فقط وقتی هیچ‌کدام درست نباشند، ترکیب فصلی نادرست است.

«یا» به زبان منطق

«یا» به زبان منطق

فرض کن مدرسه اعلام کند: «پدر یا مادر برای گرفتن کارنامه بیاید.» این جمله از دو گزارهٔ ساده ساخته شده که واژهٔ «یا» آن‌ها را به هم وصل می‌کند. در منطق، به چنین ترکیبی ترکیب فصلی می‌گوییم.

برای کوتاه‌نوشتن، هر گزاره را با یک حرف نام‌گذاری می‌کنیم:

  • pp: پدر برای گرفتن کارنامه می‌آید.
  • qq: مادر برای گرفتن کارنامه می‌آید.

حالا جملهٔ «پدر یا مادر برای گرفتن کارنامه می‌آید» را به شکل p∨qp \vee q می‌نویسیم و می‌خوانیم: «pp یا qq». نام نماد ∨\vee، فاصل است؛ یعنی رابط منطقیِ «یا».

پس برای نوشتن یک ترکیب فصلی، اول دو گزاره را مشخص کن و بعد نماد ∨\vee را میان نام‌هایشان بگذار. فعلاً هدفمان شناختن و نوشتن این ترکیب است؛ در کارت بعد می‌بینیم چه وقت درست یا نادرست می‌شود.

کتاب درسی، صفحهٔ ۵

چه وقت «یا» درست است؟

چه وقت «یا» درست است؟

فرض کن pp یعنی «پدر علی به مدرسه می‌آید» و qq یعنی «مادر علی به مدرسه می‌آید». برای درست‌بودن p∨qp \vee q، آمدن حداقل یکی از آن‌ها کافی است؛ اگر هر دو هم بیایند، باز گزاره درست است. فقط وقتی هیچ‌کدام نیایند، ترکیب فصلی نادرست می‌شود.

اما p∧qp \wedge q می‌گوید پدر و مادر می‌آیند؛ پس برای درست‌بودنش، باید هر دو آمده باشند.

جدول زیر این تفاوت را در همهٔ حالت‌ها نشان می‌دهد. «د» یعنی درست و «ن» یعنی نادرست:

ppqqp∨qp \vee qp∧qp \wedge q
دددد
دندن
نددن
نننن

به دو ردیف میانی دقت کن: وقتی فقط یکی از گزاره‌ها درست است، نتیجهٔ «یا» و «و» متفاوت می‌شود. پس هنگام خواندن جدول، اول رابط را ببین: «یا» حداقل یک درست می‌خواهد؛ «و» هر دو را.

کتاب درسی، صفحهٔ ۶

نقیض ترکیب‌ها و دمورگان

نقیض ترکیب‌ها و دمورگان

فرض کن pp یعنی «سارا آمده است» و qq یعنی «نیما آمده است». نقیضِ «سارا یا نیما آمده است» چیست؟ برای نادرست‌شدن این «یا»، باید هیچ‌کدام نیامده باشند؛ پس نقیض آن می‌شود: «سارا نیامده است و نیما نیامده است».

این همان قانون اول دمورگان است؛ نماد ∼\sim به معنی نقیض و نماد ≡\equiv به معنی هم‌ارزی است:

∼(p∨q)≡(∼p∧∼q)\sim(p\vee q)\equiv(\sim p\wedge\sim q)

برای نقیضِ «سارا و نیما آمده‌اند» کافی است دست‌کم یکی از آن‌ها نیامده باشد. پس قانون دوم چنین است:

∼(p∧q)≡(∼p∨∼q)\sim(p\wedge q)\equiv(\sim p\vee\sim q)

روش به‌خاطرسپردن: هنگام برداشتن نقیضِ بیرون پرانتز، هر دو گزاره را نقیض کن و «یا» و «و» را با هم عوض کن.

چرا این‌ها هم‌ارزند؟ در جدول ارزش، برای حالت‌های «درست، درست»، «درست، نادرست»، «نادرست، درست» و «نادرست، نادرست»، دو طرف قانون اول به‌ترتیب نادرست، نادرست، نادرست و درست می‌شوند. یکسان‌بودن همهٔ ردیف‌ها، هم‌ارزی را نشان می‌دهد.

کتاب درسی، صفحهٔ ۷

مثال حل‌شده

با بررسی همهٔ حالت‌های ارزش pp و qq نشان بده ∼(p∨q)\sim(p \vee q) و ∼p∧∼q\sim p \wedge \sim q هم‌ارزند.

  1. اگر pp و qq هر دو درست باشند، p∨qp \vee q درست و نقیض آن نادرست است. از طرفی، هر دو نقیض نادرست‌اند، پس ∼p∧∼q\sim p \wedge \sim q نیز نادرست است.

  2. اگر pp درست و qq نادرست باشد، p∨qp \vee q درست و نقیض آن نادرست است. در ترکیب ∼p∧∼q\sim p \wedge \sim q، گزارهٔ اول نادرست و دومی درست است، پس ترکیب عطفی نادرست می‌شود.

  3. اگر pp نادرست و qq درست باشد، باز هم نقیض ترکیب فصلی نادرست است. این بار ∼p\sim p درست و ∼q\sim q نادرست است، پس ترکیب عطفی آن‌ها نیز نادرست است.

  4. اگر هر دو گزاره نادرست باشند، p∨qp \vee q نادرست و نقیض آن درست است. هر دو نقیض نیز درست‌اند، پس ∼p∧∼q\sim p \wedge \sim q درست است.

  5. در هر چهار حالت، ارزش دو گزاره یکسان شد؛ بنابراین این دو گزاره هم‌ارزند.

جواب: ستون ارزش هر دو گزاره در ترتیب حالت‌های «درست، درست»، «درست، نادرست»، «نادرست، درست» و «نادرست، نادرست» برابر با «نادرست، نادرست، نادرست، درست» است؛ پس ∼(p∨q)≡∼p∧∼q\sim(p \vee q) \equiv \sim p \wedge \sim q.

نکات مهم

  • ترکیب فصلی با نماد p∨qp \vee q فقط وقتی نادرست است که هر دو گزاره نادرست باشند.
  • اگر فقط یکی از دو گزاره درست باشد، ترکیب فصلی درست و ترکیب عطفی نادرست است؛ اگر هر دو درست باشند، هر دو ترکیب درست‌اند.
  • قانون‌های دمورگان می‌گویند ∼(p∨q)≡∼p∧∼q\sim(p \vee q) \equiv \sim p \wedge \sim q و ∼(p∧q)≡∼p∨∼q\sim(p \wedge q) \equiv \sim p \vee \sim q.

تمرین تعاملی این درس (رایگان)تمرین تعاملی این درس

درس ۴ · صفحهٔ ۷ تا ۱۰ · حدود ۱۵ دقیقه · تولید هوش مصنوعی

ترکیب شرطی دو گزاره

در این درس یاد می‌گیری گزاره‌های شرطی و دوشرطی را بخوانی و ارزش‌گذاری کنی، شرط لازم و کافی را تشخیص بدهی و از هم‌ارزی‌ها و عکس نقیض در استدلال استفاده کنی.

پیش از شروع

چطور ممکن است گزارهٔ «اگر ماه از پنیر ساخته شده باشد، آن‌گاه تهران پایتخت ایران است» در منطق درست باشد؟

در منطق، یک گزارهٔ شرطی فقط وقتی نادرست است که فرض آن درست باشد، اما نتیجه‌اش نادرست باشد. پس وقتی فرض نادرست است، گزارهٔ شرطی را درست می‌دانیم؛ حتی اگر میان دو بخش آن ارتباط روزمره‌ای نبینیم.

فرض و حکم را بشناس

فرض و حکم را بشناس

جملهٔ «اگر عددی بر 44 بخش‌پذیر باشد، آن‌گاه زوج است» دو بخش دارد: یک فرض و یک حکم که با «اگر… آن‌گاه…» به هم وصل شده‌اند.

اگر بخش اول را pp و بخش دوم را qq بنامیم، این ترکیب را به شکل p⇒qp \Rightarrow q می‌نویسیم:

  • pp، یعنی «عدد بر 44 بخش‌پذیر است»، مقدم یا فرض است.
  • qq، یعنی «عدد زوج است»، تالی یا حکم است.

چرا می‌گوییم pp شرط کافی برای qq است؟ چون بخش‌پذیری بر 44 کافی است تا مطمئن شویم عدد زوج است.

چرا qq شرط لازم برای pp است؟ چون برای بخش‌پذیر بودن بر 44، زوج بودن ضروری است؛ عددِ غیرزوج نمی‌تواند بر 44 بخش‌پذیر باشد.

دقت کن: «لازم» به معنی «کافی» نیست! مثلاً 66 زوج است، اما بر 44 بخش‌پذیر نیست. پس در خواندن p⇒qp \Rightarrow q، جهت پیکان را حفظ کن: فرض برای حکم کافی است و حکم برای فرض لازم است.

کتاب درسی، صفحهٔ ۷

تنها حالت نادرستی

تنها حالت نادرستی

فرض کن گفته‌ام: «اگر امروز باران ببارد، آن‌گاه چتر همراه می‌برم.» چه زمانی این حرف نقض می‌شود؟ فقط وقتی باران ببارد، اما چتر همراه نبرم؛ یعنی مقدم درست و تالی نادرست باشد.

اگر باران نبارد، این جمله دربارهٔ همراه بردن یا نبردن چتر در آن وضعیت تعهدی ندارد. در منطق، وقتی مقدم نادرست باشد، گزارهٔ شرطی را به انتفای مقدم درست می‌دانیم؛ چه تالی درست باشد، چه نادرست.

پس جدول ارزش چنین است؛ «د» یعنی درست و «ن» یعنی نادرست:

ppqqp⇒qp \Rightarrow q
ددد
دنن
ندد
نند

نکتهٔ مهم این است که درستی گزارهٔ شرطی، به معنی درست بودن جداگانهٔ مقدم و تالی نیست. هنگام ارزش‌گذاری، دنبال همان حالت نقض بگرد: مقدم درست، تالی نادرست.

کتاب درسی، صفحهٔ ۸

عکس یا عکس نقیض؟

عکس یا عکس نقیض؟

در گزارهٔ p⇒qp \Rightarrow q، جابه‌جایی سادهٔ مقدم و تالی، عکس را می‌سازد: q⇒pq \Rightarrow p. اما برای ساختن عکس نقیض، هم جای دو گزاره را عوض می‌کنیم و هم هر دو را نقیض می‌کنیم: ∼q⇒∼p\sim q \Rightarrow \sim p.

مثلاً گزارهٔ «اگر شکلی مربع باشد، آن‌گاه مستطیل است» را در نظر بگیر. عکس آن می‌گوید: «اگر شکلی مستطیل باشد، مربع است»؛ این درست نیست، چون هر مستطیلی مربع نیست! ولی عکس نقیض می‌گوید: «اگر شکلی مستطیل نباشد، مربع نیست»؛ این با گزارهٔ اصلی هم‌ارز است.

هم‌ارزی یعنی دو گزاره در تمام حالت‌های ارزش‌گذاری، ارزش یکسان داشته باشند. یک بازنویسی هم‌ارز دیگر هم داریم:

(p⇒q)≡(∼p∨q)(p \Rightarrow q) \equiv (\sim p \vee q)

چرا؟ عبارت سمت راست فقط وقتی نادرست است که pp درست و qq نادرست باشد؛ درست همان حالت نادرستیِ گزارهٔ شرطی. پس برای بازنویسی شرطی می‌توانی از «یا» استفاده کنی، یا سراغ عکس نقیض بروی؛ اما جابه‌جاییِ تنها، هم‌ارزی را تضمین نمی‌کند.

کتاب درسی، صفحهٔ ۸

درست در همهٔ حالت‌ها

درست در همهٔ حالت‌ها

اینکه یک گزاره در یک حالت درست باشد، با اینکه همیشه درست باشد فرق دارد. برای گفتنِ «همیشه درست»، باید مطمئن شویم هیچ حالتی آن را نادرست نمی‌کند؛ برای «همیشه نادرست» هم باید در تمام حالت‌ها نتیجه نادرست باشد.

مثلاً pp را «امروز باران می‌بارد» بگیر. گزارهٔ p∨∼pp \vee \sim p می‌گوید «امروز باران می‌بارد یا باران نمی‌بارد». چه pp درست باشد و چه نادرست، یکی از دو بخش درست است؛ پس این ترکیب همیشه درست است. اما p∧∼pp \wedge \sim p می‌خواهد باریدن و نباریدن هم‌زمان برقرار باشند؛ پس همیشه نادرست است.

برای بررسی، دو راه داریم: جدول ارزش که همهٔ حالت‌ها را نشان می‌دهد، یا استدلالی که همهٔ حالت‌ها را پوشش دهد. مثلاً در p⇒pp \Rightarrow p، اگر pp درست باشد، مقدم و تالی هر دو درست‌اند؛ اگر نادرست باشد، شرطی به انتفای مقدم درست است. پس هیچ حالت نادرستی باقی نمی‌ماند.

کتاب درسی، صفحهٔ ۹

اگر و تنها اگر

اگر و تنها اگر

گاهی یک شرط یک‌طرفه کافی نیست و می‌خواهیم هر دو جهت برقرار باشد. مثلاً «یک عدد صحیح زوج است، اگر و تنها اگر بر دو بخش‌پذیر باشد»؛ یعنی هم از زوج بودن به بخش‌پذیری می‌رسیم و هم برعکس.

ترکیب دوشرطی را با p⇔qp \Leftrightarrow q نشان می‌دهیم و می‌خوانیم: «pp اگر و تنها اگر qq». معنای آن این است:

(p⇒q)∧(q⇒p)(p \Rightarrow q) \wedge (q \Rightarrow p)

پس pp برای qq هم شرط لازم است و هم شرط کافی.

اگر یکی از دو گزاره درست و دیگری نادرست باشد، یکی از جهت‌های شرطی نادرست می‌شود؛ بنابراین دوشرطی نادرست است. اگر هر دو درست باشند، هر دو جهت درست‌اند. نکتهٔ مهم این است که اگر هر دو نادرست هم باشند، هر دو جهت به انتفای مقدم درست‌اند!

ارزش ppارزش qqارزش p⇔qp \Leftrightarrow q
درستدرستدرست
درستنادرستنادرست
نادرستدرستنادرست
نادرستنادرستدرست

پس برای ارزش‌گذاری دوشرطی بپرس: «آیا ارزش دو طرف یکسان است؟»

کتاب درسی، صفحهٔ ۱۰

مثال حل‌شده

با استفاده از عکس نقیض ثابت کن: اگر a∈Za \in \mathbb{Z} و a2a^2 فرد باشد، آن‌گاه aa فرد است.

  1. مقدم «a2a^2 فرد است» و تالی «aa فرد است» است؛ به‌جای اثبات مستقیم، عکس نقیض را بررسی می‌کنیم.

  2. با جابه‌جایی و نقیض کردن دو بخش، عکس نقیض چنین می‌شود: «اگر aa زوج باشد، آن‌گاه a2a^2 زوج است»؛ چون در اعداد صحیح، فرد نبودن همان زوج بودن است.

  3. فرض می‌کنیم aa زوج باشد؛ پس برای یک عدد صحیح kk می‌توان نوشت: a=2ka=2k.

  4. با به توان دو رساندن داریم: a2=(2k)2=4k2=2(2k2)a^2=(2k)^2=4k^2=2(2k^2).

  5. چون 2k22k^2 عددی صحیح است، a2a^2 زوج است؛ پس عکس نقیض ثابت شد و به دلیل هم‌ارزی، گزارهٔ اصلی نیز درست است.

جواب: برای هر عدد صحیح aa، اگر a2a^2 فرد باشد، آن‌گاه aa فرد است.

نکات مهم

  • در p⇒qp \Rightarrow q، مقدم شرط کافی برای تالی و تالی شرط لازم برای مقدم است و این ترکیب فقط با مقدم درست و تالی نادرست، نادرست می‌شود.
  • گزارهٔ شرطی با ∼p∨q\sim p \vee q و عکس نقیض خود هم‌ارز است، اما لزوماً با عکس خود هم‌ارز نیست.
  • گزارهٔ همیشه درست در همهٔ حالت‌ها درست است و ترکیب دوشرطی دقیقاً وقتی درست است که دو گزاره هم‌ارزش باشند.

تمرین تعاملی این درس (رایگان)تمرین تعاملی این درس

درس ۵ · صفحهٔ ۱۰ تا ۱۱ · حدود ۱۱ دقیقه · تولید هوش مصنوعی

ترکیب دو شرطیِ دو گزاره

در این درس یاد می‌گیری ترکیب دوشرطی را بخوانی و ارزش آن را تعیین کنی و با مقایسهٔ ستون‌های جدول ارزش، هم‌ارزی منطقی دو عبارت را نشان دهی.

پیش از شروع

گزارهٔ «66 عددی اول است اگر و تنها اگر 5<25<2» از دو گزارهٔ نادرست ساخته شده است؛ آیا ممکن است خودِ این گزاره درست باشد؟

بله! در ترکیب دوشرطی، یکسان بودن ارزش دو گزاره مهم است، نه اینکه حتماً هر دو درست باشند. اینجا هر دو گزاره نادرست‌اند، پس ترکیب دوشرطی آن‌ها درست است.

دو شرط در دو جهت

دو شرط در دو جهت

وقتی می‌گوییم «اگر باران ببارد، زمین خیس می‌شود»، فقط یک جهت را بیان کرده‌ایم. از این جمله نمی‌توان نتیجه گرفت که اگر زمین خیس باشد، حتماً باران باریده است؛ شاید کسی زمین را شسته باشد!

اما در ترکیب دوشرطی، هر دو جهت را با هم می‌خواهیم:

  • اگر pp، آن‌گاه qq.
  • اگر qq، آن‌گاه pp.

این دو شرط با «و» به هم وصل می‌شوند؛ پس می‌نویسیم:

p⇔q  ≡  (p⇒q)∧(q⇒p)p \Leftrightarrow q \;\equiv\; (p \Rightarrow q) \wedge (q \Rightarrow p)

عبارت p⇔qp \Leftrightarrow q را می‌خوانیم: «pp اگر و تنها اگر qq» یا «pp شرط لازم و کافی برای qq است».

برای نمونه، «نقطه روی عمودمنصف یک پاره‌خط است اگر و تنها اگر فاصله‌اش از دو سر پاره‌خط برابر باشد» دو پیام دارد: قرارگرفتن روی عمودمنصف، برابری فاصله‌ها را نتیجه می‌دهد؛ و برابری فاصله‌ها هم قرارگرفتن روی عمودمنصف را نتیجه می‌دهد. پس هنگام دیدن «اگر و تنها اگر»، حواست به هر دو جهت باشد.

کتاب درسی، صفحهٔ ۱۰

هم‌ارزش باشند، درست است

هم‌ارزش باشند، درست است

برای تعیین ارزش p⇔qp \Leftrightarrow q، کافی است ارزش دو گزاره را مقایسه کنی: اگر یکسان باشند، دوشرطی درست است؛ اگر متفاوت باشند، نادرست است.

ارزش ppارزش qqارزش p⇔qp \Leftrightarrow q
درستدرستدرست
درستنادرستنادرست
نادرستدرستنادرست
نادرستنادرستدرست

ردیف آخر شاید عجیب باشد! یادت هست دوشرطی از p⇒qp \Rightarrow q و q⇒pq \Rightarrow p ساخته می‌شود؟ وقتی هر دو گزاره نادرست‌اند، هر دو شرطی مقدم نادرست دارند و درست‌اند؛ پس ترکیب آن‌ها با «و» هم درست است. اما وقتی ارزش‌ها متفاوت‌اند، یکی از دو شرطی از درست به نادرست می‌رود و نادرست می‌شود.

پس پاسخ پرسش آغاز درس روشن شد: «66 عددی اول است اگر و تنها اگر 5<25<2» درست است، چون دو طرف آن نادرست‌اند. درست‌بودن دوشرطی به معنی درست‌بودن تک‌تک طرف‌هایش نیست.

کتاب درسی، صفحهٔ ۱۰

اثبات با جدول ارزش

اثبات با جدول ارزش

چطور مطمئن شویم دو عبارت منطقی همیشه نتیجهٔ یکسانی دارند؟ بررسی یک حالت کافی نیست؛ باید همهٔ حالت‌های ممکن را بررسی کنیم.

برای این کار، جدول ارزش می‌سازیم: ابتدا همهٔ حالت‌های درست و نادرست بودن گزاره‌های ساده را می‌نویسیم، سپس ارزش بخش‌های کوچک‌تر و در پایان ارزش دو عبارت اصلی را پیدا می‌کنیم. اگر دو ستون نهایی در تمام ردیف‌ها یکسان باشند، دو عبارت هم‌ارز منطقی‌اند و بین آن‌ها نماد ≡\equiv می‌گذاریم. حتی یک ردیف متفاوت، هم‌ارزی را رد می‌کند.

مثلاً «دفتر و مداد همراه دارم» و «مداد و دفتر همراه دارم» با جابه‌جایی ترتیب، ارزش متفاوتی پیدا نمی‌کنند؛ بااین‌حال، اثبات جدولی باید همهٔ حالت‌های همراه داشتن یا نداشتن آن‌ها را پوشش دهد.

حواست باشد: p⇔qp\Leftrightarrow q خودش یک گزارهٔ مرکب است و می‌تواند در یک حالت درست باشد؛ اما A≡BA\equiv B می‌گوید دو عبارت AA و BB در هیچ حالتی اختلاف ارزش ندارند.

کتاب درسی، صفحهٔ ۱۱

مثال حل‌شده

با استفاده از جدول ارزش ثابت کن p∧q≡q∧pp \wedge q \equiv q \wedge p.

  1. دو ستون نهایی را برای p∧qp \wedge q و q∧pq \wedge p در نظر می‌گیریم؛ «و» فقط وقتی درست است که هر دو طرف درست باشند.

  2. اگر pp درست و qq درست باشد، مقدار هر دو عبارت درست است.

  3. اگر pp درست و qq نادرست باشد، مقدار هر دو عبارت نادرست است.

  4. اگر pp نادرست و qq درست باشد، مقدار هر دو عبارت نادرست است.

  5. اگر pp نادرست و qq نادرست باشد، مقدار هر دو عبارت نادرست است.

  6. همهٔ حالت‌ها بررسی شدند و دو ستون نهایی یکسان بودند؛ پس دو عبارت هم‌ارز منطقی‌اند.

جواب: ستون‌های ارزش در همهٔ حالت‌ها یکسان‌اند؛ بنابراین p∧q≡q∧pp \wedge q \equiv q \wedge p.

نکات مهم

  • ترکیب p⇔qp \Leftrightarrow q یعنی هر دو شرطِ p⇒qp \Rightarrow q و q⇒pq \Rightarrow p برقرار باشند.
  • دوشرطی وقتی درست است که دو طرف آن هم‌ارزش باشند، حتی اگر هر دو نادرست باشند.
  • برای اثبات هم‌ارزی منطقی با جدول ارزش، ستون‌های نهایی دو عبارت باید در تمام حالت‌های ممکن یکسان باشند.

تمرین تعاملی این درس (رایگان)تمرین تعاملی این درس

درس ۶ · صفحهٔ ۱۱ تا ۱۳ · حدود ۱۵ دقیقه · تولید هوش مصنوعی

سورها

در این درس یاد می‌گیری گزاره‌های سوری را با دامنهٔ مشخص بخوانی و بنویسی، درستی آن‌ها را بررسی کنی و نقیضشان را بسازی.

پیش از شروع

اگر کسی بگوید «همهٔ دانش‌آموزان کلاس عینکی‌اند»، برای رد کردن حرفش باید تک‌تک دانش‌آموزان را بررسی کنی یا دیدن یک نفر کافی است؟

دیدن فقط یک دانش‌آموزِ بدون عینک کافی است تا این ادعا رد شود. اما برای تأیید ادعای «بعضی از دانش‌آموزان عینکی‌اند»، پیدا کردن یک دانش‌آموز عینکی کافی است؛ تفاوت «همه» و «بعضی» روش بررسی ما را عوض می‌کند.

سورها و دامنهٔ متغیر

سورها و دامنهٔ متغیر

اگر بگویی «همهٔ دانش‌آموزان عینکی‌اند»، منظورت دانش‌آموزان کلاس خودت است یا همهٔ دانش‌آموزان مدرسه؟ بدون مشخص کردن این گروه، حرفت دقیق نیست. در ریاضی هم باید بدانیم متغیر از کدام مجموعه انتخاب می‌شود؛ این مجموعه دامنهٔ متغیر است.

واژه‌هایی مثل «هر» و «وجود دارد» را سور می‌نامیم:

  • نماد ∀\forall، سور عمومی، یعنی «برای هر».
  • نماد ∃\exists، سور وجودی، یعنی «وجود دارد» یا «دست‌کم یکی».

مثلاً جملهٔ «برای هر عدد حقیقی، مربع آن نامنفی است» را می‌نویسیم:

∀x∈R ; x2≥0\forall x\in\mathbb{R}\ ;\ x^2\geq 0

اینجا R\mathbb{R} دامنه است و نشان می‌دهد دربارهٔ عددهای حقیقی صحبت می‌کنیم.

جملهٔ «عدد صحیحی وجود دارد که از صفر کوچک‌تر است» هم می‌شود:

∃x∈Z ; x<0\exists x\in\mathbb{Z}\ ;\ x<0

برای خواندن این عبارت‌ها، به‌ترتیب سور، دامنه و ویژگی را پیدا کن: دربارهٔ چند عضو حرف می‌زنیم، از کدام مجموعه، و با چه ویژگی‌ای؟

کتاب درسی، صفحهٔ ۱۱

«همه» و مثال نقض

«همه» و مثال نقض

وقتی می‌گوییم «همهٔ دانش‌آموزان کلاس عینکی‌اند»، ادعایمان دربارهٔ تک‌تک دانش‌آموزان است. حتی اگر بیشترشان عینکی باشند، دیدن یک دانش‌آموز بدون عینک کافی است تا ادعا رد شود. به چنین موردی مثال نقض می‌گوییم.

در ریاضی هم گزارهٔ ∀x∈D; P(x)\forall x\in D;\ P(x) فقط وقتی درست است که ویژگی P(x)P(x) برای تمام اعضای دامنهٔ DD برقرار باشد. برای رد کردنش، کافی است یک عضو از همان دامنه پیدا کنیم که ویژگی را نداشته باشد.

دقت کن: پیدا کردن چند موردِ تأییدکننده، درستی یک ادعای عمومی را ثابت نمی‌کند؛ شاید عضوی که هنوز بررسی نکرده‌ایم، مثال نقض باشد! اگر دامنه بی‌نهایت عضو داشته باشد، برای اثبات درستی معمولاً به استدلالی نیاز داریم که همهٔ اعضا را پوشش دهد، نه فقط امتحان کردن چند عدد.

پس هنگام بررسی «برای هر»، از خودت بپرس: آیا دلیلم همهٔ دامنه را پوشش می‌دهد، یا فقط چند مورد را دیده‌ام؟

کتاب درسی، صفحهٔ ۱۲

«وجود دارد» یعنی دست‌کم یکی

«وجود دارد» یعنی دست‌کم یکی

اگر بگویی «بعضی از دانش‌آموزان کلاس عینکی‌اند»، دیدن حتی یک دانش‌آموز عینکی برای تأیید حرفت کافی است؛ لازم نیست بقیه را هم بررسی کنی.

در ریاضی هم سور وجودی ∃\exists همین معنا را دارد: دست‌کم یک عضو از دامنه، ویژگی موردنظر را دارد. ممکن است چند عضو یا حتی همهٔ اعضا آن ویژگی را داشته باشند؛ «وجود دارد» به معنی «فقط یکی» نیست.

برای درست بودن یک گزارهٔ وجودی، کافی است یک عضو مناسب پیدا کنیم. به این عضو «شاهد» می‌گوییم. حواست باشد شاهد حتماً باید در دامنهٔ مشخص‌شده باشد.

اما برای رد کردن گزارهٔ وجودی، پیدا کردن یک عضو نامناسب کافی نیست. اگر یک دانش‌آموز عینکی نباشد، هنوز ممکن است دیگری عینکی باشد! پس باید نشان دهیم هیچ عضوی از دامنه، ویژگی خواسته‌شده را ندارد.

کتاب درسی، صفحهٔ ۱۲

نقیض؛ تغییر سور و ویژگی

نقیض؛ تغییر سور و ویژگی

اگر بگوییم «همهٔ دانش‌آموزان کلاس عینکی‌اند»، نقیضش این نیست که «همهٔ دانش‌آموزان کلاس عینکی نیستند»! برای رد ادعای اول، کافی است دست‌کم یک دانش‌آموز کلاس عینکی نباشد؛ لازم نیست همه بدون عینک باشند.

پس هنگام نقیض کردن، دو تغییر هم‌زمان داریم: سور را عوض می‌کنیم و ویژگی را نقیض می‌کنیم. دامنه همان دامنهٔ قبلی می‌ماند. اگر دامنه را با DD و ویژگی را با P(x)P(x) نشان دهیم:

∼(∀x∈D; P(x))≡∃x∈D; ∼P(x)\sim(\forall x\in D;\ P(x))\equiv\exists x\in D;\ \sim P(x)

در جهت دیگر، نقیض «وجود دارد» می‌شود «برای همه، چنین نیست»:

∼(∃x∈D; P(x))≡∀x∈D; ∼P(x)\sim(\exists x\in D;\ P(x))\equiv\forall x\in D;\ \sim P(x)

مثلاً نقیض «بعضی از کتاب‌های این قفسه داستانی‌اند» این است: «هیچ‌کدام از کتاب‌های این قفسه داستانی نیستند»؛ یعنی هر کتاب این قفسه، داستانی نیست.

یادت باشد: فقط منفی کردن فعل کافی نیست؛ سور هم باید تغییر کند.

کتاب درسی، صفحهٔ ۱۳

مثال حل‌شده

ارزش گزارهٔ ∀x∈R; x2>0\forall x\in\mathbb{R};\ x^2>0 را تعیین کن و سپس نقیض آن را بنویس و ارزش نقیض را مشخص کن.

  1. سور عمومی می‌گوید مربع هر عدد حقیقی باید مثبت باشد؛ پس حتی یک عدد حقیقی که این ویژگی را نداشته باشد، گزاره را رد می‌کند.

  2. عدد x=0x=0 را بررسی می‌کنیم: 02=00^2=0 و عبارت 0>00>0 نادرست است؛ بنابراین گزارهٔ اصلی نادرست است.

  3. برای ساختن نقیض، ∀\forall را به ∃\exists و شرط x2>0x^2>0 را به x2≤0x^2\leq0 تبدیل می‌کنیم؛ دامنهٔ R\mathbb{R} تغییر نمی‌کند.

  4. نقیض برابر است با ∃x∈R; x2≤0\exists x\in\mathbb{R};\ x^2\leq0؛ یعنی عدد حقیقی‌ای وجود دارد که مربعش نامثبت است. این گزاره با شاهد x=0x=0 درست است.

جواب: گزارهٔ ∀x∈R; x2>0\forall x\in\mathbb{R};\ x^2>0 نادرست است؛ نقیض آن ∃x∈R; x2≤0\exists x\in\mathbb{R};\ x^2\leq0 است که با شاهد x=0x=0 درست می‌شود.

نکات مهم

  • سور عمومی ∀\forall یعنی «برای همه» و سور وجودی ∃\exists یعنی «دست‌کم یکی وجود دارد»؛ دامنهٔ متغیر نیز باید مشخص باشد.
  • یک مثال نقض برای رد گزارهٔ عمومی و یک شاهد مناسب برای اثبات گزارهٔ وجودی کافی است.
  • برای نقیض کردن گزارهٔ سوری، سور را عوض می‌کنیم و ویژگی را نقیض می‌کنیم، اما دامنه ثابت می‌ماند.

تمرین تعاملی این درس (رایگان)تمرین تعاملی این درس

درس ۷ · صفحهٔ ۱۳ تا ۱۶ · حدود ۱۵ دقیقه · تولید هوش مصنوعی

نقیض گزاره‌های سوری

در این درس یاد می‌گیری نقیض گزاره‌های دارای سور عمومی و وجودی را با حفظ دامنه و نقیض کردن درستِ شرط بنویسی و ارزش گزاره و نقیضش را با دلیل بررسی کنی.

پیش از شروع

اگر بگوییم «هر آسیایی، ایرانی است»، برای رد کردن این ادعا باید نشان بدهیم هیچ آسیایی ایرانی نیست، یا پیدا کردن یک آسیاییِ غیرایرانی کافی است؟

پیدا کردن حتی یک آسیاییِ غیرایرانی کافی است؛ مثلاً کسی که اهل چین است. نقیضِ «همه چنین‌اند»، «هیچ‌کدام چنین نیستند» نیست؛ بلکه می‌گوید «دست‌کم یکی چنین نیست».

رد کردن «همه» با یک مثال نقض

رد کردن «همه» با یک مثال نقض

فرض کن کسی بگوید: «همهٔ دانش‌آموزان کلاس با اتوبوس به مدرسه می‌آیند.» برای رد کردن حرفش لازم نیست ثابت کنی همه با وسیله‌ای دیگر می‌آیند؛ پیدا کردن یک دانش‌آموز که با اتوبوس نمی‌آید کافی است. به چنین موردی «مثال نقض» می‌گوییم.

پس نقیضِ «همه این ویژگی را دارند»، می‌شود «دست‌کم یک نفر این ویژگی را ندارد». عبارت «دست‌کم یک نفر» به معنی «فقط یک نفر» نیست؛ ممکن است چند نفر باشند.

در زبان نمادها داریم:

∼(∀x∈A; P(x))≡∃x∈A; ∼P(x)\sim(\forall x\in A;\ P(x))\equiv\exists x\in A;\ \sim P(x)

برای نوشتن نقیض، سه چیز را بررسی کن: سور عمومی به وجودی تبدیل شود، شرط نقیض شود و دامنه ثابت بماند. اگر ادعا دربارهٔ دانش‌آموزان یک کلاس است، مثال نقض هم باید از همان کلاس باشد، نه کلاسی دیگر.

فقط منفی کردن فعل کافی نیست: «همه با اتوبوس نمی‌آیند» اگر به معنی «هیچ‌کس با اتوبوس نمی‌آید» باشد، ادعایی بسیار قوی‌تر از نقیضِ موردنظر است.

کتاب درسی، صفحهٔ ۱۳

از «وجود دارد» به «هیچ‌کدام»

از «وجود دارد» به «هیچ‌کدام»

فرض کن کسی بگوید: «در این کیف، دست‌کم یک خودکار آبی وجود دارد.» برای رد کردن حرفش، پیدا کردن یک خودکار قرمز کافی نیست؛ شاید کنار آن، خودکار آبی هم باشد! باید مطمئن شویم هیچ خودکارِ داخل کیف آبی نیست؛ یعنی همهٔ خودکارهای همین کیف، غیرآبی‌اند.

پس نقیضِ «وجود دارد عضوی که شرط را دارد» این است: «همهٔ اعضا آن شرط را ندارند». به زبان نمادها:

∼(∃x∈A; P(x))≡∀x∈A; ∼P(x)\sim(\exists x\in A;\ P(x))\equiv\forall x\in A;\ \sim P(x)

برای نوشتن نقیض، سور وجودی را به سور عمومی تبدیل کن و شرط را هم نقیض کن. دامنهٔ AA همان می‌ماند؛ در مثال ما، همچنان فقط خودکارهای داخل همان کیف را بررسی می‌کنیم.

یادت باشد «وجود دارد» یعنی «دست‌کم یکی»، نه «دقیقاً یکی». بنابراین برای رد کردنش، نباید حتی یک عضو با شرط اولیه باقی بماند.

کتاب درسی، صفحهٔ ۱۳

نقیض کردنِ تمام شرط

نقیض کردنِ تمام شرط

اگر شرطِ یک گزاره چند بخش داشته باشد، عوض کردن سور به‌تنهایی کافی نیست؛ باید کل شرط را نقیض کنیم.

مثلاً «کسی در این کلاس هست که هم عینکی است و هم موهایش مشکی است» را در نظر بگیر. نقیضش می‌گوید: «هر کسی در این کلاس، یا عینکی نیست یا موهایش مشکی نیست.» لازم نیست هر دو ویژگی را نداشته باشد؛ نداشتنِ دست‌کم یکی کافی است.

پس طبق قانون دمورگان داریم:

∼(P∧Q)≡(∼P)∨(∼Q)\sim(P\wedge Q)\equiv(\sim P)\vee(\sim Q)

برای شرط‌های عددی هم باید مرزها را دقیق نگه داریم: نقیضِ y<0y<0 برابر y≥0y\ge 0 و نقیضِ y2≤1y^2\le 1 برابر y2>1y^2>1 است. بنابراین:

∼(y<0∧y2≤1)≡y≥0∨y2>1\sim(y<0\wedge y^2\le 1)\equiv y\ge 0\vee y^2>1

روش مطمئن: سور را عوض کن، دامنه را نگه دار و سپس نقیضِ تمام شرط را بنویس؛ نه فقط یکی از بخش‌های آن.

کتاب درسی، صفحهٔ ۱۴

مثال حل‌شده

ارزش گزارهٔ ∃y∈R; y>0∧y2≤4\exists y\in\mathbb{R};\ y>0\wedge y^2\le 4 را با دلیل تعیین کن و سپس نقیض آن را بنویس.

  1. برای بررسی درستیِ گزارهٔ وجودی، کافی است یک عدد حقیقی پیدا کنیم که هر دو شرط را داشته باشد.

  2. عدد y=1y=1 مناسب است؛ زیرا 1>01>0 و 12≤41^2\le 4، پس گزارهٔ اصلی درست است.

  3. برای نوشتن نقیض، سور وجودی را به عمومی تبدیل می‌کنیم و دامنه را نگه می‌داریم: ∀y∈R; ∼(y>0∧y2≤4)\forall y\in\mathbb{R};\ \sim(y>0\wedge y^2\le 4).

  4. نقیضِ «و» را با «یا» می‌نویسیم و هر شرط را نقیض می‌کنیم: ∀y∈R; y≤0∨y2>4\forall y\in\mathbb{R};\ y\le 0\vee y^2>4.

  5. نقیض نادرست است؛ چون برای y=1y=1 نه y≤0y\le 0 برقرار است و نه y2>4y^2>4، پس این عدد مثال نقضِ گزارهٔ عمومیِ به‌دست‌آمده است.

جواب: گزارهٔ اصلی درست است و نقیض آن، یعنی ∀y∈R; y≤0∨y2>4\forall y\in\mathbb{R};\ y\le 0\vee y^2>4، نادرست است.

نکات مهم

  • نقیضِ «برای هر عضو، شرط برقرار است» می‌گوید «عضوی وجود دارد که شرط برایش برقرار نیست» و یک مثال نقض برای رد ادعای عمومی کافی است.
  • نقیضِ «عضوی وجود دارد که شرط را دارد» می‌گوید «همهٔ اعضای همان دامنه، نقیض آن شرط را دارند».
  • هنگام نقیض کردن، علاوه بر تغییر سور، باید کل شرط را نقیض کنیم؛ از جمله «و» و «یا» جابه‌جا می‌شوند و >> به ≤\le تبدیل می‌شود.

تمرین تعاملی این درس (رایگان)تمرین تعاملی این درس

درس ۸ · صفحهٔ ۱۶ تا ۱۹ · حدود ۱۵ دقیقه · تولید هوش مصنوعی

درس ۲: جبر مجموعه‌ها

در این درس یاد می‌گیری … تعداد زیرمجموعه‌ها را حساب کنی، مجموعهٔ توانی را بشناسی و با تعریف نمادی زیرمجموعه و روش عضوگیری دلخواه، رابطه‌ها و برابری مجموعه‌ها را ثابت کنی.

پیش از شروع

اگر فقط دو عضو تازه به یک مجموعه اضافه کنیم، تعداد زیرمجموعه‌هایش دو برابر می‌شود یا چهار برابر؟ بدون نوشتن همهٔ زیرمجموعه‌ها چطور می‌توانیم بفهمیم؟

برای ساختن یک زیرمجموعه، دربارهٔ هر عضو دو انتخاب داریم: آن را برداریم یا برنداریم. دو عضو تازه، دو انتخاب مستقل تازه می‌آورند؛ پس تعداد حالت‌ها در 2×2=42\times2=4 ضرب می‌شود.

هر عضو، دو انتخاب

هر عضو، دو انتخاب

فرض کن می‌خواهی از بین چند برچسب، تعدادی را برای جلد دفترت انتخاب کنی. حتی می‌توانی هیچ‌کدام را انتخاب نکنی! برای هر برچسب، فقط دو حالت داری: انتخابش کنی یا انتخابش نکنی. هر انتخاب نهایی، یک زیرمجموعه از برچسب‌هاست.

برای مجموعهٔ A={a,b,c}A=\{a,b,c\} هم همین اتفاق می‌افتد. جای اعضا را به ترتیب a,b,ca,b,c ثابت می‌کنیم و برای هر عضو، «بودن» را با 11 و «نبودن» را با 00 نشان می‌دهیم. مثلاً کد 011011 یعنی aa را برنداشته‌ایم، اما bb و cc را برداشته‌ایم؛ پس این کد، زیرمجموعهٔ {b,c}\{b,c\} را مشخص می‌کند.

هر کد دقیقاً یک زیرمجموعه را مشخص می‌کند. برای هر جای کد دو انتخاب مستقل داریم؛ بنابراین طبق اصل ضرب، تعداد کدها و در نتیجه تعداد زیرمجموعه‌ها برابر است با:

2×2×2=232\times2\times2=2^3

به همین روش، برای مجموعه‌ای با nn عضو، تعداد زیرمجموعه‌ها 2n2^n است. کدِ تمام‌صفر، مجموعهٔ تهی و کدِ تمام‌یک، خود مجموعه را نشان می‌دهد؛ پس این دو هم در شمارش حساب شده‌اند.

کتاب درسی، صفحهٔ ۱۷

مجموعه‌ای از زیرمجموعه‌ها

مجموعه‌ای از زیرمجموعه‌ها

فرض کن A={a,b}A=\{a,b\} مجموعهٔ دو وسیلهٔ تو باشد. هر انتخاب از این وسایل، حتی انتخابِ هیچ‌کدام، یک زیرمجموعه است. حالا همهٔ انتخاب‌ها را در یک مجموعه جمع کنیم:

P(A)={∅,{a},{b},{a,b}}P(A)=\{\varnothing,\{a\},\{b\},\{a,b\}\}

این مجموعهٔ توانیِ AA است؛ اعضای آن، خودشان مجموعه‌اند! چون AA دو عضو دارد، مجموعهٔ توانی‌اش 22=42^2=4 عضو دارد.

به تفاوت نمادها دقت کن: a∈Aa\in A یعنی خودِ aa عضوِ AA است؛ اما {a}⊆A\{a\}\subseteq A یعنی مجموعهٔ تک‌عضویِ {a}\{a\} زیرمجموعهٔ AA است. همین مجموعه، یک عضوِ مجموعهٔ توانی هم هست: {a}∈P(A)\{a\}\in P(A).

خودِ AA هم زیرمجموعهٔ خودش است؛ ولی زیرمجموعهٔ سره نیست. زیرمجموعهٔ سره باید با مجموعهٔ اصلی نابرابر باشد؛ مثل {a}\{a\} در این مثال.

یک نکتهٔ ظریف: در B={a,{a},∅}B=\{a,\{a\},\varnothing\}، سه عضوِ متمایز داریم. تهی هم اینجا یک عضو است و نباید هنگام شمردن نادیده گرفته شود.

کتاب درسی، صفحهٔ ۱۷

همهٔ اعضا یا یک مثال نقض

همهٔ اعضا یا یک مثال نقض

فرض کن AA مجموعهٔ دانش‌آموزان یک کلاس و BB مجموعهٔ اعضای کتابخانه باشد. برای اینکه بگوییم A⊆BA\subseteq B، باید همهٔ دانش‌آموزان آن کلاس عضو کتابخانه باشند؛ عضو بودن چند نفر کافی نیست.

تعریف نمادی همین حرف است:

A⊆B⇔∀x; (x∈A⇒x∈B)A\subseteq B\Leftrightarrow\forall x;\ (x\in A\Rightarrow x\in B)

نماد ∀\forall یعنی «برای هر». پس هر عضوی از AA را که در نظر بگیریم، باید در BB هم باشد. لازم نیست هر عضو BB در AA باشد؛ کتابخانه می‌تواند اعضای دیگری هم داشته باشد.

حالا اگر حتی یک دانش‌آموز کلاس عضو کتابخانه نباشد، ادعای زیرمجموعه‌بودن رد می‌شود. به چنین عضوی مثال نقض می‌گوییم:

A⊈B⇔∃x; (x∈A∧x∉B)A\not\subseteq B\Leftrightarrow\exists x;\ (x\in A\wedge x\notin B)

نماد ∃\exists یعنی «وجود دارد» و ∧\wedge یعنی «و». دقت کن: مثال نقض باید در مجموعهٔ اول باشد و در دومی نباشد؛ پیدا کردن عضوی در جهت برعکس، ادعای ما را رد نمی‌کند.

کتاب درسی، صفحهٔ ۱۷

از یک عضو دلخواه شروع کن

از یک عضو دلخواه شروع کن

برای اثبات A⊆BA\subseteq B لازم نیست اعضا را فهرست کنیم. فرض می‌کنیم xx عضوی دلخواه از AA است و با کمک فرض‌ها نشان می‌دهیم x∈Bx\in B. دلخواه یعنی هیچ ویژگی ویژه‌ای برای این عضو انتخاب نکرده‌ایم؛ پس استدلال دربارهٔ همهٔ اعضای AA معتبر است.

ویژگی زنجیره‌ای: اگر A⊆BA\subseteq B و B⊆CB\subseteq C، مسیر عضو چنین است:

x∈A⇒x∈B⇒x∈Cx\in A\Rightarrow x\in B\Rightarrow x\in C

پس A⊆CA\subseteq C. مثل اینکه هر عضو تیم مدرسه، دانش‌آموز مدرسه و هر دانش‌آموز مدرسه، عضو کتابخانه باشد؛ آن‌گاه هر عضو تیم، عضو کتابخانه هم هست.

متمم‌ها: متمم AA نسبت به مرجع UU، شامل اعضای UU است که در AA نیستند. اگر A⊆BA\subseteq B، عضوی دلخواه از B′B' بگیر؛ این عضو در BB نیست، پس نمی‌تواند در AA باشد، وگرنه طبق فرض باید در BB هم می‌بود! بنابراین در A′A' است و B′⊆A′B'\subseteq A'.

مجموعهٔ تهی: برای ∅⊆A\varnothing\subseteq A نمی‌توان عضوی از تهی برداشت. اما گزارهٔ شرطیِ x∈∅⇒x∈Ax\in\varnothing\Rightarrow x\in A همیشه درست است، چون مقدّم آن نادرست است؛ پس تهی زیرمجموعهٔ هر مجموعه است.

کتاب درسی، صفحهٔ ۱۸

برابری یعنی دو مسیر

برابری یعنی دو مسیر

فرض کن AA مجموعهٔ اعضای گروه ورزش و BB مجموعهٔ اعضای گروه هنر مدرسه باشد. هر عضو گروه ورزش، حتماً در مجموعهٔ «اعضای ورزش یا هنر» حضور دارد؛ پس A⊆A∪BA\subseteq A\cup B. در زبان نمادی، از x∈Ax\in A به x∈A∪Bx\in A\cup B می‌رسیم؛ لازم نیست آن عضو در هر دو گروه باشد.

حالا اگر A⊆CA\subseteq C و B⊆CB\subseteq C باشند، عضو دلخواه x∈A∪Bx\in A\cup B را دنبال کن: این عضو در AA یا در BB است. در هر حالت، طبق فرض‌ها در CC قرار دارد؛ بنابراین A∪B⊆CA\cup B\subseteq C.

اما زیرمجموعه‌بودن در یک جهت، برابری نیست؛ شاید مجموعهٔ دوم اعضای بیشتری داشته باشد. برای برابری باید هر دو مسیر را بررسی کنیم:

A=B⇔[(A⊆B)∧(B⊆A)]A=B\Leftrightarrow[(A\subseteq B)\wedge(B\subseteq A)]

پس در اثبات برابری، یک بار از عضو دلخواه مجموعهٔ اول شروع می‌کنیم و به دومی می‌رسیم؛ بار دیگر مسیر برعکس را می‌رویم. با این کار مطمئن می‌شویم هیچ‌کدام عضو اضافه‌ای ندارد.

کتاب درسی، صفحهٔ ۱۹

مثال حل‌شده

اگر به مجموعهٔ متناهی AA، دو عضو تازه و متمایز اضافه کنیم، تعداد زیرمجموعه‌های آن 2424 تا بیشتر می‌شود؛ مجموعهٔ اولیه چند عضو دارد؟

  1. تعداد اعضای اولیه را nn می‌نامیم؛ پس تعداد زیرمجموعه‌های اولیه 2n2^n است.

  2. با اضافه‌شدن دو عضو تازه، تعداد اعضا n+2n+2 و تعداد زیرمجموعه‌ها 2n+22^{n+2} می‌شود.

  3. افزایش تعداد زیرمجموعه‌ها برابر با 2424 است؛ بنابراین 2n+2−2n=242^{n+2}-2^n=24.

  4. چون 2n+2=4×2n2^{n+2}=4\times2^n، داریم 3×2n=243\times2^n=24 و در نتیجه 2n=82^n=8.

  5. از 8=238=2^3 نتیجه می‌گیریم n=3n=3؛ برای بررسی نیز 25−23=32−8=242^5-2^3=32-8=24 است.

جواب: مجموعهٔ اولیه 33 عضو دارد.

نکات مهم

  • یک مجموعهٔ nn عضوی، 2n2^n زیرمجموعه دارد و مجموعهٔ توانی آن، همین زیرمجموعه‌ها را به‌عنوان عضو در خود جای می‌دهد.
  • رابطهٔ A⊆BA\subseteq B یعنی هر عضو AA در BB است و برای رد آن، یافتن یک عضو از AA که در BB نباشد کافی است.
  • در روش عضوگیری دلخواه، مسیر یک عضو دلخواه را تا مجموعهٔ مقصد دنبال می‌کنیم و برای اثبات برابری دو مجموعه، زیرمجموعه‌بودن را در هر دو جهت نشان می‌دهیم.

تمرین تعاملی این درس (رایگان)تمرین تعاملی این درس

درس ۹ · صفحهٔ ۱۹ تا ۲۱ · حدود ۱۲ دقیقه · تولید هوش مصنوعی

دو مجموعه مساوی

در این درس یاد می‌گیری با بررسی عضویت و زیرمجموعه بودن دوطرفه، برابری مجموعه‌ها را تشخیص بدهی و چند رابطهٔ ساده میان مجموعه‌ها را اثبات کنی.

پیش از شروع

آیا ممکن است دو مجموعه با ظاهر کاملاً متفاوت، دقیقاً یک مجموعه باشند؟ مثلاً مجموعهٔ جواب‌های یک معادله با مجموعه‌ای که اعضایش را فهرست کرده‌ایم؟

بله! برابر بودن مجموعه‌ها به شکل نوشتن آن‌ها بستگی ندارد؛ مهم این است که دقیقاً اعضای یکسانی داشته باشند. برای اثبات این برابری، بررسی می‌کنیم که هر عضو هرکدام، عضو دیگری هم باشد.

از عضو دلخواه تا زیرمجموعه

از عضو دلخواه تا زیرمجموعه

فرض کن همهٔ اعضای گروه تئاتر و همهٔ اعضای گروه سرود، دانش‌آموز همین مدرسه‌اند. اگر کسی در یکی از این دو گروه باشد، آیا می‌تواند دانش‌آموز این مدرسه نباشد؟

برای اثبات A⊆BA\subseteq B هم همین‌طور فکر می‌کنیم: یک عضو دلخواه از مجموعهٔ اول می‌گیریم و نشان می‌دهیم حتماً عضو مجموعهٔ دوم است:

x∈A⇒x∈Bx\in A\Rightarrow x\in B

«دلخواه» یعنی دربارهٔ عضوی خاص حرف نمی‌زنیم؛ استدلالمان باید برای هر عضو مجموعهٔ اول درست باشد. پس بررسی چند عضو به‌تنهایی، اثبات نیست.

اگر مجموعهٔ اول یک اجتماع باشد، عضویت در آن را به «یا» باز می‌کنیم:

x∈A∪B⇒x∈A∨x∈Bx\in A\cup B\Rightarrow x\in A\lor x\in B

حالا باید هر دو حالت را بررسی کنیم و در هر حالت، با کمک فرض‌های مسئله به عضویت در مجموعهٔ مقصد برسیم. این روش مثل بررسی دو مسیر است که باید مطمئن شویم هر دو به یک مقصد می‌رسند.

کتاب درسی، صفحهٔ ۱۹

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

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

ممکن است دو نفر فهرست یکسانی از دوستانشان بنویسند، اما ترتیب اسم‌ها متفاوت باشد. آیا افراد فهرست عوض شده‌اند؟ نه؛ در مجموعه‌ها هم اعضا مهم‌اند، نه ترتیب یا شکل نوشتن.

برای اینکه بگوییم A=BA=B، باید هر دو شرط زیر برقرار باشند:

  • A⊆BA\subseteq B: هیچ عضوی از AA بیرون از BB نباشد.
  • B⊆AB\subseteq A: هیچ عضوی از BB بیرون از AA نباشد.

پس معیار برابری این است:

A=B⇔[(A⊆B)∧(B⊆A)]A=B\Leftrightarrow[(A\subseteq B)\wedge(B\subseteq A)]

ممکن است یک مجموعه با فهرست اعضا و دیگری با یک شرط نوشته شود؛ برای مقایسه باید ببینیم دقیقاً چه عضوهایی دارند، نه اینکه نوشته‌هایشان چقدر شبیه است.

حواست باشد: زیرمجموعه بودن فقط در یک جهت کافی نیست؛ شاید مجموعهٔ دوم عضو اضافه‌ای داشته باشد. برای رد برابری نیز کافی است یک عضو پیدا کنی که فقط در یکی از دو مجموعه باشد.

کتاب درسی، صفحهٔ ۱۹

اثبات برابری در دو جهت

اثبات برابری در دو جهت

فرض کن AA مجموعهٔ دانش‌آموزان علاقه‌مند به فوتبال و BB مجموعهٔ علاقه‌مندان به والیبال باشد. «علاقه‌مند به فوتبال و والیبال» همان «علاقه‌مند به والیبال و فوتبال» است؛ جابه‌جایی ترتیب، افراد مشترک را تغییر نمی‌دهد.

برای اثبات A∩B=B∩AA\cap B=B\cap A باید دو جهتِ زیرمجموعه بودن را نشان دهیم:

  • جهت اول: عضو دلخواه xx را از A∩BA\cap B می‌گیریم. پس x∈Ax\in A و x∈Bx\in B. با عوض کردن ترتیب این دو شرط، داریم x∈Bx\in B و x∈Ax\in A؛ بنابراین x∈B∩Ax\in B\cap A. پس A∩B⊆B∩AA\cap B\subseteq B\cap A.
  • جهت دوم: اگر x∈B∩Ax\in B\cap A باشد، آنگاه x∈Bx\in B و x∈Ax\in A؛ پس x∈A∩Bx\in A\cap B. بنابراین B∩A⊆A∩BB\cap A\subseteq A\cap B.

حالا که زیرمجموعه بودن در هر دو جهت برقرار است، برابری ثابت می‌شود. نکتهٔ مهم این است که در این استدلال، جای دو شرطِ متصل با «و» عوض شد، نه خودِ اعضای مجموعه‌ها.

کتاب درسی، صفحهٔ ۱۹

وقتی تفاضل تهی می‌شود

وقتی تفاضل تهی می‌شود

تفاضل A−BA-B یعنی مجموعهٔ عضوهایی که در AA هستند، اما در BB نیستند. حالا اگر A⊆BA\subseteq B باشد، آیا چنین عضوی پیدا می‌شود؟ نه؛ چون هر عضو AA حتماً در BB هم هست. پس چیزی برای تفاضل باقی نمی‌ماند و داریم:

A−B=∅A-B=\emptyset

مثلاً اگر AA مجموعهٔ دانش‌آموزان تیم والیبال مدرسه و BB مجموعهٔ همهٔ دانش‌آموزان همان مدرسه باشد، هیچ عضو تیمی بیرون از مجموعهٔ دانش‌آموزان مدرسه نیست.

برای پیوند دادن این نتیجه به برابری مجموعه‌ها، دقت کن: چون تفاضل هیچ عضوی ندارد، A−B⊆∅A-B\subseteq\emptyset است؛ از طرفی مجموعهٔ تهی زیرمجموعهٔ هر مجموعه‌ای است، پس ∅⊆A−B\emptyset\subseteq A-B. این دو جهت، برابری را ثابت می‌کنند.

حواست به ترتیب باشد: از A⊆BA\subseteq B نمی‌توان نتیجه گرفت B−AB-A هم تهی است؛ ممکن است BB عضوهایی بیرون از AA داشته باشد.

کتاب درسی، صفحهٔ ۲۰

پل میان مجموعه‌ها و گزاره‌ها

پل میان مجموعه‌ها و گزاره‌ها

چطور می‌توان از قوانین گزاره‌ها برای فهمیدن قوانین مجموعه‌ها کمک گرفت؟ کافی است شرط عضویت را به زبان «یا» و «و» بنویسیم:

  • x∈A∪Bx\in A\cup B یعنی x∈A∨x∈Bx\in A\vee x\in B؛ عضویت در دست‌کم یکی از دو مجموعه کافی است.
  • x∈A∩Bx\in A\cap B یعنی x∈A∧x∈Bx\in A\wedge x\in B؛ عضویت در هر دو مجموعه لازم است.

مثلاً اگر AA مجموعهٔ اعضای گروه ورزش و BB مجموعهٔ اعضای گروه نقاشی باشد، اجتماع شامل دانش‌آموزانی است که در دست‌کم یکی از این گروه‌ها هستند؛ اشتراک فقط اعضای هر دو گروه را شامل می‌شود.

این ترجمه، پلی برای بررسی قوانین است. همان‌طور که جابه‌جایی دو گزاره در ترکیب «یا» ارزش آن را تغییر نمی‌دهد، جابه‌جایی دو مجموعه در اجتماع هم اعضا را تغییر نمی‌دهد. همچنین در اجتماع سه مجموعه، تغییر جای پرانتزها شرط «عضویت در دست‌کم یکی از سه مجموعه» را عوض نمی‌کند.

در نمودار ون هم می‌توان این برابری‌ها را دید: اگر دو عبارت دقیقاً ناحیه‌های یکسانی را مشخص کنند، اعضای یکسانی دارند. برای اثبات کلی، شرط عضویت یک عضو دلخواه را بررسی می‌کنیم.

کتاب درسی، صفحهٔ ۲۱

مثال حل‌شده

فرض کن AA و BB دو مجموعه با مرجع UU باشند و A⊆BA\subseteq B. ثابت کن A∪B=BA\cup B=B.

  1. برای اثبات برابری، باید دو رابطهٔ A∪B⊆BA\cup B\subseteq B و B⊆A∪BB\subseteq A\cup B را نشان دهیم.

  2. عضو دلخواه x∈A∪Bx\in A\cup B را در نظر بگیر. طبق تعریف اجتماع، x∈Ax\in A یا x∈Bx\in B است.

  3. اگر x∈Ax\in A باشد، از فرض A⊆BA\subseteq B نتیجه می‌شود x∈Bx\in B؛ در حالت دیگر نیز از ابتدا x∈Bx\in B است. پس A∪B⊆BA\cup B\subseteq B.

  4. برای جهت دوم، هر عضو دلخواه x∈Bx\in B شرطِ x∈Ax\in A یا x∈Bx\in B را دارد؛ بنابراین x∈A∪Bx\in A\cup B و در نتیجه B⊆A∪BB\subseteq A\cup B.

  5. اکنون هر دو رابطه برقرارند؛ پس طبق تعریف برابری مجموعه‌ها، A∪B=BA\cup B=B.

جواب: با اثبات هر دو جهتِ زیرمجموعه بودن، نتیجه می‌گیریم A∪B=BA\cup B=B.

نکات مهم

  • برای اثبات زیرمجموعه بودن، از یک عضو دلخواه مجموعهٔ اول شروع می‌کنیم و نشان می‌دهیم عضو مجموعهٔ دوم است.
  • برابری دو مجموعه یعنی زیرمجموعه بودن در هر دو جهت؛ شکل نوشتن مجموعه‌ها ملاک برابری نیست.
  • عضویت در اجتماع با «یا» و در اشتراک با «و» بیان می‌شود و اگر A⊆BA\subseteq B باشد، تفاضل A−BA-B تهی است.

تمرین تعاملی این درس (رایگان)تمرین تعاملی این درس

درس ۱۰ · صفحهٔ ۲۱ تا ۲۷ · حدود ۱۵ دقیقه · تولید هوش مصنوعی

قوانین و اعمال بین مجموعه‌ها

در این درس یاد می‌گیری با قوانین اجتماع، اشتراک، متمم، جذب و دمورگان عبارت‌های مجموعه‌ای را ساده کنی و با بررسی عضویت و زیرمجموعه‌بودن، دلیل برابری مجموعه‌ها را توضیح بدهی.

پیش از شروع

در یک کلاس، بعضی دانش‌آموزها عضو گروه ورزش‌اند و بعضی عضو گروه موسیقی. آیا «عضو هر دو گروه نبودن» همان «عضو هیچ‌کدام نبودن» است؟

نه؛ کسی که عضو هر دو گروه نیست، ممکن است عضو یکی از آن‌ها باشد یا عضو هیچ‌کدام نباشد. این تفاوت با قوانین دمورگان روشن می‌شود؛ قوانینی که نشان می‌دهند متمم گرفتن چگونه اجتماع و اشتراک را به هم تبدیل می‌کند.

جابه‌جایی و شرکت‌پذیری

جابه‌جایی و شرکت‌پذیری

فرض کن مجموعهٔ اعضای گروه ورزش AA و مجموعهٔ اعضای گروه موسیقی BB باشد. برای پیدا کردن دانش‌آموزانی که عضو دست‌کم یکی از این گروه‌ها هستند، مهم نیست اول فهرست کدام گروه را بخوانی. برای پیدا کردن اعضای مشترک هم ترتیب فهرست‌ها اثری ندارد. این همان جابه‌جایی است:

A∪B=B∪AA\cup B=B\cup A

A∩B=B∩AA\cap B=B\cap A

حالا گروه نقاشی، یعنی CC، را هم اضافه کن. اگر فقط اجتماع داشته باشیم، مهم نیست ابتدا کدام دو فهرست را ترکیب کنیم؛ نتیجه شامل اعضای دست‌کم یکی از سه گروه است:

(A∪B)∪C=A∪(B∪C)(A\cup B)\cup C=A\cup(B\cup C)

اگر فقط اشتراک داشته باشیم، در هر دو پرانتزبندی دنبال اعضای هر سه گروه هستیم:

(A∩B)∩C=A∩(B∩C)(A\cap B)\cap C=A\cap(B\cap C)

این ویژگی شرکت‌پذیری نام دارد. دقت کن: این قانون برای تغییر پرانتزها هنگامی است که عمل‌ها یکسان‌اند.

برای توضیح برابری‌ها، عضوی دلخواه مثل xx را در نظر بگیر: شرط عضویت آن در دو طرف یکسان است؛ مثلاً «عضو AA یا BB بودن» با «عضو BB یا AA بودن» تفاوتی ندارد.

کتاب درسی، صفحهٔ ۲۱

توزیع‌پذیری در هر دو جهت

توزیع‌پذیری در هر دو جهت

در حساب، ضرب را روی جمع پخش می‌کنیم. در مجموعه‌ها نکتهٔ جالب این است که هم اشتراک روی اجتماع پخش می‌شود، هم اجتماع روی اشتراک:

A∩(B∪C)=(A∩B)∪(A∩C)A\cap(B\cup C)=(A\cap B)\cup(A\cap C)

A∪(B∩C)=(A∪B)∩(A∪C)A\cup(B\cap C)=(A\cup B)\cap(A\cup C)

به الگو دقت کن: مجموعهٔ بیرون پرانتز در هر دو بخش تکرار می‌شود و عمل داخل پرانتز، بین دو بخش قرار می‌گیرد.

برای فهم قانون دوم، فرض کن AA گروه ورزش، BB گروه موسیقی و CC گروه نمایش باشد. سمت چپ یعنی دانش‌آموز عضو ورزش باشد، یا هم‌زمان عضو موسیقی و نمایش باشد. سمت راست دو شرط دارد: «ورزش یا موسیقی» و «ورزش یا نمایش». عضو ورزش هر دو شرط را دارد؛ کسی هم که عضو ورزش نیست، برای داشتن هر دو شرط باید عضو موسیقی و نمایش باشد. پس دو طرف اعضای یکسانی دارند.

این قوانین را برعکس هم بخوان! تبدیل (A∪B)∩(A∪C)(A\cup B)\cap(A\cup C) به A∪(B∩C)A\cup(B\cap C) فاکتورگیری است؛ یعنی بخش مشترکِ دو عبارت را بیرون می‌آوریم.

کتاب درسی، صفحهٔ ۲۳

ابزارهای ساده‌سازی

ابزارهای ساده‌سازی

فرض کن UU مجموعهٔ همهٔ دانش‌آموزان کلاس و AA مجموعهٔ اعضای گروه ورزش باشد. متمم AA، یعنی A′A'، شامل دانش‌آموزان همین کلاس است که عضو گروه ورزش نیستند؛ پس متمم همیشه به مجموعهٔ مرجع وابسته است.

هر دانش‌آموز یا در AA است یا در A′A' و هیچ‌کس هم‌زمان در هر دو نیست. بنابراین:

A∪A′=UA\cup A'=U

A∩A′=∅A\cap A'=\varnothing

برای کار با مرجع و مجموعهٔ تهی هم این چهار رابطه کمک می‌کنند:

A∪U=UA∩U=AA\cup U=U\qquad A\cap U=A

A∪∅=AA∩∅=∅A\cup\varnothing=A\qquad A\cap\varnothing=\varnothing

معنایشان را به یاد بسپار: اجتماع با «همه»، همه را می‌دهد؛ اشتراک با «هیچ»، هیچ عضوی باقی نمی‌گذارد.

تفاضل را هم می‌توان بازنویسی کرد: اگر BB گروه موسیقی باشد، A−BA-B یعنی اعضای ورزش که عضو موسیقی نیستند. پس باید هم در AA باشند و هم در B′B':

A−B=A∩B′A-B=A\cap B'

این تبدیل، عبارت‌های دارای تفاضل را برای استفاده از قوانین اجتماع و اشتراک آماده می‌کند.

کتاب درسی، صفحهٔ ۲۳

زیرمجموعه و قوانین جذب

زیرمجموعه و قوانین جذب

فرض کن AA مجموعهٔ دانش‌آموزان تیم والیبال مدرسه و BB مجموعهٔ همهٔ دانش‌آموزان مدرسه باشد. چون هر عضو تیم، دانش‌آموز مدرسه است، داریم A⊆BA\subseteq B. پس اضافه‌کردن اعضای تیم به فهرست مدرسه، عضو تازه‌ای نمی‌آورد؛ همچنین اعضای مشترک این دو فهرست، همان اعضای تیم‌اند:

A∪B=BA∩B=AA\cup B=B\qquad A\cap B=A

یعنی اجتماع، مجموعهٔ فراگیرتر و اشتراک، مجموعهٔ زیرمجموعه را می‌دهد. برعکس هم می‌توان نتیجه گرفت: هرکدام از این دو تساوی برقرار باشد، حتماً A⊆BA\subseteq B است.

حالا به قوانین جذب برسیم؛ این قوانین برای هر دو مجموعه برقرارند، حتی اگر هیچ‌کدام زیرمجموعهٔ دیگری نباشد:

  • چون A∩B⊆AA\cap B\subseteq A، افزودن این بخش مشترک به AA چیزی را تغییر نمی‌دهد: A∪(A∩B)=AA\cup(A\cap B)=A.
  • چون A⊆A∪BA\subseteq A\cup B، گرفتن اشتراکِ AA با این مجموعهٔ فراگیرتر، همان AA را می‌دهد: A∩(A∪B)=AA\cap(A\cup B)=A.

پس در جذب، به‌جای حفظ‌کردن ظاهر عبارت، بپرس: «کدام مجموعه در دیگری جا گرفته است؟»

کتاب درسی، صفحهٔ ۲۵

متمم گرفتن با دمورگان

متمم گرفتن با دمورگان

به پرسش گروه ورزش و موسیقی برگردیم. اگر AA گروه ورزش و BB گروه موسیقی باشد، «عضو هیچ‌کدام نبودن» یعنی نه عضو AA باشی و نه عضو BB. پس بیرونِ اجتماع بودن، همان عضوِ هر دو متمم بودن است:

(A∪B)′=A′∩B′(A\cup B)'=A'\cap B'

اما «عضو هر دو گروه نبودن» یعنی در بخش مشترک نباشی؛ ممکن است عضو فقط یکی از گروه‌ها باشی یا عضو هیچ‌کدام نباشی. کافی است دست‌کم در یکی از گروه‌ها عضو نباشی:

(A∩B)′=A′∪B′(A\cap B)'=A'\cup B'

این‌ها قوانین دمورگان هستند. برای متمم گرفتن از یک اجتماع یا اشتراک، عمل را عوض کن و از هر مجموعه متمم بگیر. فقط جابه‌جاکردن علامت عمل کافی نیست!

برای فهم دلیل قانون اول، یک عضو دلخواه از مجموعهٔ مرجع UU در نظر بگیر: بیرونِ A∪BA\cup B بودن دقیقاً یعنی هم بیرونِ AA و هم بیرونِ BB بودن. این استدلال در جهت برگشت هم برقرار است؛ پس دو مجموعه برابرند.

کتاب درسی، صفحهٔ ۲۷

مثال حل‌شده

با استفاده از قوانین مجموعه‌ها، عبارت (A−B)∪(A∩B)(A-B)\cup(A\cap B) را ساده کن.

  1. تفاضل را به اشتراک با متمم تبدیل می‌کنیم: (A−B)∪(A∩B)=(A∩B′)∪(A∩B)(A-B)\cup(A\cap B)=(A\cap B')\cup(A\cap B).

  2. با توزیع‌پذیری از عامل مشترک فاکتور می‌گیریم: (A∩B′)∪(A∩B)=A∩(B′∪B)(A\cap B')\cup(A\cap B)=A\cap(B'\cup B).

  3. اجتماع هر مجموعه با متممش برابر مجموعهٔ مرجع است؛ بنابراین A∩(B′∪B)=A∩UA\cap(B'\cup B)=A\cap U.

  4. اشتراک با مجموعهٔ مرجع چیزی را حذف نمی‌کند؛ پس A∩U=AA\cap U=A. یعنی اعضای مجموعهٔ اول، چه در مجموعهٔ دوم باشند و چه نباشند، همگی در نتیجه باقی می‌مانند.

جواب: (A−B)∪(A∩B)=A(A-B)\cup(A\cap B)=A

نکات مهم

  • در اجتماع و اشتراک، جابه‌جایی و شرکت‌پذیری برقرارند و هر دو عمل نسبت به یکدیگر توزیع‌پذیرند؛ خواندن قانون توزیع‌پذیری از راست به چپ همان فاکتورگیری است.
  • برای ساده‌سازی، از روابط متمم، مرجع و تهی و تساوی A−B=A∩B′A-B=A\cap B' کمک بگیر؛ اگر A⊆BA\subseteq B باشد، آنگاه A∪B=BA\cup B=B و A∩B=AA\cap B=A و قوانین جذب نیز از همین رابطه‌ها نتیجه می‌شوند.
  • در قوانین دمورگان، متمم به هر دو مجموعه می‌رسد و اجتماع و اشتراک جای هم را می‌گیرند: (A∪B)′=A′∩B′(A\cup B)'=A'\cap B' و (A∩B)′=A′∪B′(A\cap B)'=A'\cup B'.

تمرین تعاملی این درس (رایگان)تمرین تعاملی این درس

درس ۱۱ · صفحهٔ ۲۷ تا ۳۰ · حدود ۱۵ دقیقه · تولید هوش مصنوعی

قوانین دمورگان

در این درس یاد می‌گیری قوانین دمورگان را با معنای عضویت توضیح بدهی، عبارت‌های مجموعه‌ای را ساده کنی و برای بررسی تساوی‌ها و توصیف ناحیه‌های نمودار ون از آن‌ها کمک بگیری.

پیش از شروع

اگر دانش‌آموزی عضو گروه ورزش یا گروه موسیقی نباشد، آیا کافی است فقط عضو یکی از این دو گروه نباشد؟

نه؛ او باید نه عضو گروه ورزش باشد و نه عضو گروه موسیقی. همین تفاوت میان «یا» و «و» هنگام متمم‌گرفتن، کلید فهم قوانین دمورگان است.

متمم، «یا» و «و» را عوض می‌کند

متمم، «یا» و «و» را عوض می‌کند

فرض کن AA گروه ورزش و BB گروه موسیقی مدرسه باشد و مجموعهٔ مرجع UU همهٔ دانش‌آموزان مدرسه باشد. کسی که عضو هیچ‌کدام از این دو گروه نیست، هم بیرون از AA است و هم بیرون از BB. پس متممِ اجتماع، اشتراکِ متمم‌هاست:

(A∪B)′=A′∩B′(A\cup B)'=A'\cap B'

حالا «عضو هر دو گروه نبودن» را در نظر بگیر. کافی است دانش‌آموز دست‌کم در یکی از گروه‌ها عضو نباشد؛ ممکن است عضو گروه دیگر باشد یا عضو هیچ‌کدام نباشد. بنابراین متممِ اشتراک، اجتماعِ متمم‌هاست:

(A∩B)′=A′∪B′(A\cap B)'=A'\cup B'

این‌ها قوانین دمورگان هستند: متمم وارد پرانتز می‌شود، هر دو مجموعه را متمم می‌کند و اجتماع و اشتراک را با هم عوض می‌کند.

برای فهم دلیل قانون اول، عضوی دلخواه مانند xx را دنبال کن: اگر xx بیرونِ اجتماع باشد، در هیچ‌یک از دو مجموعه نیست؛ پس در هر دو متمم است. برعکس، اگر در هر دو متمم باشد، بیرونِ اجتماع است. این رفت‌وبرگشت نشان می‌دهد دو طرف دقیقاً اعضای یکسانی دارند.

کتاب درسی، صفحهٔ ۲۷

تفاضل را برای ساده‌سازی آماده کن

تفاضل را برای ساده‌سازی آماده کن

تفاضلِ A−BA-B یعنی اعضایی که در AA هستند، اما در BB نیستند. مثلاً اگر AA مجموعهٔ اعضای گروه ورزش و BB مجموعهٔ اعضای گروه موسیقی باشد، A−BA-B ورزشکارانی را نشان می‌دهد که عضو گروه موسیقی نیستند؛ نه همهٔ کسانی که فقط در یکی از این دو گروه‌اند.

این معنا را می‌توانیم با اشتراک بنویسیم:

A−B=A∩B′A-B=A\cap B'

چرا این تبدیل کمک می‌کند؟ چون قوانین دمورگان دربارهٔ اجتماع و اشتراک‌اند. با تبدیل تفاضل، می‌توانیم این قوانین را مستقیم به کار ببریم.

برای ساده‌سازی، این مسیر را دنبال کن:

  • ابتدا تفاضل‌ها را به اشتراک با متمم تبدیل کن.
  • اگر متمم روی یک پرانتز است، قانون دمورگان را به کار ببر: اجتماع و اشتراک جابه‌جا می‌شوند و هر دو مجموعه متمم می‌شوند.
  • سپس با خواصی مثل شرکت‌پذیری و توزیع‌پذیری، عبارت را جمع‌وجور کن.

یادت باشد متممِ متممِ یک مجموعه، خود آن مجموعه است: (B′)′=B(B')'=B. پس هنگام بازکردن پرانتز، متمم‌ها را با دقت دنبال کن.

کتاب درسی، صفحهٔ ۲۸

یک مثال نقض کافی است

یک مثال نقض کافی است

فرض کن کسی بگوید: «همهٔ گوشی‌ها دوربین دارند.» برای رد این ادعا لازم نیست همهٔ گوشی‌های دنیا را بررسی کنی؛ پیدا کردن یک گوشی بدون دوربین کافی است. به چنین موردی «مثال نقض» می‌گوییم.

در تساوی‌های مجموعه‌ای هم همین منطق را داریم. وقتی ادعا می‌کنیم یک تساوی همواره برقرار است، یعنی برای هر انتخاب مجازِ مجموعه‌ها درست است. پس برای رد آن، کافی است یک انتخاب پیدا کنیم که دو طرفش برابر نباشند؛ یعنی دست‌کم یک عضو در یک طرف باشد و در طرف دیگر نباشد.

مثلاً برای بررسی ادعای A−(B−C)=(A−B)−CA-(B-C)=(A-B)-C، اگر ساده‌سازی پیش نرفت، هنوز حق نداریم بگوییم ادعا نادرست است؛ شاید راه مناسبی انتخاب نکرده‌ایم! باید مجموعه‌هایی پیدا کنیم و نشان دهیم حاصل دو طرف متفاوت است.

تفاوت مهم: یک نمونهٔ درست، تساوی همیشگی را اثبات نمی‌کند؛ اما یک مثال نقض، آن را رد می‌کند.

کتاب درسی، صفحهٔ ۲۸

از شمول دوطرفه تا تساوی

از شمول دوطرفه تا تساوی

اجتماع، همهٔ اعضای دو مجموعه را در بر می‌گیرد؛ اشتراک، فقط اعضای مشترک را. پس اگر A∪B=A∩BA\cup B=A\cap B باشد، چه اتفاقی افتاده است؟ هیچ عضوی نمی‌تواند فقط در یکی از دو مجموعه باشد؛ وگرنه در اجتماع هست، اما در اشتراک نیست!

برای دقیق‌کردن این استدلال، یک عضو دلخواه از AA در نظر بگیر. این عضو حتماً در A∪BA\cup B است. طبق فرض، اجتماع همان اشتراک است؛ پس عضو ما در A∩BA\cap B و بنابراین در BB هم هست. نتیجه می‌گیریم A⊆BA\subseteq B.

حالا جای دو مجموعه را عوض کن: هر عضو BB نیز در اجتماع، سپس در اشتراک و در نتیجه در AA است؛ یعنی B⊆AB\subseteq A. شمول در هر دو جهت یعنی دو مجموعه دقیقاً اعضای یکسان دارند، پس A=BA=B.

مثلاً اگر فهرستِ «اعضای دست‌کم یکی از دو گروه» دقیقاً همان فهرستِ «اعضای هر دو گروه» باشد، اعضای دو گروه یکسان‌اند.

کتاب درسی، صفحهٔ ۲۹

از جمله به ناحیهٔ ون

از جمله به ناحیهٔ ون

برای پیدا کردن ناحیهٔ درست، جمله را به شرط‌های کوچک‌تر بشکن. «و» یعنی هر دو شرط هم‌زمان برقرار باشند؛ پس با اشتراک نشانش می‌دهیم. «یا» یعنی دست‌کم یکی از شرط‌ها برقرار باشد؛ پس اجتماع می‌نویسیم. در ریاضی، «یا» بخش مشترک دو مجموعه را هم شامل می‌شود، مگر اینکه گفته باشیم «فقط یکی».

مثلاً فرض کن AA مجموعهٔ اعضای گروه ورزش، BB اعضای گروه موسیقی و CC اعضای گروه نمایش باشد. «عضو ورزش یا موسیقی، ولی نه نمایش» دو شرط دارد: عضو A∪BA\cup B بودن و عضو CC نبودن. بنابراین ناحیهٔ موردنظر این است:

(A∪B)∩C′(A\cup B)\cap C'

در نمودار ون، بخش‌های داخل دست‌کم یکی از دو دایرهٔ AA و BB را نگه می‌داریم، اما هر بخشی را که داخل CC است کنار می‌گذاریم. حواست باشد: شرط «در CC نباشند» به تمام اجتماع مربوط است، نه فقط به BB.

کتاب درسی، صفحهٔ ۳۰

مثال حل‌شده

با استفاده از جبر مجموعه‌ها نشان بده حذف اعضای اجتماعِ BB و CC از AA، همان نتیجهٔ اشتراکِ A−BA-B و A−CA-C را می‌دهد؛ یعنی A−(B∪C)=(A−B)∩(A−C)A-(B\cup C)=(A-B)\cap(A-C).

  1. از طرف چپ شروع می‌کنیم و تفاضل را به اشتراک تبدیل می‌کنیم: A−(B∪C)=A∩(B∪C)′A-(B\cup C)=A\cap(B\cup C)'.

  2. قانون دمورگان را به کار می‌بریم: A∩(B∪C)′=A∩(B′∩C′)A\cap(B\cup C)'=A\cap(B'\cap C').

  3. با شرکت‌پذیری و رابطهٔ A∩A=AA\cap A=A، عاملِ AA را تکرار و عبارت را گروه‌بندی می‌کنیم: A∩(B′∩C′)=(A∩B′)∩(A∩C′)A\cap(B'\cap C')=(A\cap B')\cap(A\cap C').

  4. هر اشتراک را دوباره به تفاضل تبدیل می‌کنیم: (A∩B′)∩(A∩C′)=(A−B)∩(A−C)(A\cap B')\cap(A\cap C')=(A-B)\cap(A-C)؛ به طرف راست رسیدیم.

جواب: پس برای هر سه مجموعهٔ دلخواه، A−(B∪C)=(A−B)∩(A−C)A-(B\cup C)=(A-B)\cap(A-C) برقرار است.

نکات مهم

  • در قوانین دمورگان، متممِ اجتماع برابر اشتراکِ متمم‌ها و متممِ اشتراک برابر اجتماعِ متمم‌هاست.
  • برای ساده‌سازی، تفاضل را به کمک A−B=A∩B′A-B=A\cap B' به اشتراک تبدیل کن و برای ترجمهٔ ناحیه‌های ون، شرط‌های عضویت را دقیق بخوان.
  • برای اثبات تساوی می‌توان شمول دوطرفه را نشان داد، اما برای رد یک تساوی همیشگی، یک مثال نقض کافی است.

تمرین تعاملی این درس (رایگان)تمرین تعاملی این درس

درس ۱۲ · صفحهٔ ۳۰ تا ۳۴ · حدود ۱۵ دقیقه · تولید هوش مصنوعی

ضرب دکارتی بین دو مجموعه

در این درس یاد می‌گیری ضرب دکارتی دو مجموعه را بسازی، تعداد اعضای آن را در حالت متناهی به دست آوری، نمودارش را تشخیص بدهی و اثر جابه‌جایی مجموعه‌ها و تهی بودن آن‌ها را توضیح بدهی.

پیش از شروع

فرض کن برای ورود به یک برنامه باید اول نام کاربری و بعد رمز را وارد کنی؛ آیا جابه‌جا کردن این دو، همان اطلاعات قبلی را به برنامه می‌دهد؟ این موضوع چه ربطی به ضرب دو مجموعه دارد؟

در یک زوج مرتب، جای هر مؤلفه بخشی از اطلاعات آن است؛ درست مثل جای نام کاربری و رمز. ضرب دکارتی همهٔ زوج‌های مرتبی را می‌سازد که مؤلفهٔ اولشان از مجموعهٔ اول و مؤلفهٔ دومشان از مجموعهٔ دوم انتخاب می‌شود؛ پس جابه‌جایی مجموعه‌ها معمولاً نتیجه را تغییر می‌دهد.

هر مؤلفه، جای خودش

هر مؤلفه، جای خودش

برای ورود به یک برنامه، «نام کاربری، رمز» با «رمز، نام کاربری» فرق دارد؛ جای هر کدام مهم است. در زوج مرتب هم ترتیب اهمیت دارد: در (x,y)(x,y)، مؤلفهٔ اول xx و مؤلفهٔ دوم yy است. دو زوج مرتب فقط وقتی برابرند که مؤلفه‌های هم‌جای آن‌ها برابر باشند.

ضرب دکارتی دو مجموعه، مجموعه‌ای از زوج‌های مرتب است:

A×B={(x,y)∣x∈A ∧ y∈B}A\times B=\{(x,y)\mid x\in A\ \wedge\ y\in B\}

یعنی برای ساختن هر عضو، مؤلفهٔ اول را از AA و مؤلفهٔ دوم را از BB برمی‌داریم و همهٔ انتخاب‌های مجاز را در نظر می‌گیریم. پس اعضای حاصل، خودِ اعضای دو مجموعه نیستند؛ زوج‌های مرتبِ ساخته‌شده از آن‌ها هستند.

اگر جای مجموعه‌ها عوض شود، نقش آن‌ها هم عوض می‌شود: در B×AB\times A مؤلفهٔ اول از BB می‌آید. بنابراین نمی‌توان همیشه جای دو مجموعه را عوض کرد و انتظار همان حاصل را داشت.

کتاب درسی، صفحهٔ ۳۰

شمردن بدون جا انداختن

شمردن بدون جا انداختن

فرض کن می‌خواهی همهٔ ترکیب‌های «نان و نوشیدنی» را برای صبحانه بشماری. هر نوع نان می‌تواند با تک‌تک نوشیدنی‌ها همراه شود؛ پس برای هر نان، به تعداد نوشیدنی‌ها انتخاب داری. در ضرب دکارتی هم همین اتفاق می‌افتد.

برای دو مجموعهٔ متناهی، اگر n(A)=mn(A)=m و n(B)=kn(B)=k باشد، هر عضو AA با همهٔ kk عضوِ BB زوج مرتب می‌سازد. بنابراین mm گروه داریم که هرکدام شامل kk زوج مرتب‌اند:

n(A×B)=m×k=n(A)n(B)n(A\times B)=m\times k=n(A)n(B)

هیچ زوجی دوبار شمرده نمی‌شود: زوج‌های مربوط به دو عضو متفاوتِ AA، مؤلفهٔ اول متفاوتی دارند؛ در هر گروه هم مؤلفه‌های دوم متفاوت‌اند.

راهِ جا نینداختن: یک عضوِ مجموعهٔ اول را ثابت نگه دار و آن را با همهٔ اعضای مجموعهٔ دوم جفت کن؛ بعد سراغ عضو بعدی برو. اگر فقط تعداد زوج‌ها را می‌خواهی، لازم نیست همه را بنویسی؛ کافی است تعداد اعضای دو مجموعه را در هم ضرب کنی، نه اینکه جمع کنی.

کتاب درسی، صفحهٔ ۳۰

از زوج مرتب تا نمودار

از زوج مرتب تا نمودار

هر زوج مرتب (x,y)(x,y) را می‌توان یک نقطه روی صفحهٔ مختصات دید: xx جای افقی و yy جای عمودی آن را مشخص می‌کند. برای رسم A×BA\times B، همهٔ نقطه‌هایی را می‌خواهیم که x∈Ax\in A و y∈By\in B باشد؛ مثل نشانی روی نقشه که هم خیابان و هم کوچه‌اش باید مجاز باشند.

شکل نمودار به نوع مجموعه‌ها بستگی دارد:

  • اگر هر دو مجموعه، تعداد متناهی عضو داشته باشند، نمودار از نقطه‌های جدا تشکیل می‌شود.
  • اگر AA یک بازه و BB فقط شامل یک عدد باشد، یک پاره‌خط افقی داریم. سرِ بازِ بازه را با دایرهٔ توخالی و سرِ بسته را با نقطهٔ پر نشان می‌دهیم.
  • اگر A=RA=\mathbb{R} باشد و BB فقط یک عضو داشته باشد، یک خط افقی کامل داریم.
  • اگر هر دو مجموعه بازه باشند، همهٔ نقاط یک ناحیهٔ مستطیلی مجازند؛ فقط دور مستطیل را نمی‌خواهیم، داخل آن هم جزو نمودار است.
  • اگر A=B=RA=B=\mathbb{R} باشد، هیچ محدودیتی برای مختصات نداریم و نمودار، تمام صفحه است.

پس پیش از رسم، جداگانه بپرس: «حرکت افقی چقدر آزاد است؟ حرکت عمودی چطور؟»

کتاب درسی، صفحهٔ ۳۲

وقتی یک طرف خالی است

وقتی یک طرف خالی است

فرض کن می‌خواهی یک لباس و یک کفش انتخاب کنی. چند لباس داری، اما هیچ کفشی برای انتخاب نیست؛ آیا می‌توانی حتی یک جفت «لباس، کفش» بسازی؟ نه، چون یکی از دو انتخاب لازم وجود ندارد.

در ضرب دکارتی هم هر زوج مرتب به یک عضو از هر مجموعه نیاز دارد. اگر مجموعهٔ دوم تهی باشد، مؤلفهٔ دوم را از کجا بیاوریم؟ اگر مجموعهٔ اول تهی باشد، مؤلفهٔ اولی نداریم. پس برای هر مجموعهٔ AA داریم:

A×∅=∅×A=∅A\times\varnothing=\varnothing\times A=\varnothing

بیایید دلیل را با برهان خلف هم ببینیم: برخلاف حکم، فرض کن A×∅A\times\varnothing عضوی مثل (x,y)(x,y) داشته باشد. طبق تعریف ضرب دکارتی، باید x∈Ax\in A و y∈∅y\in\varnothing باشد؛ اما مجموعهٔ تهی هیچ عضوی ندارد! پس فرض ما نادرست است و حاصل تهی است.

دقت کن: حاصل، «مجموعه‌ای با یک عضو به نام تهی» نیست؛ اصلاً هیچ زوج مرتبی ساخته نشده است.

کتاب درسی، صفحهٔ ۳۲

چه وقت جابه‌جایی ممکن است؟

چه وقت جابه‌جایی ممکن است؟

در ضرب دکارتی معمولاً جابه‌جایی دو مجموعه، حاصل را عوض می‌کند؛ اما برای دو مجموعهٔ ناتهی، حاصل‌ها دقیقاً وقتی برابرند که خود مجموعه‌ها برابر باشند:

A×B=B×A  ⟺  A=BA\times B=B\times A\iff A=B

چرا؟ فرض کن حاصل‌ها برابرند. یک عضو دلخواه xx از AA بردار. چون BB ناتهی است، می‌توانی عضوی مثل yy از آن انتخاب کنی. پس (x,y)∈A×B(x,y)\in A\times B. با برابر بودن حاصل‌ها، همین زوج در B×AB\times A هم هست؛ بنابراین مؤلفهٔ اولش، یعنی xx، باید در BB باشد. پس A⊆BA\subseteq B. با همین استدلال برای اعضای BB، داریم B⊆AB\subseteq A؛ در نتیجه A=BA=B.

برعکس، اگر A=BA=B باشد، هر دو حاصل همان A×AA\times A هستند.

مثلاً اگر فهرست نوشیدنی‌های دو کافه ناتهی باشد، مجموعهٔ تمام سفارش‌های دوتایی «یکی از کافهٔ اول، یکی از کافهٔ دوم» تنها وقتی با حالت جابه‌جا برابر است که فهرست‌هایشان یکسان باشند. شرط ناتهی بودن را فراموش نکن؛ اگر یک فهرست خالی باشد، هر دو حاصل تهی‌اند، حتی اگر فهرست‌ها برابر نباشند.

کتاب درسی، صفحهٔ ۳۳

مثال حل‌شده

اگر A={1,2}A=\{1,2\} و B={0,3}B=\{0,3\} باشد، A×BA\times B و B×AB\times A را بنویس، تعداد اعضای آن‌ها را به دست آور و نمودارشان را توصیف کن. آیا این دو حاصل‌ضرب برابرند؟

  1. در A×BA\times B مؤلفهٔ اول را از AA می‌گیریم و هر انتخاب را با همهٔ اعضای BB جفت می‌کنیم: A×B={(1,0),(1,3),(2,0),(2,3)}A\times B=\{(1,0),(1,3),(2,0),(2,3)\}.

  2. در B×AB\times A جای مجموعه‌های تأمین‌کنندهٔ مؤلفه‌ها عوض می‌شود: B×A={(0,1),(0,2),(3,1),(3,2)}B\times A=\{(0,1),(0,2),(3,1),(3,2)\}.

  3. هر مجموعه دو عضو دارد؛ پس n(A×B)=n(B×A)=2×2=4n(A\times B)=n(B\times A)=2\times2=4 که با شمارش زوج‌های نوشته‌شده هم سازگار است.

  4. برای نمودار A×BA\times B چهار نقطهٔ فهرست اول را روی صفحه مشخص می‌کنیم؛ نمودار B×AB\times A هم چهار نقطهٔ فهرست دوم است. نقطه‌ها را به هم وصل نمی‌کنیم، چون مجموعه‌ها فقط همین مختصات را مجاز می‌دانند.

  5. زوج (1,0)(1,0) عضو A×BA\times B است، ولی عضو B×AB\times A نیست، چون 1∉B1\notin B؛ بنابراین A×B≠B×AA\times B\ne B\times A، با اینکه تعداد اعضایشان برابر است.

جواب: A×B={(1,0),(1,3),(2,0),(2,3)}A\times B=\{(1,0),(1,3),(2,0),(2,3)\} و B×A={(0,1),(0,2),(3,1),(3,2)}B\times A=\{(0,1),(0,2),(3,1),(3,2)\}؛ هرکدام 44 عضو دارند، اما برابر نیستند و نمودار هرکدام شامل چهار نقطهٔ جداست.

نکات مهم

  • در A×BA\times B مؤلفهٔ اول از AA و مؤلفهٔ دوم از BB انتخاب می‌شود و برای مجموعه‌های متناهی داریم n(A×B)=n(A)n(B)n(A\times B)=n(A)n(B).
  • نمودار ضرب دکارتی شامل همهٔ نقاط مجاز است و با توجه به مجموعه‌ها می‌تواند نقطه‌های جدا، پاره‌خط، خط، ناحیهٔ مستطیلی یا تمام صفحه باشد.
  • ضرب دکارتی با مجموعهٔ تهی، تهی است و برای دو مجموعهٔ ناتهی، برابری A×B=B×AA\times B=B\times A دقیقاً زمانی برقرار است که A=BA=B باشد.

تمرین تعاملی این درس (رایگان)تمرین تعاملی این درس

درس‌های فصل ۱ را تعاملی بخوان

در پنل یادگیری 1xAi هر کدام از این درس‌ها قدم به قدم پیش می‌رود: بعد از هر بخش یک سوال کوتاه، بعد مثال حل‌شده و در پایان برگهٔ خروج. جوابت ثبت می‌شود و سوال‌های هر درس در روزهای بعد برای مرور برمی‌گردند. درس‌های تعاملی رایگان‌اند؛ فقط تصحیح پاسخ کوتاه سهمیهٔ روزانهٔ رایگان دارد.

ساختن حساب رایگان است و بعد از ثبت‌نام مستقیم به همین بخش از پنل برمی‌گردی.

فصل ۱ آمار و احتمال یازدهم · رایگان