В чем заключается основное назначение разработанной джорджем буллем логической системы кратко

Обновлено: 05.07.2024

Имя английского математика Джорджа Буля, а скорее не оно само, а название изобретенной им алгебры, теперь называемой булевой, известно практически любому, кто хоть как-то соприкоснулся с основами устройства компьютеров.

Отец Буля был то ли сапожником, то ли книготорговцем, но в любом случае он не смог дать сыну серьезного образования. Поэтому в школе будущий математик в основном изучал латынь и иностранные языки, а после смерти отца, с 16 лет, был вынужден работать помощником учителя. Став учителем и в возрасте 20 лет создав собственную школу, он осознал необходимость обучения в ней математике, а для этого нужно было выучиться самому.

В 1849 году Джордж Буль получил в дополнение к почетным титулам и нормальные жизненные условия, он вплоть до своей безвременной кончины в 1864 году преподавал в Куинз-колледже, известном сегодня как Коркский университет.

Надо сказать, что в истории компьютеров было очень много случайностей. Иногда начинает казаться, что за ними кроется какая-то таинственная, если не сказать мистическая детерминированность. Не составляет исключения и чудесное озарение Шеннона, который догадался, каким образом можно приложить абстрактный математический аппарат к сугубо инженерному делу. Этому событию предшествовала последовательность псевдослучайных событий.

Логические элементы.

Буфер (повторитель)

Буфер (повторитель) представляет собой просто усилительный каскад. В логическом смысле усиление является аналоговой функцией, а не цифровой, но буферы часто требуются и в цифровых схемах. Например, биты адреса при выходе из процессора оказываются довольно слабыми по нагрузочной способности, и их нельзя подавать в шину адреса без усиления по току. Поэтому на каждой линии адреса имеется буфер, который усиливает ток передаваемого бита. Имеются буферы и на каждой линии шины данных компьютера (практически здесь есть два буфера по одному для каждого направления). Буферы обеспечивают надежную работу шин адреса и данных. Логика работы буфера заключается в следующем. При подаче на вход буфера логического состояния такое же состояние появляется и на выходе буфера. Если на вход подается Н-уровень (высокий уровень напряжения, например 2,4 вольта), на выходе также действует Н-уровень, а при подаче на вход L-уровня (низкий уровень напряжения, например, 0.2 вольта) на выходе будет L-уровень. На электрических принципиальных схемах буфер обозначается треугольником; вход подается на сторону треугольника, а выход снимается с противолежащей вершины. Логическое состояние при подаче на любой из буферов быстро проходит на выход и усиливается по току. На прохождение сигнала от входа к выходу требуется определенное время, которое называется временем задержки распространения.

Рис. 1. Буфер (усилитель)

Инверторы

На рис. 4 показана таблица истинности элемента AND с двумя входами. При большем числе входов результат будет аналогичным. Имеется только одна комбинация входов, когда на выходе появляется Н-уровень. Обозначение элемента AND приведено на рис. 4, причем все выходы независимо от их числа подаются на плоскую сторону, а выход снимается с закругленной вершины. Элемент AND напоминает некоторый ключ, который включает и выключает схему, подсоединенную к его выходу. Обычно на одном или нескольких входах элемента AND действуют Н-уровни, поэтому на выходе имеется L-уровень, что соответствует выключенному состоянию. При включении схемы на все входы элемента AND подаются Н-уровни. Элемент AND изменяет выход с L-уровня на Н-уровень и включает схему, подсоединенную к выходу. Таблицы истинности позволяют полностью проверить работу этого элемента. Когда в элементе AND (см. рис. 4) хотя бы один из входов имеет L-уровень, на выходе должен действовать L-уровень. Только когда на обоих входах есть Н-уровни, выход должен иметь L-уровень. При проверке входов и выхода с помощью логического пробника, тестера или осциллографа они должны соответствовать таблице истинности. Если выход не верен, то микросхема неисправна.

Рис. 4. В таблице истинности показаны два входа и один выход

Обозначение элемента OR (рис. 5) напоминает обозначение элемента AND, только выход показывается острым, а не закругленным. Обычно плоская часть для входов закруглена. Для проверки правильности работы элемента OR используется таблица истинности.

Рис. 5. На таблице истинности показаны два входа и один выход, но число входов может быть больше.

По таблице истинности элемента NAND (рис. 6) видно, что его выходы аналогичны выходам элемента AND, но инвертированы. Элемент AND формирует на выходе Н-уровень только при наличии Н-уровней на всех входах, а на выходе элемента NAND действует L-уровень только при наличии Н-уровней на всех входах. В любой другой ситуации на выходе элемента NAND имеется Н-уровень.

