bulevy-funktsii-i-postr.-log.-skhem (1016573), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Описание этих функций дано в таблице 3.6.№1.Двоичный наборфункцииf0  x1, x2    0000 Формулаf0  x1, x2   0( x1 , x2 – фиктивные переменные)10Таблица 3.6.Название функцииКонстанта 02.f1  x1, x2    0001f1  x1, x2   x1  x2  x1  x2  x1 & x23.f 2  x1, x2    0010 f 2  x1, x2   x1  x2f3  x1, x2    0011f3  x1, x2   x1( x2 – фиктивная переменная)45.6.f 4  x1, x2    0100 f 4  x1, x2   x2  x1f5  x1, x2    0101f5  x1, x2   x2( x1 – фиктивная переменная)7.f6  x1, x2    0110 f6  x1, x2   x1  x28.f7  x1, x2    0111f7  x1, x2   x1  x2  x1  x29.f8  x1, x2   100010.f9  x1, x2   100111.f10  x1, x2   1010 f8  x1, x2   x1  x2  x1  x2Конъюнкция(функция «И»,логическоеумножение)Отрицание импликации «из x1следует x2 »Тождественнаяфункция x1Отрицание импликации «из x2следует x1 »Тождественнаяфункция x2Сумма по модулю 2 (неравнозначность)Дизъюнкция(функция«ИЛИ»,логическое сложение)Стрелка Пирса(логическаяфункция «ИЛИНЕ»)f9  x1, x2   x1  x2  Эквивалентность(равнозначность) x1 x2  x1  x2f10  x1, x2   x2  x2( x1 – фиктивная переменная)11Отрицание x2f11  x1, x2   1011f11  x1, x2   x2  x113.f12  x1, x2   1100 f12  x1, x2   x1  x1( x2 – фиктивная переменная)14.f13  x1, x2   1101f13  x1, x2   x1  x215.f14  x1, x2   1110 16.f15  x1, x2   111112.Импликация «изx2 следует x1 »Отрицание x1Импликация «изx1 следует x2 »Штрих Шеффераf14  x1, x2   x1  x2 (логическаяфункция «И x1 | x2НЕ»)f15  x1, x2   1Константа 1( x1 , x2 – фиктивные переменные)Далее будет показано, что операции дизъюнкция, конъюнкция, стрелка Пирса, штрих Шеффера, сумма по модулю 2 справедливы для произвольного числа переменных.

Поэтому для данных операций в таблице 3.7 показаны вентили с п входами.Таблица 3.7.НазваниевентиляОсновные типы логических вентилейУсловное графическое обоПример реализуемойзначениефункцииИЛИдизъюнкторY  X1  X 2Х1 0 0 1 1Х2 0 1 0 1Y 0 1 1 112ИконъюнкторY  X1  X 2Х1 0 0 1 1Х2 0 1 0 1Y 0 0 0 1ИЛИ-НЕY  X1  X 2  X1  X 2Х1 0 0 1 1Х2 0 1 0 1Y 1 0 0 0И-НЕY  X1 | X 2  X1  X 2Х1 0 0 1 1Х2 0 1 0 1Y 1 1 1 013Сумматорпо модулю2Y  X1  X 2Х1 0 0 1 1Х2 0 1 0 1Y 0 1 1 0Для краткости, в названии вентиля принято писать число,равное количеству входов в вентиль, например, «3ИЛИ» означает, что логический элемент «ИЛИ» имеет три входа.Число булевых функций, зависящих от n переменных, равноn22 . Используя этот факт, можно получить оценку числа функций от 10 переменных. Всего таких функций будет 1022  21024  21000  210100 1000100  10300 .Таким образом, при росте числа переменных число функцийвозрастает очень быстро и их табличное задание становится неудобным.4. Равенство функцийВ обычной алгебре справедливо равенство x  y  y  x , несмотря на то, что в левой части записана функция от двух переменных, а в правой - от одной.

Для функции от двух переменных x  y  y  переменная y является фиктивной, так как она невлияет на значения этой функции. Поэтому функции от разногочисла переменных ведут себя одинаково и их можно приравнять.Аналогичные ситуации встречаются и среди булевых функций. Например, тождественные функции f3  x1, x2   x1 из таблицы 3.6, где x2 – фиктивная переменная, и 1  x1   x1 из таблицы3.3 ведут себя одинаково. Возникает вопрос: можно ли их приравнять?14Чтобы ввести понятие равенства булевых функций дадимформальные определения существенных и фиктивных переменных.Определение 4.1.

Переменная xi 1  i  n  булевой функцииf  x1,...xi 1, xi , xi 1,..., xn  называется существенной, если можноуказатьдвоичныенаборы n  1,...,i 1,0,i 1,...,n и n  1,...,i 1,1,i 1,..., n  , отличающиеся лишь по одной i-й   компоненте, такие что f  n  f  n . В противном случае переменная xi называется фиктивной переменной функцииf  x1,...xi 1, xi , xi 1,..., xn  .Определение 4.2. Двоичные наборы n  1,...,i 1,0,i 1,...,n  и  n  1,...,i 1,1,i 1,..., n  ,отличающиеся только по одной i-й компоненте, называют соседними.Если xi является фиктивной переменной для функцииf  x1,..., xi 1, xi , xi 1,..., xn  , то её можно удалить из таблицы истинности данной функции. Для этого вычёркиваются все строки,соответствующие двоичным наборам вида  x1,..., xi 1,0, xi 1,..., xn  ,а затем столбец переменной xi .

