מבוא ללוגיקה
תוכן
כללי – הגדרת טיעון, הגדרת תקפות, הגדרת מבוססות

פרק 1: תחשיב הפסוקים
סימני השפה
נוסחה בנויה כהלכה  - נב"כ (הגדרה רקורסיבית)

פרק 2: סמנטיקה של תחשיב הפסוקים
טבלאות אמת
הגדרות – טאוטולוגיה, סתירה, קונטינגנציה, קונסיסטנטיות 

פרק 3: דידוקציה טבעית בתחשיב הפסוקים
כללי ההיסק של תחשיב הפסוקים: 
כלל החזרה ((Repetition
הכנסת קוניונקציה ( (Introduction
סילוק קוניונקציה  (Elimination)
הכנסת אימפליקציה  (Introduction)
סילוק אימפליקציה (Elimination)
הכנסת שלילה  (Introduction)
סילוק שלילה  Elimination)  )
הכנסת דיסיונקציה  ( Introduction)
סילוק דיסיונקציה Elimination) (
הכנסת שקילות (אקויולנציה)   ( Introduction)
סילוק שקילות (אקויולנציה)   ( Elimination)
משפט השלמות והמבוססות בתחשיב הפסוקים

פרק 4: תחשיב הפרדיקטים
סימני השפה
נוסחה בנויה כהלכה  - נב”כ (הגדרה רקורסיבית)
הגדרות – טווח הכמת, מופע קשור, מופע חופשי, הצבה אחידה

פרק 5: דדוקציה טבעית בתחשיב הפרדיקטים
כללי ההיסק של תחשיב הפרדיקטים: 
הכנסת כמת כולל( Introduction)
סילוק כמת כולל   ( Elimination)
הכנסת כמת ישי   ( Introduction)
סילוק כמת ישי   ( Elimination)

פרק 6: סמנטיקה של תחשיב הפרדיקטים
פשר
משפט השלמות והמבוססות בתחשיב פרדיקטים

כללי
טיעון -  מבנה הכולל קבוצה של טענות, בו טענה אחת (הנקראת 'מסקנת הטיעון') מוצגת כנובעת מהטענות האחרות  (הנקראות 'הנחות הטיעון').
טיעון הוא תקף אם ורק אם כל הטיעונים בעלי אותו המבנה (כמו הטיעון הנתון), אשר כל הנחותיהם אמיתיות - מסקנתם אמיתית.
(הגדרה שקולה: טיעון הוא תקף אם ורק אם אין אף טיעון בעל אותו המבנה (כמו הטיעון הנתון), אשר כל הנחותיו אמיתיות ומסקנתו שקרית.)
טיעון הוא מבוסס אם ורק אם הוא טיעון תקף והנחותיו אמיתיות.

פרק 1: תחשיב הפסוקים

סימני השפה
משתנים פסוקיים: A, B,...  ....p,q,r…
קשרים פסוקיים:	                        , , , ,  סוגריים: (  ) או [ ] או { }

נוסחה בנויה כהלכה  - נב"כ (הגדרה רקורסיבית)
1.	כל משתנה פסוקי הוא נב"כ.
2.	אם ,   הן נב”כ , אזי גם הנוסחות הבאות הן נב"כ:
		()      ()     ()     (.)    ()
3.	שום דבר אחר אינו נב”כ.
בכל נב"כ שאינו משתנה פסוקי יש לפחות קשר אחד.  הקשר היחיד שאינו נמצא בתוך סוגריים, פרט לסוגריים החיצוניים, הוא הקשר הראשי של הנב"כ.

הסכמה על השמטת סוגריים:  יש להשמיט סוגריים חיצוניים. כמו כן, יש להשמיט סוגריים במקרה החד-משמעי של שלילה. ( לדוגמא: AB במקום  A)B)  )

פרק 2: סמנטיקה של תחשיב הפסוקים
טבלאות אמת

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

  	        .	        	       	         	
T    F	T   T       T	T   T        T	T   T       T	T   T        T
F    T	T   F       F	T   F        T	T   F       F	T   F        F
		F   T       F	F   T        T	F   T       T	F   T        F
		F   F       F		F   F        F	F   F       T	F   F        T

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

