הבדלים בין גרסאות בדף "תרגול 3 תשעז"
(יצירת דף עם התוכן "===קבוצות קשרים שלמות=== תרגיל: הוכח באמצעות טבלאות אמת שניתן להציג את הקשרים 'גרירה' ו'וגם'...") |
|||
(2 גרסאות ביניים של 2 משתמשים אינן מוצגות) | |||
שורה 1: | שורה 1: | ||
− | + | חזרה ל[[83-116, בדידה 1 להנדסה, מערכי תרגול|דף מערכי התרגול]]. | |
− | + | ==צורות נורמליות: CNF ,DNF== | |
− | + | ישנן שתי "צורות נורמליות" להצגת '''כל''' פסוקית - DNF ו CNF. | |
− | + | ||
− | + | ||
− | === | + | ====תרגיל==== |
+ | יהי <math>A</math> פסוק ויהי <math>C</math> צורת CNF שלו ו-<math>D</math> צורת DNF שלו. הוכיחו או הפריכו: <math>C\equiv D</math> | ||
− | + | פתרון: ברור שהוכחה.... | |
+ | |||
+ | כעת, אחרי שהבנו שאלו שתי '''צורות''' שונות לאותו פסוק, כלומר הן שקולות, נבין איך צרים צורות אלו. | ||
===DNF=== | ===DNF=== | ||
שורה 121: | שורה 122: | ||
<math>C_1 \land C_2 \land C_3 \land C_4 \land C_5 </math> | <math>C_1 \land C_2 \land C_3 \land C_4 \land C_5 </math> | ||
+ | |||
הרחבה על עניינים אלו (שלושת התרגולים הראשונים) ניתן למצוא פה [[88-101 חשיבה מתמטית]] | הרחבה על עניינים אלו (שלושת התרגולים הראשונים) ניתן למצוא פה [[88-101 חשיבה מתמטית]] |
גרסה אחרונה מ־06:38, 5 בנובמבר 2017
חזרה לדף מערכי התרגול.
תוכן עניינים
צורות נורמליות: CNF ,DNF
ישנן שתי "צורות נורמליות" להצגת כל פסוקית - DNF ו CNF.
תרגיל
יהי פסוק ויהי צורת CNF שלו ו- צורת DNF שלו. הוכיחו או הפריכו:
פתרון: ברור שהוכחה....
כעת, אחרי שהבנו שאלו שתי צורות שונות לאותו פסוק, כלומר הן שקולות, נבין איך צרים צורות אלו.
DNF
ביטוי בצורת DNF מורכב מאוסף "פסוקיות" המחוברות ביניהן על ידי פעולות "או". כל פסוקית בעצמה מורכבת מאטומים המחוברים ביניהם על ידי פעולות "וגם". כל אטום הוא משתנה או שלילת משתנה.
בצורה סכמטית: כאשר כל מהצורה וכל שווה למשתנה או לשלילתו .
דוגמא: נמצא את צורת DNF של טבלת האמת הבאה:
0 | 0 | 0 | 0 |
0 | 0 | 0 | 1 |
1 | 0 | 1 | 0 |
1 | 1 | 0 | 0 |
0 | 0 | 1 | 1 |
1 | 1 | 0 | 1 |
0 | 1 | 1 | 0 |
0 | 1 | 1 | 1 |
נתמקד בשורות שערך האמת שלהן הוא 1 (שורות 3, 4, 6).
לשורה 3 נתאים את הפסוקית
מה עשינו? החלפנו כל משתנה שערכו 0 בשלילה שלו, וכל משתנה שערכו 1 השארנו בלי לגעת.
מה יצא לנו מזה? שימו לב שרק הצבה של ערכי האמת של שמופיעים בשורה 3 תתן ערך אמת 1 ב . כל הצבה אחרת (כלומר: הצבה של ערכי אמת של המשתנים בשורה אחרת) תתן 0 ב .
באופן דומה נייצר עבור שורה 4 ו עבור שורה 6:
כעת ה DNF של טבלת האמת היא פשוט
.
CNF
ביטוי בצורת CNF מורכב מאוסף "פסוקיות" המחוברות ביניהן על ידי פעולות "וגם". כל פסוקית בעצמה מורכבת מאטומים המחוברים ביניהם על ידי פעולות "או". כל אטום הוא משתנה או שלילת משתנה.
בצורה סכמטית: כאשר כל מהצורה וכל שווה למשתנה או לשלילתו .
נדגים על הדוגמא לעיל.
נתמקד בשורות שערך האמת שלהן הוא 0 (שורות 1, 2, 5, 7, 8)
לשורה 1 נתאים את הפסוקית
מה עשינו? כל משתנה שערכו 0 השארנו בלי לגעת, וכל משתנה שערכו 1 החלפנו בשלילתו.
מה יצא לנו מזה? שימו לב שרק הצבה של ערכי האמת של שמופיעים בשורה 1 תתן ערך אמת 0 ב . כל הצבה אחרת (כלומר: הצבה של ערכי אמת של המשתנים בשורה אחרת) תתן 1 ב .
באופן דומה נייצר עבור שורות 2 , 5, 7 ו-8:
כעת ה CNF של טבלת האמת היא פשוט
הרחבה על עניינים אלו (שלושת התרגולים הראשונים) ניתן למצוא פה 88-101 חשיבה מתמטית