כמה זהויות לוגיות

דה מורגן		
		
גרירה		
		
דיסטריבוטיביות		

כלל -בביטוי עם משתנה קשור, אפשר להחליף את המשתנה בכל משתנה אחר, שאינו בתחום הקשירה 

שלילת לכל		
שלילת קיים		
לכל – גם		
קיים - או		

תורת הקבוצות הנאיבית

שיוויון קבוצות		
הכלה		
משפט		
		
קבוצה ריקה מוכלת בכל קבוצה		
איחוד		
חיתוך		
הפרש		
הפרש סימטרי		
דיסטריבוטיביות		

הקבוצה המשלימה
(כאשר יש מובן ל U)		
הפרש		
הפרש סימטרי		
		
דה-מורגן		
זהות		

מכפלה קרטזית		
הגדרת זוג סדור		

קבוצת החזקה

קבוצה תת-הקבוצות של A
		
עוצמתה		
דוגמא:		
		
משפט		

יחסים
  
יחס 	תת קבוצה של : 	
יחס הפוך
		
הרכבת יחסים		
יחס משלים		
יחס סימטרי		
		
יחס טרנסיטיבי		
יחס רפלקסיבי
בקבוצה A		
יחס שקילות	רפלקסיבי + סימטרי + טרנסיטיבי	
אי רפלקסיבי		
אנטי סימטרי		
אנטי סימטרי חזק
(גם לא עם עצמו)		
סדר חלקי 	רפלקסיבי + אנטי סימטרי + טרנסיטיבי 	
סדר חלקי חזק 	אי רפלקסיבי + טרנסיטיבי  	
סדר מלא	סדר חלקי    +  	
סדר מלא חזק	סדר חלקי  חזק+ 	
איחוד יחסים		

מחלקת שקילות -  מחלקת השקילות של x  היא כל האיברים שמקיימים את יחס השקילות איתו

קבוצת המנה -  קבוצת מחלקות השקילות.

חלוקות

חלוקה P של A היא קבוצת תת-קבוצות לא ריקות של A
המקיימת		
הקבוצות זרות		

משפט: קבוצת מחלקות השקילות היא חלוקה.

פונקציות

יחס חד ערכי	לכל  קיים לכל היותר  אחד כך ש 	
יחס מלא	לכל  קיים לפחות  אחד כך ש 	
פונקציה	היא יחס מ A ל B חד ערכי ו-מלא	
פונקציה חח"ע	מספר הגדרות:
1. היחס ההפוך חד ערכי
2. 
3. 	
פונקציה על	1. היחס ההפוך מלא
2. 	
הרכבה	
	
כלל 		
פונקציה הפיכה	פונקציה חח"ע ו-על.  נקראת גם פ' שקילות

הרכבת פונקציות

הרכבת פונקציות היא אסוציאטיבית		
אם  חח"ע	אז  חח"ע	
אם  על	אז  על	
אם  חח"ע	אז  חח"ע	
אם  על	אז  על	
אם  חח"ע ו- על	אז  חח"ע	
אם  על ו- חח"ע	אז  על	

משפט:  הפיכה  קיימת ,
כך ש: 
אם קיימת היא יחידה ותסומן: 
חשבון עוצמות

מכפלה		
עוצמת קבוצת היחסים בקבוצה		
קבוצת הפונקציות מ-A ל-B		
ל A,B זרות		
לכל A,B		

הגדרה:    הפיכה	
הגדרה:  A בת מניה  הפיכה	
הגדרה:   קבוצה אינסופית יש לה תת-קבוצה בת מניה	
משפט:   לכל קבוצה סופית A, קיים n טבעי כך שקיימת
          הפיכה, ואז 	
משפט:  אם A בת מניה  ו אז B סופית או בת מניה	

שמות:
א"ב סופי ,  קבוצת כל המחרוזות באורך סופי מעל  .
אם A  אינסופית וקיימת פונקציה חלקית שהיא על, אז A בת מניה.

	1. אם קיימת    חח"ע
2. אם קיימת  על או 	
	אם 
כלומר קיימת  חח"ע 
אבל לא קיימת הפיכה	

משפט קנטור
לכל קבוצה A, 
הוכחה שלא קיימת בעזרת שיטת האלכסון.

משפט קנטור-ברנשטיין

כלל הסנדביץ': אם אז 

חשבון עוצמות אינסופיות
כללי האריתמטיקה הבסיסיים הנוגעים בחיבור, כפל וחזקות של מספרים טבעיים תקפים גם לעוצמות אינסופיות.
אי שויון חלש נשמר.
אי שויון חזק אינו נשמר. 
פעולות הפוכות – חיסור, חילוק, שורש, לוגריתם אינן ניתנות להכללה עבור עוצמות אינסופיות.

