Герасимов В.Г. (ред). - Электрические измерения и основы электроники (1998) (529641), страница 46
Текст из файла (страница 46)
Рис.6.2 Таб шца истинности совок) и- ности булевых функций одной переменной х! ) г)) в) ж) Рис.6.3. Обозначения простейших логических элементов. а повторитель; б инвертор; в - элемент неравнозначности (сумматор по модулю 2);; элемент И; д — элемент И вЂ” НЕ (Шеффера), элемент ИЛИ; ж - элеменз ИЛИ НЕ (Пирса) 11ри п=2 получаем уже 16 различных булевых функций, таблица истинности которых приведена на рис.6.4. Среди булевых функций двух переменных встречаются уже знакомые нам функции генераторов О (РО(л Рхо)) и ! (Р);(л)х„)), а также повторения и инверсии переменных: Г;(л )л н) = л О, Еш(л Рх о) = 7О,' Гз(л !лп) =.х !, Г! э(х Рл0) = .х р Далее отметим пару взаимно инверсных функций Гь(л !.то)=Гч(хйлн) . Функция Рб(анхо) принимает значение 1, если входящие в нее переменные имеют различ ныезначения,и называется функцией н ер ав поз и ач н ост" (с у м м ы и о м о д у л ю 2).
Операция суммы по модулю 2 обозначае~ ся символом В и выполняется по следующим правилам: О 9 О = О О+ 1 = 1 О+ О =1;19 1 = О. что записывают в виде Р~(хнхв)=х0йл! . Рнс 6.4. Ьулевы функции двух переменных Заметим. что значения Рь(х~хо) совпадают с содержимым младшего разряда при суммировании двух одноразрядных двоичных чисел, поэтому соответствующий цифровой элемент (сумматор по модулю 2), обозначение которого дано на рис.6.3,в, часто используют при построении су мматоров двоичных чисел. Оставшиеся восемь попарно инверсных булевых функций обладают таким замечательным свойством, что они принимают значение 1 (либо 0) на одном единственном наборе переменных и равны О (соответственно 1) на всех остальных наборах. Среди этих функций отметим функции Е~(л рх О), инверсную ей г~4(л )хв)= г~(х~хв), а также гт(л ~лп) и инверсную ей функци|о Яхрлп)= Рт(х~хр).
Функцию Г~(х~хо), принимающую значение 1, если все входящие в нее переменные равны 1, называют к о н ъ ю н к и и е й (о и е р а ц и е й И). Поскольку значения Е (л~хо) совпадают с произведением ее аргументов,еетакженазывают логическим умножением и записывают с использованием знака операции умножения ( х ) либо символа пересечения ( л ): Г~(х ~хо)=лох х~ — — хвх~=х~улхр Обозначение э л е м е н та И, реализующего операцию конъюнкции, приведено н ар и с.6.3„. Элемент, реализующий функцию Г~4(л ~хо)=лл,хв, инверсную конъюнкции,называют элементом И вЂ” НЕ(элементом ШефФ е р а).
Его обозначение дано на рис. 6.3,д. Функцию Гт(л ~хо), принимающую значение (1, если все входящие в нее переменные равны О, называют д и з ъ ю н к ц и е й. Иными словами, дизъюнкция равна 1, если хотя бы одна из ее переменных равна 1. По этой причине функцию Ет(х ~ хо) часто также называют л о г и ч е с к и м ~ложен нем (операцией ИЛИ) изаписываютсиспользованием знака операции суммирования (+) либо символа объединения ( ): Р 7(х1хо)=хо+х~=хвн хр Обозначение элемента ИЛИ показано на рнс.6.3,е. Функцию Рх(х1хо), инверсную дизъюнкции, записывают в "нде Ря(л~хо)=го+ л.~ и называют о п е Р а ц и е й И Л И вЂ” Н Е Об бозначение реализующего эту операцию э л е м е н т а И Л И -- Н Е (элемент Пирса) дано на рис. 6.3„ж.
При помощи операций инверсии (НЕ), конъюнкции (И) и дизъюнкцив (ИЛИ) можно получить аналитическую запись произвольной булевой функции. Вначале покажем, что с помощью операций И, НЕ можно описать любую функцию, принимающую значение 1 на единственном наборе переменных, и равную 0 на всех остальных наборах.
Запишем, например выражение для функции Е4(х,х„) (см. рис.6,4), равную 1 на единственном наборе с номером 1 (х,=О, хо=1). Для этого рассмотрим произведение х, хо, в которое переменная х, входит с инверсией, так как в этом наборе х, =О, а переменная хо — без инверсии (так как в этом наборе х =1), По определению конъюнкции, функция равна 1; если оба сомножителя рав. ны 1, что соответствует набору с номером 1, откуда получаем запись ~4(~РО):1~:~О . Подобным образом с помощью операций ИЛИ, НЕ можно записать любую функцию, принимающую значение 0 на единственном наборе переменных и 1 — на всех остальных, например, Р'1з(х1хо) (см,рис.6.4), принимающую единственное значение О на наборе с номером 2 (х =1, х =0) .
Для этого свяжем операцией дизъюнкции переменную хо, так как в этом наборе х =О, и инверсию х, (так как в этом наборе х1 =1). Поскольку дизъюнкция равна О, если каждое из ее слагаемых равно О, приходим к выводу, что Р'1з(х~хо)=хо+х~, принимает единственное значение 0 именно на наборе с номером 2. Если данная функция равна 1 на нескольких наборах переменных, для каждого из этих наборов запишем соответствующую конъюнкцию, как это было показано выше, а затем все эти конъюнкции свяжем операцией дизъюнкции.
Поскольку дизъюнкция равна 1, если хотя бы одно из слагаемых равно 1, получаем аналитическую запись данной функции, равной 1 на всех перечисленных наборах. Аналогично, если функция равна 0 на нескольких наборах, то, записав для каждого нз них соответствуюшуьо дизъюнкцию, все эти дизъюнкцяя надо связать операцией конъюнкции. Конечно, нз этих двух вариантов записи одной и той же данной функции всегда предпочитают более ком палтт ю запись с меньшим количеством входящих в нее членов (конъюякций или дизъюнкций).
Задача 6.2. Составить аналитическую запись булевой функции тре" переменных Г(хз х1хо) в соответствии с таблицей истинности, приведе" ной на рис.6.1. Р е ш е н н е. В соответствии с формулой (6.2) эта булева функ'в' равна 1 на наборах 3,5.6 и 7. Двоичные коды этих наборов (х~хгтв) =011.101,110,111. Каждому из этих наборов сопоставим конъюнкцшс которой переменную берем без инверсии, если она входит в набор с сО значением 1.
или с инверсией. сели в данном наборе она равна О. Указав 254 ные конъюнкции объединяем операцией дизъюнкцни, что дает запись Р (Х2Х1ХО) Х2Х1ХО+ Х2Х1ХО Х2Х1ХО+ Х2Х1ХО' Задача 6.3*. Составить аналитическую запись булевых функций трех переменных р1(хгх1хо), Гг(хгх1хо), Гз(хгх1хо), Р4(хгх1хо), таблица истинности которых представлена на рис.6.1. Ответ: с1(хгх1хо) =хгх1хо+ хгх1хо+.хгх1хо, Рг(хгх1ХО) =Х2Х1ХО+ Хгх1ХО+ Хгх1хО + хгх1хо.
3( 2 1 О) 2 1 О 2 1 О 2~1~0> Г4(хгх1хо) =х2х1хО+ х2х1хо+ х2х1хо + х2х1хО 6.3. 'УПРОЩЕНИЯ БУЛЕВЫХ ФУНКЦИЙ Аналитические выражения булевых функций, применяя алгебраические преобразования, как правило, приводят к более простому виду. Для характеристики сложности выражения булевой функции вводят понятие ранга.
Рангом булевой функции (или ее отдельного члена) называют общее число входящих в ее выражение переменных (с инверсией или без нее). Смысл дальнейших алгебраических преобразований заключается в том, чтобы, используя соотношения булевой алгебры, получить выражение данной функции с минимальным количеством членов наименьшего ранга, так юк для его реализации потребуется не только меньшее количество, но и более простые цифровые элементы (с наименьппы числом входов). Большинство правил алгебраических преобразований булевых функций совпадают с правилами обычной алгебры, но вместе с ними имеют место следующие специфические свойства введенных ранее логических операции: 1) х = х 2) х х = 0 3) х +'х = 1 4) х х =- х 5) х+х = х б) х+ 1 = 1 7) ху = х + у 8) х + у = ху (6.3) Последнюю пару соотношений называют т е о р с м о й д в о й- ~ т в е.н н о с т и (д с М о р г а н а) и формулируют так: отрицание ~~нъюнкции (дизъюнкции) равно дизъюнкции (конъюнкции) отрицаний 'ходящих в нее членов, Пугем многократного применения зтой теоремы ~'нверсню сложных булевых выражений обычно опускают до уровня ниве ерсин отдельных переменных.
Задача 6.4. Получить аналитическое выражение булевой функции четырех переменных, принимающей значение 0 на наборах с номерами 2, 9, 15 и значение 1 — на остальных наборах. Ответ: Г (хзхгх1хо)= (хз+ хг+ х1+ хо)(хз+ хг+ х1+ хо)(хз+ хг+ х1+ хо). Как правило, для упрощения булевых выражений используют при. емы склеивания и поглощения. В с к л е и в а н и и, как минимум, участвует пара, так называемых, со с е д н и х ч л е н о в, представляющих собой члены одинакового ранга, содержащие общую часть Ги некоторую переменную х, которая в один иэ соседних членов входит с отрицанием, а в другой — без него. При объединении соседних членов операцией дизъюнкции или конъюнкции соответственно получаем Рк+Гл=Е(л+х) =Р' !=Р (Г+х)(Г+.л-)=Р+Гх+хГ+л'.л=Ц+л+л)+О=У; т.е.
в любом случае за счет исключения переменной л. ранг окончательного выражения уменьшается на единицу. В и о г л о щ е н и и участвуют члены различного ранга, причем член меньшего ранга должен обязательно входить в качестве составной части в член более старшего ранга. Объединение таких членов операцией дизъюнкции или конъюнкции дает Р+Гх=Ц1+.л) =К Г(Г+л) =Г+Р'л =Р, т.е. происходит своеобразное «поглощение» члена старшего ранга чле- ном Г меньшего ранга. Задача 6.5. Упростить выражение булевой функции Е(Л2 Л!Хо) ХОЛ ОЛ2+ ХОЛ $А2 ЛОХ!Л1+ ЛОХ!Л2 Р е ш е н и е.
Заметим, что в данном выражении последний член является соседним для трех остальных членов, поэтому его можно с ними склеить попарно. В соответствии со свойством номер 5 из (6.3) допишем еще два слагаемых вида хол ~ л2. Теперь для каждой полученной пары соседних слагаемых используем прием склеивания, окончательно получаем ~(-л2-л1-лО) л1-" 2 х0~2 -~0л!. Количество слагаемых этого выражения, а также их ранг на единицу меньше исходных значений.
Задача 6.6. Записать упрощенное выражение булевой функции трех переменных, принимающих значение 0 на наборах с номером 1, 4, 5 и значение 1 — на всех остальных наборах. ОшВе )и: Цх2л ~хО) =х~+ хОл 2. Задача 6.7." Упростить булевы функции трех переменных, выражения которых записаны в ответах задачи 6.3. 256 ОПЗВВР$: Р1(хтх1хо) =Х1ХО+ Х1х2 1'2(хгх1хо) =хохг+ х1хг+ хох1,' 3( 2 1 О) Ох1 Охг> 4( гх1 0) Ох2 1 2' Задача 6.8.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
