История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
Топ:
Эволюция кровеносной системы позвоночных животных: Биологическая эволюция – необратимый процесс исторического развития живой природы...
Процедура выполнения команд. Рабочий цикл процессора: Функционирование процессора в основном состоит из повторяющихся рабочих циклов, каждый из которых соответствует...
Интересное:
Уполаживание и террасирование склонов: Если глубина оврага более 5 м необходимо устройство берм. Варианты использования оврагов для градостроительных целей...
Что нужно делать при лейкемии: Прежде всего, необходимо выяснить, не страдаете ли вы каким-либо душевным недугом...
Мероприятия для защиты от морозного пучения грунтов: Инженерная защита от морозного (криогенного) пучения грунтов необходима для легких малоэтажных зданий и других сооружений...
Дисциплины:
2017-12-12 | 518 |
5.00
из
|
Заказать работу |
|
|
Введем в рассмотрение характеристическую функцию единицы F a (X n-1,…X i,…X 1,X 0), которая равна 1 на наборе значений переменных (X n-1,…X i,…X 1,X 0), обозначенном a, и равна 0 на всех остальных наборах.
Наборы значений переменных удобно задавать по номерам, которые получаются при рассмотрении набора как двоичного числа.
Пример.
F 2 (X,Y,Z,W) – характеристическая функция единицы для набора значений переменных (X,Y,Z,W) с номером 2. (0010 = 2).
В таблице представлены функции F 3 и F 5 , которые принимают значение 1 на наборах №3 и 5, соответственно (отсчет начинается с набора №0).
X | Y | Z | F3 | F5 |
Теорема 1.
Любая бф не равная константе 0 может быть представлена в виде
(X n-1,…X i,…X 1,X 0) = F a1 F a2 … F ai = F a i, при условии, что a iÎ M 1*, где M 1* - множество всех номеров, на которых F(X n-1,… X i,… X 1, X 0) равна 1.
Доказательство:
Возьмем произвольный набор с номером a.
Пусть на этом наборе F(X n-1,…X 1, X 0) = 1.
Тогда в правой части равенства найдется F a (X n-1, …X i,…X 1,X 0) и правая часть будет иметь вид 1 F, тоесть значения левой и правой части совпадают.
Если на наборе с номером a мы имеем F(X n-1, …X i,…X 1,X 0) = 0, то справа не будет F a , и правая часть будет иметь вид 0 0 … 0, то есть будет равна 0.
Таким образом, значения левой и правой части всегда совпадают.
Следствие.
Любая бф не равная константе 0 может быть представлена в виде
F(X n-1,…X i,…X 1,X 0) = F a i, где - знак операции «сумма по модулю два».
X | Y | Результаты операций «дизъюнкции» и «суммы по модулю два» совпадают, если X и Y одновременно не равны 1. | ||
|
F a1 F a2 ... F ai = F a1 F a2 ... F ai , так как среди характеристических функций единицы F ai только одна принимает значение 1, а остальные равны нулю.
Замечание: Операция «сумма по модулю два» не является операцией алгебры Буля, но часто используется в булевых алгебрах с расширенным набором операций.
Рассмотрим процедуру получения характеристических функций единицы.
Если рассматривать b как степень булевой переменной X, то
Т. е. X b = 1 только в том случае, если значение Х равно значению b.
Докажем это с помощью таблицы истинности.
Х | b | Xb |
Отсюда следует, что конъюнкция степеней булевых переменных X n-1,…X i,…X 1, X 0 равна 1, если для всех Х значения степеней равны значениям переменных. Поэтому конъюнкция переменных X n-1, … X 1, X 0 со степенями, соответственно, a n-1,...a 1,a 0 является характеристической функцией единицы для набора значений переменных a n-1,...a 1, a 0.
Рассмотрим примеры характеристических функций.
Характеристическая функция единицы для набора №3 функции от трех переменных
F 3 (X,Y,Z) = F 011 (X,Y,Z) = X 0 &Y 1 &Z 1 =
Характеристическая функция единицы для набора №10 функции от четырех переменных
F 10 (X,Y,Z,W) = F 1010 (X,Y,Z,W) = X 1 Y 0 Z 1 W 0=
Зная как построить характеристические функции единицы, можно на основании теоремы 1 сформулировать правило получения аналитической записи любой бф не равной константе 0:
|
|
Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...
Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначенные для поддерживания проводов на необходимой высоте над землей, водой...
Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!