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

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

צורות נורמליות

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

הקבוצה NFF: קבוצה המוגדרת באינדוקציה:

בסיס: $plot:\[\left\{ {T,F} \right\} \cup \left\{ {{p_i}|i \in \mathbb{N}} \right\} \cup \left\{ {\neg {p_i}|i \in \mathbb{N}} \right\}\]$ . סגור: $plot:\[\left\{ {{F_ \wedge },{F_ \vee }} \right\}\]$ .

דוגמאות: חוקי: $plot:\[\left( {\neg {p_5} \vee {p_8}} \right)\]$ , $plot:\[\left( {\left( {\neg {p_7} \vee \neg {p_4}} \right) \wedge {p_5}} \right)\]$ . לא חוקי: $plot:\[\left( {\neg \left( {\neg {p_8}} \right)} \right)\]$ , $plot:\[\left( {\neg \left( {{p_1} \vee {p_2}} \right)} \right)\]$ .

משפט ה-NFF: לכל פסוק $plot:\[\alpha \]$ קיים פסוק $plot:\[\alpha '\]$ מצורת ה-NFF כך ש: 1) $plot:\[\alpha \equiv \alpha '\]$ . 2) $plot:\[\alpha \]$ ו- $plot:\[\alpha '\]$ מכילים את אותם האטומים.

בהינתן פסוק $plot:\[\alpha \]$ , נתרגם את $plot:\[\alpha \]$ לפסוק $plot:\[\alpha ''\]$ ב- $plot:\[\left\{ {\neg , \vee , \wedge } \right\}\]$ : נשרטט ל- $plot:\[\alpha ''\]$ עץ יצירה. נדחוף את ה-" $plot:\[\neg \]$ " כלפי מטה בעזרת השקילויות הבאות: $plot:\[\neg T = F,\neg F = T,\neg \neg \delta = \delta ,\neg \left( {{\alpha _1} \wedge {\alpha _2}} \right) = \left( {\neg {\alpha _1} \vee \neg {\alpha _2}} \right),\neg \left( {{\alpha _1} \vee {\alpha _2}} \right) = \left( {\neg {\alpha _1} \wedge \neg {\alpha _2}} \right)\]$ .