אוטומטים ושפות פורמליות/תכונות של שפות רגולריות/משפט מיהיל-נרוד: הבדלים בין גרסאות בדף

תוכן שנמחק תוכן שנוסף
Gran (שיחה | תרומות)
מ ניוט, קטגוריה.
Gran (שיחה | תרומות)
שורה 15:
===מחלקות שקילות===
[[קובץ:Set partition.svg|שמאל|ממוזער|150px|דוגמא למחלקות שקילות של עיגול. כל מחלקת שקילות מסומנת בצבע אחד. שתי נקודות בעלות אותו הצבע נמצאות באותה מחלקת שקילות.]]
יחס שקילות מחלק את הקבוצה, שמעליה הוא מוגדר, ל'''מחלקות שקילות''': בהינתן קבוצה A ויחס שקילות R שהוגדר עליה, מגדירים את '''מחלקת השקילות''' של איבר כלשהו כקבוצת כל האיברים השקולים לו. מתכונות יחס השקילות עולה שכל איבר בקבוצה יהיה שייך למחלקת שקילות אחת בלבד, ולכן יחס השקילות מחלק את הקבוצה לתת קבוצות זרות שה[[איחוד (מתמטיקה)|איחוד]]שהאיחוד שלהן הוא הקבוצה כולה.
 
בנוסף, בהינתן [[חלוקה (תורת הקבוצות)|חלוקה]] של הקבוצה, ניתן לבנות יחס שקילות כך שכל זוג איברים נמצא ביחס שקילות [[אם ורק אם]] שני האיברים היו באותה קבוצה בחלוקה.
 
לדוגמה: בהנחה שכל אדם בעולם הוא תושב של מדינה אחת ויחידה, הרי היחס "בעל תושבות משותפת" מחלק את כל תושבי העולם למחלקות שקילות, שכל אחת מהן מכילה את כל תושביה של מדינה מסוימת.
 
 
== משפט מיהיל-נרוד ==