הועלה לאתר:  
מספר עמודים: 25
הורדת המסמך בגרסה להדפסהלהורדת המסמך בשלמותו

לוגיקה - סיכום נקודות

סיכום מאת: ניר אדר

הרחבת המושגים לקבוצת פסוקים

  1. השמה plot:\[z\] מספקת קבוצת פסוקים plot:\[X\] אם plot:\[z\] מספקת את כל הפסוקים ב-plot:\[X\]. לכל plot:\[\alpha  \in X\], plot:\[z \vDash \alpha \]. מסמנים: plot:\[z \vDash X\].
  2. פסוק plot:\[\alpha \] נובע לוגית מקבוצת פסוקים plot:\[X\] אם לכל השמה plot:\[z\] שמספקת את plot:\[X\] מתקיים plot:\[z \vDash \alpha \]. דוגמא: plot:\[\left\{ {\neg {p_0} \to \neg {p_1},{p_1}} \right\} \vDash {p_0}\].
  3. קבוצת פסוקים plot:\[X\] היא ספיקה אם קיימת השמה המספקת את plot:\[X\].

נכון/לא נכון:

  1. אם כל פסוק ב-plot:\[\Sigma \] ספיק, אז plot:\[\Sigma \] ספיקה. לא נכון. למשל: plot:\[\Sigma  = \left\{ {{p_0},\neg {p_0}} \right\}\].
  2. אם plot:\[\Sigma  \vDash \alpha \] אז לכל plot:\[\beta  \in \Sigma \] מתקיים plot:\[\beta  \vDash \alpha \]. לא נכון.
  3. בהינתן קבוצת פסוקים plot:\[\Sigma \] ופסוק plot:\[\alpha \], אם plot:\[\Sigma  \cup \left\{ \alpha  \right\}\] ספיקה אז plot:\[\Sigma  \cup \left\{ {\neg \alpha } \right\}\] לא ספיקה.

    לא נכון, לדוגמא: plot:\[\Sigma  = \phi \] ו-plot:\[\alpha  = {p_0}\].

הגדרה: נאמר שפסוקים plot:\[\alpha ,\beta \] שקולים לוגית ונסמן plot:\[\alpha  \equiv \beta \] אם לכל השמה plot:\[z\] מתקיים plot:\[\bar z\left( \alpha  \right) = \bar z\left( \beta  \right)\]. כלומר, plot:\[ \Leftrightarrow a \equiv \beta \]\[\alpha  \vDash \beta \] וגם plot:\[\beta  \vDash \alpha \].

טענה: plot:\[\alpha  \equiv \beta \] אמ"מ plot:\[\left( {\alpha  \to \beta } \right) \wedge \left( {\beta  \to \alpha } \right)\]

הסימון ╞: עבור השמה – מספק,       עבור פסוקים – גורר לוגית.

דוגמאות לשימושים בנביעה לוגית

  1. לכל פסוקים plot:\[\alpha ,\beta ,\gamma \], אם plot:\[\left\{ {\gamma ,\neg \alpha } \right\} \vDash \beta \] וגם plot:\[\left\{ {\gamma ,\neg \alpha } \right\} \vDash \neg \beta \] אזי plot:\[\gamma  \vDash \alpha \].
  2. לכל זוג פסוקים plot:\[\alpha ,\gamma \] אם plot:\[\left\{ {\gamma ,\neg \alpha } \right\} \vDash \alpha \] אזי plot:\[\gamma  \vDash \alpha \].
  3. לכל קבוצת פסוקים plot:\[X\] ופסוקים plot:\[\alpha ,\beta \], אם plot:\[X \cup \left\{ \alpha  \right\} \vDash \beta \] וגם plot:\[X \cup \left\{ {\neg \alpha } \right\} \vDash \beta \]

    אזי plot:\[X \vDash \beta \].
  4. לכל שתי קבוצות plot:\[{\Sigma _1},{\Sigma _2}\], אם plot:\[{\Sigma _1} \subseteq {\Sigma _2}\] אזי לכל פסוק plot:\[\alpha \], אם plot:\[{\Sigma _1} \vDash \alpha \] אזי plot:\[{\Sigma _2} \vDash \alpha \].

תכונות של פסוקים

  1. כל פסוק בשפה מורכב מאטום בודד, או שהוא מתחיל ב-'(' ונגמר ב-')'.
  2. בכל פסוק plot:\[\alpha \] מספר הסוגריים הימניים שווה למספר הסוגריים השמאליים.

הגדרת רישא: פסוק plot:\[\alpha \] ייקרא רישא (prefix) של plot:\[\beta \] אם plot:\[\alpha ,\beta \] סדרות סימנים כך ש-plot:\[\alpha  = {\alpha _1}...{\alpha _n}\]

ו- plot:\[\beta  = {\beta _1}...{\beta _k}\] וגם plot:\[n \leqslant k\] וגם לכל plot:\[1 \leqslant i \leqslant n\] מתקיים plot:\[{a_i} = {b_i}\]. plot:\[\alpha \] הוא רישא ממש של plot:\[\beta \] אם plot:\[\alpha \] הוא רישא של plot:\[\beta \] וגם plot:\[n < k\].

  1. לכל פסוק plot:\[\beta \], אם plot:\[\alpha \] הוא רישא ממש לא ריקה של plot:\[\beta \], אז מספר הסוגרים השמאליים ב-plot:\[\alpha \] גדול ממש ממספר הסוגרים הימניים ב-plot:\[\alpha \].

תגיות המסמך:

לפרק הקודםמושגי יסוד
לפרק הבאהצבות
מאת: bentz

תיקון

מציעה להחליף את
(a¬)
ב
a¬
שכן (a¬) אינו פסוק
מאת: משה ב

סמנטיקה
שיתוף:
| עוד