יסודות הלוגיקה ותורת הקבוצות

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

פסוקים, קשרים לוגיים וטבלאות אמת

פסוק הוא טענה שאפשר לייחס לה ערך אמת: אמת או שקר. למשל, הטענה „7 הוא מספר ראשוני” היא פסוק אמת, והטענה „4=5” היא פסוק שקר. שאלה כמו „מהו מספר ראשוני?” או ציווי כמו „הוכח את הטענה” אינם פסוקים, משום שאין להם ערך אמת.

במתמטיקה מופיעים גם ביטויים תלויי משתנה, למשל „x>2”. ביטוי כזה אינו פסוק כל עוד לא נקבעו תחום המשתנה וערכו. למשל, אם קובעים ש־x הוא מספר ממשי ו־x=3, מתקבל פסוק אמת; אם x=1, מתקבל פסוק שקר.

קשרים לוגיים מאפשרים לבנות פסוקים מורכבים מפסוקים פשוטים. הסימונים המקובלים הם:

• שלילה: ¬P. אמת כאשר P שקר, ושקר כאשר P אמת.
• וגם: P∧Q. אמת רק כאשר שני הרכיבים אמת.
• או: P∨Q. אמת כאשר לפחות אחד מהרכיבים אמת.
• גרירה: P→Q. אמת פרט למקרה שבו P אמת ו־Q שקר.
• שקילות: P↔Q. אמת כאשר לשני הרכיבים אותו ערך אמת.

טבלת אמת מציגה את ערך האמת של פסוק מורכב בכל הצירופים האפשריים של ערכי הרכיבים. הטבלה הבאה מגדירה את השלילה, ה„וגם” וה„או”:

p	q	¬p	p∧q	p∨q
אמת	אמת	שקר	אמת	אמת
אמת	שקר	שקר	שקר	אמת
שקר	אמת	אמת	שקר	אמת
שקר	שקר	אמת	שקר	שקר

ה„או” המתמטי הוא או כוללני: הוא מתקיים גם כאשר שני התנאים נכונים. לכן הטענה „מספר טבעי הוא זוגי או גדול מ־5” נכונה גם עבור 6, משום שהוא מקיים את שני התנאים.

הגרירה היא הקשר המרכזי במשפטים מהצורה „אם... אז...”. טבלת האמת שלה היא:

p	q	p→q
אמת	אמת	אמת
אמת	שקר	שקר
שקר	אמת	אמת
שקר	שקר	אמת

הגרירה מקבלת את ערך האמת שקר רק כאשר ההנחה אמת והמסקנה שקר. אם ההנחה שקר, הגרירה נחשבת אמת מבחינה פורמלית, גם אם המסקנה שקר. אפשר להבין שקילות כשילוב של שתי גרירות: P↔Q שקולה ל־(P→Q)∧(Q→P).

קבוצות, שייכות, הכלה ושוויון

קבוצה היא אוסף מוגדר היטב של עצמים מתמטיים. העצמים שבאוסף נקראים איברים. נהוג לסמן קבוצות באותיות לטיניות גדולות, כגון A או B, ואת האיברים באותיות קטנות, כגון x.

אפשר לתאר קבוצה ברשימה מפורשת של איבריה, למשל A={1,2,3}, או באמצעות תכונה, למשל B={x∈ℕ | x זוגי}, כלומר קבוצת המספרים הטבעיים הזוגיים. סדר האיברים ברשימה אינו משנה, וגם חזרה על איבר אינה משנה את הקבוצה: {1,2,1} היא אותה קבוצה כמו {1,2}.

שייכות היא יחס בין איבר לקבוצה. הסימון x∈A פירושו ש־x הוא איבר של A. הסימון x∉A פירושו ש־x אינו איבר של A. למשל, אם A={1,2,3}, אז 2∈A אך 4∉A.

הכלה היא יחס בין שתי קבוצות. נאמר ש־A מוכלת ב־B, ונסמן A⊆B, אם כל איבר של A הוא גם איבר של B. בניסוח לוגי:

A⊆B פירושו ∀x, אם x∈A אז x∈B.

הקבוצה הריקה, המסומנת ∅, היא קבוצה שאין בה איברים. היא מוכלת בכל קבוצה: ∅⊆A. הסיבה היא שאין ב־∅ איבר שיכול להפר את תנאי ההכלה.

שוויון בין קבוצות פירושו שיש להן בדיוק אותם איברים. אם A ו־B הן קבוצות, אז A=B אם ורק אם כל איבר של A שייך ל־B וכל איבר של B שייך ל־A. לכן דרך שימושית להוכיח שוויון היא להוכיח שתי הכלות: A⊆B וגם B⊆A.

דוגמה: נגדיר A={1,2}, B={1,2,3}, C={2,1}. אז A⊆B, כי כל איבר של A נמצא גם ב־B. גם A=C, כי שתי הקבוצות מכילות בדיוק את האיברים 1 ו־2, והסדר אינו משנה. לעומת זאת, B≠A, כי 3∈B אך 3∉A.

שייכות והכלה הן יחסים שונים. הביטוי 1∈A אומר שהמספר 1 הוא איבר של A. הביטוי {1}⊆A אומר שהקבוצה המכילה רק את 1 מוכלת ב־A. לעומת זאת, הביטוי {1}∈A אינו נכון בדרך כלל, משום ש־{1} היא קבוצה ולא מספר. אם רוצים שקבוצה תופיע כאיבר, יש להגדיר זאת במפורש. למשל, אם D={{1},2}, אז {1}∈D.

איחוד, חיתוך, משלים והפרש

