תרגול 3 תשעז - היסטוריית גרסאות

אריאל ב־06:38, 5 בנובמבר 2017

2017-11-05T06:38:50Z

→ הגרסה הקודמת		גרסה מ־06:38, 5 בנובמבר 2017
שורה 1:		שורה 1:
	חזרה ל[[83-116, בדידה 1 להנדסה, מערכי תרגול\|דף מערכי התרגול]].		חזרה ל[[83-116, בדידה 1 להנדסה, מערכי תרגול\|דף מערכי התרגול]].

	==~~קבוצות קשרים שלמות~~==		==צורות נורמליות: CNF ,DNF==

	~~תרגיל: הוכח באמצעות טבלאות אמת שניתן להציג את הקשרים~~ '~~גרירה~~' ו'~~וגם~~' ~~באמצעות~~ 'או' ~~ושלילה בלבד~~		ישנן שתי "צורות נורמליות" להצגת '''כל''' פסוקית - DNF ו CNF.

	~~פתרון:~~		====תרגיל====
	~~מתקיים~~ <math>A~~\to B \equiv \neg A \or B~~</math>		יהי <math>A</math> פסוק ויהי <math>C</math> צורת CNF שלו ו-<math>D</math> צורת DNF שלו. הוכיחו או הפריכו: <math>C\equiv D</math>
	~~ומתקיים~~ <math>~~A \and B~~ \equiv ~~\neg(\neg A \or \neg B)~~</math>

	~~==צורות נורמליות~~: ~~CNF ,DNF==~~		פתרון: ברור שהוכחה....

	~~ישנן~~ שתי ~~"צורות נורמליות" להצגת~~ '''כל''' ~~פסוקית - DNF ו CNF~~.		כעת, אחרי שהבנו שאלו שתי '''צורות''' שונות לאותו פסוק, כלומר הן שקולות, נבין איך צרים צורות אלו.

	===DNF===		===DNF===
שורה 124:		שורה 123:
	<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>

	~~====תרגיל====~~
	~~יהי <math>A</math> פסוק ויהי <math>C</math> צורת CNF שלו ו-<math>D</math> צורת DNF שלו. הוכיחו או הפריכו: <math>C\equiv D</math>~~

	~~פתרון: ברור שהוכחה....~~

	הרחבה על עניינים אלו (שלושת התרגולים הראשונים) ניתן למצוא פה [[88-101 חשיבה מתמטית]]		הרחבה על עניינים אלו (שלושת התרגולים הראשונים) ניתן למצוא פה [[88-101 חשיבה מתמטית]]

אריאל ב־18:42, 4 בנובמבר 2017

2017-11-04T18:42:56Z

→ הגרסה הקודמת		גרסה מ־18:42, 4 בנובמבר 2017
שורה 1:		שורה 1:
	חזרה ל[[83-116, בדידה 1 להנדסה, מערכי תרגול\|דף מערכי התרגול]].		חזרה ל[[83-116, בדידה 1 להנדסה, מערכי תרגול\|דף מערכי התרגול]].

	===קבוצות קשרים שלמות===		==קבוצות קשרים שלמות==

	תרגיל: הוכח באמצעות טבלאות אמת שניתן להציג את הקשרים 'גרירה' ו'וגם' באמצעות 'או' ושלילה בלבד		תרגיל: הוכח באמצעות טבלאות אמת שניתן להציג את הקשרים 'גרירה' ו'וגם' באמצעות 'או' ושלילה בלבד
שורה 9:		שורה 9:
	ומתקיים <math>A \and B \equiv \neg(\neg A \or \neg B)</math>		ומתקיים <math>A \and B \equiv \neg(\neg A \or \neg B)</math>

	===צורות נורמליות: CNF ,DNF===		==צורות נורמליות: CNF ,DNF==

	ישנן שתי "צורות נורמליות" להצגת '''כל''' פסוקית - DNF ו CNF.		ישנן שתי "צורות נורמליות" להצגת '''כל''' פסוקית - DNF ו CNF.
שורה 123:		שורה 123:

	<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>

			====תרגיל====
			יהי <math>A</math> פסוק ויהי <math>C</math> צורת CNF שלו ו-<math>D</math> צורת DNF שלו. הוכיחו או הפריכו: <math>C\equiv D</math>

			פתרון: ברור שהוכחה....

	הרחבה על עניינים אלו (שלושת התרגולים הראשונים) ניתן למצוא פה [[88-101 חשיבה מתמטית]]		הרחבה על עניינים אלו (שלושת התרגולים הראשונים) ניתן למצוא פה [[88-101 חשיבה מתמטית]]

Mathzeta2 ב־17:36, 24 באוקטובר 2017

2017-10-24T17:36:44Z

→ הגרסה הקודמת		גרסה מ־17:36, 24 באוקטובר 2017
שורה 1:		שורה 1:
			חזרה ל[[83-116, בדידה 1 להנדסה, מערכי תרגול\|דף מערכי התרגול]].

	===קבוצות קשרים שלמות===		===קבוצות קשרים שלמות===

אריאל: יצירת דף עם התוכן "===קבוצות קשרים שלמות=== תרגיל: הוכח באמצעות טבלאות אמת שניתן להציג את הקשרים 'גרירה' ו'וגם'..."

2016-11-29T13:15:41Z

יצירת דף עם התוכן "===קבוצות קשרים שלמות=== תרגיל: הוכח באמצעות טבלאות אמת שניתן להציג את הקשרים 'גרירה' ו'וגם'..."

דף חדש

===קבוצות קשרים שלמות===

תרגיל: הוכח באמצעות טבלאות אמת שניתן להציג את הקשרים 'גרירה' ו'וגם' באמצעות 'או' ושלילה בלבד

פתרון:
מתקיים <math>A\to B \equiv \neg A \or B</math>
ומתקיים <math>A \and B \equiv \neg(\neg A \or \neg B)</math>

===צורות נורמליות: CNF ,DNF===

ישנן שתי "צורות נורמליות" להצגת '''כל''' פסוקית - DNF ו CNF.

===DNF===

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

בצורה סכמטית: <math>D_1 \lor D_2 \lor \dots \lor D_n</math> כאשר כל <math>D_i</math> מהצורה <math>p_1\land p_2 \land \dots \land p_m</math> וכל <math>p_i</math> שווה למשתנה <math>x</math>
או לשלילתו <math>\lnot x</math>.

דוגמא: נמצא את צורת DNF של טבלת האמת הבאה:

{| border="1" align="center" style="text-align:center;"
|<math>f(x_1,x_2,x_3)</math>
| <math>x_3</math>
|<math>x_2</math>
|<math>x_1</math>
|-
|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 נתאים את הפסוקית <math>D_1=\lnot x_1 \land x_2 \land \lnot x_3</math>

מה עשינו? החלפנו כל משתנה שערכו 0 בשלילה שלו, וכל משתנה שערכו 1 השארנו בלי לגעת.

מה יצא לנו מזה? שימו לב שרק הצבה של ערכי האמת של <math>x_1,x_2,x_3</math> שמופיעים בשורה 3 תתן ערך אמת 1 ב <math>D_1</math>. כל הצבה אחרת (כלומר: הצבה של ערכי אמת של המשתנים בשורה אחרת) תתן 0 ב <math>D_1</math>.

באופן דומה נייצר <math>D_2</math> עבור שורה 4 ו <math>D_3</math> עבור שורה 6:

<math>D_2=\lnot x_1 \land\lnot x_2 \land x_3, \quad D_3=x_1\land \lnot x_2 \land x_3</math>

כעת ה DNF של טבלת האמת היא פשוט

<math>D_1\or D_2 \or D_3=(\lnot x_1 \land x_2 \land \lnot x_3) \or (\lnot x_1 \land \lnot x_2 \land x_3) \or (x_1 \land \lnot x_2 \land x_3)</math>.

===CNF===

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

בצורה סכמטית: <math>C_1 \land C_2 \land \dots \land C_n</math> כאשר כל <math>C_i</math> מהצורה
<math>q_1\lor q_2 \lor \dots \lor q_m</math> וכל <math>q_i</math> שווה למשתנה <math>x</math>
או לשלילתו <math>\lnot x</math>.

נדגים על הדוגמא לעיל.

נתמקד בשורות שערך האמת שלהן הוא 0 (שורות 1, 2, 5, 7, 8)

לשורה 1 נתאים את הפסוקית <math>C_1= x_1 \lor x_2 \lor x_3</math>

מה עשינו? כל משתנה שערכו 0 השארנו בלי לגעת, וכל משתנה שערכו 1 החלפנו בשלילתו.

מה יצא לנו מזה? שימו לב שרק הצבה של ערכי האמת של <math>x_1,x_2,x_3</math> שמופיעים בשורה 1 תתן ערך אמת 0 ב <math>C_1</math>. כל הצבה אחרת (כלומר: הצבה של ערכי אמת של המשתנים בשורה אחרת) תתן 1 ב <math>C_1</math>.

באופן דומה נייצר <math>C_2,C_3,C_4,C_5</math> עבור שורות 2 , 5, 7 ו-8:

<math>C_2= x_1 \lor \lnot x_2 \lor \lnot x_3, C_3=\lnot x_1\lor \lnot x_2 \lor x_3</math>

<math> C_4=x_1 \lor \lnot x_2 \lor \lnot x_3, C_5= \lnot x_1 \lor \lnot x_2 \lor \lnot x_3</math>

כעת ה CNF של טבלת האמת היא פשוט

<math>C_1 \land C_2 \land C_3 \land C_4 \land C_5 </math>

הרחבה על עניינים אלו (שלושת התרגולים הראשונים) ניתן למצוא פה [[88-101 חשיבה מתמטית]]