תרגול 2 תשעז: הבדלים בין גרסאות בדף

מתוך Math-Wiki
(יצירת דף עם התוכן "==כמתים ופרדיקטים== ===פרדיקטים=== בניגוד לאטומים שהם ללא משתנים ה'''פרדיקטים''' הינם פונקצי...")
 
 
(26 גרסאות ביניים של 4 משתמשים אינן מוצגות)
שורה 1: שורה 1:
==כמתים ופרדיקטים==
חזרה ל[[83-116, בדידה 1 להנדסה, מערכי תרגול|דף מערכי התרגול]].
 
==כַּמָּתִים ופרדיקטים==


===פרדיקטים===
===פרדיקטים===


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


גם אטומים וגם פרדיקטים יכולים להיות אמיתיים (מסמנים 1 או T) או שקריים (מסמנים 0 או F). המינוח המקובל הוא שאטום/פרדיקט הוא בעל '''ערך אמת''' T (במידה שהוא נכון) או בעל ערך אמת F (במידה שאינו נכון)
גם אטומים וגם פרדיקטים יכולים להיות אמיתיים (מסמנים 1 או T) או שקריים (מסמנים 0 או F). המינוח המקובל הוא שאטום/פרדיקט הוא בעל '''ערך אמת''' T (במידה שהוא נכון) או בעל '''ערך אמת''' F (במידה שאינו נכון).
כיוון שאטומים הם ללא משתנים הם יכולים להיות T או F אבל לא שניהם. לעומתם פרדיקטים הם תלויים במשתנים ולכן ערך האמת שלהם יקבע לפי ההצבה במשתנים. למשל הפרדיקט <math>S(x,y)=x<y</math> יהיה נכון במקרה ש <math>S(2,3)</math> ולא נכון במקרה ש <math>S(3,2)</math>


הצרן: לכל מספר p גדול מ-1:  (p ראשוני) אמ"מ (אם הוא מחלק מכפלת מספרים אז הוא מחלק את אחד המספרים).
כיוון שאטומים הם ללא משתנים הם יכולים להיות T או F אבל לא שניהם. לעומתם, פרדיקטים הם תלויים במשתנים ולכן ערך האמת שלהם יקבע לפי ההצבה במשתנים. למשל הפרדיקט <math>P(x,y)=x<y</math> יהיה נכון במקרה ש <math>P(2,3)</math> ולא נכון במקרה ש <math>P(3,2)</math>.
 
פתרון: 
ההצרנה <math>\forall p >1 : (P(p)\iff Q(p))</math> כאשר
*  <math>P(x)</math> הוא הפרדיקט "x" הוא ראשוני.
* <math>Q(x)</math> הוא הפרדיקט <math>\forall a,b : p|ab \Rightarrow (p|a \lor p|b)</math>


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


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


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


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


בעת שלילה של פסוק לוגי, הכמתים 'לכל' ו'קיים' מתחלפים זה עם זה, והשלילה עוברת הלאה. את השלילה על הקשרים ניתן לבצע באמצעות טאוטולוגיות וטבלאות אמת.
פתרון: 
ההצרנה <math>\forall p >1 : (P(p)\iff Q(p))</math> כאשר
*  <math>P(x)</math>  הוא הפרדיקט "<math>x</math> הוא ראשוני".
* <math>Q(x)</math> הוא הפרדיקט <math>\forall a,b : p|ab \Rightarrow (p|a \lor p|b)</math>


לדוגמא:
הערה: סדר הכמתים כן משנה (לפעמים) למשל <math>\exist x\forall y S(x,y)</math> לא שקול לפסוק <math>\forall y \exist x S(x,y)</math>.


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


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


*"'''קיים''' אדם כך ש'''לא''' קיים דג עם מספר קשקשים כגיל האדם או שאורכו עשירית מאורך האדם"
נשים לב כי בשביל לקבוע אם הפסוק <math>\forall x P(x)</math> אנחנו צריכים לדעת איזה <math>x</math>-ים "חוקיים" (בהנחה שאנחנו יודעים את <math>P</math>).


נמשיך:
'''סימון:''' נעיר שיש דרכים רבות לכתוב פסוקים כגון אלו. מקובל למשל <math>\forall x P(x)</math>, <math>(\forall x)P(x)</math>  או <math>\forall x, P(x)</math>. כל הסגנונות חוקיים, בתנאי שהפסוק ניתן לקריאה באופן חד-משמעי.