מניה בסיסית

עקרון שובך היונים – אם מספר היונים גדול ממספר התאים, יש שתי יונים באותו תא (ניסוח לא פורמאלי להגדרת ">").
עקרון הסכום – חלוקה למקרים. אם זרות אז: 
עקרון הכפל – לניסוי רב שלבי, שבכל שלב אפשרויות בחירה

מעבר למשלים - 
אפשרויות לסדר n אנשים בשורה: , במעגל: 
תמורות ללא חזרות	פ' חח"ע 		
תמורות עם חזרות	פונקציה
		
צרופים ללא חזרות	תת קבוצות בעוצמה k של קבוצה בעוצמה n		
צרופים עם חזרות	לחלק k כדורים ל n תאים		

פונקציות יוצרות

עבור סידרה  הפ' היוצרת תהיה: 
כדי לחלץ את הסדרה מהפונקציה, נשאל: מה המקדם של ?

  

משפט הבינום:

סכום של סידרה הנדסית:

פונקציה יוצרת של סדרת סכומים חלקיים
אם F יוצרת את     אז  יוצרת את

נוסחאות נסיגה

נוסחת נסיגה הומוגנית
לדוגמא:		
1. מחלצים פולינום אופייני		
2. נוסחא לאיבר כללי תהיה		
3. בעזרת תנאי התחלה נמצא את A,B	

נוסחת נסיגה לא הומוגנית
לדוגמא:		
1. נשתמש בפונקציות יוצרות		
2. בד"כ נעזר בשברים חלקיים		
	
3. כדי לפרק את הביטוי לאיבר כללי נעזר בנוסחה		

פונקציות יוצרות מעריכיות
כאשר יש תמורות במקום צרופים
פ' יוצרת מעריכית יוצרת את סידרת הנגזרות שלה ב x=0

לדוגמא:		

	
פתרון		

שיטת ברנולי לפתרון פולינומים
נבנה נוסחת נסיגה כך ששורשי הפולינום האופייני יהיו 
כאשר לכל   k גדול מ 1 . ככל שנפתח את הסדר חלוקת איברים סמוכים תשאף להיות.

למשל חישוב .     נגדיר: 
נפתח פולינום אופייני		
		
סדרת הנסיגה תהיה		

הכלה – הדחה

התכונה הבסיסית		
אופרטור האיחוד של כל האיברים של קבוצה
		
חיתוך של קבוצה ריקה		

נוסחת ההכלה הדחה 
תהי F משפחת תת-קבוצות עם "תכונות רעות" של U סופית
- מספר כל האיברים ללא "תכונות רעות" (שלא שייכים לקבוצות F)
נוסחת ההכלה הדחה 
		
כאשר השימוש ב U אסור		

אי סדר טוטאלי
בכמה תמורות של n איברים שום איבר אינו במקומו הטבעי?

 n זוגי
		
 n אי-זוגי

גרפים

משפט	בכל גרף פשוט בעל 2 קודקודים לפחות, יש זוג קודקודים בעלי אותה דרגה	
משפט	סכום דרגות הקודקודים שווה כפלים מספר הקשתות

