תרגול 2 תשעז

חזרה לדף מערכי התרגול.

כַּמָּתִים ופרדיקטים

פרדיקטים

בלוגיקה מתמטית, פרדיקט הוא פונקציה המקבלת משתנה או כמה משתנים, ומחזירה ערך אמת (T או F). זוהי הכללה של האטומים שפגשנו בתרגול הקודם, שאינם אלא פרידקטים ללא משתנים. לדוגמה ניתן להגדיר את הפרדיקט [math]\displaystyle{ S(x) }[/math] להיות "[math]\displaystyle{ x }[/math] הינו סטודנט באוניברסיטה".

גם אטומים וגם פרדיקטים יכולים להיות אמיתיים (מסמנים 1 או T) או שקריים (מסמנים 0 או F). המינוח המקובל הוא שאטום/פרדיקט הוא בעל ערך אמת T (במידה שהוא נכון) או בעל ערך אמת F (במידה שאינו נכון).

כיוון שאטומים הם ללא משתנים הם יכולים להיות T או F אבל לא שניהם. לעומתם, פרדיקטים הם תלויים במשתנים ולכן ערך האמת שלהם יקבע לפי ההצבה במשתנים. למשל הפרדיקט [math]\displaystyle{ P(x,y)=x\lt y }[/math] יהיה נכון במקרה ש [math]\displaystyle{ P(2,3) }[/math] ולא נכון במקרה ש [math]\displaystyle{ P(3,2) }[/math].

כמתים

בנוסף, לקשרים ניתן להוסיף כמתים (quantifiers). החשובים שבהם הם הכמת "לכל" [math]\displaystyle{ \forall }[/math] (זו A הפוכה, קיצור המילה All) והכמת "קיים" [math]\displaystyle{ \exist }[/math] (זו E הפוכה, קיצור המילה Exist).

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

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

לעומתה הטענה השניה טוענת שניתן למצוא סטודנט אחד (לפחות) שהוא חרוץ (אם רוצים להוכיח את הטענה צריך למצוא סטודנט שהוא חרוץ ואם רוצים להוכיח כי הטענה לא נכונה צריך לעבור בין כל הסטודנטים ולוודא שהם אינם חרוצים).

תרגיל: הצרן: לכל מספר p גדול מ-1: (p ראשוני) אמ"מ (אם הוא מחלק מכפלת מספרים אז הוא מחלק את אחד המספרים).

פתרון: ההצרנה [math]\displaystyle{ \forall p \gt 1 : (P(p)\iff Q(p)) }[/math] כאשר

• [math]\displaystyle{ P(x) }[/math] הוא הפרדיקט "[math]\displaystyle{ x }[/math] הוא ראשוני".
• [math]\displaystyle{ Q(x) }[/math] הוא הפרדיקט [math]\displaystyle{ \forall a,b : p|ab \Rightarrow (p|a \lor p|b) }[/math]

הערה: שמות המשתנים אינם חשובים למשל עבור הפרדיקט [math]\displaystyle{ S(x,y) }[/math] המוגדר [math]\displaystyle{ x\leq y }[/math] הפסוק [math]\displaystyle{ \forall x\forall y S(x,y) }[/math] הוא זהה לפסוק [math]\displaystyle{ \forall t\forall s S(t,s) }[/math].

הערה: סדר הכמתים כן משנה (לפעמים) למשל [math]\displaystyle{ \exist x\forall y S(x,y) }[/math] לא שקול לפסוק [math]\displaystyle{ \forall y \exist x S(x,y) }[/math].

לדוגמא: יש הבדל בין "לכל סיר קיים מכסה" לבין "קיים מכסה שמתאים לכל סיר". האם אחד מן הפסוקים האלו גורר את השני?

עוד דוגמא: הצרן את המשפט "לכל מספר טבעי יש מספר טבעי הגדול ממנו" פתרון: [math]\displaystyle{ \forall n\in\mathbb{N}\,\exists m\in\mathbb{N}:n\lt m }[/math] לעומת זאת [math]\displaystyle{ \exists m\in\mathbb{N}\,\forall n\in\mathbb{N}:n\lt m }[/math] פירושו שקיים מספר טבעי שגדול מכל המספרים הטבעיים.

נשים לב כי בשביל לקבוע אם הפסוק [math]\displaystyle{ \forall x P(x) }[/math] אנחנו צריכים לדעת איזה [math]\displaystyle{ x }[/math]-ים "חוקיים" (בהנחה שאנחנו יודעים את [math]\displaystyle{ P }[/math]).

סימון: נעיר שיש דרכים רבות לכתוב פסוקים כגון אלו. מקובל למשל [math]\displaystyle{ \forall x P(x) }[/math], [math]\displaystyle{ (\forall x)P(x) }[/math] או [math]\displaystyle{ \forall x, P(x) }[/math]. כל הסגנונות חוקיים, בתנאי שהפסוק ניתן לקריאה באופן חד-משמעי.