*"קיים אדם ש'''לכל''' דג בעולם '''לא נכון''' ש(יש לו מספר קשקשים כגיל האדם או שאורכו עשירית מאורך האדם)"
הערה: לכל כמת יש אזור תחולה. בתוך אזור תחולה שמות המשתנים אינם חשובים. למשל עבור הפרדיקט <math>S(x,y)</math> המוגדר <math>x\leq y</math> הפסוק <math>\forall x\forall y S(x,y)</math> הוא זהה לפסוק <math>\forall t\forall s S(t,s)</math>.


כלומר
====תרגיל====
*"קיים אדם שלכל דג בעולם יש מספר קשקשים שונה מגיל האדם וגם אורכו של הדג שונה מעשירית אורך האדם"


שימו לב שגם למשתנים בהגדרות יש אזור תחולה. צריך לשים לב לא להתבלבל באזורים האלו, וכדי למנוע "התנגשויות" בשמות, פשוט נחליף אותם. למשל נגדיר מספר <math>x</math> להיות '''דו־ריבועי''' אם קיימים <math>y,z</math> כך ש-<math>x=y^2+z^2</math>. הוכיחו שלכל זוג מספרים <math>x,y</math> אם הם מספרים דו־ריבועיים, אז גם המספר <math>xy</math> הוא דו־ריבועי.


הערה: סדר הכמתים הוא חשוב (כמו בעברית) - לדוגמא: יש הבדל בין "לכל סיר קיים מכסה" לבין "קיים מכסה שמתאים לכל סיר".דוגמא: הצרן את המשפט "לכל מספר טבעי יש מספר טבעי הגדול ממנו" פתרון: <math>\forall n\in\mathbb{N}\,\exists m\in\mathbb{N}:n<m</math> לעומת זאת <math>\exists m\in\mathbb{N}\,\forall n\in\mathbb{N}:n<m</math> פירושו שקיים מספר טבעי שגדול מכל המספרים הטבעיים.
פתרון: נגדיר את הפרדיקט <math>Q(x)</math> להיות T אם ורק אם <math>x</math> הוא מספר דו־ריבועי (הצרינו זאת!). אנו נדרשים להוכיח את הטענה <math>\forall x\forall y:(Q(x) \land Q(y)) \rightarrow Q(xy)</math>.


*תרגיל: הצרן את המשפט "כל מספר ממשי ניתן לקרב ע"י מספרים רציונאליים בקירוב טוב כרצוננו"
לפי ההגדרה, אם <math>x</math> הוא דו־ריבועי, אז קיימים <math>a,b</math> כך ש-<math>x=a^2+b^2</math>, ובאופן דומה אם <math>y</math> דו־ריבועי, אז קיימים <math>c,d</math> כך ש-<math>y=c^2+d^2</math>. כדי להוכיח ש-<math>xy</math> הוא גם דו־ריבועי, יש להראות שקיימים <math>e,f</math> כך ש-<math>xy=e^2+f^2</math>. נעזר בזהות <math>(a^2+b^2)(c^2+d^2) = (ac-bd)^2+(ad+bc)^2</math>. לכן קיבלנו <math>xy = (ac-bd)^2+(ad+bc)^2</math>, ומכאן שנוכל לבחור את <math>e,f</math> הדרושים לנו להיות  <math>e=ac-bd</math>, <math>f=ad+bc</math>.
פתרון: <math>\forall x\in\mathbb{R}\,\exists A\subset\mathbb{Q}:\forall\epsilon\in\mathbb{R}_{+}\exists q\in A\,:|x-q|<\epsilon</math> .


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


פתרון: נכתוב את הרמות השונות
בעת שלילה של פסוק לוגי, הכמתים 'לכל' ו'קיים' מתחלפים זה עם זה, והשלילה עוברת הלאה. כלומר לכל פרדיקט <math>P</math>,
* <math>\neg(\forall x\in\mathbb{R}\,\exists A\subset\mathbb{Q}:\forall\epsilon\in\mathbb{R}_{+}\exists q\in A\,:|x-q|<\epsilon )</math>
* <math>\ \neg \forall x: P(x) \equiv \exists x: \neg P(x)</math>, וכך גם
* <math>\exists x\in\mathbb{R}\,\neg( \exists A\subset\mathbb{Q}:\forall\epsilon\in\mathbb{R}_{+}\exists q\in A\,:|x-q|<\epsilon )</math>
* <math>\ \neg \exists x: P(x) \equiv \forall x: \neg P(x)</math>.
* <math>\exists x\in\mathbb{R}\, \forall A\subset\mathbb{Q}:\neg(\forall\epsilon\in\mathbb{R}_{+}\exists q\in A\,:|x-q|<\epsilon )</math>
* <math>\exists x\in\mathbb{R}\, \forall A\subset\mathbb{Q}:\exists\epsilon\in\mathbb{R}_{+}\neg(\exists q\in A\,:|x-q|<\epsilon )</math>
* <math>\exists x\in\mathbb{R}\, \forall A\subset\mathbb{Q}:\exists\epsilon\in\mathbb{R}_{+}\forall q\in A\,\neg(:|x-q|<\epsilon )</math>
*<math>\exists x\in\mathbb{R}\,\forall A\subset\mathbb{Q}:\exists\epsilon\in\mathbb{R}_{+}\forall q\in A\,:|x-q|\geq\epsilon</math>


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


