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

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

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

Pronex Normal Form

שלב 1:   הגדרת נוסחאות חסרות כמתים מעל מילון plot:\[\tau \] - מסומן plot:\[QF\left( \tau  \right)\].

            בסיס: נוסחאות אטומיות.     סגור: קשרים.

שלב 2:   הגדרת plot:\[PNF\left( \tau  \right)\]:           בסיס: plot:\[QF\left( \tau  \right)\].   סגור: כמתים.

משפט ה-PNF

לכל נוסחה plot:\[\alpha \] קיימת נוסחה plot:\[\alpha '\] מצורת PNF כך ש-plot:\[\alpha ' \equiv \alpha \].

ההוכחה באינדוקציית מבנה על מבנה הנוסחה.

בסיס:     plot:\[\alpha \] נוסחה אטומית plot:\[\alpha  \Leftarrow \] מצורת PNF.

סגור:     נניח של-plot:\[\alpha ,\beta \] קיימים שקולים plot:\[\alpha ',\beta '\] מצורת PNF.

            כמתים: plot:\[\forall {v_i}\alpha \], נמצא נוסחה: plot:\[\forall {v_i}\alpha '\] וכך גם ל-plot:\[\exists \].

            קשרים: נניח plot:\[\left( {\alpha  \to \beta } \right)\], ואז:

  1. plot:\[\left( {\alpha ' \to \beta '} \right)\]
  1. מתרגמים ל-plot:\[\left\{ {\neg , \wedge , \vee } \right\}\]: plot:\[\left( {\neg \alpha ' \vee \beta '} \right)\]
  1. עושים renaming למשתנים הקשורים ב-plot:\[\alpha '\] כך שלא יופיע ב-plot:\[\beta '\] ולהיפך.
  1. משתמשים בשקילויות הבאות:
  • plot:\[\neg \forall {v_i}\varphi  \equiv \exists {v_i}\neg \varphi \]
  • plot:\[\neg \exists {v_i}\varphi  \equiv \forall {v_i}\neg \varphi \]
  • plot:\[\forall {v_i}\left( {\varphi  \wedge \psi } \right) \equiv \forall {v_i}\varphi  \wedge \forall {v_i}\psi \]
  • plot:\[\exists {v_i}\left( {\varphi  \vee \psi } \right) \equiv \exists {v_i}\varphi  \vee \exists {v_i}\psi \]
  • אם plot:\[{v_i}\] לא חופשי ב-plot:\[\psi \] אז: plot:\[\left( {\forall {v_i}\varphi  \vee \psi } \right) \equiv \forall {v_i}\left( {\varphi  \vee \psi } \right)\]
  • אם plot:\[{v_i}\] לא חופשי ב-plot:\[\psi \] אז: plot:\[\left( {\forall {v_i}\varphi  \wedge \psi } \right) \equiv \forall {v_i}\left( {\varphi  \wedge \psi } \right)\]
  • אם plot:\[{v_i}\] לא חופשי ב-plot:\[\psi \] אז: plot:\[\left( {\exists {v_i}\varphi  \vee \psi } \right) \equiv \exists {v_i}\left( {\varphi  \vee \psi } \right)\]

תגיות המסמך:

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

תיקון

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

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