שלילת פסוקים

מהי השלילה של הפסוק "לכל סיר יש מכסה המתאים לו", או "לכל מאכל, יש מישהו שמכין אותו טעים"?

בעת שלילה של פסוק לוגי, הכמתים 'לכל' ו'קיים' מתחלפים זה עם זה, והשלילה עוברת הלאה. כלומר לכל פרדיקט [math]\displaystyle{ P }[/math],

• [math]\displaystyle{ \ \neg \forall x: P(x) \equiv \exists x: \neg P(x) }[/math], וכך גם
• [math]\displaystyle{ \ \neg \exists x: P(x) \equiv \forall x: \neg P(x) }[/math].

שלילה על הקשרים ניתן לבצע באמצעות טאוטולוגיות וטבלאות אמת.

תרגיל

כתבו פסוק השקול לפסוק הבא ללא שימוש בקשר השלילה.

[math]\displaystyle{ \lnot (\forall a\in \mathbb{Z} \exists b\in \mathbb{N} (a|b\rightarrow (a\lt b\land a+b\neq 0))) }[/math]

פיתרון:

[math]\displaystyle{ \exists a\in \mathbb{Z} \forall b\in \mathbb{N} (a|b \land (a\geq b \lor a+b=0)) }[/math]

שימו לב שנעזרו בשקילות [math]\displaystyle{ \ (A\rightarrow B) \equiv ((\neg A) \lor B) }[/math] ובחוקי דה-מורגן.

תרגיל

הוכח או הפרך (משתני הפרדיקט נלקחים מהטבעיים):

א. [math]\displaystyle{ (\forall n (P(n) \lor Q(n))) \Rightarrow ((\forall n P(n)) \lor (\forall n Q(n))) }[/math]

ב. [math]\displaystyle{ (\forall n (P(n) \lor Q(n))) \Leftarrow ((\forall n P(n)) \lor (\forall n Q(n))) }[/math]

פיתרון:

א. הפרכה. ניקח את [math]\displaystyle{ P(n) }[/math] להיות [math]\displaystyle{ 1 }[/math] על הזוגיים ו-[math]\displaystyle{ 0 }[/math] על אי-זוגיים, ו-[math]\displaystyle{ Q(n) }[/math] להפך. אכן כל מספר טבעי הוא זוגי או אי-זוגי, אך זה לא נכון שכל מספר הוא זוגי או שכל מספר הוא אי-זוגי.

ב. הוכחה: יהי [math]\displaystyle{ n }[/math] לפי הנתון מתקיים [math]\displaystyle{ P(n) \lor Q(n) }[/math] כדרוש.

• תרגיל: הצרן את המשפט "כל מספר ממשי ניתן לקרב ע"י מספרים רציונאליים בקירוב טוב כרצוננו"

פתרון: [math]\displaystyle{ \forall x\in\mathbb{R}\,\exists A\subset\mathbb{Q}:\forall\epsilon\in\mathbb{R}_{+}\exists q\in A\,:|x-q|\lt \epsilon }[/math] .

מה היא שלילתו של המשפט?

פתרון: נכתוב את השלילות השונות האפשריות:

• [math]\displaystyle{ \neg(\forall x\in\mathbb{R}\,\exists A\subset\mathbb{Q}:\forall\epsilon\in\mathbb{R}_{+}\exists q\in A\,:|x-q|\lt \epsilon ) }[/math]
• [math]\displaystyle{ \exists x\in\mathbb{R}\,\neg( \exists A\subset\mathbb{Q}:\forall\epsilon\in\mathbb{R}_{+}\exists q\in A\,:|x-q|\lt \epsilon ) }[/math]
• [math]\displaystyle{ \exists x\in\mathbb{R}\, \forall A\subset\mathbb{Q}:\neg(\forall\epsilon\in\mathbb{R}_{+}\exists q\in A\,:|x-q|\lt \epsilon ) }[/math]
• [math]\displaystyle{ \exists x\in\mathbb{R}\, \forall A\subset\mathbb{Q}:\exists\epsilon\in\mathbb{R}_{+}\neg(\exists q\in A\,:|x-q|\lt \epsilon ) }[/math]
• [math]\displaystyle{ \exists x\in\mathbb{R}\, \forall A\subset\mathbb{Q}:\exists\epsilon\in\mathbb{R}_{+}\forall q\in A\,\neg(:|x-q|\lt \epsilon ) }[/math]
• [math]\displaystyle{ \exists x\in\mathbb{R}\,\forall A\subset\mathbb{Q}:\exists\epsilon\in\mathbb{R}_{+}\forall q\in A\,:|x-q|\geq\epsilon }[/math]

תרגילים: דוגמאות של הצרנת ושלילת המושגים 'תלות לינארית', 'גבול סדרה', 'חח"ע', וכדומה