לדלג לתוכן

שלמות (לוגית)

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

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

מאפיינים אחרים הקשורים לשלמות

[עריכת קוד מקור | עריכה]

התכונה הפוכה לשלמות נקראת תקינות : מערכת היא: sundness ביחס לתכונה (בעיקר תוקף סמנטי) אם לכל אחד מהמשפטים שלה יש תכונה זו.

צורות של שלמות

[עריכת קוד מקור | עריכה]

שלמות אקספרסיבית-Expressive

[עריכת קוד מקור | עריכה]

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

שלמות פונקציונלית-Functional completeness

[עריכת קוד מקור | עריכה]

קבוצה של חיבורים לוגיים הקשורים למערכת פורמלית מלאה מבחינה פונקציונלית אם היא יכולה לבטא את כל פונקציות ההצעה(אנ').

שלמות סמנטית-Semantic completeness

[עריכת קוד מקור | עריכה]

שלמות סמנטית היא ההפך לתקינות-soundness (אנ') עבור מערכות פורמליות. מערכת פורמלית היא שלמה ביחס לטאוטולוגיות או "שלמה מבחינה סמנטית" כאשר כל הטאוטולוגיות שלה הן משפטים, ואילו מערכת פורמלית היא "soundness (אנ')" כאשר כל המשפטים הם טאוטולוגיות (כלומר, הם נוסחאות תקפות מבחינה סמנטית: נוסחאות שנכונות תחת כל פרשנות שפת המערכת התואמת את כללי המערכת). כלומר, מערכת פורמלית שלמה מבחינה סמנטית אם

[1]

לדוגמה, משפט השלמות של גדל קובע-Gödel's completeness theorem (אנ') שלמות סמנטית עבור לוגיקה מסדר ראשון.

שלמות חזקה

[עריכת קוד מקור | עריכה]

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

השלמות-הפרכה-Refutation-completeness

[עריכת קוד מקור | עריכה]

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

[2]

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

דוגמאות למערכות השלמות להפרכה כוללות: רזולוציית SLD על סעיפי הורן-Horn clauses, סופרפוזיציה-Superposition calculus על לוגיקה סתמית משוואה-clausal (אנ') מסדר ראשון, רזולוציית רובינסון על קבוצות סעיפים.[3] האחרון אינו שלם מאוד: למשל מתקיים אפילו בתת-קבוצה של לוגיקה מסדר ראשון, אבל לא ניתן לגזור ממנו לפי החלטה. למרות זאת, ניתן לגזור.

שלמות תחבירית-Syntactical completeness

[עריכת קוד מקור | עריכה]

מערכת פורמלית S היא שלמה תחבירית או שלמה באופן דדוקטיבי או שלמה מקסימלית אם עבור כל משפט (נוסחה סגורה) φ של שפת המערכת או φ או ¬φ הוא משפט של S. זה נקרא גם השלמות שלילה, והוא חזק יותר משלימות סמנטית. במובן אחר, מערכת פורמלית שלמה מבחינה תחבירית אם ורק אם לא ניתן להוסיף לה משפט בלתי ניתן להוכחה מבלי להכניס חוסר עקביות. לוגיקה פרופוזיציונית פונקציונלית של אמת ולוגיקת פרדיקט מסדר ראשון הן שלמות מבחינה סמנטית, אך אינן שלמות מבחינה תחבירית (לדוגמה, ההצהרה הלוגית הטענתית המורכבת ממשתנה טענה יחיד A אינה משפט, וגם שלילתו). משפט חוסר השלמות של גדל מראה שכל מערכת ניתנת לחישוב בעלת עוצמה מספקת, כגון אריתמטיקה של Peano, אינה יכולה להיות עקבית וגם שלמה מבחינה תחבירית.

שלמות מבנית-Structural completeness

[עריכת קוד מקור | עריכה]

בלוגיקה על-אינטואיציונית-Superintuitionistic logic ומודאלית-modal logics (אנ'), היגיון מושלם מבחינה מבנית אם כל כלל קביל ניתן לגזירה.

שלמות הדגם-Model completeness

[עריכת קוד מקור | עריכה]

תיאוריה היא מודל שלמה אם ורק אם כל הטבעה של המודלים שלה היא הטבעה יסודית-Elementary embedding

הפניות-References

[עריכת קוד מקור | עריכה]

Hunter, Geoffrey (אנ'), Metalogic: An Introduction to the Metatheory of.Standard First-Order Logic, University of California Press, 1971

David A. Duffy (1991). Principles of Automated Theorem Proving. Wiley. Here: sect. 2.2.3.1, p.33.

Stuart J. Russell, Peter Norvig (1995). A Modern Approach. Prentice Hall. Here: sect. 9.7, p.286

קישורים חיצוניים

[עריכת קוד מקור | עריכה]

הערות שוליים

[עריכת קוד מקור | עריכה]
  1. ^ Hunter, Geoffrey, Metalogic: An Introduction to the Metatheory of Standard First-Order Logic, University of California Press, 1971
  2. ^ David A. Duffy (1991). Principles of Automated Theorem Proving. Wiley. Here: sect. 2.2.3.1, p.33
  3. ^ Stuart J. Russell, Peter Norvig (1995). A Modern Approach. Prentice Hall. Here: sect. 9.7, p.286