В результате получается таблицаистинности для некоторой новой функцииg  x1,..., xi 1, xi 1,..., xn   f  x1,..., xi 1,1, xi 1,..., xn  .Будем говорить, что функция g  x1,..., xi 1, xi 1,..., xn  получена изфункции f  x1,..., xi 1, xi , xi 1,..., xn  путём удаления фиктивнойпеременной xi .Отметим, что при удалении фиктивной переменной xi таблица истинности для функции g  x1,..., xi 1, xi 1,..., xn  не изменится,есливместострок,соответствующихнаборам x1,..., xi 1,0, xi 1,..., xn  , вычеркнуть строки, соответствующиенаборам  x1,..., xi 1,1, xi 1,..., xn  .15Аналогично можно ввести и обратную операцию, получитьизфункциифункциюg  x1,..., xi 1, xi 1,..., xn f  x1,..., xi 1, xi , xi 1,..., xn  путём добавления фиктивной переменxi .нойВэтомслучаезначениефункцииf  x1,..., xi 1, xi , xi 1,..., xn  на любом наборе находится из равенств:f  x1,..., xi 1,0, xi 1,..., xn   g  x1,..., xi 1, xi 1,..., xn  ;f  x1,..., xi 1,1, xi 1,..., xn   g  x1,..., xi 1, xi 1,..., xn  .В дальнейшем не будем различать функции, получающиесядруг из друга добавлением или удалением фиктивных переменных.Определение 4.3.

Две функции алгебры логики называютсяравными, если одну из них можно получить из другой путём добавления или изъятия любого числа фиктивных переменных.Пример 4.1. Для данной функции f  x, y, z   1010 1010  :1) выяснить, какие её переменные являются существенными,а какие – фиктивными;2) выразить f  x, y, z  формулой, содержащей только существенные переменные.Решение.1. Запишем таблицу истинности функции f .х у z0000111100110011f  x, y, z 0101010110101010Количество строк и столбцов в таблице вычисляются поформулам:16количество строк = 2n + строка для заголовка,где n - количество переменных, т.е.

23  1  9 ;количество столбцов = количество переменных + столбецзначений функции,т.е. 3  1  4 .Так как в таблице истинности булевой функции наборы выписываются в порядке возрастания их номеров, то в дальнейшемстолбец с номерами наборов в таблицу включать не будем.2. Рассмотрим пары соседних наборов отличающихся по переменной x и значения функции на этих наборах:f  0,0,0   f 1,0,0   1; f  0,0,1  f 1,0,1  0 ;f  0,1,0   f 1,1,0   1; f  0,1,1  f 1,1,1  0 .Значит, x - фиктивная переменная.Рассмотрим пары соседних наборов отличающихся по переменной y . Так какf  0,0,0   f  0,1,0   1; f  0,0,1  f  0,1,1  0 ;f 1,0,0   f 1,1,0   1; f 1,0,1  f 1,1,1  0 ,то y - фиктивная переменная.Рассматривая пары соседних наборов отличающихся по переменной z , находим, что f  0,0,0   f  0,0,1 , поэтому z - существенная переменная.3.

Вычёркиваем из таблицы истинности для функцииf  x, y, z  строки, соответствующие двоичным наборам вида 0, y, z  и столбец переменной x :уz  y, z 001101011010Функция   y, z  получена из функции f  x, y, z  путём удаления фиктивной переменной x , поэтому f  x, y, z     y, z  .17Так как y - фиктивная переменная, то вычёркиваем из полученной таблицы для функции   y, z  строки, соответствующиедвоичным наборам вида  0, z  и столбец переменной y :zg  z0110Из таблицы для функции   y, z  получили таблицу функцииg  z  , формула которой g  z   z .Так как f  x, y, z     y, z   g  z  , то f  x, y, z   z .Пример 4.2.

Для функции g  x, y   x  y , которая существенно зависит от обеих переменных, построить функцию f  x, y, z  ,которая получается из g  x, y  введением фиктивной переменнойz.Решение. Таблица функции g  x, y  имеет вид:xy0 0 1 10 1 0 1g 0 0 0 1Таблица истинности функции f  x, y, z  получается из таблицы истинности функции g  x, y  следующим образом: на наборах x, y,0 определяем значения функции f  x, y, z  формулойf  x, y,0   g  x, y  , а на наборах  x, y,1 - формулойf  x, y,1  g  x, y  .

Строим таблицу истинности:xyzf0000001001000110181000101011011111Получили f  x, y, z    00000011 .4.1. Графическая интерпретация фиктивной переменной0 1у xf«»f«»б)f«»в)f«»г)&«»а)д)Рис. 4.1.1. Способы реализации функциина логическом элементе функциии вентиле «2И».Логическому элементу соответствует определённая функция,которая отображает зависимость выходного сигнала от входныхсигналов. Наличие фиктивной переменной означает, что существует вход логического элемента, на который подаются входныесигналы, не влияющие на формирование выходного сигнала.Например, логический элемент функции f  x, y, z  из примера 4.2содержит вход, соответствующий фиктивной переменной z . Кэтому входу можно подключать как сигналы соответствующиепеременным x или y (рис.4.1.1 а), б)), так и сигналы соответству19ющие константам 0 или 1 (рис.4.1.1 в), г)).

Таким образом, наличие у логических элементов входов, соответствующих фиктивным переменным, позволяет использовать логические элементы сбольшим количеством входов в качестве логических элементов сменьшим количеством входов.Для функций g  x, y  и f  x, y, z  из примера 4.2 на рис.

Характеристики

Список файлов учебной работы