הגדרות
נוסחה היא טאוטולוגיה אם ורק אם לכל הערכה של המשתנים הפסוקיים בה, ערך הנוסחה הוא T . 
נוסחה היא סתירה אם ורק אם לכל הערכה של המשתנים הפסוקיים בה, ערך הנוסחה הוא F . 
נוסחה היא קונטינגנציה אם ורק אם אינה סתירה ואינה טאוטולוגיה.
קבוצת נוסחאות היא קונסיסטנטית אם ורק אם יש מצב עניינים (שורה בלוח האמת) שבו כל הנוסחאות בקבוצה מקבלות את הערך T. 

פרק 3: דידוקציה טבעית בתחשיב הפסוקים
הוכחה של נב"כ  C מתוך קבוצת נב"כ  P1…Pn היא סידרה סופית של שורות בעלות הצורה
	  <הצדקה ,    נב"כ,  מספר סידורי>
שבה 
1.	P1,…,Pn מופיעות ראשונות בסדרה  וכולן מוצדקות ב'Prem' ( Premise – הנחה)
והנב"כ האחרונה בסידרה היא הנב"כ C.
2.	לכל נב"כ יש הצדקה.
3.	כל נב"כ שאינה הנחה התקבלה על ידי אחד מכללי ההיסק הבאים.

תאורמה: נב"כ יכיחה ללא הנחות היא תאורמה.

יש כללים הכרוכים ביצירת "תת-הוכחה", שמתחילה בהיפותיזה (בצעד i), ומסומנת על ידי קו אנכי משמאל. תת-ההוכחה כולה משמשת להצדקת צעד j על ידי הכלל. (כאלה הם כלל הכנסת אימפליקציה, כלל הכנסת שלילה וכלל סילוק דיסיונקציה.) 

i. 	…	Hyp

j-1	…
j …		הצדקה

כללי ההיסק של תחשיב הפסוקים