==קבוצות קשרים שלמות==
====תרגיל====
הוכיחו או הפריכו:


תרגיל: הוכח באמצעות טבלאות אמת שניתן להציג את הקשרים 'גרירה' ו'וגם' באמצעות 'או' ושלילה בלבד
<math>\lnot (\forall a\in \mathbb{N} \exists b\in \mathbb{N} (a|b\rightarrow (a\leq b\land a+b<a\cdot b)))</math>


פתרון:  
פיתרון: ראשית נראה מה הטענה בעצם אומרת:
מתקיים <math>A\to B \equiv \neg A \or B</math>
ומתקיים <math>A \and B \equiv \neg(\neg A \or \neg B)</math>


===צורות נורמליות: CNF ,DNF===
<math>\exists a\in \mathbb{N} \forall b\in \mathbb{N} (a|b \land (a>b \lor a+b\geq a\cdot b))</math>


ישנן שתי "צורות נורמליות" להצגת '''כל''' פסוקית - DNF ו CNF.
שימו לב שנעזרו בשקילות <math>\ (A\rightarrow B) \equiv ((\neg A) \lor B)</math> ובחוקי דה-מורגן. כעת נשים לב שאם <math>a|b</math> אז <math>a\leq b</math> ולכן כדי שזה יהיה נכון צריך שיתקיים <math>a+b\geq a\cdot b</math> וזה אכן קורה עבור <math>a=1</math>.


===DNF===
====תרגיל====


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


בצורה סכמטית: <math>D_1 \lor D_2 \lor \dots \lor D_n</math> כאשר כל <math>D_i</math> מהצורה <math>p_1\land p_2 \land \dots \land p_m</math> וכל <math>p_i</math> שווה למשתנה <math>x</math>
א. <math>(\forall n (P(n) \lor Q(n))) \Rightarrow ((\forall n P(n)) \lor (\forall n Q(n)))</math>
או לשלילתו <math>\lnot x</math>.


דוגמא: נמצא את צורת DNF של טבלת האמת הבאה:
ב. <math>(\forall n (P(n) \lor Q(n))) \Leftarrow ((\forall n P(n)) \lor (\forall n Q(n)))</math>


פיתרון:


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


