 |
אכן. אפשר להוכיח את זה, וגם שזה הדבר הכי טוב שאפשר להשיג. אני אנסה לכתוב בתמציתיות, אבל עם קצת יותר הרחבה זאת יוצאת הוכחה ריגורוזית לכל דבר:
הדרך לייצר 2 בחזקת n פחות 1 NOT'ים בעזרת n שערים היא להשתמש בשערי ה- NOT ע"מ לגלות בדיוק כמה ביטים דלוקים יש: נגדיר את מספר הביטים הדלוקים ב- m - מספר n ספרתי בייצוג ביטי. פונק' שהיא 1 אמ"מ יותר מחצי מהביטים דלוקים קל להגדיר - זוהי פונק' MAJ. בעזרת ה- NOT הראשון יהיו לנו שתי פונק' - כל אחת היא 1 אמ"מ ביט ה- most של m הוא משהו מסוים. כעת נניח שיש לנו 2 בחזקת k פונק' מציינות (שכל אחת מהן היא 1 אמ"מ k ביטי ה- most הם משהו מסוים). כל אחת תוחמת את m במקטע מסוים, ומכל אחת נוכל לחשב את הפונק' המציינת ש- m נמצא במחצית העליונה של המקטע ע"י AND של הפונק' המציינת עם פונק' MAJ מתאימה. לאחר שחישבנו את המחציות העליונות נאחד את כולן (OR) ונהפוך את כולן ביחד בעזרת NOT אחד - ואז נחתוך (AND) את התוצאה עם כל מקטע לקבלת המחציות התחתונות של כל אחד מ- 2 בחזקת k המקטעים. קיבלנו 2 בחזקת k+1 פונק' מציינות חדשות - שאומרות מה ערך k+1 ביטי ה- most של m. בהנתן מס' הביטים הדלוקים m קל לחשב את ה- NOT של משתנה מסוים - הוא 0 אמ"מ לפחות (למעשה בדיוק) m מהמשתנים האחרים הם 1 (וזה MAJ כמובן).
למה אי אפשר לחשב 2 בחזקת n שערי NOT בעזרת n שערים (אם אתה מתמטיקאי ולא מהנדס שמחכה שהמעגל יתייצב אחרי כמה איטרציות)? משיקולי מונוטוניות: אם אפשר אז אפשר לחשב כל פונק' על 2 בחזקת n משתנים, אבל אם נדגום את הפונק' ב- (2 בחזקת n) ועוד 1 המקומות מהצורה 000.0111.11, ונחשוב עליה כעל פונק' מ- {0,1,...,2^n} ל- {0,1}), אז AND,OR הן פונק' מונוטוניות במובן הרגיל (מכאן והלאה מונוטוניות=מונוטוניות לא יורדת), ולכן לפני שמפעילים את ה- NOT הראשון יש לנו מקטע מונוטוני אחד (כל הפונק' מונוטוניות על כל הקטע). בכל פעם שמפעילים NOT, הוא מסוגל לפצל כל מקטע מונוטוני ל-2 מקטעי מונוטוניות (שבמסגרתם נשארות כל הפונק' לאחר מכן, בשל המונוטוניות), ולכן בסוף יהיו לנו לכל היותר 2 בחזקת n מקטעי מונוטוניות => קיים מקטע מונוטוניות באורך 2 לפחות => לא ניתן לייצג את כל הפונק' (וזה כמובן לא משנה על איזה פונק' הפעלנו NOT בכל שלב ומה עשינו אח"כ).
ניסיתי לכתוב בתמציתיות - אם יצא לי לא מובן אני אפרט עוד.
|
 |
RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש