השפה הפורמלית L גל חץ

Question 1

סימני השפה אג”ח

Answer 1

פסוקים אטומים
קשרים
סוגריים

Question 2

נב”כ באג”ח

Answer 2

רכיב אחרון בסדרת בנייה
סדרת בנייה היא סדרה סופית של סימנים

Question 3

מערכת היסק

Answer 3

אקסיומות ומודוס פוננס
(L~→1) (α → (β → α))
(L~→2) ((α → (β → γ)) → ((α → β) → (α → γ)))
(L~→3) (((~α) → (~β)) → (β → α))

Question 4

הוכחה במערכת היסק (יכיח)

Answer 4

בוכחה היא סדרה סופית של נבכ”ים שכל איבר בה (למעט האחרון) מקיים
אקסיומה
תוצאה של מודוס פוננס על נבכ”יפ קודמים

Question 5

הוכחה מהנחות במערכת היסק

Answer 5

בוכחה היא סדרה סופית של נבכ”ים שכל איבר בה (למעט האחרון) מקיים
אקסיומה
תוצאה של מודוס פוננס על נבכ”יפ קודמים
הנחה

Question 6

תכונות של הוכחות : רישא

Answer 6

אם סדרה היא הוכחה מקבוצת הנחות
אז כל תת סדרה יכולה להיות הוכחה של הנב”כ האחרון מאותה קבוצת הנחות

Question 7

תכונות של הוכחות : שרשור

Answer 7

חיבור שתי סדרות הוכחה מאותה קבוצת הנחות

Question 8

תכונות של הוכחות : שילוב

Answer 8

כמו שרשור רק עם חופש תנועה

Question 9

תכונות של הוכחות : הכלה

Answer 9

ניתן להוסיך הנחות לקבוצה ועדיין להוכיח את אותו הפסוק

Question 10

תכונות של הוכחות : טענת עזר

Answer 10

אם ניתן להוכיח את אלפא מקבוצת הנחות וניתן להוכיח את ביתא מקבוצת הנחות ואלפא אז ניתן להוכיח את ביתא מקבוצת הנחות

Question 11

תכונות של הוכחות : סופיות

Answer 11

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

Question 12

תכונות של הוכחות : ניתוק

Answer 12

כמו מודוס פוננס רק בניתוק

Question 13

משפט הדדוקציה

Answer 13

בתמסיר

Question 14

עקביות

Answer 14

קבוצת נבכ”ים היא עקבית כל עוד לא ניתן להוכיח את דבר ושלילתו
במילים אחרות, אין שני איברים בסדרת נבכ”ים שהם דבר ושלילתו

Question 15

למת הסופיות

Answer 15

אם כל תת קבוצה סופית של קבוצת נבכ”ים היא עקבית, אז גם קבוצת הנבכ”ים עקבית

Question 16

סדרה אינסופית עולה של קבוצות נבכ”ים

Answer 16

סדרה סדורה של קבוצות נבכ”ים המתקיימות לכל מספר טבעי
כאשר סדר הסדרה הסדורה הינו לפי הכלה (1 מוכל ב2 וכן הלאה עד אינסוף)

Question 17

קבוצת האיחוד של כל הקבוצות בסדרה אינסופית עולה של קבוצות נבכ”ים תקיים:

Answer 17

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

Question 18

למת ההזחה

Answer 18

אם ביתא יכיחה מקבוצת הנחות אז ניתן להוכיח את אלפא אז ביתא מאותה קבוצת הנחות

בעזרת L1

Question 19

משפט ההוכחה בדרך השלילה: טענות עזר

Answer 19

ניתן להוכיח כל נב”כ על ידי שימוש בדבר ושלילתו
מקבוצה לא עקבית של נבכ”ים ניתן להוכיח כל נב”כ

הוכיח בעזרת הנחה בשלילה
למת הזחה
L3
תכונת הניתוק

Question 20

משפט ההוכחה בדרך השלילה

Answer 20

אם איחוד קבוצת נבכ”ים ושלילת אלפא אינו עקבי אז אלפא יכיח מקבוצת הנבכ”ים

Question 21

שימוש במשפט ההוכחה בדרך השלילה

Answer 21

דאבל נגייטן