{| border="1" align="center" style="text-align:center;"
ב. הוכחה: יהי <math>n</math>. אם מתקיים <math>P(n)</math> אז בפרט מתקיים <math>P(n) \lor Q(n)</math> כדרוש. אחרת, לפי השקילות <math>a\lor b \equiv \lnot a \rightarrow b</math>, מתקיים שלכל מס' טבעי, ובפרט עבור <math>n</math>, מתקיים <math>Q(n)</math>, ולכן מתקיים <math>P(n) \lor Q(n)</math> כדרוש.
|<math>f(x_1,x_2,x_3)</math>
| <math>x_3</math>
|<math>x_2</math>
|<math>x_1</math>
|-
|0
|0
|0
|0
|-
|0
|0
|0
|1


|-
====תרגיל====
|1
הצרן את המשפט "כל מספר ממשי ניתן לקרב ע"י מספרים רציונאליים בקירוב טוב כרצוננו".
|0
|1
|0


|-
פתרון: <math>\forall x\in\mathbb{R}\,\exists A\subset\mathbb{Q}:\forall\epsilon\in\mathbb{R}_{+}\exists q\in A\,:|x-q|<\epsilon</math>.
|1
|1
|0
|0


|-
מה היא שלילתו של המשפט?
|0
|0
|1
|1


|-
פתרון: נכתוב את השלילות השונות האפשריות:
|1
* <math>\neg(\forall x\in\mathbb{R}\,\exists A\subset\mathbb{Q}:\forall\epsilon\in\mathbb{R}_{+}\exists q\in A\,:|x-q|<\epsilon )</math>
|1
* <math>\exists x\in\mathbb{R}\,\neg( \exists A\subset\mathbb{Q}:\forall\epsilon\in\mathbb{R}_{+}\exists q\in A\,:|x-q|<\epsilon )</math>
|0
* <math>\exists x\in\mathbb{R}\, \forall A\subset\mathbb{Q}:\neg(\forall\epsilon\in\mathbb{R}_{+}\exists q\in A\,:|x-q|<\epsilon )</math>
|1
* <math>\exists x\in\mathbb{R}\, \forall A\subset\mathbb{Q}:\exists\epsilon\in\mathbb{R}_{+}\neg(\exists q\in A\,:|x-q|<\epsilon )</math>
* <math>\exists x\in\mathbb{R}\, \forall A\subset\mathbb{Q}:\exists\epsilon\in\mathbb{R}_{+}\forall q\in A\,\neg(|x-q|<\epsilon )</math>
*<math>\exists x\in\mathbb{R}\,\forall A\subset\mathbb{Q}:\exists\epsilon\in\mathbb{R}_{+}\forall q\in A\,:|x-q|\geq\epsilon</math>


|-
תרגילים:
|0
דוגמאות של הצרנת ושלילת המושגים 'תלות לינארית', 'גבול סדרה', 'חח"ע', וכדומה
|1
|1
|0
 
|-
|0
|1
|1
|1
 
|-
 
|}
 
נתמקד בשורות שערך האמת שלהן הוא 1 (שורות 3, 4, 6).
 
לשורה 3 נתאים את הפסוקית  <math>D_1=\lnot x_1 \land x_2 \land \lnot x_3</math>
 
מה עשינו? החלפנו כל משתנה שערכו 0 בשלילה שלו, וכל משתנה שערכו 1 השארנו בלי לגעת.
 
מה יצא לנו מזה? שימו לב שרק הצבה של ערכי האמת של <math>x_1,x_2,x_3</math> שמופיעים בשורה 3 תתן ערך אמת 1 ב <math>D_1</math>. כל הצבה אחרת (כלומר: הצבה של ערכי אמת של המשתנים בשורה אחרת) תתן 0 ב <math>D_1</math>.
 
באופן דומה נייצר <math>D_2</math> עבור שורה 4 ו <math>D_3</math> עבור שורה 6:
 
<math>D_2=\lnot x_1 \land\lnot x_2 \land x_3, \quad D_3=x_1\land \lnot x_2 \land x_3</math>
 
כעת ה DNF של טבלת האמת היא פשוט
 
<math>D_1\or D_2 \or D_3=(\lnot x_1 \land x_2 \land \lnot x_3) \or (\lnot x_1 \land \lnot x_2 \land x_3) \or (x_1 \land \lnot x_2 \land x_3)</math>.
 
===CNF===
 
ביטוי בצורת CNF מורכב מאוסף "פסוקיות" המחוברות ביניהן על ידי פעולות "וגם". כל פסוקית בעצמה מורכבת מאטומים המחוברים ביניהם על ידי פעולות "או". כל אטום הוא משתנה או שלילת משתנה.
 
בצורה סכמטית: <math>C_1 \land C_2 \land \dots \land C_n</math> כאשר כל <math>C_i</math> מהצורה
<math>q_1\lor q_2 \lor \dots \lor q_m</math> וכל <math>q_i</math> שווה למשתנה <math>x</math>
או לשלילתו <math>\lnot x</math>.
 
נדגים על הדוגמא לעיל.
 
נתמקד בשורות שערך האמת שלהן הוא 0 (שורות 1, 2, 5, 7, 8)
 
לשורה 1 נתאים את הפסוקית  <math>C_1= x_1 \lor x_2 \lor  x_3</math>
 
מה עשינו? כל משתנה שערכו 0 השארנו בלי לגעת, וכל משתנה שערכו 1 החלפנו בשלילתו.
 
מה יצא לנו מזה? שימו לב שרק הצבה של ערכי האמת של <math>x_1,x_2,x_3</math> שמופיעים בשורה 1 תתן ערך אמת 0 ב <math>C_1</math>. כל הצבה אחרת (כלומר: הצבה של ערכי אמת של המשתנים בשורה אחרת) תתן 1 ב <math>C_1</math>.
 