Рис. 6. Таблица истинности элемента NAND

Элемент NAND — это просто элемент AND с добавленным инвертором. Из элементов NAND состоят все ТТЛ-микросхемы, т.е. он является основным логическим элементом. Только на элементах NAND можно реализовать любой другой логический элемент или регистр. ТТЛ-микросхема состоит из биполярных транзисторов, диодов и резисторов. Имеются ТТЛ-транзисторы с несколькими эмиттерами, обычные транзисторы с одним эмиттером, р-n-переходы, действующие как диоды, и крошечные интегральные резисторы. Базовый элемент NAND состоит из пяти частей (рис. 7): один элемент AND, один элемент NOT и три буфера (элементы YES). Элемент AND выполнен на многоэмиттерном транзисторе с соответствующим числом входов (эмиттеров). Он формирует Н-уровень при наличии Н-уровней на всех входах. Выход элемент AND подается на инвертор NOT, который инвертирует и усиливает сигнал.

Затем сигнал разделяется на два тракта. По одному тракту сигнал проходит через помехоустойчивый буфер, а затем через второй буфер, предназначенный для усиления Н-уровня сигнала. По второму тракту усиливается L-уровень сигнала. Выходные буферы объединяются и обеспечивают общий выход. Отметим, что при любом уровне, выходной сигнал оказывается усиленным.

Рис. 7. Элемент NAND

Таблица истинности элемента NOR на рис. 8 показывает, что на выходе элемента NOR имеется Н-уровень только при наличии L-уровней на всех входах; в противном случае на выходе действует L-уровень. Выход является инвертированным выходом элемента OR. Элемент NOR, является объединением элемента OR и инвертора. Есть много разновидностей таких логических элементов, которые можно использовать при проектировании цифровых устройств.

Рис. 8. Обозначение элемента NOR и его таблица истинности

Рис. 9. Обозначение элемента EOR

Таблица истинности элемента EOR, для первых трех комбинаций, совпадает с таблицей истинности элемента OR, но в четвертой комбинации имеется различие. В элементе OR при наличии Н-уровней на двух входах выход также должен иметь Н-уровень, а в элементе EOR в этой ситуации на выходе образуется L-уровень. Различие между элементами OR и EOR только в этой комбинации. Если поразмыслить, то выходы элемента OR не строго соответствуют логике. По определению элемента OR, если один или второй вход имеют Н-уровень, то выход должен иметь Н-уровень. Это истинно для входных комбинаций LL, LH и HL. В комбинации LL ни один из входов не имеет Н-уровня, поэтому на выходе L-уровень. В комбинациях LH и HL один из входов имеет Н-уровень, поэтому на выходе должен быть Н-уровень. Однако в последней комбинации НН оба входа имеют Н-уровень, а не первый или второй, а на выходе элемента OR сохраняется Н-уровень, что противоречит логике. Здесь скрыто определенное противоречие элемента OR. Элемент EOR подчиняется логике. Четыре входных комбинации двухвходового элемента EOR логически повторяют элемент OR за исключением комбинации НН. Когда на обоих входах элемента EOR имеются Н-уровни, выход в соответствии с логикой имеет L-уровень. Элемент EOR формирует на выходе Н-уровень, только в том случае, когда один или второй из входов имеют Н-уровень, но не тогда, когда оба они имеют Н-уровень. Отметим, что иногда элемент EOR называют XOR.

Элемент ENOR представляет собой элемент EOR с добавленным инвертором, который на схемах обозначается аналогично элементу EOR, но с кружком на выходе элемента (рис. 10). Таблица истинности показывает, что выход элемента ENOR является инвертированным выходом элемента DOR. При проверке составного элемента ENOR удобнее игнорировать функцию ENOR и проверять оба элемента отдельно. Например, следует проверить оба входа элемента EOR и его выход. Если выходной сигнал не соответствует ожидаемому, элемент неисправен. Если выход правилен, следует проверить вход и выход инвертора. Неправильный вход или выход могут локализовать неисправность.

Рис. 10. Таблица истинности элемента ENOR

Элементы ENOR и другие можно образовать, используя другие микросхемы. Например, на рис. 10 показано, как образовать элемент ENOR из пяти элементов NAND.

Альтернативные обозначения

Обозначения элементов NOT, AND, NAND и NOR на схемах распознаются довольно легко. Для этих элементов имеются альтернативные обозначения, приведенные на рис. 11. Элемент AND можно показать как элемент OR с кружками инверсии на входах и выходе. Такое обозначение означает, что схема выполняет функцию AND, но при этом она вначале инвертирует входы, затем объединяет их по ИЛИ и инвертирует выход. Окончательный результат представляет объединение входных сигналов по И.