פעולות על קבוצות מאפשרות לבנות קבוצה חדשה מקבוצות נתונות. נניח ש־U היא קבוצת אוניברסום, כלומר קבוצת כל העצמים הרלוונטיים לדיון, ו־A ו־B הן קבוצות המוכלות ב־U.

איחוד של שתי קבוצות הוא קבוצת כל האיברים שנמצאים לפחות באחת מהן:

A∪B = {x∈U | x∈A או x∈B}

חיתוך של שתי קבוצות הוא קבוצת כל האיברים שנמצאים בשתיהן:

A∩B = {x∈U | x∈A וגם x∈B}

ההפרש A\B הוא קבוצת האיברים שנמצאים ב־A אך אינם ב־B:

A\B = {x∈U | x∈A וגם x∉B}

המשלים של A ביחס לאוניברסום U הוא קבוצת כל האיברים של U שאינם ב־A:

A^c = U\A = {x∈U | x∉A}

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

U={1,2,3,4,5,6}
A={1,2,3,4}
B={3,4,5}

אז:

• A∪B={1,2,3,4,5}
• A∩B={3,4}
• A\B={1,2}
• B\A={5}
• A^c={5,6}

הדוגמה מראה שההפרש אינו פעולה סימטרית: A\B ו־B\A אינן שוות בדרך כלל. אם החיתוך של שתי קבוצות ריק, כלומר A∩B=∅, אומרים ש־A ו־B זרות.

דיאגרמת ון ממחישה את הקשר בין האזורים השונים. כאשר שני מעגלים חופפים בתוך מלבן האוניברסום, האיחוד הוא כל שטח שני המעגלים והחיתוך הוא האזור המשותף. ההפרש A\B הוא החלק של A שאינו ב־B, והמשלים A^c הוא כל מה שנמצא מחוץ ל־A אך בתוך האוניברסום.

תרגום טענה מתמטית לניסוח לוגי מדויק

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

השלבים העיקריים בתרגום הם:

1. זיהוי המשתנים ותחומם: מספרים טבעיים ℕ, שלמים ℤ, רציונליים ℚ, ממשיים ℝ או קבוצה כללית.
2. פירוק התנאים בטענה לקשרים לוגיים.
3. בחירת הכמתים המתאימים: ∀ פירושו „לכל”, ∃ פירושו „קיים”.
4. בדיקת סדר הכמתים והקשרים, משום ששינוי הסדר עשוי לשנות את המשמעות.

הסימון k | n פירושו ש־k מחלק את n, כלומר ש־n מתחלק ב־k.

דוגמה ראשונה: „ריבועו של כל מספר ממשי אינו שלילי”. נזהה את המשתנה x בתחום ℝ ואת התכונה x²≥0. הניסוח הפורמלי הוא:

∀x∈ℝ, x²≥0

דוגמה שנייה: „קיים מספר שלם שהוא זוגי וגדול מ־10”. כאן נדרש קיום, ולכן משתמשים ב־∃. התכונות „זוגי” ו„גדול מ־10” חייבות להתקיים יחד, ולכן הן מחוברות ב־∧:

∃n∈ℤ, (2 | n) ∧ (n>10)

דוגמה שלישית: „אם מספר טבעי מתחלק ב־6, אז הוא מתחלק ב־2”. זו טענה על כל מספר טבעי, ולכן מופיע ∀. התנאי „מתחלק ב־6” הוא ההנחה, ו„מתחלק ב־2” הוא המסקנה, ולכן הקשר הוא גרירה:

∀n∈ℕ, (6 | n) → (2 | n)

בטענות הכוללות „לכל” משתמשים לעיתים קרובות בגרירה: אם העצם שייך לתחום או מקיים תנאי מסוים, אז נובעת מסקנה. לעומת זאת, בטענות הכוללות „קיים” משתמשים לעיתים קרובות בקשר „וגם”, משום שדורשים מאותו עצם לקיים כמה תכונות יחד.

הקשר בין לוגיקה לקבוצות ניכר בתרגום טענות על שייכות והכלה. למשל, הטענה „A מוכלת ב־B” מתורגמת כך:

∀x, (x∈A) → (x∈B)

הטענה „ל־A ול־B יש איבר משותף” מתורגמת כך:

∃x, (x∈A) ∧ (x∈B)

טענה זו שקולה לטענה ש־A∩B≠∅. הטענה „אין איבר של A שאינו ב־B” שקולה ל־A\B=∅ וגם ל־A⊆B.

גם שלילת טענות כמתיות מתורגמת לפי כללים קבועים. שלילת „לכל” הופכת ל„קיים” עם שלילת התכונה:

¬(∀x, P(x)) ≡ ∃x, ¬P(x)

שלילת „קיים” הופכת ל„לכל” עם שלילת התכונה:

¬(∃x, P(x)) ≡ ∀x, ¬P(x)

למשל, הטענה „לא כל המספרים הממשיים חיוביים” פירושה שקיים מספר ממשי שאינו חיובי:

∃x∈ℝ, x≤0

דוגמה מלאה לתרגום: ננסח את הטענה „לכל מספר טבעי, אם הוא זוגי ומתחלק ב־3, אז הוא מתחלק ב־6”. תחילה נזהה את המשתנה n ואת התחום ℕ. לאחר מכן נפרק את ההנחה לשתי תכונות: „זוגי” ו„מתחלק ב־3”, ונחבר אותן ב־∧. המסקנה היא „מתחלק ב־6”. הניסוח הלוגי הוא:

∀n∈ℕ, ((2 | n) ∧ (3 | n)) → (6 | n)

זהו ניסוח מדויק של הטענה: התחום, התנאים והקשר ביניהם מפורשים.