חידה בלוגיקה בוליאנית

[CodeGuru]

האם תוכל לבנות מעגל בעל שלוש כניסות ושלוש יציאות שמחשב את הNOT של שלושת הכניסות באמצעות שני שערי NOT בלבד (ושערי AND ו OR בכמות לא מוגבלת)?
אם כן, איך. אם לא, למה לא?

[TheWizard]

כותרת: נראה לי שאי אפשר
אני לא בטוח כיצד להוכיח את זה…
אבל כמובן חלק מן ההוכחה הוא שמשערי OR ו-AND לא ניתן לבנות שער NOT.

[דניאלק]

כותרת: שעון אני מניח שאי אפשר…
F = (AC + BC´)´
כש
C = 1, F = A´
C = 0, F = B´
ואז השתמשנו רק ב
,NOT אחד
בשביל 2 סיביות
אבל לא מקבלים את הפלטים בו זמנית, אז זה כנראה לא פתרון לחידה….

חשבתי אולי שעון + latch
אבל אני לא מכיר אחד כזה שמשתמש בפחות מ2 שערי
NOT
(NAND ליתר דיוק)

סתם חשיבה בקול רם…
אבל שעון בטח אסור לפי התנאים של החידה, נכון?

[TheWizard]

כותרת: דיברתי מוקדם מדי
לאחר חיפוש (נסיון של כל מיני דברים על דף, טבלאות מצבים, שילובים שונים בין A, B, C, AND, OR, וכו´) ארוך ומייגע שלא הניב את הפתרון, חיפשתי ומצאתי באינטרנט עמוד שבו רשום שיש פתרון ושמה שחשבתי זה לא נכון (שאין פתרון ושלא ניתן ליצור עוד NOT), וכן שאסור להשתמש במחזירים (יציאה המחוברת לכניסה) כפי שדניאל חשב.
מצטער אם הרסתי חלק מהחידה (השאלה האם בכלל יש פתרון)

אז כן אפשר, אבל זה נורא נורא מסובך
משהו שכן הבנתי זה שיש להשתמש ב-2 ה-NOTים על ביטויים הכוללים את שלושת הקלטים (A,B,C)

[גררר]

כותרת: נראה לי…
AND ו OR אינם מערכת פעולות שלמה

עם NOT הם כן.

מכאן בשלילה נוכיח שאי אפשר לבנות NOT מOR ו AND

[דניאלק]

כותרת: תשובה לגררר
אפשר. TheWizard כבר ציין את זה.
אני אישית נואשתי מהחיפושים, ומצאתי את הפתרון באיזה אתר(מן הסתם, אני לא אפרסם את התשובה), אבל יש פתרון. אולי יש מקום לפרסם רמז…

[MoD]

כותרת: נראה לי…
לא פתרתי את זה.. (וזה נראה לי דיי מסובך..)
אבל נראה שלפתור את המעגל הזה יש צורך בבניית מעגל XOR.. נכון?..
(או שאני לגמרי לא בכיוון?)

[במקרה עברתי ……..]

כותרת: אי אפשר כי המערכת אינה שלמה !
(ולכן אי אפשר לקבל את הפונקציה NOT ע"י AND וOR)
AND וOR אינה מערכת שלמה.

[old_בן]

כותרת: פתרון
אני יודע שזו חידה ישנה, אבל השארתם אותה לא פתורה. אז הנה הוכחה שאין פתרון.

צדק מי שאמר ש- AND ו- OR לא יוצרים מערכת שלמה, כי לא כל פונקציה בוליאנית אפשר ליצור בעזרתם.

אז אילו פונקציות כן אפשר ליצור בעזרתם? כמובן פונקציות מונוטוניות לא יורדות לא טריוויאליות. פונקציות מונוטוניות לא יורדות הן כאלו שבהן אף יציאה לא קטנה כאשר מגדילים חלק מהכניסות (לצורך העניין, TRUE גדול מ- FALSE). הפונקציות הטריוויאליות הן הפונקציות שכל היציאות שלהן קבועות, ואותן כמובן אי אפשר ליצור רק מ- AND ו- OR בלי קבועים.

אפשר להוכיח שכל פונקציה מונוטונית לא יורדת לא טריוויאלית אפשר ליצור עם AND ו- OR, אבל זה לא נחוץ כרגע. מה שחשוב וקל להוכיח זה שאפשר ליצור רק פונקציות כאלה. ההוכחה היא באינדוקציה על המעגל, וצעד האינדוקציה משתמש בזה ש- AND לבד ו- OR לבד הן פונקציות כאלה.

נגדיר ש- nית ערכים תקרא לא גדולה מ- nיה אחרת אם אף ערך אינו גדול מהערך המתאים לו ב- nיה האחרת.

עכשיו ננסה לבדוק מעגל כנדרש וניכשל. בינתיים אנחנו בטוחים בדבר אחד: אל שני ה- NOTים שיש לנו נכנסות שתי היציאות d ו- e של פונקציה מונוטונית של הקלט (a,b,c), והפלט הוא פונקציה מונוטונית (עם 3 יציאות) של ((a,b,c,NOT(d),NOT(e).

אבל בואו נסתכל על הקלטים:
(F,F,F)
(T,F,F)
(T,T,F)
(T,T,T)
כל קלט גדול יותר מקודמו, ולכן ערכי d ו- e לא יכולים לקטון במעבר מאחד לשני. יש נקודה שבה d יתחלף מ- F ל- T, ונקודה שבה e יתחלף מ- F ל- T. כלומר יש לכל היותר שלושה ערכים שונים לזוג (d,e), ולכן יש שני קלטים ברשימה לעיל שבהם d ו- e מקבלים אותו ערך.

עבור שני הקלטים האלה, ((a,b,c,NOT(d),NOT(e) גדל במעבר מאחד לשני, אבל ((NOT(a),NOT(b),NOT(c) דווקא קטן, ולכן זו לא פונקציה מונוטונית.

[מאת]

תגובות