حاصل ضرب دکارتی

تعریف حاصل ضرب دکارتی :

اگر A و B رو مجموعه ی غیر تهی باشند ، مجموعه ی را حاصل ضرب دکارتی دو مجموعه می نامیم .

قوانین و نکات مربوط به حاصل ضرب دکارتی :

تعریف رابطه :

هر زیر مجموعه ی A × B مانند R ، را یک رابطه از A به B می نامیم .

R رابطه ای است روی A یعنی اگر R یک رابطه باشد و ، می نویسیم : aRb و می گوییم : a در رابطه است با b .

تعداد رابطه هایی که می توان از یک مجموعه ی m عضوی به یک مجموعه ی n عضوی نوشت : .

تعداد رابطه هایی که می توان روی مجموعه ی A نوشت :

وارون یک رابطه :

اگر R یک رابطه باشد ، وارون R را تعریف می کنیم :

ترکیب دو رابطه :

اگر دو رابطه روی A باشند ، تعریف می کنیم :

نمایش یک رابطه با گراف جهت دار :

هر رابطه ای روی مجموعه ی متناظر با یک گراف جهت دار است . به این صورت که رأس به رأس وصل است .

مثال :

دقت کنید که اگر ، در گراف متناظر با R ، جهت فلش از رأس به رأس است .

نمایش یک رابطه با یک ماتریس :

هر رابطه روی مجموعه ی متناظر با یک ماتریس صفر و یک به نام ماتریس مجاورت است . ماتریس مجاورت رابطه ی R را به این شکل تعریف می کنیم :

ضرب بولي ماتريس‌هاي صفر و يک :

اگر دو ماتريس صفر و يک باشند، تعريف مي‌کنيم :

اشتراک دو ماتريس صفر و يک :

دو ماتريس صفر و يک باشند، اشتراک B ,A را اگر

به اين صورت تعريف مي‌کنيم :

کوچکتر يا مساوي بودن براي ماتريس‌هاي صفر و يک:

اگر دو ماتريس صفر و يک باشند تعريف مي‌کنيم:

تعداد ماتريس‌هاي A که در شرط صدق مي‌کنند : 2 به توان تعداد يک‌هاي B

تعداد ماتريس‌هاي B که در شرط صدق مي‌کنند : 2 به توان تعداد يک‌هاي A

خواص رابطه ها :

خاصیت بازتابی ( انعکاسی ) :

R روی A دارای خاصیت بازتابی است

تشخیص رابطه ی بازتابی از روی گراف متناظر با آن :

اگر روی همه ی رأس ها طوقه داشته باشیم ، آن رابطه بازتابی است .

تشخیص رابطه ی بازتابی از روی ماتریس مجاورت آن ( M ) :

اگر باشد، آن رابطه بازتابي است.

تعداد رابطه‌هاي بازتابي روي مجموعه‌ي n عضوي A :

اگر دو رابطه‌ي بازتابي روي A باشند، بازتابي‌اند، اما بازتابي نيستند.

خاصیت تقارنی :

تشخیص رابطه ی متقارن از روی گراف متناظر با آن :

اگر یال ها در صورت وجود دو طرفه باشند ، آن رابطه متقارن است .

تشخیص رابطه ی متقارن از روی ماتریس مجاورت آن ( M ) :

اگر باشند ، آن رابطه متقارن است .

تعداد رابطه‌هاي متقارن روي مجموعه‌ي n عضوي A :

اگر دو رابطه‌ي متقارن روي A باشند، متقارن هستند.

خاصیت تعدی ( ترايایی ) :

تشخیص رابطه ی ترایایی از روی گراف متناظر با آن :

اگر یالی از a به b و یالی از b به c وجود داشته باشد ، باید یالی از a به c داشته باشیم تا آن رابطه ترایایی باشد .

تشخیص رابطه ی ترایایی از روی ماتریس مجاورت آن ( M ) :

اگر باشد‌، آن رابطه ترايايي است.

اگر دو رابطه ي ترايايي روي A باشند ، ترايايي هستند اما لزوماً ترايايي نيستند .

خاصیت پاد تقارنی :

R روی A دارای خاصیت پاد تقارنی است .

تشخیص رابطه ی پاد تقارنی از روی گراف متناظر با آن :

اگر یال ها در صورت وجود یک طرفه باشند ، رابطه پاد تقارنی است .

تشخیص رابطه ی تقارنی از روی ماتریس مجاورت آن ( M ) :

اگر آن رابطه پاد متقارن روي A :

تعداد رابطه هاي پاد متقارن روي مجموعه n عضوي A‌ :

اگر دو رابطه پاد متقارن روي A باشند ، پاد متقارن هستند ، اما لزوماً‌ پاد متقارن نيستند .

رابطه ی هم ارزی :

رابطه ای که دارای سه خاصیت بازتابی ، تقارنی و ترایایی باشد ، رابطه ی هم ارزی نام دارد.

اگر دو رابطه ي هم ارزي روي A باشند هم ارزي هستند و هم ارزي نيست . در مورد نمي توان گفت .

دسته ي هم ارزي : اگر R يک رابطه ي هم ارزي روي A‌باشد و ، دسته ي هم ارزي a رابا نماد نشان مي دهيم و آن را تعريف مي کنيم .

تعداد رابطه های هم ارزی روی مجموعه ی n عضوی A = تعداد کل افرازهای A .

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

رابطه ی مرتب :

رابطه ای که دارای سه خاصیت بازتابی ، ترایایی و پاد تقارنی باشد ، رابطه ی مرتب نام دارد .