Пристрій для розв’язання комбінаторно – логічних задач

1. Пристрій для розв'язання комбінаторнологічних задач, який має К груп інформаційних входів (К - кількість співмножників) по n розрядів у кожній (n - кількість змінних), виходи результату, лічильник, блок пам'яті, тригер, перший і другий елементи HI, вихід ознаки відсутності рішення, вихід ознаки наявності рішення, керуючий вхід, перший елемент І, причому вихід тригера з'єднаний з виходом ознаки наявності рішення, та через перший елемент НІ з першим входом першого елемента І, керуючий вхід з'єднаний з другим входом першого елемента І та з керуючим входом блока пам'яті, вихід першого елемента І з'єднаний з лі 38565 пам'яті, вхід читання якого підключений до тактового входу пристрою, і-й вихід блоку пам'яті підключений до і-го виходу результату рішення пристрою і до других входів m елементів і-й групи. Недоліком відомого пристрою є обмежені функціональні можливості. В основу винаходу поставлено задачу створити пристрій для розв’язання комбінаторно-логічних задач, а саме рівнянь виду: П1&П2&...&Пk=1, де: Пі= Аі1&Х1 v Ai2&X2v...vAin&Xn, Aij Î {0,1}. Поставлене завдання вирішується тим, що пристрій для розв'язання комбінаторно-логічних задач містить К груп інформаційних входів по n розрядів у кожній, виходи результату, лічильник, блок пам'яті, тригер, перший і другий елементи НІ, вихід ознаки відсутності рішення, вихід ознаки наявності рішення, керуючий вхід, перший елемент І, причому вихід тригера з'єднаний з виходом ознаки наявності рішення, та через перший елемент НІ з першим входом першого елемента І, керуючий вхід з'єднаний з другим входом першого елемента І та з керуючим входом блока пам'яті, вихід першого елемента І з'єднаний з рахунковим входом лічильника, перші n виходів якого з'єднані з адресними входами блока пам'яті, (n+1)-ий вихід з'єднаний з виходом ознаки відсутності рішення, та через другий елемент НІ з'єднаний з третім входом першого елемента І, згідно з винаходом має у своєму складі К блоків обчислення значення співмножника, другий елемент І, причому виходи блока пам'яті з'єднані з першими групами входів блоків обчислення значення співмножника, і-та група інформаційних входів з'єднана з другою групою входів і-го блоку обчислення значення співмножника, виходи блоків обчислення значення співмножника з'єднані з відповідними входами другого елементу І, вихід якого з'єднаний з одиничним входом тригера. Поставлене завдання вирішується також тим, що блок обчислення значення співмножника має у своєму складі n елементів І та елемент АБО, причому і-ті входи першої та другої групи входів блоку з'єднані з входами і-го елемента І, виходи елементів І з'єднані з відповідними входами елемента АБО, вихід якого з'єднаний з виходом блоку. На фіг. 1 представлена функціональна схема пристрою для розв'язання комбінаторно-логічних задач, на фіг. 2 представлена функціональна схема блоку обчислення значення співмножника. Пристрій для розв'язання комбінаторно-логічних задач містить К груп інформаційних входів по n розрядів у кожній 1, виходи результату 2, лічильник 3, К блоків обчислення значення співмножника 4, другий елемент І 5, блок пам’яті 6, тригер 7, перший і другий елементи HI 8, 9, вихід ознаки відсутності рішення 10, вихід ознаки наявності рішення 11, керуючий вхід 12, перший елемент I 13. Елементи пристрою для розв'язання комбінаторнo-логічних задач з'єднані таким чином. Вихід тригера 7 з'єднаний з виходом ознаки наявності рішення 11, та через перший елемент НІ 8 з першим входом елемента I 13, керуючий вхід 12 з'єднаний з другим входом першого елемента І та з керуючим входом блока пам'яті 6, вихід першого елемента I 13 з'єднаний з рахунковим входом лічильника 3, перші n виходів якого з'єднані з адресними входами блока пам'яті 6, (n+1)-ий вихід з'єднаний з виходом ознаки відсутності рішення 10, та через другий елемент HI з'єднаний з третім входом першого елемента І, виходи блока пам'яті 6 з'єднані з першими групами входів блоків обчислення значення співмножника 4, і-та група інформаційних входів з'єднана з другою групою входів іго блоку обчислення значення співмножника 4і, виходи блоків обчислення значення співмножника 4 з'єднані з відповідними входами другого елементу І, вихід якого з'єднаний з одиничним входом тригера 7. Блок обчислення значення співмножника 4 має у своєму складі елемент АБО 14 та n елементів I 15, причому і-ті входи першої та другої групи входів блоку з'єднані з входами і-го елемента І 15і, виходи елементів I 15 з'єднані з відповідними входами елемента АБО 16, вихід якого з’єднаний з виходом блоку. Всі елементи, що входять до складу пристрою є відомими елементами автоматики і обчислювальної техніки і можуть бути виконані по будь-якій відомій схемі. Працює пристрій для розв'язання комбінаторнo-логічних задач таким чином. Пристрій призначено для рішення логічних рівнянь вигляду: П1&П2&...&Пk=1, де: Пі = Аі1&Х1 v Ai2&X2v...vAin&Xn, Aij Î {0,1}, n - кількість змінних; k - кількість співмножників. На інформаційні входи 11-1k подаються значення коефіцієнтів А відповідно для кожного співмножника, причому Aij =1, якщо у диз'юнктивну форму і -го співмножника входить змінна Xj (інакше - 0). Пошук рішення полягає у послідовному формуванні двійкових кодів та визначення значень співмножників, при цьому знаходиться рішення мінімальної потужності. У початковому стані тригер 7 знаходиться в стані "1", двійковий лічильник 3 в стані 0...0. У залежності від двійкового коду, що поступає з виходу лічильника 3, з виходу блоку 6 пам'яті видаються сигнали "1", у відповідних позиціях, при цьому номери позицій "1", що формуються для кожного стану лічильника 3, є лексикографічне впорядкованими, тобто спочатку записані коди для сполучень по одному елементу, потім по два, по три і т.д. Наприклад, для n=3 ці коди мають вигляд: 001, 010, 100, 011, 101, 110, 111. На (n+1)-м виході двійкового лічильника - сигнал "0", на виході елемента HI 9 "1", тому після подачі на керуючий вхід 12 тактових імпульсів через елемент І 13 імпульси поступають на рахунковий вхід двійкового лічильника 3, змінюючи його стан і відповідне двійкове слово на виходах блоку пам'яті 6. Значення і-го вихідного розряду блоку б пам'яті відповідає значенню х. Блоки, обчислення значення співмножника 4 обчислюють значення співмножників, а елемент 5 I обчислює їх кон'юнкцію. У процесі рішення можуть бути два випадки. Рішення рівняння існує. При цьому на виході 11 з'являється ознака наявності рішення, і значення розрядів на виходах 2 результату відповідає значенням х. Рішення немає. У цьому випадку після перебору всіх варіантів двійковий лічильник 3 на (n+1) 2 38565 ому виході формує сигнал "1", при цьому на виході 10 з'являється ознака відсутності рішення, через елемент НІ 9 на вхід елемента І 13 поступає сиг нал "0", що закриває надходження імпульсів на рахунковий вхід лічильника 3. Таким чином, пристрій розв'язує логічні рівняння. Фіг. 1 Фіг. 2 3 38565 __________________________________________________________ ДП "Український інститут промислової власності" (Укрпатент) Україна, 01133, Київ-133, бульв. Лесі Українки, 26 (044) 295-81-42, 295-61-97 __________________________________________________________ Підписано до друку ________ 2001 р. Формат 60х84 1/8. Обсяг ______ обл.-вид. арк. Тираж 50 прим. Зам._______ ____________________________________________________________ УкрІНТЕІ, 03680, Київ-39 МСП, вул. Горького, 180. (044) 268-25-22 ___________________________________________________________ 4