בינה מלאכותית

ספר אלקטרוני מאת: ניר אדר

6.1.6. תרגיל

תהי T קבוצת כל הפסוקיות שנוצרו משלילת המשפט. תהי A קבוצת כל הפסוקיות שנוצרו מהאקסיומות. תהי P קבוצת כל הפסוקיות המשתתפות בהוכחה.

האם יתכן כי T ו-P הן זרות?
האם יתכן כי P ו-A הן זרות?

תשובה:

1. יתכן ש-P ו-T הן זרות, במקרה הקיצוני בו קבוצת האקסיומות אינה עקבית (ואז נגיע לסתירה בלי צורך בשום קבוצת תמיכה).

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

2. יתכן ש-P ו-A הן זרות. זה יקרה במקרה בו המשפט אותו אנו רוצים להוכיח הוא טאוטולוגיה. לדוגמא: $plot:\[\left( {X \vee \neg X} \right)\]$ .

שלילת הפסוק הינה: $plot:\[\left( {X \wedge \neg X} \right)\]$ . במעבר לפסוקיות, נוסף את הפסוקיות $plot:\[\left\{ X \right\},\left\{ {\neg X} \right\}\]$ . איחוד של שתיהן ייתן את הסתירה המבוקשת, ללא שימוש בפסוקיות מ-A.