Двоичные переменные и переключательные функции

 

Для формального описания узлов ЭВМ при их анализе и синтезе используется аппарат алгебры логики. Основные положения алгебры логики разработал в XIX в. английский математик Джордж Буль. Алгебру логики называют также булевой алгеброй.

В булевой алгебре различают двоичные переменные и переключательные функции.

Двоичные переменные могут принимать два значения: 0 и 1. Они называются также логическими или булевыми переменными и обозначаются символами х₁,x₂,х₃,...

Переключательные функции (ПФ) зависят от двоичных переменных. Они, как и аргументы, могут принимать лишь два значения: 0 или 1. ПФ называют также логическими или булевыми функциями. Будем обозначать ПФ в виде f(х₁,x₂,х₃,...). указывая в скобках аргументы, либо в виде y₁,y₂,y₃,... . ПФ в свою очередь могут служить аргументами еще более сложных логических функций. Следовательно, можно построить ПФ любой заранее заданной сложности, пользуясь ограниченным числом логических связей.

ПФ принято задавать таблицами истинности, в которых для всех наборов переменных указываются соответствующие им значения ПФ. Формирование значений ПФ в таблице истинности выполняется в соответствии с логикой работы устройства (сумматора, сдвигателя, преобразователя кодов и т. д.).

Набор переменных — это совокупность значений двоичных переменных, каждая из которых может быть равна 0 или 1. Если число аргументов (независимых переменных) ПФ равно n (т. е. х₁,x₂,х₃,...x_n), то существует 2 различных сочетаний этих переменных, т. е. наборов.

Табл. 3.1 представляет собой таблицу истинности для некоторых ПФ f₁ и f₂, зависящих от двоичных переменных х₁,x₂,х₃. Так как n = 3 (три переменных), табл. 3.1 содержит 8 строк, соответствующих 2³ = 8 наборам переменных х₁,x₂,х₃. Для каждого набора в табл. 3.1 записаны значения ПФ f₁ и f₂, равные 0 или 1. По таблице истинности записывается аналитическое выражение для ПФ (рассматривается в следующих параграфах).

Элементарные логические операции над двоичными переменными реализуются схемами, называемыми логическими элементами. Число входов логического элемента соответствует числу аргументов воспроизводимой им булевой функции.

Элементарные логические операции над двоичными переменными реализуются элементарными электронными схемами, которые называются электронными логическими элементами или просто логическими элементами. Число входов логического элемента соответствует числу аргументов воспроизводимой им булевой функции. 

Элементарные логические операции над двоичными переменными реализуются электронными схемами, которые называются электронными логическими элементами или просто логическими элементами. Число входов ЛЭ соответствует числу аргументов воспроизводимой им булевой функции

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

38 Элементарная дизьюнкция и её ранг. Конъюктивные формы представленияпереключательных функций (КНФ и СКНФ). Запись СКНФ по таблицам истинности.

Дизъюнктивной нормальной формой(ДНФ) булевой функции f(x₁, …, x_n) назовем дизъюнкцию различных элементарных конъюнкций, задающую функцию f(x₁, …, x_n).

Длиной ДНФ назовем число ее конъюнкций, а рангом ДНФ – сумму рангов конъюнкций.

39 Базовые элементы ЭВМ, МИС, СИС, БИС. Типы сигналов в ЭВМ. Потенциальные, импульсные, динамические и логические элементы. Элементы памяти. Специальные элементы ЭВМ.

Схемотехника — научно-техническое направление, занимающееся проблемами анализа и синтеза отдельных приборов радиотехники, связи, автоматики, вычислительной техники с целью обеспечения оптимального выполнения ими заданных функций и расчета параметров входящих в них элементов.

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

Основу элементной базы ЭВМ составляют цифровые интегральные схемы (ИС). Их сложность характеризуется степенью функциональной интеграции К_и (К_и= lg N_эл гдеN_эл —число элементов И — НЕ либо ИЛИ — НЕ, расположенных на кристалле ИС).

В зависимости от сложности интегральные схемы подразделяются на следующие типы:

МИС — малые интегральные схемы, содержащие один или несколько логических элементов (К_и ≈1);

СИС — средние интегральные схемы, содержащие один или несколько функциональных узлов (сумматоров, счетчиков и др.) и имеющие обычно К_и = 1...2;

БИС — большие интегральные схемы, содержащие одно или несколько функциональных устройств (арифметическое устройство, арифметико-логическое устройство АЛУ, устройство управления УУ, запоминающее устройство ЗУ) и имеющие К_и = 2 - 4;

СБИС — сверхбольшие БИС, выполняющие функции целых цифровых систем (например, микроЭВМ) и имеющие К_и > 4.

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

Элемент памяти - триггер. Транзисторы и логические схемы на их основе сами по себе элементами памяти быть не могут, так как после прекращения действия входного импульса сразу возвращаются в исходное состояние.

Для элемента памяти нужно устройство, которое под действием входного сигнала могло бы переключаться из состояния 0 в состояние 1 и обратно и при этом после прекращения действия входного импульса запомнило бы свое состояние и могло находиться в нем неопределенно долго (до прихода следующего переключающего входного сигнала). Такие электронные схемы, имеющие два равнозначных варианта устойчивых значений, называют бистабильными ячейками или триггерами.

Так как входной сигнал кратковременный, а устойчивое состояние триггера сохраняется как угодно долго (при условии, что не происходит отключения питания схемы), то триггер тем самым выполняет логическую функцию запоминания.

Запоминающие элементы на ТТЛ-схемах (транзисторно-транзисторная логика на биполярных транзисторах) хорошо приспособлена к технологии больших интегральных схем (БИС). Их преимущество - высокая степень интеграции. ТТЛ-элементы могут быть совмещены с элементами, построенными на транзисторных переключателях тока.

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

40 Закон булевой алгебры.

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

Для сравнения, элементарная алгебра занимается арифметическими выражениями и операциями.

Булева алгебра получила свое название в честь своего создателя Джорджа Буля (1854 г.), являющегося одним из предтеч математической логики.

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

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

1. закон двойного отрицания: not not x = x

2. закон коммутативности (от перестановки аргументов результат не меняется): x₁ or x₂ = x₂ or x₁ x₁ and x₂ = x₂ and x₁

3. закон ассоциативности (порядка вычислений): x₁ or (x₂ or x₃) = (x₁ or x₂) or x₃ x₁ and (x₂ and x₃) = (x₁ and x₂) and x₃

4. закон дистрибутивности (раскрытия скобок): x₁ or (x₂ and x₃) = (x₁ or x₂) and (x₁ or x₃) x₁ and (x₂ or x₃) = (x₁ and x₂) or (x₁ and x₃)

5. правила де Моргана: not (x₁ or x₂) = not x₁ and not x₂ not (x₁ and x₂) = not x₁ or not x₂

6. правила операций с константами 0 и 1: not 0 = 1, not 1 = 0, x or 0 = x, x or 1 = 1, x and 1 = x, x and 0 = 0

7. правила операций с переменной и её инверсией: x or not x = 1 x and not x = 0

Справедливость основных законов (тождеств) булевой алгебры может быть доказана перебором всех значений переменных, входящих в соотношения. Из основных законов можно легко получить следующие важные соотношения:

1. закон поглощения: x₁ or (x₁ and x₂) = x₁ x₁ and (x₁ or x₂) = x₁

2. закон идемпотентности (повторное применение не даёт ничего нового): x or x or ... or x = x x and x and ... and x = x

3. на основании закона дистрибутивности, а также 7-го и 6-го законов: x₁ or (not x₁ and x₂) = x₁ or x₂