באופן דומה נייצר <math>C_2,C_3,C_4,C_5</math> עבור שורות 2 , 5, 7 ו-8:
 
<math>C_2= x_1 \lor \lnot x_2 \lor \lnot x_3, C_3=\lnot x_1\lor \lnot x_2 \lor x_3</math>
 
<math> C_4=x_1 \lor \lnot x_2 \lor \lnot x_3, C_5= \lnot x_1 \lor \lnot x_2 \lor \lnot x_3</math>
 
כעת ה CNF של טבלת האמת היא פשוט
 
<math>C_1  \land C_2 \land C_3 \land C_4 \land C_5 </math>
 
הרחבה על עניינים אלו (תרגול זה וקודמו) ניתן למצוא פה [[88-101 חשיבה מתמטית]]

גרסה אחרונה מ־16:50, 19 במרץ 2019

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

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

פרדיקטים

בלוגיקה מתמטית, פרדיקט הוא פונקציה המקבלת משתנה או כמה משתנים, ומחזירה ערך אמת (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{ \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{ 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{ x }[/math] להיות דו־ריבועי אם קיימים [math]\displaystyle{ y,z }[/math] כך ש-[math]\displaystyle{ x=y^2+z^2 }[/math]. הוכיחו שלכל זוג מספרים [math]\displaystyle{ x,y }[/math] אם הם מספרים דו־ריבועיים, אז גם המספר [math]\displaystyle{ xy }[/math] הוא דו־ריבועי.

פתרון: נגדיר את הפרדיקט [math]\displaystyle{ Q(x) }[/math] להיות T אם ורק אם [math]\displaystyle{ x }[/math] הוא מספר דו־ריבועי (הצרינו זאת!). אנו נדרשים להוכיח את הטענה [math]\displaystyle{ \forall x\forall y:(Q(x) \land Q(y)) \rightarrow Q(xy) }[/math].

לפי ההגדרה, אם [math]\displaystyle{ x }[/math] הוא דו־ריבועי, אז קיימים [math]\displaystyle{ a,b }[/math] כך ש-[math]\displaystyle{ x=a^2+b^2 }[/math], ובאופן דומה אם [math]\displaystyle{ y }[/math] דו־ריבועי, אז קיימים [math]\displaystyle{ c,d }[/math] כך ש-[math]\displaystyle{ y=c^2+d^2 }[/math]. כדי להוכיח ש-[math]\displaystyle{ xy }[/math] הוא גם דו־ריבועי, יש להראות שקיימים [math]\displaystyle{ e,f }[/math] כך ש-[math]\displaystyle{ xy=e^2+f^2 }[/math]. נעזר בזהות [math]\displaystyle{ (a^2+b^2)(c^2+d^2) = (ac-bd)^2+(ad+bc)^2 }[/math]. לכן קיבלנו [math]\displaystyle{ xy = (ac-bd)^2+(ad+bc)^2 }[/math], ומכאן שנוכל לבחור את [math]\displaystyle{ e,f }[/math] הדרושים לנו להיות [math]\displaystyle{ e=ac-bd }[/math], [math]\displaystyle{ f=ad+bc }[/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{N} \exists b\in \mathbb{N} (a|b\rightarrow (a\leq b\land a+b\lt a\cdot b))) }[/math]

פיתרון: ראשית נראה מה הטענה בעצם אומרת:

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

שימו לב שנעזרו בשקילות [math]\displaystyle{ \ (A\rightarrow B) \equiv ((\neg A) \lor B) }[/math] ובחוקי דה-מורגן. כעת נשים לב שאם [math]\displaystyle{ a|b }[/math] אז [math]\displaystyle{ a\leq b }[/math] ולכן כדי שזה יהיה נכון צריך שיתקיים [math]\displaystyle{ a+b\geq a\cdot b }[/math] וזה אכן קורה עבור [math]\displaystyle{ a=1 }[/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) }[/math] אז בפרט מתקיים [math]\displaystyle{ P(n) \lor Q(n) }[/math] כדרוש. אחרת, לפי השקילות [math]\displaystyle{ a\lor b \equiv \lnot a \rightarrow b }[/math], מתקיים שלכל מס' טבעי, ובפרט עבור [math]\displaystyle{ n }[/math], מתקיים [math]\displaystyle{ Q(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]

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

אוחזר מתוך "https://math-wiki.com/index.php?title=תרגול_2_תשעז&oldid=80510"