Альтернативное обозначение элемента OR состоит из элемента AND с кружками инверсии на входах и выходе. Можно встретить элемент NOR в виде элемента AND с инвертированными входами, а элемент NAND - как элемент OR с инвертированными входами. У инвертора кружок инверсии может находиться на входе, а не на выходе. У элемента AND один из четырех входов может иметь кружок инверсии. На схемах можно встретить разнообразные обозначения, правильными являются базовые. Вы должны уметь проследить, как бит проходит от одного элемента к другому. В исправных микросхемах он должен подчиняться таблицам истинности. Напряжение (логический уровень, состояние) бита изменяется в соответствии с логической функцией того элемента, через который он проходит.

Рис.11. Элемент NOR с кружками NOT на входах действует как элемент AND

Построение схем из элементов

Напомним, что элементы NOT, AND и OR реализованы из микроскопических транзисторов, диодов, резисторов и конденсаторов, размещенных на кристалле кремния. Из этих базовых элементов образуются элементы NAND, NOR, EOR и ENOR. Для усиления сигналов применяются буферы. Рассмотренные элементы, за исключением буферов, при работе компьютера просто включаются и выключаются в предсказуемой последовательности. Следующий этап заключается в построении из элементов более сложных схем: триггеров, защелок, регистров сдвига, счетчиков, сумматоров, шифраторов, дешифраторов, мультиплексоров и др.

Триггер можно построить на двух биполярных транзисторах, двух полевых транзисторах и других приборах. Напомним, что триггер это схема, которая может хранить Н- или L-уровень. Он хранит логический бит, когда один из двух элементов включен, а другой выключен. Триггер изменяет состояние, когда внешний сигнал заставляет измениться состояния элементов. Другими словами, выключенный элемент включается, а включенный выключается. Поведение триггера обычно описывает таблица истинности. Взаимодействие элементов и триггеров обеспечивает цифровую обработку.

Защелка тоже предназначена для хранения бита. Типичной защелкой служит D-триггер (буква D означает Data - данные). Защелка, как и триггер, может хранить Н- или L-уровень. Группа на восьми D-триггеров может хранить байт данных.

В компьютерах часто применяется микросхема мультиплексора, которая представляет собой набор логических элементов для управления передачами битов по линиям шины. Например, 16 бит необходимо подавать в два приема по восемь битов на одни и те же адресные входы. Именно такую задачу и решает мультиплексор.

Дешифратор, например, имеет три входа данных и формирует из них восемь выходных сигналов. Три входных бита образуют восемь комбинаций LLL, LLH, LHL, LHH, HLL, HLH, HHL и ННН. Каждая из этих комбинаций дешифруется внутренними элементами и выбирает одну из восьми выходных линий. У дешифратора имеется также три входа разрешения, упрощающих применение микросхемы.

Кроме проведения счета триггеры и логические элементы могут действовать как регистры сдвига. Регистр сдвига - это группа триггеров, которые могут сдвигать свое содержимое на один бит вправо или влево по импульсу управления.

Свидетельство и скидка на обучение каждому участнику

Зарегистрироваться 15–17 марта 2022 г.

Джордж Буль

Джордж Буль по праву считается отцом математической логики. Для обработки логических выражений в математической логике была создана алгебра высказываний, или алгебра логики. Поскольку основы такой алгебры были заложены в трудах английского математика Джоржа Буля, то алгебра логики получила также название булевой алгебры. Алгебра логики отвлекается от смыслового содержания высказываний и принимает во внимание только истинность или ложность высказывания.

В ХХ столетии ученые объединили созданный Джорджем Булем математический аппарат с двоичной системой счисления, заложив тем самым основы для разработки цифрового электронного компьютера.

Джордж Буль родился в Линкольне (Англия) в семье мелкого торговца. Материальное положение его родителей было тяжелым, поэтому Джордж смог окончить только начальную школу для детей бедняков; в других учебных заведениях он не учился. Этим отчасти и объясняется, что, не связанный традицией, он пошел в науке собственным путем. Буль самостоятельно изучал латынь, древнегреческий, немецкий и французский языки, изучил философские трактаты. С ранних лет Буль искал работу, оставляющую возможности для самообразования. После многих неудачных попыток Булю удалось открыть маленькую начальную школу, в которой он преподавал сам. Школьные учебники по математике привели его в ужас своей нестрогостью и нелогичностью, Буль вынужден был обратиться к сочинениям классиков науки и самостоятельно проштудировать обширные труды Лапласса и Лагранжа.

