Булева алгебра и построение логических схем. Логические и битовые операции: AND, OR, NOT, XOR — таблицы значений
Математическая логика изучает методы и средства оперирования логическими формулами (выражениями). В этом уроке мы изучим обозначения, синтаксис (грамматику) и семантику (значение) различных логических выражений.
Высказывание и операции над высказыванием
Исходным (базовым) понятием является простое высказывание.
Под высказыванием обычно понимают всякое предположение, утверждающее что-либо о чем-либо. Если смысл, содержащийся в высказывании, соответствует действительности, то высказывание является истинным, иначе ложным.
Обычно элементарные высказывания обозначают строчными буквами латинского алфавита $a$, $b$, $c$, $x$, $y$ …, которые являются логическими переменными в логических формулах. Истинные значения обозначаются буквой И (True, T) или 1, а ложные – Л (False, F) или 0.
Унарные функции
$n = 1$ — количество аргументов. $k_n = 2^n = 2$ $k_ф = 2$
Бинарные функции
$n = 2$ — количество аргументов. $k_n = 2^2 = 4$ $k_ф = 2^4 = 16$
| $x$ | $y$ | $f_0$ | $f_1$ | $f_2$ | $f_3$ | $f_4$ | $f_5$ | $f_6$ | $f_7$ | $f_8$ | $f_9$ | $f_<10>$ | $f_<11>$ | $f_<12>$ | $f_<13>$ | $f_<14>$ | $f_<15>$ |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| const «0» | $x \land y$ | пер. $x$ | пер. $y$ | $x \xor y$ | $x \lor y$ | const «1» |
Номер функции совпадает с двоичной записью функции
- $f_1$ — коньюнкция. $x \& y$ — $x$ и $y$ — $
and $ $x \&\& y$ - $f_7$ — дизъюнкция. $x | y$ — $x$ или $y$
- $f_<11>$ и $f_<13>$ — импликация (следование)
- $f_9$ — равнозначность, эквивалентность, равносильность. $
\equiv $ - $f_6$ — равнозначность, эквивалентность, равносильность. $
\equiv $
Из элементарных высказываний можно составить более сложные с помощью логических связок:
- $\lnot$ — логическое "не" (отрицание)
- $\land$ — логическое "и" (конъюнкция) — «и одновременно»
- $\lor$ — логическое "или" (дизъюнкция)
- $\Rightarrow$ — "логическое следствие" (импликация)
- $\equiv$ — "эквивалентность"
- круглых скобок (, ) — групировка операций.
- . есть и другие (менее распространённые) связки.
Логические связки можно определить с помощью таблицы истинности. В левой части этой таблицы перечисляются все возможные комбинации значений логических переменных $x$ и $y$. В правой части – соответствующие им им значения выражений из переменных и логических связок.
| $x$ | $y$ | $\lnot x$ | $x \land y$ | $x \lor y$ | $x \Rightarrow y$ | $x \equiv y$ |
| 0 | 0 | 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 | 1 |
Связки имеют следующий приоритет: $\lnot \land \lor \Rightarrow \equiv$ (приоритет можно изменить с помощью скобок). Высказывания (формулы) из простых высказываний, связок и скобок, называют правильно построенными формулами или просто формулами.
Значение логических связок близко к соответствующим высказываниям на естественном языке. Например смысл связок $\lnot$ и $\land$ практически совпадает со смыслом слов «не» и «и». Однако имеются и некоторые различия. Так формула $x \lor y$ несколько шире, чем русское «$x$ или $y$». Выражение «$x$ или $y$» по смыслу это формула $x \land \lnot y \lor \lnot x \land y$ (исключающее или). Еще больше различий между семантикой формулы $x \Rightarrow y$ в логике высказываний и выражению «из $x$ следует $y$». В русском языке это выражение истинно, если истинны $x$ и $y$, т.е. предложение русского языка по смыслу совпадает с формулой $x \land y$. Логическое следствие истинно также, если $x$ и $y$ ложны или $x$ ложна, а $y$ истинна. Логическую формулу $x \Rightarrow y$ следует интерпретировать на естественном языке так: «Если $x$ истинна, то $y$ тоже истинна, а остальное неизвестно».
Таблица истинности — таблица в которой в левой части перечислены все возможные значения переменных, а в правой части значения функции. Для построения таблицы истинности выписываются все возможные значения аргументов, а потом поэтапно вычисляем значения.
Для любой формулы также можно написать таблицу истинности. Например:
| $x$ | $y$ | $\lnot x$ | $\lnot y \lor y$ | $\lnot x \land (\lnot y \lor y)$ | $\lnot x \land (\lnot y \lor y) \Rightarrow \lnot x$ |
| 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 | 1 |
Если формула содержит $n$ переменных, то в таблице истинности будет $2^n$ строк (в примере формула содержит 2 переменные и $2^2 = 4$ строки). Кроме того, данная формула истинна на любом наборе значений своих переменных (везде 1). Такие формулы называются тождественно истинными или тавтологиями. В противоположной ситуации, формула является тождественно ложной или невыполнимой. Если две разные формулы принимают одинаковые значения на любом наборе значений переменных, то такие формулы называют равносильными. Равносильные формулы обозначаются знаком равенства =.
Законы алгебры логики
В логике высказываний известно много общезначимых формул, которые также называются законами логики высказываний. Основными законами являются следующие:
- законы идемпотентности (повторение действия над объектом не изменяет его, латинский idem — «тот же самый» и potens — «способный»):
- $x \land x = x$
- $x \lor x = x$
- $x \land (y \lor x) = x$
- $x \lor (y \land x) = x$
Доказать эти и последующие законы можно с помощью построения таблиц истинности или простейших логических рассуждений.
Следующая группа законов представляет взаимосвязь между логическими операциями:- $(x \equiv y) = (x \Rightarrow y) \land (y \Rightarrow x)$
- $x \Rightarrow y = \lnot x \lor y$
- законы Де Моргана
- $\lnot(y \lor x) = \lnot y \land \lnot x$
- $\lnot(y \land x) = \lnot y \lor \lnot x$
Замечательным следствием приведенных выше законов является следующий факт. Любую логическую формулу можно заменить равносильной ей, но содержащую только две логические операции:
- конъюнкцию "и" и отрицание "не"
- дизъюнкцию "или" и отрицание "не"
Дальнейшее исключение логических операций, очевидно, невозможно, то есть приведенные пары представляют минимальный базис для построения правильно построенных формул. Однако существует операция, с помощью которой можно представить любую логическую связку. Эта операция получила название «штрих Шеффера» и определяется следующим образом:
$x$ $y$ $x | y$ 0 0 1 0 1 0 1 0 0 1 1 0 На основании этого определения можно ввести следующие законы, выражающие взаимосвязь операции «штрих Шеффера» и других логических связок:
- $\lnot x = x | x$ — связка «не» через «штрих Шеффера»
- $x \land y = (x | y) | (x | y)$ — связка «и» через «штрих Шеффера»
Также следует отметить, что $x | y= \lnot (x \lor y)$.
К основным законам алгебры логики также относятся следующие:- коммутативные законы (от перестановки мест результат не меняется)
- $x \land y = y \land x$
- $х \lor y = y \lor x$
- $x \land (y \lor z) = (x \land y) \lor (x \land z)$
- $x \lor (y \land z) = (x \lor y) \land (x \lor z)$
- $x \land (y \land z) = (x \land y) \land z$
- $x \lor (y \lor z) = (х \lor y) \lor z$
С помощью законов логики можно осуществлять равносильные преобразования. Такие преобразования используются для доказательств, приведения формул к заданному виду, упрощения формул.
Под сложностью формул обычно понимается количество символов, используемых для ее записи. То есть формула $\alpha$ проще формулы $\beta$, если $\alpha$ содержит меньше букв и логических операций. Например, для формулы $(\lnot (x \lor y) \Rightarrow x \lor y) \land y$ можно записать следующую цепочку преобразований, приводящих ее к более простому виду:
$(\lnot \lnot(x \lor y) \lor x \lor y) \land y = (x \lor y \lor x \lor y) \land y = (x \lor y) \land y = y$.
Операция XOR
Операция XOR — это операция "побитное не равно" или сложение по модулю 2 для отдельных битов, в логике обозначается $x \oplus y$.
Задача "Повторные числа"
Входной файл содержит большое число чисел (целых или действительных) или строк, среди них все повторяются чётное число раз, и только одно — нечётное число раз. Вывести то, которое повторяется нечётное число раз.
Решение: завести переменную нужного типа, инициализировать её нулями, выполнять операцию XOR с каждым новым числом (строкой), в результате останется только число (строка), встречающаяся нечётное число раз.
Вычисление значения логического выражения
Для вычисления значения логического выражения мы можем просто поставить (replace) переменные как значения, потом прогнать все операции с наибольшим приоритетом (логическое НЕ, затем И), затем в операциях с меньшим приоритетом (ИЛИ).
Построение таблиц истинности
Логическая функция – функция, переменные которой принимают одно из двух значений: $1$ или $0$.
Любую логическую функцию можно задать с помощью таблицы истинности: набор всех возможных аргументов записывается в левой части таблицы, а соответствующие значения логической функции – в правой части.
Таблица истинности – таблица, которая показывает, какие значения примет составное выражение при всех возможных наборах значений простых выражений, входящих в него.
Равносильными называются логические выражения, последние столбцы таблиц истинности которых совпадают. Равносильность обозначается с помощью знака $«=»$.
При составлении таблицы истинности важно учитывать следующий порядок выполнения логических операций:
Приоритетом в выполнении порядка выполнения операций пользуются скобки.
Алгоритм построения таблицы истинности логической функции
Определяют количество строк: кол-во строк = $2^n + 1$ (для строки заголовка), $n$ – количество простых выражений. Например, для функций двух переменных существует $2^2 = 4$ комбинации наборов значений переменных, для функций трех переменных – $2^3 = 8$ и т.д.
Определяют количество столбцов: кол-во столбцов = кол-во переменных + кол-во логических операций. При определении количества логических операций учитывают также порядок их выполнения.
Заполняют столбцы результатами выполнения логических операций в определенной последовательности, учитывая таблицы истинности основных логических операций.
Совершенная нормальная форма — дизъюнктивная и конъюнктивная, правило построения
Нормальная форма логической формулы характеризуется тем, что для нее не свойственны эквивалентность, отрицание формул неэлементарного типа и знаки импликации.
Существует две формы нормального типа: КНФ (конъюнктивная нормальная форма) и ДНФ (дизъюнктивная нормальная форма).
СДНФ — совершенная дизъюнктивная нормальная форма формулы. СДНФ — способ написания функции алгебры логики в качестве логического выражения.
Осторожно! Если преподаватель обнаружит плагиат в работе, не избежать крупных проблем (вплоть до отчисления). Если нет возможности написать самому, закажите тут.
СДНФ формулы — это равнозначная ей формула, которая представляет собой дизъюнкцию элементарных конъюнкций, при которых функция достигает показателя «1».
ДНФ выглядит следующим образом:
СДНФ обладает некоторыми определенными свойствами:
- включает различные элементарные конъюнкции;
- все логические слагаемые формулы содержат все переменные, которые входят в функцию F;
- ни в одном логическом слагаемом не содержится переменная и её отрицание.
К СДНФ возможно привести любую формулу алгебры логики. Исключение составляет только тождественно ложная формула. СДНФ можно получить как используя таблицы истинности, так и через равносильные преобразования.
При построении таблицы истинности важно помнить, что логические переменные со значением «0» необходимо брать с отрицанием.
Что такое СКНФ
СКНФ — совершенная конъюнктивная нормальная форма. Формулу можно назвать таковой, когда она — конъюнкция неповторяющихся элементарных дизъюнкций.
Формула должна соответствовать нескольким условиям, чтобы называться СКНФ:
- в ней отсутствуют одинаковые элементарные дизъюнкции;
- дизъюнкции не содержат одинаковые переменные;
- все дизъюнкции содержат каждую переменную из входящих в конъюнктивную нормальную функцию такого типа.
Правила построения по таблице истинности
Дизъюнктивная форма
Если функция равна 1, то для всех наборов переменных, при которых это происходит, записывается произведение. Однако переменные, которые имеют значение 0, берутся с отрицанием.
Конъюнктивная форма
Когда функция равна 0, то для всех наборов переменных, при которых это происходит, записывается сумма. Однако переменные, которые имеют значение 1, берутся с отрицанием.
Алгоритм приведения к СДНФ и СКНФ
Рассмотрим логическую функцию в виде таблицы истинности.
Алгоритм построения СДНФ по таблице истинности выглядит следующим образом:
- Отметить наборы переменных, значение функции F на которых равно 1.
- Записать для всех отмеченных наборов конъюнкцию всех переменных так: если значение некоторой переменной в этом наборе равняется 1, в конъюнкцию включается сама переменная. В случае противного результата, в конъюнкцию включается ее отрицание.
- Связать полученные конъюнкции операциями дизъюнкции.
Построим совершенную ДНФ:
И как результат получим следующую СДНФ:
Алгоритм построения СКНФ по таблице истинности выглядит следующим образом:
- Отметить в таблице истинности наборы переменных, значение функции F на которых равно 0.
- Записать для всех отмеченных наборов дизъюнкцию всех переменных — в том случае, когда значение некоторой переменной в этом наборе равняется 0, в дизъюнкцию включается сама переменная, если происходит наоборот, то в дизъюнкцию включается ее отрицание.
- Связать полученные дизъюнкции операциями конъюнкции.
Построим совершенную КНФ:
И как результат получим следующую СКНФ:
Рассмотрев алгоритмы построения СДНФ и СКНФ ясно, что в случае подавляющей части наборов значений переменных функция равна 0, то значительно легче построить и СДНФ для получения ее формулы, а в обратном случае — СКНФ.
Доказательство эквивалентности
Эквивалентность — понятие, означающее, что две и более формул представляют одну и ту же функцию. Для обозначения эквивалентности могут использоваться следующие знаки: \( \equiv , = , \Leftrightarrow .\)
Доказать эквивалентность формул можно двумя способами.
- Первый заключается в построении и сравнении таблиц истинности обеих функций. В этом случае результат будет истинным только в том случае, когда оба высказывания либо ложны, либо истинны.
- Второй вариант — метод эквивалентных преобразований. Суть этого метода — построение цепи эквивалентных формул на основе ранее доказанных эквивалентностей.
Далее следуют примеры с некоторыми эквивалентными преобразованием в булевой алгебре и новыми эквивалентностями, которые возможно получить с их помощью.
Поглощение
Склеивание
Обобщенное склеивание
\(xz\;\vee\;y\overline z\;\vee\;xy\;=\;xz\;\vee y\overline z\)
\(xz\;\vee\;y\overline z\;\vee\;xy\;=\;xz\;\vee y\overline z\;\vee\;xyz\;\vee\;xy\overline z\;=\;xz\;\vee\;y\overline z\)
Расщепление
\(x\;\vee\;\overline xy\;=\;xy\;\vee\;x\overline y\;\vee\;\overline xy\;=\;xy\;\vee\;x\overline y\;\vee\;xy\;\vee\;\overline xy\;=\;x\;\cdot\;l\;\;\vee\;y\;\cdot\;l\;=\;x\;\vee\;y\)
Примеры с решением
Задача №1
Приведите к СКНФ \(((((A\rightarrow B)\rightarrow\overline A)\rightarrow\overline B)\rightarrow\overline C)\) .
Через применение закона де Моргана и правила \( x\;\rightarrow\;y\;=\;\overline x\;\vee\;y\) упростим выражения:
\(F\;=\;((((A\;\rightarrow\;B)\;\rightarrow\;\overline A)\;\rightarrow\overline B)\;\rightarrow\;\overline C)\;=\;(((\overline A\;\vee\;B)\;\rightarrow\;\overline A)\;\rightarrow\;\overline B)\;\rightarrow\overline C\;)\;=\)
\(=\;((((\overline A\;\vee\;B)\;\rightarrow\overline A)\;\rightarrow\overline B)\;\rightarrow\;\overline C)\;=\;((\overline<((\overline A\;\vee\;B)>\;\vee\;\overline A)\;\rightarrow\overline B)\;\rightarrow\overline C)\;=\)
\(=(((\overline A\;\vee\;B)\;\vee\;\overline A)\;\rightarrow\;\overline B)\;\rightarrow\;\overline C)\;=((\overline<(\overline<(\overline A\vee B)>\;\vee\;\overline A\;)>\;\vee\;\overline B)\;\rightarrow\;\overline C)\;=\)
\(=\;((\overline<(\overline A\;\vee\;B)>\;\vee\;\overline A)\;\wedge\;B)\;\vee\;\overline C\;=\;(((A\;\wedge\;\overline B)\;\vee\;\overline A)\;\wedge B)\;\vee\;\overline C\;=\)
\(=((A\overline B\;\vee\;\overline A)\;\vee\;\overline A)\;\wedge\;B)\;\vee\;\overline C\;=(((A\;\wedge\;\overline B)\;\vee\;\overline A)\;\wedge\;B)\;\vee\;\overline C\;=\)
\(=\;((A\overline B\;\vee\;\overline A)\;\wedge\;B)\;\vee\;\overline C\;=\;(A\overline BB\;\vee\;\overline AB)\;\vee\;\overline C\;=\;(0\;\vee\;\overline AB)\;\vee\;\overline C\;=\;\overline AB\;\vee\;\overline C\)
Далее приведем выражение к КНФ:
\(F\;=\;\overline AB\;\vee\;\overline C\;\;=\;(\overline A\;\vee\;\overline C)\;\wedge\;(B\;\vee\;\overline C)\)
Далее приведем выражение к СКНФ:
\(F\;=\;(\overline A\;\vee\;\overline C)\;\wedge\;(B\;\vee\;\overline C)\;=\;(\overline A\;\vee\:\overline C\;\vee\;B\overline B)\;\wedge\;(A\overline A\;\vee\;B\;v\;\overline C)\;=\)
\(=\;(\overline A\;\vee\;\overline C\;\vee\;B)\;\wedge\;(A\;\vee\;B\;\vee\;\overline C)\;\wedge\;(\overline A\;\vee\;\overline C\;\vee\;\overline B)\;\wedge\;(\overline A\;\vee\;B\;\;\overline C)\)
Задача №2
Используя эквивалентные преобразования, постройте ДНФ функции \(f(\widetilde x^n)\)
\(f(\widetilde x^3) = (\overline
x_2\;\oplus\;x_3)\;\cdot\;(x_1x_3\;\rightarrow\;x_2)\) \(f(\widetilde x^3) = (\overline
x_2\;\oplus\;x_3)\;\cdot\;(x_1x_3\;\rightarrow\;x_2) = ((\overline x_2\;\cdot\;\overline \;)\;\vee\;(\overline<\overline x_2>\;\cdot\;x_3))\;\cdot\;(\overline \;\vee\;x_2)\;=\) \(=(\overline
x_2\overline \;\cdot(x_1\vee x_3\vee x_2)\;\vee\;x_1x_3\;\cdot\;(\overline \;\vee\;\overline \;\vee\;x_2)\;\vee\;\overline x_3\;\cdot\;(\overline \;\vee\;\overline \;\vee\;x_2))\;=\) Логические схемы и таблицы истинности
Логические схемы создаются для реализации в цифровых устройствах булевых функций (функций алгебры логики).
В цифровой схемотехнике цифровой сигнал — это сигнал, который может принимать два значения, рассматриваемые как логическая «1» и логический «0».
Логические схемы могут содержать до 100 миллионов входов и такие гигантские схемы существуют. Представьте себе, что булева функция (уравнение) такой схемы была потеряна. Как восстановить её с наименьшими потерями времени и без ошибок? Наиболее продуктивный способ — разбить схему на ярусы. При таком способе записывается выходная функция каждого элемента в предыдущем ярусе и подставляется на соответствующий вход на следующем ярусе. Этот способ анализа логических схем со всеми нюансами мы сегодня и рассмотрим.
Логические схемы реализуются на логических элементах: «НЕ», «И», «ИЛИ», «И-НЕ», «ИЛИ-НЕ», «Исключающее ИЛИ» и «Эквивалентность». Первые три логических элемента позволяют реализовать любую, сколь угодно сложную логическую функцию в булевом базисе. Мы будем решать задачи на логические схемы, реализованные именно в булевом базисе.
Для обозначения логических элементов используется несколько стандартов. Наиболее распространёнными являются американский (ANSI), европейский (DIN), международный (IEC) и российский (ГОСТ). На рисунке ниже приведены обозначения логических элементов в этих стандартах (для увеличения можно нажать на рисунок левой кнопкой мыши).
На этом уроке будем решать задачи на логические схемы, на которых логические элементы обозначены в стандарте ГОСТ.
Задачи на логические схемы бывают двух видов: задача синтеза логических схемы и задачи анализа логических схем. Мы начнём с задачи второго типа, так как в таком порядке удаётся быстрее научиться читать логические схемы.
Чаще всего в связи с построением логических схем рассматриваются функции алгебры логики:
- трёх переменных (будут рассмотрены в задачах анализа и в одной задаче синтеза);
- четырёх переменных (в задачах синтеза, то есть в двух последних параграфах).
Рассмотрим построение (синтез) логических схем
- в булевом базисе «И», «ИЛИ», «НЕ» (в предпоследнем параграфе);
- в также распространённых базисах «И-НЕ» и «ИЛИ-НЕ» (в последнем параграфе).
Логические схемы строятся на основе логических выражений и функций. Бывает, что изначально составленная функция является излишне сложной, из-за чего её схемная или программная реализация оказывается избыточной. Способам и приёмам минимизации логических функций посвящены отдельные материалы сайта — минимизация логических функций: общие сведения, минимизация логических функций: метод непосредственных преобразований и минимизация логических функций: метод Квайна.
Задача анализа логических схем
Задача анализа заключается в определении функции f , реализуемой заданной логической схемой. При решении такой задачи удобно придерживаться следующей последовательности действий.
- Логическая схема разбивается на ярусы. Ярусам присваиваются последовательные номера.
- Выводы каждого логического элемента обозначаются названием искомой функции, снабжённым цифровым индексом, где первая цифра — номер яруса, а остальные цифры — порядковый номер элемента в ярусе.
- Для каждого элемента записывается аналитическое выражение, связывающее его выходную функцию с входными переменными. Выражение определяется логической функцией, реализуемой данным логическим элементом.
- Производится подстановка одних выходных функций через другие, пока не получится булева функция, выраженная через входные переменные.
Пример 1. Найдите булеву функцию логической схемы и составьте таблицу истинности для логической схемы.
Решение. Разбиваем логическую схему на ярусы, что уже показано на рисунке. Запишем все функции, начиная с 1-го яруса:
Теперь запишем все функции, подставляя входные переменные x, y, z :
В итоге получим функцию, которую реализует на выходе логическая схема:
Таблица истинности для данной логической схемы:
x y z f 1 1 1 0 1 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 1 0 0 Найти булеву функцию логической схемы самостоятельно, а затем посмотреть решение
Пример 2. Найдите булеву функцию логической схемы и составьте таблицу истинности для логической схемы.
Пример 3. Найдите булеву функцию логической схемы и составьте таблицу истинности для логической схемы.
Продолжаем искать булеву функцию логической схемы вместе
Пример 4. Найдите булеву функцию логической схемы и составьте таблицу истинности для логической схемы.
Решение. Разбиваем логическую схему на ярусы. Запишем все функции, начиная с 1-го яруса:
Теперь запишем все функции, подставляя входные переменные x, y, z :
В итоге получим функцию, которую реализует на выходе логическая схема:
Таблица истинности для данной логической схемы:
x y z f 1 1 1 0 1 1 1 1 0 0 1 1 1 0 1 1 0 1 1 0 0 0 0 0 0 1 1 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 0 0 0 1 1 Пример 5. Найдите булеву функцию логической схемы и составьте таблицу истинности для логической схемы.
Решение. Разбиваем логическую схему на ярусы. Структура данной логической схемы, в отличие от предыдущих примеров, имеет 5 ярусов, а не 4. Но одна входная переменная — самая нижняя — пробегает все ярусы и напрямую входит в логический элемент в первом ярусе. Запишем все функции, начиная с 1-го яруса:
Теперь запишем все функции, подставляя входные переменные x, y, z :
В итоге получим функцию, которую реализует на выходе логическая схема:
Таблица истинности для данной логической схемы:
x y z f 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 0 1 1 0 0 1 0 1 0 1 1 1 1 1 0 1 0 1 1 1 0 0 1 1 0 1 0 0 0 1 0 1 Задача синтеза логических схем в булевом базисе
Разработка логической схемы по её аналитическому описанию имеет название задачи синтеза логической схемы.
Каждой дизъюнкции (логической сумме) соответствует элемент «ИЛИ», число входов которого определяется количеством переменных в дизъюнкции. Каждой конъюнкции (логическому произведению) соответствует элемент «И», число входов которого определяется количеством переменных в конъюнкции. Каждому отрицанию (инверсии) соответствует элемент «НЕ».
Часто разработка логической схемы начинается с определения логической функции, которую должна реализовать логическая схемы. В этом случае дана только таблица истинности логической схемы. Мы разберём именно такой пример, то есть, решим задачу, полностью обратную рассмотренной выше задаче анализа логических схем.
Пример 6. Построить логическую схему, реализующую функцию с данной таблицей истинности:
x y f 1 1 0 1 0 0 0 1 1 0 0 0 Решение. Разбираем таблицу истинности для логической схемы. Определяем функцию, которая получится на выходе схемы и промежуточные функции, которые на входе принимают аргументы x и y . В первой строке результатом реализации выходной функции при том, что значения входных переменных равны единицам, должен быть логический «0», во второй строке — при разных значениях входных переменных на выходе тоже должен быть логический «0». Поэтому нужно, чтобы выходная функция была конъюнкцией (логическим произведением).
Теперь подбираем промежуточные функции. Получаем следующую таблицу для промежуточных функций и выходной функции — конъюнкции промежуточных функций:
0 0 0 0 1 0 1 1 1 0 1 0 Для построения логической схемы необходимо элементы, реализующие логические операции, указанные в выходной функции, располагать в порядке, заданной этой функцией. Из выражения видно, что понадобятся 3 схемы «НЕ», две двухвходовых схемы «И» и одна двухвходовая схема «ИЛИ». В соответствии с выходной функцией получаем следующую логическую схему:
А теперь очередь дошла до функций алгебры логики четырёх переменных. Сначала выполним синтез логической схемы в булевом базисе.
Пример 7. Построить в булевом базисе логическую схему, реализующую функцию алгебры логики
Решение. Для построения логической схемы потребуются 4 схемы «НЕ», одна трёхвходовая схема «И», 2 двухвходовые схемы «И» и одна трёхвходовая схема «ИЛИ». В соответствии с этим получаем следующую логическую схему:
Задача синтеза логических схем в базисах «И-НЕ» и «ИЛИ-НЕ»
Часто для сокращения числа микросхем используют элементы «И-НЕ» или/и «ИЛИ-НЕ». Рассмтрим примеры, как построить схему, реализующую ту же функцию, что в предыдущем примере, но, сначала в базисе «И-НЕ», а затем в базисе «ИЛИ-НЕ».
Пример 8. Построить в базисе «И-НЕ» логическую схему, реализующую функцию алгебры логики .
Решение. Логическая функция должна быть приведена к виду, содержащему только операции логического умножения (конъюнкции) и инвертирования (отрицания). Это делается при помощи двойного инвертирования исходного выражения функции и применения закона де Моргана:
Для построения логической схемы потребуются 8 схем «И-НЕ». Получаем следующую логическую схему:
Пример 9. Построить в базисе «ИЛИ-НЕ» логическую схему, реализующую функцию алгебры логики .