שינויים
/* תרגיל */
חזרה ל[[83-116, בדידה 1 להנדסה, מערכי תרגול|דף מערכי התרגול]]. ==כמתים כַּמָּתִים ופרדיקטים==
===פרדיקטים===
גם אטומים וגם פרדיקטים יכולים להיות אמיתיים (מסמנים 1 או T) או שקריים (מסמנים 0 או F). המינוח המקובל הוא שאטום/פרדיקט הוא בעל '''ערך אמת''' T (במידה שהוא נכון) או בעל '''ערך אמת''' F (במידה שאינו נכון).
כיוון שאטומים הם ללא משתנים הם יכולים להיות T או F אבל לא שניהם. לעומתם, פרדיקטים הם תלויים במשתנים ולכן ערך האמת שלהם יקבע לפי ההצבה במשתנים. למשל הפרדיקט <math>SP(x,y)=x<y</math> יהיה נכון במקרה ש <math>SP(2,3)</math> ולא נכון במקרה ש <math>SP(3,2)</math>.
===כמתים===
בנוסף, לקשרים ניתן להוסיף כמתים(quantifiers). החשובים שבהם הם הכמת "לכל" <math>\forall</math> (זו A הפוכה, קיצור המילה All) והכמת "קיים" <math>\exist</math>(זו E הפוכה, קיצור המילה Exist).
תפקיד מרכזי של הכמת הוא להבהיר את כוונת הטענה. למשל הטענה ש "סטונדט הוא יצור חרוץ" יכולה לקבל 2 משמעויות בעזרת הכמתים. או "כל סטודנט הוא יצור חרוץ" או "קיים סטודנט שהוא יצור חרוץ".
לעומתה הטענה השניה טוענת שניתן למצוא סטודנט אחד (לפחות) שהוא חרוץ (אם רוצים להוכיח את הטענה צריך למצוא סטודנט שהוא חרוץ ואם רוצים להוכיח כי הטענה לא נכונה צריך לעבור בין כל הסטודנטים ולוודא שהם אינם חרוצים).
פתרון:
ההצרנה <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>Sסדר הכמתים כן משנה (x,yלפעמים)למשל </math> המוגדר <math>x\leq y</math> הפסוק <math>\forall exist x\forall y S(x,y)</math> הוא זהה לא שקול לפסוק <math>\forall ty \forall s exist x S(tx,sy)</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>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>P</math>, * <math>\ \neg \forall x: P(x) \equiv \exists x: \neg P(x)</math>, וכך גם* <math>\ \neg \exists x: P(x) \equiv \forall x: \neg P(x)</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>\exists a\in \mathbb{N} \forall b\in \mathbb{N} (a|b \land (a>b \lor a+b\geq a\cdot b))</math>
ב. הוכחה: יהי <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>\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>\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>\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>
תרגילים:
דוגמאות של הצרנת ושלילת המושגים 'תלות לינארית', 'גבול סדרה', 'חח"ע', וכדומה