Первым попытался перевести законы мышления (формальную логику) из словесного царства, полного неопределенностей, в царство математики, был немецкий ученый Готфрид Вильгельм Лейбниц (в 1666 г.). Спустя более ста лет, в 1816 году, уже после смерти Лейбница, Джордж Буль подхватил его идею о создании логического универсального языка, подчиняющегося строгим математическим законам. Буль изобрел своеобразную алгебру – систему обозначений и правил, применимую ко всевозможным объектам, от чисел и букв, до предложений.

Буль был, вероятно, одним из первых математиков, обратившимся к логической проблематике. Буль не считал логику разделом математики, но находил глубокую аналогию между символическим методом алгебры и символическим методом представления логических форм и силлогизмов.

Буль изобрел своеобразную алгебру – систему обозначений и правил, применимую ко всевозможным объектам, от чисел до предложений. Пользуясь этой системой, он мог закодировать высказывания (утверждения, истинность или ложность которых требовалось доказать) с помощью символов своего языка, а затем манипулировать ими, подобно тому как в математике манипулируют числами. Основными операциями булевой алгебры являются конъюнкция (И), дизъюнкция (ИЛИ), отрицание (НЕ).

Через некоторое время стало понятно, что система Буля хорошо подходит для описания электрических переключателей схем. Ток в цепи может либо протекать, либо отсутствовать, подобно тому, как утверждение может быть либо истинным, либо ложным.

А еще несколько десятилетий спустя, уже в ХХ столетии, ученые объединили созданный Джорджем Булем математический аппарат с двоичной системой счисления (цифры которой 0 и 1 также подходят для описание двух состояний: утверждение истинно - утверждение ложно, лампочка горит - лампочка не горит), заложив тем самым основы для разработки цифрового электронного компьютера.

Список использованной литературы

Алгебра логики — раздел математической логики, в котором изучаются логические операции над высказываниями. Высказывания могут быть истинными и ложными.

Содержание

Определение

Высказывания строятся над множеством , где B — непустое множество, над элементами которого определены три операции:

отрицание (унарная операция), конъюнкция (бинарная), дизъюнкция (бинарная),

а также две константы — логический ноль 0 и логическая единица 1.

Дизъю́нкт — пропозициональная формула, являющаяся дизъюнкцией одного или более литералов (например ). Конъюнкт — пропозициональная формула, являющаяся конъюнкцией одного или более литералов (например ).

Аксиомы

$\neg$

g₁(x) — отрицание/негация (g₁(x) = x = x')

g₂(x) — тождественная функция (g₂(x) = x)

Здесь 0 и 1 — тождественные нуль и единица соответственно,

f₁(x, y) — конъюнкция (f₁(x, y) = x&y = xy = xy = min(x, y)),

$\lor$

f₂(x, y) — дизъюнкция (f₂(x, y) = xy = max(x, y)),

f₃(x, y) — эквивалентность (f₃(x, y) = xy = xy = xy),

$\oplus$

f₄(x, y) — сумма по модулю два (f₄(x, y) = xy),

f₅(x, y) — импликация от y к x (f₅(x, y) = xy = xy),

f₆(x, y) — импликация от x к y (f₆(x, y) = xy = xy),

f₁₁—f₁₄ — функции только одного аргумента,

Все вышеперечисленные функции называются логическими связками.

Логические операции

Простейшим и наиболее широко применяемым примером такой алгебраической системы является множество B, состоящее всего из двух элементов:

Как правило, в математических выражениях Ложь отождествляется с логическим нулём, а Истина — с логической единицей, а операции отрицания (НЕ), конъюнкции (И) и дизъюнкции (ИЛИ) определяются в привычном нам понимании. Легко показать, что на данном множестве B можно задать четыре унарные и шестнадцать бинарных отношений, представленных в таблице справа, однако все они могут быть получены через суперпозицию трёх выбранных операций.

Логика высказываний послужила основным математическим инструментом при создании компьютеров. Она легко преобразуется в битовую логику: истинность высказывания обозначается одним битом (0 — ЛОЖЬ, 1 — ИСТИНА); тогда операция приобретает смысл вычитания из единицы; — немодульного сложения; & — умножения; — равенства; — в буквальном смысле сложения по модулю 2 (исключающее Или — XOR); — непревосходства суммы над 1 (то есть A B = (A + B) Свойства логических операций

Существуют методы упрощения логической функции: например, Карта Карно, метод Куайна - Мак-Класки

История

Своим существованием наука обязана английскому математику Джорджу Булю, который исследовал логику высказываний. Первый в России курс по алгебре логики был прочитан П. С. Порецким в Казанском государственном университете

Читайте также: