גליון 1

שאלה 1

נגדיר את הקשר NAND על ידי:

א. כתבו את טבלת האמת של הקשר .
ב. הראו:
ג. הראו: הקשר בפני עצמו מהווה מערכת קשרים שלמה.

פתרון

א.

ב.
נוכיח באמצעות טבלת אמת

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

נשאר רק , נסתכל על טבלת האמת של

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

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

שאלה 2

הוכיחו את הזהויות הבאות:
א.

ב.

פתרון 2

א.
נוכיח באמצעות טבלת אמת

ב.
נוכיח באמצעות טבלת אמת

תרגיל 3

הקדמה
נאמר, שפסוק הוא בצורת CNF אם הוא מהצורה כאשר כל הוא מהצורה ו- הוא המשתנה או שלילתו .
נאמר, שפסוק הוא בצורת DNF אם הוא מהצורה כאשר כל הוא מהצורה של ו- הוא המשתנה או שלילתו .
לדוגמה: הפסוק

הוא פסוק בצורת DNF, והפסוק

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

התרגיל:
הראו: לכל טבלת אמת על המשתנים קיים פסוק בצורת CNF שמייצג אותה.

פתרון 3

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

או בקצרה

על פי מה שהוכחנו בשאלה 2

עכשיו נסתכל בתוך

על פי מה שהוכחנו בשאלה 2

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