כלל החזרה ((Repetition
ניתן להעתיק נב"כ לשורה כלשהי j , אם אותה נב"כ היתה בשורה קודמת i , בתנאי שאין תת-הוכחה המכילה את הנב"כ בשורה  i שאינה מכילה גם את הנב"כ בשורה j.

i.	α	...				i.	α	…				i.		α	…	
				או          	j-n.		…	Hyp

j.	α	i Rep			j.		α	i Rep		j.	α	i Rep 

הכנסת קוניונקציה ( (Introduction
ניתן להצדיק נב"כ שהיא קוניונקציה  בשורה k אם בשורות קודמות היו הנב"כ  והנב"כ    מוצדקות.
i.			…								
j.			…							
k.			i,j  I								

סילוק קוניונקציה  (Elimination)
ניתן להצדיק את כל אחד מן הקוניונקטים בשורה j , אם הנב"כ שהיא הקוניונקציה  מוצדקת בשורה  i. 

i.			…							i.			…										או
j.			i, E 							j.			i, E

הכנסת אימפליקציה  (Introduction)
ניתן להצדיק נב"כ מהצורה  בשורה j ע"י יצירת תת-הוכחה, המתחילה בשורה i בה מופיעה היפותיזה , ומסתיימת בשורה j-1 בה מופיע . יציאה מתת-ההוכחה מוצדקת ע"י  I.   

i.	    		Hyp

j-1.	    		…
j.			i – (j-1), I

סילוק אימפליקציה (Elimination)
אם הנב"כ בשורה  i היא אימפליקציה  והרישא   מופיע בשורה אחרת j, ניתן לכתוב את הסיפא  בשורה k, מתחת לשורות i ו-j. 

i.			….													
j.			….	 

k.			i, j E		

הכנסת שלילה  (Introduction)
ניתן להצדיק בשורה j את הנב"כ , על ידי יצירת תת-הוכחה המתחילה בשורה i, בה מופיעה היפותיזה  , ומסתיימת בסתירה מפורשת כלשהי. יציאה מתת-ההוכחה מוצדקת ע"י  I. 
סתירה מפורשת היא קוניונקציה של נב"כ כלשהי ושלילתה.

i.				Hyp

j-1.				…
j.				i – (j-1), I 

הערה: ניתן להשמיט את השורה של הקוניונקציה המפורשת בתנאי ששתי הנוסחאות הסותרות מופיעות בתוך תת ההוכחה. כך,  למשל,

i.		 		Hyp

j.				…
k-1.	   	 		…
k.				i – j, (k-1), I 

סילוק שלילה  Elimination)  )
אם הנב"כ בשורה i היא מהצורה  אזי בשורה מאוחרת יותר ניתן לכתוב את .

i.			…

j.			i  E

הכנסת דיסיונקציה  ( Introduction)
ניתן להצדיק נב"כ דיסיונקציה  בשורה j  אם אחד הדיסיונקטים,  או , הופיע קודם לכן בשורה i.  
	
i.			…								i.			…
						או

j.			i  I								j.			i  I

סילוק דיסיונקציה Elimination) (
אם בשורה i מופיעה דיסיונקציה  , אזי ניתן לכתוב נוסחה כלשהי  ולהצדיקה, בתנאי שיש שתי תת-הוכחות, המניחות כהיפותיזות את כל אחד מן הדיסיונקטים, ושתיהן מסתיימות באותה הטענה  . 

i.			…
j.			Hyp	

k.			…
l.			Hyp

m.			…
m+1.			i, j-k, l-m,  E

הכנסת שקילות (אקויולנציה)   ( Introduction)
ניתן להצדיק נב"כ שקילות  ע"י הצדקה בשורות קודמות של האימפליקציות בשני הכיוונים. 

i.			…

j.			…
k.			i,j, I

סילוק שקילות (אקויולנציה)   ( Elimination)
אם בשורה  i מופיעה שקילות , אזי ניתן לכתוב את אחת האימפליקציות בשורה j שאחריה.

i.			…								i.			…
							או	
j.			i, E 							j.			i, E

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

פרק 4: תחשיב הפרדיקטים
סימני השפה
קבועים  אינדיבידואליים:				     a,  b, ... k, a1, b1, ... k1... 
משתנים אינדיבידואליים: 			              x, y, z,..., x1, y1, z1...		
פרדיקטים:	 					… , P, Q  …F, G, 					
(פרדיקט הוא חד-מקומי, דו-מקומי, או n-מקומי, על פי מספר המקומות שלימינו.)
קשרים פסוקיים:		                        , , , ,  כמתים:		כמת ישי:       כמת כולל:  או   (x)
סוגריים: (  ) או [ ] או { }

נוסחה בנויה כהלכה  - נב”כ (הגדרה רקורסיבית)
1.	אם  1,...,n   הם או קבועים או משתנים  אינדיבידואלים, P הוא פרדיקט   n-מקומי כלשהו, אזי
	 P1,...,n היא נב"כ.  נוסחה זו נחשבת לנוסחה אטומית.
2.	אם ,   הן נב”כ , אזי גם הנוסחות הבאות:	
				          ()       ()       ()       (.)       ()
3.	אם G היא נב"כ שבה מופיע משתנה  אזי גם, (G)   (G) נב”כ.
4.	שום דבר אחר אינו נב”כ.

הסכמה על השמטת סוגריים:  יש להשמיט סוגריים חיצוניים. יש להשמיט סוגריים במקרה החד-משמעי של שלילה. כמו כן, יש להשמיט סוגריים במקרה החד-משמעי של כמת. לדוגמא: xAxBaa במקום   (xAx)Baa.	 

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

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

פרק 5: דדוקציה טבעית בתחשיב הפרדיקטים
כללי ההיסק של תחשיב הפרדיקטים
כל כללי ההיסק של הדידוקציה הטבעית בתחשיב הפסוקים הם כללים גם בתחשיב הפרדיקטים.

הכנסת כמת כולל( Introduction)  
ניתן להצדיק נב"כ מהצורה G בשורה j, ע"י יצירת תת-הוכחה שמתחילה בשורה i.  זוהי תת-הוכחה כללית ביחס למשתנה  שאינו מופיע חופשי בשורה קודמת ל-i , שמסתיימת בשורה j-1 בנב"כ G, כאשר G מתקבלת מ- Gע"י הצבה אחידה, ובתנאי שאם  שונה מ- אז  אינו מופיע חופשי ב- G. 

i.   				Hyp

j-1	     G		…
j	G		i – (j-1) I

סילוק כמת כולל   ( Elimination) 
אם בשורה i  מופיעה נב"כ מהצורה G, ניתן לכתוב בשורה j  G, כאשר  הוא אינדיבידואל (משתנה או קבוע) כלשהו (כולל x עצמו), ו-  G התקבל מ- G   על ידי הצבה אחידה של    במקום   .
i.	xGx		…

j.	G			i, E	
הכנסת כמת ישי   ( Introduction) 
אם בשורה i  מופיעה נב"כ מהצורה G, ניתן לכתוב בשורה j  G , כאשר  הוא משתנה או קבוע כלשהו, ו- G  התקבל מ- G   על ידי הצבה  אחידה של  במקום , בתנאי שאם  שונה מ-  אזי  אינו מופיע חופשי ב- G.  

i.	G		…

j.	G	i, I

סילוק כמת ישי   ( Elimination)
אם בשורה i  מופיעה נב"כ מהצורה G , ניתן להצדיק את הנב"כ H בשורה k ע"י יצירת תת-הוכחה המתחילה בהיפותיזה G, כאשר המשתנה  הוא משתנה כלשהו שלא הופיע חופשי בצעד קודם ל-j, H הוא נב"כ כלשהו שבו  אינו מופיע חופשי,ו-  Gהתקבלה מ- G   על ידי הצבה אחידה של    במקום  .

i.	G		…
j. 		G		Hyp

k-1.		H		…
k.	H		i, j-k E

פרק 6: סמנטיקה של תחשיב הפרדיקטים

פשר
פשר (אינטרפרטציה, מודל) לתחשיב הפרדיקטים הוא מבנה הכולל תחום דיון D שהוא קבוצה לא ריקה של אובייקטים אינדיבידואלים,שני ערכי אמת: T (אמת) ו- F (שקר),והתאמה של אלמנטים בפשר לנוסחאות בשפה, המקיימת את התנאים הבאים: 
1.	כל קבוע אינדיבידואלי יציין אובייקט אינדיבידואלי מסויים, וכל משתנה יציין אוביקט אינדיבידואלי כלשהו.
2.	כל פרדיקט חד-מקומי יציין קבוצה של אובייקטים בתחום שהפרדיקט חל עליהם.
3.	כל פרדיקט דו-מקומי R יציין את הזוגות הסדורים של אובייקטים כך שהאובייקט ש- מציין אכן נמצא ביחס שהפרדיקט הדו-מקומי R מציין לאובייקט ש-  מציין. 
4.	פסוק אטומי  G (שבו  קבוע ו-G פרדיקט חד-מקומי) מציין את הערך T אם"ם האובייקט ש- מציין אכן נמצא בין האובייקטים שהפרדיקט חל עליהם.
5.	פסוק אטומי  G (שבו  ו- הם קבועים ו-G פרדיקט דו-מקומי) מציין את הערך T אם"ם זוג האובייקטים הסדור ש-  ו- מציינים בהתאמה הוא אכן בין הזוגות של אובייקטים שהפרדיקט חל עליהם.
6.	תנאי האמת של נב”כ שבה האופרטור הראשי הוא קשר, הם כמו בתחשיב הפסוקים:
  G         מקבל ערך T אם"ם G  מקבל את הערך F .
	HG  מקבל ערך T אם"ם H ו- G מקבלים ערך T.
	HG מקבל ערך F אם"ם H ו- G מקבלים ערך F.
	HG מקבל ערך F אם"ם H מקבל ערך T ו-G מקבל ערך F.
	HG מקבל ערך T אם"ם הערך של  H זהה לערך  של G.				 
 7.	נב”כ  Gשהאופרטור הראשי בה הוא כמת כולל ו-G נב”כ כלשהי שבה  מופיע חופשי, היא אמיתית אם"ם הנוסחא G מקבלת ערך T עבור כל אובייקט בתחום.
8.	נב”כ   G  שהאופרטור הראשי בה הוא כמת ישי ו-G נב”כ כלשהי שבה  מופיע חופשי,  היא אמיתית אם"ם קיים אובייקט בתחום שעבורו G מקבלת ערך T. 

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

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