Логические основы
Предназначен для людей с небольшим или отсутствующим воздействием цифровой логики, а также тех, кто хочет обновить или понять булеву алгебру на более глубоком уровне, эта статья просматривает самые основы булевой алгебры. Цель состоит в том, чтобы подготовить вас к последующим статьям, которые углубляются в аспекты булевой алгебры.
Рекомендуемый уровень
начинающий
Что такое логическая алгебра «цифровая логика» и «логическая логика», являются сингулярными, а «булевая алгебра» лишь немного отличается, что подразумевает более математически ориентированный подход к анализу или разработке цифровых систем
Булева алгебра (названная в честь Джорджа Була) включает в себя только два значения - FALSE и TRUE. Иногда мы используем разные имена в зависимости от того, что имеет смысл; общие имена: {F, T}, {LO, HI}, {L, H} или {0, 1}. Подобно нормальной алгебре, мы имеем булевы операторы, которые принимают один или два операнда и производят значение (булево значение). «Операнд» - это не что иное, как значение (или сигнал), а «оператор» - не что иное, как некоторая манипуляция значениями для получения результата. В обычной арифметике выражение «2 + 3» имеет два операнда («2» и «3») и один оператор («+»), которые дают результат «5».
Булева алгебра включает в себя три примитивных оператора: один унарный (принимает один операнд) и два двоичных (принимает два операнда) - унарный оператор является оператором логического отрицания (NOT), а бинарные операторы - логической дизъюнкцией (OR) и логической связью (А ТАКЖЕ). Это все, что нужно отслеживать: два возможных значения: FALSE и TRUE, которыми управляют три оператора, NOT, OR и AND.
Пришло время указать, что в разных областях используется другая терминология. В более математических областях мы говорим о логических операциях и логических функциях, а в более инженерно-ориентированных областях мы говорим о логических воротах. Но в каждом случае мы принимаем один или несколько входных сигналов (операндов) и используя логический логический элемент (логический оператор) для получения выходного сигнала (результата), который зависит только от текущих входных сигналов (для тех, кто уже знает о комбинаторной логике и последовательная логика, мы будем держать обсуждение сосредоточенным на комбинаторной логике - для тех, кто еще не знает об этих двух типах логики, забудьте прочесть этот в скобках комментарий). Для наших целей, поскольку AAC имеет очень инженерно-ориентированное направление, мы будем использовать терминологию, наиболее часто встречающуюся в технических областях. Однако, введя основные положения в следующем разделе, мы представим операторные обозначения, используемые как в инженерном, так и в математическом; это полезно, потому что большинство инженеров и техников будут время от времени дискутировать с людьми, которые используют нетехнические обозначения.
Таблицы правды
Поскольку булева алгебра настолько ограничена значениями, которые могут принимать сигналы, мы можем описать или даже определить функции, просто исчерпывая перечисление всех возможных комбинаций входных сигналов вместе со значением полученного результата. Этот список известен как таблица истинности. Примерная таблица
Пример таблицы истинности| В | Y | |
| F | F | T |
| F | T | F |
| T | F | F |
| T | T | T |
В этой таблице «A» и «B» находятся входные сигналы, а «Y» - выходной сигнал. Обычное соглашение состоит в том, что входы указаны в левых столбцах и выходы в правой колонке - промежуточные сигналы, если они есть, идут между входными и выходными столбцами. Поскольку мы будем обсуждать только ворота, которые имеют один выход и не имеют промежуточных сигналов, самый правый столбец - это выход, а все остальные столбцы - входы. Эта примерная таблица достаточна для определения конкретного логического затвора; если бы мы описывали эти ворота словами, мы могли бы сказать что-то вроде: «Выход TRUE тогда и только тогда, когда оба входа одинаковы». Затем мы можем дать этим воротам имя «Equality Gate» с символом «EQ» и написать выражения, такие как
$$ Y = A \ text {EQ} B $$
и скажем, что Y TRUE тогда и только тогда, когда A равно B.
Для простых ворот (и даже умеренно сложных логических функций) таблицы истинности являются предпочтительным способом описания и определения их, потому что они недвусмысленны. Например, что, если мы просто сказали, что нам нужны ворота, выход которых был TRUE, если два входа были равны? Это неоднозначно, потому что мы на самом деле не сказали, какой результат должен быть, когда они не равны. Если мы говорим, что мы хотим, чтобы ворота, выход которых был ИСТИНА, только когда выходы равны, мы на самом деле не сказали, что должно быть результатом, когда ARE равны, мы исключили только то, что они могут быть равны, когда они не равны. Мы могли бы, конечно, утверждать, что в обоих случаях «это очевидно» - и в этих простых случаях это был бы очень сильный аргумент. Но в целом это может быть не очевидно, и мы в конечном итоге полагаемся на человека, читающего описание, происходящего, чтобы интерпретировать его так же, как мы это делали, когда мы его написали - это рецепт неправильной коммуникации и возможной катастрофы. Используя таблицу истинности, нет абсолютно никакой возможности для неправильной интерпретации (при условии, что мы используем «правильную» таблицу истинности, а это означает, что включены все возможные комбинации ввода).
Таблица истинности выше имеет ровно одну строку для каждой возможной комбинации входов и поэтому известна как «явная» или «полностью перечислимая» таблица истинности. Но количество строк, необходимых для такой таблицы, растет экспоненциально с количеством входов. Например, для устройства с шестью входами потребуется шестьдесят четыре строки. Мало того, что это займет много места, но это делает таблицу истинности намного сложнее понять для большинства людей. Поэтому мы разрабатываем ярлыки, чтобы мы могли описать несколько строк из явной таблицы в одной строке так называемой «сжатой» таблицы истинности. Существует несколько конвенций, которые используются, но здесь мы будем использовать только один: «не волнует». Рассмотрим следующую таблицу:
Конденсированная таблица истины| В | Y | |
| 0 | Икс | 0 |
| Икс | 0 | 0 |
| 1 | 1 | 1 |
«Х» в данной ячейке означает, что эта строка применяется для ЛЮБЫХ значений этого ввода. Поэтому в первой строке приведенной выше таблицы указано, что если A равно 0, то вывод равен 0 независимо от того, какое значение B может иметь. Точно так же он говорит, что если B равно 0, то вывод равен 0 независимо от того, какое значение A может иметь. Одна потенциальная проблема с уплотненной таблицей заключается в том, что несколько рядов применяются к одному и тому же набору входных значений. Например, какая строка определяет поведение, когда оба A и B равны 0? Поскольку применяются как первая, так и вторая строки, таблица «переопределена». Однако, если все строки, которые относятся к данному набору входов, дают один и тот же результат, таблица является последовательной и все еще действительной. Если они несовместимы, то таблица просто не является действительной таблицей истинности. Обратите внимание, что полностью перечисленная таблица истинности никогда не может быть недействительной - она может быть «неправильной», что означает, что она не представляет собой логическую функцию, которую мы хотели, но она всегда будет представлять собой действительную логическую функцию.
Три основных булевых оператора
Каждый из трех основных булевых операторов NOT, OR и AND имеет условный символ, который используется для них (на самом деле существует более одного, но те, которые мы показываем здесь, являются наиболее распространенными) и таблицу истинности, которая определяет их; в этом разделе мы предоставим их, а также более общие обозначения, используемые для выражения их в инженерных, программных и математических / логических контекстах. Следует иметь в виду, что синтаксис, используемый конкретным языком программирования, задается этим языком и может быть совершенно иным, чем то, что показано здесь, что является доминирующей нотацией на языках C. Кроме того, языки программирования имеют дело с переменными, которые могут принимать не только два значения, поэтому многие из них имеют несколько операторов, которые имеют дело с этой ситуацией по-разному. Поскольку это далеко выходит за рамки этой процедуры, мы не будем различать эти различные методы, поэтому просто помните, что, хотя заданные операторы программирования представляют одну и ту же логическую операцию, они НЕ эквивалентны в деталях того, как эта операция применяется.
НЕТ-ворота (логическое отрицание)
| Y | |
| F | T |
| T | F |
Общие способы выражения NOT
| инженерия | $$ Y; знак равно \ overline {A}; знак равно A '; знак равно NOT (A); знак равно НЕ; A; знак равно -A $$ |
| программирование | $$ Y; знак равно ! A; знак равно \ tilde {} A $$ |
| Математика и формальная логика | $$ Y; знак равно \ lnot A $$ |
Также известный как логическое отрицание, этот унарный оператор просто производит противоположное значение операнда. На общем английском языке мы можем сказать: «Y истинно, если A НЕ является истинным».
Обратите внимание, что, особенно в инженерных контекстах, мы можем указать логическое отрицание несколькими способами. В технике три наиболее распространенных способа - это перебор, с апострофом после операнда (известный как «постфиксный оператор») или с синтаксисом типа функции. С функционально подобным синтаксисом имя может быть NOT (), INV () или NEG () для «не», «обратное» или «отрицание» соответственно. Вы также можете увидеть отрицательный знак, используемый перед операндом (известный как «префиксный оператор»), но это становится все более необычным. Перебор можно легко написать вручную, но его трудно ввести в текстовый документ или компьютерную программу, поэтому широко используется апостип постфикса.
Ворота OR (логическая дизъюнкция)
| В | Y | |
| F | F | F |
| F | T | T |
| T | F | T |
| T | T | T |
Обычный способ выражения ИЛИ
| инженерия | $$ Y; знак равно A + B; знак равно OR (A, B); знак равно A; ИЛИ; B $$ |
| программирование | $$ Y; знак равно A; |; B; знак равно A; ||; B $$ |
| Математика и формальная логика | $$ Y; знак равно A \ lor B $$ |
Также известный как логическая дизъюнкция, этот двоичный оператор создает TRUE-выход, если любой из его операндов имеет значение TRUE или, иначе говоря, он выдает FALSE-вывод тогда и только тогда, когда оба его операнда FALSE. В общем английском мы могли бы сказать: «Y истинно, если A истинно ИЛИ B истинно».
Когда мы говорим о сигналах, которые OR'ed вместе, мы часто говорим о том, что результатом является «сумма» этих сигналов. Это связано с использованием символа «+» для оператора OR, и эта терминология широко и формально принимается. Однако, как правило, считается плохой формой сказать, что мы «добавляем» эти сигналы вместе, хотя вы будете слышать это время от времени.
Логические соединения (логический коннектор)
| В | Y | |
| F | F | F |
| F | T | F |
| T | F | F |
| T | T | T |
| инженерия | $$ Y; знак равно A \ cdot B; знак равно AB; знак равно (A) (B); знак равно И (A, B); знак равно A; А ТАКЖЕ; B $$ |
| программирование | $$ Y; знак равно A; \ &; B; знак равно A; \ & \ &; B $$ |
| Математика и формальная логика | $$ Y; знак равно A \ land B $$ |
Также известный как логический коннектор, этот двоичный оператор создает TRUE-вывод тогда и только тогда, когда BOTH его операндов TRUE или, иначе говоря, он выдает FALSE-вывод, если любой из его операндов FALSE. В общем английском мы могли бы сказать: «Y истинно, если A истинно, а B истинно».
Когда мы говорим о сигналах, которые были объединены, мы часто говорим о том, что результатом является «продукт» этих сигналов. Это связано с использованием различных обозначений для умножения, используемых для оператора И, и эта терминология широко и формально принимается. Однако, как правило, считается плохой формой сказать, что мы «умножаем» эти сигналы вместе, хотя вы будете слышать это время от времени.
Приоритет операторов и ассоциативность
Приоритет операторов (также известный как «порядок операций») - это просто правила, которые диктуют, какой оператор выполняется первым, когда у нас в противном случае был бы выбор выбора между двумя разными операторами (или, вернее, двумя операторами разного приоритета). С другой стороны, ассоциативность операторов - это просто правило, которое диктует, какой оператор выполняется первым, когда мы в противном случае имели бы выбор между двумя операторами, которые являются одинаковыми (или, вернее, двумя операторами с одинаковым приоритетом). Поскольку данное выражение, если оно оценивается в соответствии с правилами приоритета и ассоциативности, может не реализовать желаемую логическую функцию, мы можем переопределить эти правила с помощью круглых скобок (которые на самом деле являются просто другим оператором с наивысшим приоритетом).
Прежде чем обсуждать правила приоритетности и ассоциативности булевой алгебры, рассмотрим их для нормальной алгебры и арифметики, с которыми нам удобно. В отсутствие круглых скобок мы знаем, что умножение и деление имеют приоритет над сложениями и вычитаниями; говорят, что умножение и деление имеют «более высокий приоритет» или «более высокий порядок», чем сложение или вычитание. Мы также знаем, что если мы имеем несколько операторов умножения и / или деления, мы выполняем их слева направо и одинаково для операторов сложения и / или вычитания. Это называется «левая ассоциативность».
Давайте рассмотрим, как эти правила применяются к следующему выражению.
$$ A + B * C / D - E + F * G / H * I - J * K + L $$
Так как умножение и деление являются операторами с наивысшим приоритетом, мы сначала разделяем это выражение на группы, которые содержат только эти два оператора. Для этой цели мы будем использовать квадратные скобки (мы удалим их позже).
$$ A + (B * C / D) - E + (F * G / H * I) - (J * K) + L $$
Внутри каждой группы мы имеем «факторы», которые являются операндами для оператора умножения или деления. Мы оцениваем эти операторы в соответствии с ассоциативностью, которая для умножения и деления является слева направо (левая ассоциативная).
$$ A + (((B * C) / D)) - E + ((((F * G) / H) * I)) - ((J * K)) + L $$
На этом этапе мы имеем «термины», которые являются всеми операндами для оператора сложения или вычитания. На данный момент мы могли бы удалить квадратные скобки, но они полезны в визуально идентифицирующих терминах, которые состоят из нескольких факторов. Теперь мы отказываемся от операторов сложения и вычитания в соответствии с их ассоциативностью, которая также остается ассоциативной. Мы продолжим и удалим квадратные скобки в это время.
$$ (((((A + ((B * C) / D)) - E) + (((F * G) / H) * I)) - (J * K)) + L) $$
Это называется выражением «полностью скобки», значение которого заключается в том, что оно не зависит от правил приоритета и ассоциативности. Причина проста, эти правила диктуют, какой оператор оценивать, когда у нас есть выбор, но полное выражение в скобках не дает нам такого выбора.
Сместив наше внимание на булеву альгабра, мы обнаруживаем, что нет правил приоритета и ассоциативности, которые являются универсальными. Это особенно актуально, когда мы начинаем добавлять больше операторов (которые представляют собой не что иное, как короткие сокращения для определенных комбинаций трех основных). Языки программирования, по своей природе, должны иметь четко определенные правила приоритета и ассоциативности, но они могут значительно варьироваться от одного языка к другому. По этой причине лучше писать булевы выражения с либеральной дозой круглых скобок.
Сказав это, большинство языков программирования сходится на довольно последовательном соглашении, которое само по себе является достаточно естественным, хотя и довольно произвольным, результатом использования операторской нотации. В обычной арифметике унарный знак минуса («отрицательный знак») имеет более высокий приоритет, чем умножение или сложение. Поскольку мы используем символ умножения для AND и символ добавления для OR, это приводит к булевскому приоритету {NOT, AND, OR} (в порядке от наивысшего до самого низкого). Как и в случае с большинством бинарных операторов, И и ИЛИ оба являются левыми ассоциативными. Ассоциативность НЕ зависит от используемой нотации. Если используется префиксный оператор, например «~», «!», «$$ \ lnot $$» или даже не-функциональный «NOT», тогда оператор является правильным ассоциативным, но если используется постфиксный оператор, такой как конечный апостроф, оператор остается ассоциативным. Это имеет смысл только с несколькими примерами.
Левый ассоциативный NOT:
$$ \ text {NOT NOT} A = \ text {NOT (NOT} A) $$
$$ \ sim \ sim A = \ sim ( sim A) $$
Если бы они были ассоциативными, мы бы НЕ НЕ были такими же, как (НЕ НЕ) A, что бессмысленно, так как оператор, работающий на операторе, не определен (хотя да, мы могли бы определить его, если бы захотели).
Правый ассоциативный NOT:
$$ A '' = (A ')' $$
Подобно префиксному оператору, если бы этот постфиксный оператор не оставался ассоциативным, мы имели бы A '' = A (''), который не был бы определен.
Итак, рассмотрим следующий пример, полностью скопировав его.
$$ Y = A \ text {AND NOT} B \ text {OR NOT} A \ text {AND} B = AB '+ A' B $$
Мы начинаем с оператора с наивысшей точностью, НЕ, и получаем
$$ Y = A \ text {AND} ( text {NOT} B) text {OR (NOT} A) text {AND} B = A (B ') + (A') B $$
Затем мы переходим к следующему наивысшему, И, и получаем
$$ Y = (A \ text {AND (NOT} B)) text {OR ((NOT} A) text {AND} B) = (A (B ')) + ((A') B) $ $
И, наконец, у нас есть только один оставшийся оператор, который мы в скобках поставим только для полноты, чтобы получить
$$ Y = ((A \ text {AND (NOT} B)) text {OR ((NOT} A) text {AND} B)) = ((A B ')) + ((A') B)) $$
Одна из распространенных ошибок, которые делают люди, не признает, что, используя эти очень общие правила приоритета, это
$$ AB '; \ neq; (AB) '$$
Хотя это было бы правдой, если бы все три оператора считались одинаковыми, и они оставались ассоциативными, что было бы необычным, но не неслыханным. Вместо
$$ AB '; знак равно (A) (B ') $$
Вывод
Это была довольно легкая статья, которая, надеюсь, подготовила вас к ряду статей, которые будут изучать многие аспекты цифровой логики и булевой алгебры на гораздо более глубоком уровне - фактически на уровне, глубже, чем большинство курсов. Это полезно, потому что для того, чтобы по-настоящему осмыслить дизайн цифровой логики, необходимо быть полностью осведомленным о концепциях и тонкостях, на которых он основан, а также знать об общих заблуждениях и ошибках, которые часто ловят менее хорошо подготовленных дизайнеров.
Предстоящие статьи
- Булевы выражения и логическая схема
- Оценка логической логики через таблицы истинности
- Булевские тождества
- Логическая двойственность
- Логика пузырей
- Шестнадцать логических ворот с двумя входами - включая импликацию и торможение
- Универсальные логические ворота - больше, чем просто NAND и NOR
- Канонические формы - SOP и POS
- Внедрение CMOS стандартных логических ворот
Следующая статья в серии: Булевы тождества