גרף פשוט	גרף ללא לולאות וללא קשתות מקבילות	
תת גרף	יקרא תת גרף של G אם .
אם G' מכיל קשת אז שתי קצותיה ימצאו גם ב G'.	
תת גרף מושרה	תת גרף של G=(V,E), שקבוצת קודקודיו V' ומכיל את כל הקשתות ב E ששני קודקודיהם ב V'.	
טיול \ הילוך	סדרת קודקודים, שבין כל שני עוקבים בה, יש קשת.	
מסלול \ מסילה	הילוך שבו אף קשת לא חוזרת יותר מפעם אחת	
מסלול פשוט	הילוך שבו אף קודקוד לא חוזר יותר מפעם אחת	
מעגל	מסלול שבו הקודקוד הראשון והאחרון זהים	
מעגל פשוט	מסילה פשוטה סגורה בקשת בין הקצוות	
קשירות	היחס על v: "קיים מסלול בין קודקוד x ל y".
זהו יחס שקילות.	
רכיב קשירות	כל תת גרף המושרה ע"י מחלקת השקילות של היחס	
גרף קשיר	גרף בעל רכיב קשירות יחיד	
עץ	גרף קשיר שאין בו מעגלים מספר קשתות  	
יער	גרף שאין בו מעגלים (ולכן גם פשוט)
מספר קשתות  	
מעגל אוילר	מעגל הכולל את כל קשתות הגרף (כ"א פעם אחת).
	
גרף אוילר	גרף קשיר שיש בו מעגל אוילר.
- ניתן לצייר גרף אוילר במשיכת קולמוס אחת.	
משפט	גרף קשיר הוא גרף אוילר  לכל קודקוד x, זוגי.	
בגרף מכוון	גרף קשיר מכוון הוא גרף אוילר אם לכל קודקוד x, דרגת הכניסה שווה לדרגת היציאה    .	
הגרף השלם	הגרף השלם על n קודקודים הוא הגרף שבו קיימת קשת בין כל זוג קודקודים שונים מסומן:   .	
גרף דו צדדי	הוא דו צדדי אם ניתן לחלק את V לשתי קבוצות זרות כך שכל קשתות הגרף הם בין הקבוצות	
משפט	גרף דו צדדי  אין בו מעגל באורך אי זוגי.	

איזומורפיזם
גרפים הם איזומורפיים אם קיימת פונקציה הפיכה  עבורה לכל זוג קודקודים יש ביניהם קשת ב     יש קשת בין ל  ב .
בגרפים איזומורפיים:  ו- .

גרף משלים
בהינתן גרף , הגרף המשלים הוא על אותם קודקודים כך שבין כל שני קודקודים יש קשת ב     אין ביניהם קשת ב.

משפט העצים
יהי T גרף בעל n קודקודים. הטענות הבאות שקולות:
1.	T הוא עץ
2.	T קשיר מינימאלי
3.	T חסר מעגלים מקסימלי
4.	T קשיר בעל n-1 קשתות
5.	T חסר מעגלים בעל n-1 קשתות
6.	לכל זוג קודקודים יש ב T מסילה יחידה, שהם קצותיה
7.	T קשיר, ובכל תת גרף שלו יש קודקוד בדרגה 0 או 1.

נוסחת קיילי
מספר העצים בעלי קודקודים הוא  .

קוד פריפר
התאמת סדרה לעץ:
1.	מורידים את העלה הכי נמוך
2.	רושמים את הקודקוד המחובר אליו
3.	ממשיכים עד שנשארת קשת אחת ושני קודקודים

כל קודקוד  מופיע  פעמים בסדרה. אורך הסדרה n-2.

התאמת עץ לסדרה:
1.	יוצרים טבלה של כל הקודקודים ודרגותיהם בעץ
2.	עוברים על תווי הסדרה באותו כיוון שיצרנו אותה (שמאל לימין)
3.	מוצאים עלה בעל מספר מינימאלי ומחברים אותו לתו הנוכחי בסדרה
4.	מעדכנים את הדרגות (מחסירים 1 פעמיים) ומוחקים את התו, שהשתמשנו בו. וחוזר חלילה...

דיאגרמה מישורית	של גרף היא דיאגרמה במישור שבו כל נקודת חיתוך היא קודקוד	
גרף מישורי	גרף שיש לו דיאגרמה מישורית	
נוסחת אוילר	גרף מישורי קשיר. נסמן: n מספר הקודקודים, m מספר הקשתות, f מספר הפאות 
	
גרף מישורי משולשי	גרף משורי שכל פאותיו משולשים	
משפט	גרף מישורי בעל מספר מקסימלי של קשתות ו 3 קודקודים לפחות הוא גרף משולשי.	
משפט 	בגרף מישורי סכום היקפי הפאות הוא פעמיים מספר הקשתות. ובגרף משולשי:  .  
ביחד עם נוסחת אוילר:
	
משפט	בגרף מישורי פשוט בעל לפחות 3 קודקודים:
	
משפט	בגרף דו צדדי מישורי פשוט בעל לפחות 3 קודקודים:

משפט קורטובסקי
גרף מישורי       אי אפשר לכווץ אותו ל או ל .

מספר הצביעה	של גרף הוא מספר הצבעים המינימאלי שבו ניתן לצבוע את כל הקודקודים בגרף כך שאין קודקודים סמוכים באותו צבע	
גרף k צביע	ניתן לצבוע את הגרף ב k צבעים כך ששתי קצוות של כל קשת צבועים בצבעים שונים. כלומר, מספר הצביעה הוא k לכל היותר	
		
גרף דואלי	של גרף מישורי הוא בעל אותה קבוצת קשתות של הגרף המקורי. הקודקודים שלו הם הפאות של הגרף המקורי וקצות כל קשת הן הפאות משני צידיה.

הגרף הדואלי לגרף אוילר הוא דו-צדדי – כל מפה מצוירת ב"משיכת קולמוס" אפשר לצבוע בשני צבעים	
		
משפט ארבעת הצבעים	כל גרף מישורי ללא לולאות הוא 4-צביע. בנוסח דואלי: אפשר לצבוע כל "מפה" בארבעה צבעים לכל היותר, כך שלמדינות גובלות צבעים שונים. בכיתה הוכחנו גירסאות חלשות יותר – כל גרף משורי ללא לולאות הוא 6-צביע. כל גרף משורי ללא לולאות הוא 5-צביע