Реферати, курсові, дисертації, дипломи

[ Алгебра Буля Дж та її застосування в теорії та практиці інформатики ]

<div style="font-size:16px;text-align:justify;">
	 Алгебра Дж. Буля і її застосування в теорії та практиці інформатики Інформація, з якою мають справу різного роду автоматизовані <a href="Інформаційні_системи" title="Інформаційні системи">інформаційні системи</a>, зазвичай називається даними., А самі такі системи - автоматизованими системами обробки даних (АСОД). Розрізняють вихідні (вхідні), проміжні і вихідні дані. Дані розбиваються на окремі складові, звані елементарними даними або елементами даних. Вживаються елементи даних різних типів. Тип даних (елементарних) залежить від значень, які ці дані можуть приймати. У сучасній безпаперовій інформатики серед різних типів елементарних даних найбільш уживаними є цілі і речові числа, слова (в деякому подалфавіте байтового алфавіту) і так звані булеві величини. Перші два типи величин потребують поясненні тільки у зв'язку з конкретними особливостями їх подання в сучасних ЕОМ. Насамперед розрізняють бінарне і двійково-десяткове представлення чисел. У двійковому поданні використовується двійкова система числення з фіксованим числом двійкових розрядів (найчастіше 32 або, для малих ЕОМ, 16 розрядів, включаючи розряд для представлення знака числа). Якщо нулем позначати плюс, а одиницею - мінус, то 00001010 означає ціле число + ( 2 Березня +2 l) = + l0, а 10001100 - число-(2 3 + 2 2) = -12 (для простоти взято 8-розрядне подання). Зауважимо, що знак числа в машинному поданні часто виявляється зручним ставити не на початку , а в кінці числа. У разі дійсних чисел (а фактично, з урахуванням обмеженою розрядності, дробових двійкових чисел) вживаються дві форми уявлення: з фіксованою та з плаваючою комою. У першому випадку просто заздалегідь умовляються про місце знаходження зайнятої, не вказуючи її фактично в коді числа. Наприклад, якщо домовитись, що кома стоїть між 3-м і 4-м розрядами праворуч, то код 00001010 означатиме число 00001,010 = (1 + 0 • 2 -1 + 1 • 2 -2 + 0 • 2 -3) = 1,25. У другому випадку код числа розбивається на два коди відповідно до подання числа у вигляді х = а • 2 b. При цьому число а (зі знаком) називається мантиси, а число b (зі знаком) - характеристикою числа х. Про становище коду характеристики і мантиси (разом з їх знаками) у загальному коді числа також встановлюються заздалегідь. Для економії числа розрядів в характеристиці b її часто представляють у вигляді b = 2k b 1, де k - фіксована константа (зазвичай k = 2). Вводячи ще одну константу m і вважаючи b = 2 k b 2 - m, можна уникнути також використання в коді характеристики знака (при малих b 2> 0 число b негативно, а при великих - позитивно). У двійково-десятковому поданні звичайні десяткові цифри (а також кома і знак) кодуються двійковими цифрами. При цьому для економії місця часто використовується так званий упакований код, коли за допомогою одного байта кодується не одна, а дві десяткові цифри. Подібне уявлення дозволяє в принципі кодувати числа будь значності. На практиці зазвичай все ж обмежують цю значность, хоча і настільки великими межами, що можна вважати їх необмеженими. Тип даних «довільне слово у вхідному алфавіті» не потребує спеціальних пояснень. Єдина умова - необхідність розрізняти межі окремих слів. Це досягається використанням спеціальних обмежувачів і покажчиків довжини слів. Тип булева змінна присвоюється елементарним даними, здатним приймати лише два значення: «істина» (і) і «брехня» (л). Для представлення булевих величин зазвичай використовується двійковий алфавіт з умовою і = 1, p = 0. Як відомо, моделлю в математиці прийнято називати будь безліч об'єктів, на яких визначено ті чи інші предикати. Під предикатом тут і далі розуміється функція у = f (x i,. .., X n), аргументи (x i,. .., x n) якої належать даній безлічі М, а значення (у) може бути або істиною, або брехнею. Іншими словами, предикат являє собою змінну (залежне від параметрів (Xi,. .., Х n} висловлювання. Воно описує деякий властивість, якою може володіти або не мати набір елементів (Xi, ..., Xn) безлічі М. Число п елементів цього набору може бути будь-яким. При л = 2 виникає особливо поширений тип предиката, який носить найменування бінарного відносини або просто відносини. Найбільш уживаними видами відносин є відносини рівності (=) і нерівності (¹). Ці відносини природно вводяться для елементарних даних будь-якого даного типу. Тим самим відповідний тип даних перетворюється в модель. Стосовно числах (цілим або речовим) природним чином вводяться також відношення порядку>, <,>, £, ³. Тим самим для відповідних типів даних визначаються багатші моделі. Будь-яке безліч М, як відомо, перетворюється в алгебру, якщо на ньому задано деякий кінцеве безліч операцій. Під операцією розуміється функція у = f (Xi,. .., Хп), аргументи н значення якої є елементами безлічі М. При л = 1 операція називається унарний, а при п = 2 - бінарною. Найбільш поширеними є бінарні операції. Для цілих чисел природним чином вводяться бінарні операції додавання, віднімання та множення, а також унарний операція зміни знаку числа. У разі дійсних чисел до них додається бінарна операція ділення і (якщо необхідно) унарна операція взяття зворотного величини. Зрозуміло. при необхідності можуть бути введені й інші операції. Особливе місце в машинній інформатики займає булева алгебра, що вводиться на безлічі величин типу булевих. Її основу складають дві бінарні операції: кон'юнкція («і»), диз'юнкція ("або") і одна унарна операція: заперечення («не»). Кон'юнкція позначається символом / \ і задається правилами 0 / \ 0 = 0, 0 / \ 1 = 0, 1 / \ 0 = 0, 1 / \ 1 = 1. Для диз'юнкції використовуються символ V і право 0 V 0 = 0, 0 V 1 == 1, 1 V 0 = 1, 1 V 1 = 1. Нарешті, заперечення ù змінює значення булевої величини на протилежне: ù 0 = 1, ù 1 = 0. Послідовність виконання операцій проводиться в порядку убування пріоритетів від ù к / \ і далі до V (якщо спеціальною розстановкою дужок не обумовлено протилежне). Наприклад, порядок дій у формулі ù a / \ b \ / c / \ ù d відповідає прямо вказаною дужками порядку: ((Ù a) / \ b) V (с / \ ù a)). У принципі можуть бути введені й інші операції, однак виявляється, що будь-яку таку операцію можна виразити у вигляді формули, що використовує тільки кон'юнкції, диз'юнкції і заперечення. Таким чином, запроваджений набір операцій є для булевої алгебри універсальним. Оскільки будь-яка алфавітна (буквено-цифрова)<a href="Інформація" title="Інформація"> інформація</a> може бути закодована в двійковій формі, то подібним чином можуть бути закодовані умови і вирішення завдань мул будь-якій області знань. Якщо число таких задач звичайно (хоча, може бути, і дуже велике), то існують максимальна довжина т коду умов цих завдань і максимальна довжина n коду n х рішень. У такому разі рішення всіх цих завдань (в двійковому коді) можуть бути отримані з їх умов за допомогою деякої системи булевих функцій y i = f i (x i, х 2, ... ..., x m) (i == 1, ..., n). У свою чергу всі ці функції можуть бути виражені через елементарні булеві операції кон'юнкції, диз'юнкції і заперечення. Існують різні способи представлення булевих величин (двійкових цифр) у вигляді тих чи інших фізичних (зазвичай електричних) сигналів (високе і низьке напруга, імпульси струму різної полярності і т. п.). Вибравши форму подання (двійкових) сигналів, можна побудувати елементарні пристрої, звані зазвичай логічними вентилями (або логічними елементами), які реалізують елементарні булеві операції. Іншими словами, вихідні сигнали цих пристроїв є елементарні булеві функції (результат виконання елементарних булевих операцій) від вхідних сигналів, як це показано на рис. 1. Маючи запас таких елементів, можна будувати більш складні <IMG SRC=dopc968439.zip ALIGN=LEFT><IMG SRC=dopc968440.zip ALIGN=LEFT><IMG SRC=dopc968441.zip ALIGN=LEFT> х <IMG SRC=dopc968439.zip ALIGN=LEFT><IMG SRC=dopc968439.zip ALIGN=LEFT> y <IMG SRC=dopc968444.zip ALIGN=LEFT><IMG SRC=dopc968439.zip ALIGN=LEFT><IMG SRC=dopc968446.zip ALIGN=LEFT> x <IMG SRC=dopc968439.zip ALIGN=LEFT><IMG SRC=dopc968439.zip ALIGN=LEFT> y <IMG SRC=dopc968449.zip ALIGN=LEFT><IMG SRC=dopc968450.zip ALIGN=LEFT><IMG SRC=dopc968451.zip ALIGN=LEFT><IMG SRC=dopc968452.zip ALIGN=LEFT> <IMG SRC=dopc968439.zip ALIGN=LEFT><IMG SRC=dopc968449.zip ALIGN=LEFT><IMG SRC=dopc968455.zip ALIGN=LEFT><IMG SRC=dopc968456.zip ALIGN=LEFT><IMG SRC=dopc968439.zip ALIGN=LEFT> x схеми, під'єднуючи виходи одних елементів до входів інших. Якщо при таких з'єднаннях уникати виникнення замкнутих контурів (наприклад, приєднання виходу елемента на один з його власних входів), то виникає клас схем, званих звичайно комбінаційними схемами. Такі схеми перебувають в однозначному відповідно до формулами булевої алгебри, так що з їх допомогою може бути виражена будь-яка система булевих функцій. Наприклад, схема, зображена на рис. 2, реалізує систему булевих функцій u = x / \ y \ / ù z і v = ù (X V y V z). На практиці побудова комбінаційних схем ускладнюється, оскільки сигнали при проходженні через вентилі послаблюються, спотворюють свою первісну форму, запізнюються. Тому необхідно поряд з логічними елементами включати в схему різного роду погоджують елементи (підсилювачі, формувачі сигналів та ін.) Завдання цих елементів - зробити схему працездатною і надійною. <IMG SRC=dopc968458.zip NAME=graphics1 ALIGN=BOTTOM WIDTH=460 HEIGHT=221 BORDER=0> Зі сказаного ясно, що можна побудувати комбінаційну схему для вирішення будь-якого кінцевого безлічі завдань, вирішення яких однозначно визначаються їх умовами (подаються на вхід схеми). Зокрема, якщо обмежитися якось фіксованою точністю подання дійсних чисел (розрядністю), то можна в принципі побудувати комбінаційну схему, яка обчислює яку задану речову функцію у = f (x i, ..., x n) (в двійкових кодах). На практиці, однак, виявляється, що вже схема помножувача (обчислює функцію у = X 1 • Х 2) при розрядності (двійковій) 32 і більше виявляється настільки складною, що множення в сучасних ЕОМ воліють реалізувати іншим, так званим алгоритмічним способом, про який мова піде нижче. У той же час багато, більш прості функції, наприклад функції додавання двох чисел, реалізуються комбінаційними схемами прийнятною складності. Відповідна схема носить найменування паралельного суматора. Слід зауважити, що успіхи мікроелектроніки роблять можливим побудова все більш складних схем. Якщо ще в 60-і роки кожен логічний елемент збирався з декількох фізичних елементів (транзисторів, діодів, опорів тощо), то вже до початку 80-х років промисловістю випускаються так звані інтегральні схеми, що містять багато сотень і навіть тисячі логічних вентилів. При цьому важливо підкреслити, що не тільки самі <a href="Логічні_елементи" title="Логічні елементи">логічні елементи</a>, але й з'єднання між ними (тобто вся схема в цілому) виготовляються одночасно в єдиному технологічному процесі на тонких пластинках хімічно чистого кремнію та інших речовин розмірами в частки квадратного сантиметра. Завдяки цьому різко зменшилася вартість виготовлення схем і підвищилася їхня надійність. Володіючи можливістю реалізувати будь ф і до с и р о в а н н и е залежності між вхідними і вихідними сигналами »комбінаційні схеми нездатні навчатися, адаптуватися до мінливих умов. На перший погляд здається, що така адаптація обов'язково вимагає структурних змін у схемі,. тобто зміни зв'язків між її елементами, а можливо, і складу цих елементів. Подібні зміни неважко реалізувати шляхом механічних перемиканні. Однак такий шлях практично неприйнятний через різке погіршення практично всіх параметрів схеми (швидкодії, габаритів, надійності та ін.) Існує набагато більш ефективний шлях вирішення зазначеної проблеми, заснований па введення в схему на додаток до вже перерахованих логічним елементам так званих е. Лемента пам'яті. Крім своїх вхідних і вихідних сигналів, елемент пам'яті характеризується ще третина інформаційним параметром - так званим станом цього елементу. Стан елементу пам'яті може змінюватися (але не обов'язково) лише в задані дискретні моменти часу t 1, t 2, ... під впливом сигналів, що з'являються на його входах в ці моменти. Найбільш уживана так звана синхронна організація роботи елементів пам'яті, при якій моменти їх можливих перемиканні (зміні стану) слідують один за одним через один і той же фіксований проміжок часу D t = const, званий тактом. Ці моменти визначаються звичайно з допомогою імпульсів, що виробляються спеціальним тактирующие синхрогенератора. Кількість тактових імпульсів, що видаються ним протягом однієї секунди, називається тактовою частотою. У сучасній електроніці вживаються в основному виконавчі елементи пам'яті, стан яких представляє собою булеву величину. Іншими словами, елемент пам'яті здатний запам'ятати всього лише один біт інформації. При необхідності запам'ятовування більшої кількості інформації використовується складова пам'ять (запам'ятовуючий пристрій), що складається з певної кількості елементів. В реальних умовах це безліч, зрозуміло, завжди звичайно, хоча в теоретичних дослідженнях буває зручно розглядати і нескінченну пам'ять (принаймні потенційно). У найпростішому випадку безліч елементів пам'яті організується в так званий реєстр, т. е. в (кінцеву) лінійно впорядковану послідовність елементів, званих розрядами (осередками) регістру. Розряди нумеруються послідовними натуральними числами 1, 2, ..., п. Число п цих розрядів називається довжиною регістру. Стану в, окремих розрядів складають (булеві) вектор о, званий станом регістра. Вхідні і вихідні сигнали окремих розрядів розглянутого регістра (також передбачувані булевими) складають відповідно вхідний х і вихідний у (векторні)<a href="Сигнал" title="Сигнал"> сигнали</a> даного регістра. Зауважимо ще раз, що в переважній більшості випадків у = а. Звичайна последовательностная схема, яка називається також кінцевим автоматом, складається з регістра пам'яті і двох комбінаційних схем. Умовність такого подання полягає насамперед у тому, що в схемі з чисто двійковими сигналами можна перемкнути сигнал і на один з виходів, а на інших виходах де мати нічого (це був би третій вид сигналу, відмінний як від 0, так і від 1) . Крім того, в переважній більшості випадків схеми недоцільно будувати окремо одна від Інший, так як при цьому, взагалі кажучи, зростає загальне число використовуваних логічних елементів. Однак ці умовності не змінюють головного - зроблених оцінок для числа різних комбінаційних схем, реалізованих кінцевим автоматом. Крім того, при деяких реалізаціях двійкових сигналів (наприклад, імпульсами різної полярності) в електронних схемах природним чином реалізується і третій вид сигналу, а саме, відсутність будь-яких імпульсів. У цьому випадку запропонована інтерпретація фактично втрачає свою умовність і може бути реалізована практично. Процесори Процесором називається пристрій, здатний виконувати деякий заданий набір операцій над даними в структурованої пам'яті і виробляти значення заданого набору логічних умов над цими даними. Стандартна схема процесора складається з двох пристроїв, званих звичайно арифметико-логічним пристроєм (АЛП) і пристроєм керування (УУ). У схему АЛП включається структурована пам'ять, що складається, як правило, з регістрів, до яких може додаватися один або кілька стеків, За допомогою спеціальних комбінаційних схем в структурованої пам'яті може здійснюватися той чи інший набір перетворень. Як вже зазначалося вище, перетворення (операції), що задаються комбінаційними схемами, на сьогоднішньому етапі розвитку мікроелектроніки воліють робити досить простими. Тому операції, виконувані АЛУ за один такт синхронізуючого генератора, називаються мікрооперацій, а відповідний їх виконання такт - мікротактом. Вибір тієї чи іншої мікрооперації здійснюється шляхом подання коду цієї мікрооперації на спеціальний керуючий вхід АЛП. 
	</div>

Будь ласка, не зберігайте тестовий текст.
Ваш ip: 3.140.185.170 буде збережений.

категорії
за типом
за алфавітом
завантажені