67606

Разложение булевых функций по переменным

Лекция

Математика и математический анализ

Это представление называется разложением функции по m переменным x1xm. Разложение по одной переменной 1 Разложение по всем n переменным 2 При Опр. Это разложение называется совершенной дизъюнктивной нормальной формой представления функции fx1xn.

Русский

2014-09-12

174.5 KB

9 чел.

Лекция №15

Разложение булевых функций по переменным.

Возникают вопросы:

1) всякая ли функция может быть записана с помощью формулы?

2) как это сделать?

Совершенная дизъюнктивная нормальная форма.

Обозначим, где равен либо 0, либо 1. Тогда

.

Поскольку

,

то x=1   x=.

Теорема о разложении функции по переменным || Каждую функцию Булевой алгебры  при любом  можно представить в следующей форме:

,

где дизъюнкция берется по всем наборам значений переменных . ||

опр || Это представление называется разложением функции по m переменным x1,…xm.||

Доказательство.

  1.  Рассмотрим произвольный набор значений . Левая часть равенства имеет вид . Правая часть

(в сумме только одно произведение отлично от нуля: то в котором )

.

Теорема доказана.

Разложение по одной переменной

1)

Разложение по всем n переменным

2)

При

Опр. Это разложение называется совершенной дизъюнктивной нормальной формой представления функции f(x1,…,xn).

Теорема || Каждая функция алгебры логики может быть выражена в виде формулы, содержащей только отрицание, конъюнкцию и дизъюнкцию. ||

Доказательство ||

1) Если , то

2) Если  , то

Примеры

1)

x1

x2

f

0

0

1

0

1

1

1

0

0

1

1

1

(это СДНФ; теперь преобразуем)

2) Следующий пример. Дана таблица

x1

x2

x3

f

0

0

0

1

0

0

1

1

0

1

0

0

0

1

1

0

1

0

0

0

1

0

1

1

1

1

0

0

1

1

1

1

3) 

x1

x2

x3

x4

f

0

0

0

0

0

0

0

0

1

1

0

0

1

0

0

0

0

1

1

0

0

1

0

0

1

0

1

0

1

0

0

1

1

0

0

0

1

1

1

0

1

0

0

0

1

1

0

0

1

1

1

0

1

0

0

1

0

1

1

0

1

1

0

0

0

1

1

0

1

0

1

1

1

0

1

1

1

1

1

0

4) Аналитический способ

5)

Пусть . Согласно теореме двойственности

Это разложение называется совершенной конъюнктивной нормальной формой.

Примеры

1)

2)

x1

x2

f

0

0

0

0

1

1

1

0

1

1

1

0

3)

x1

x2

x3

f

0

0

0

0

0

0

1

1

0

1

0

1

0

1

1

1

1

0

0

1

1

0

1

0

1

1

0

1

1

1

1

1

4)

x1

x2

x3

x4

0

0

0

0

0

0

0

0

1

1

0

0

1

0

0

0

0

1

1

0

0

1

0

0

1

0

1

0

1

0

0

1

1

0

0

0

1

1

1

0

1

0

0

0

1

1

0

0

1

1

1

0

1

0

0

1

0

1

1

0

1

1

0

0

0

1

1

0

1

0

1

1

1

0

1

1

1

1

1

0

5)


 

А также другие работы, которые могут Вас заинтересовать

28564. Система RSA. Использование алгоритма Евклида для расчета секретного ключа d 23.69 KB
  Подобный блок может быть интерпретирован как число из диапазона 0; 2i1;; для каждого такого числа назовем его mi вычисляется выражение ci=mie mod n 3.По теорема Эйлера если число n представимо в виде двух простых чисел p и q то для любого x имеет место равенство Xp1q1 mod n =1 Для дешифрования RSAсообщений воспользуемся этой формулой. Возведем обе ее части в степень y: Xyp1q1 mod n = 1 y=1 Теперь умножим обе ее части на x : xyp1q11 mod n =...
28565. Алгоритма цифровой подписи Эль Гамаля, преимущества по сравнению с методом RSA, недостатки 13.41 KB
  Алгоритма цифровой подписи Эль Гамаля преимущества по сравнению с методом RSA недостатки. В отличие от RSA метод ЭльГамаля основан на проблеме дискретного логарифма. По сравнению с методом RSA данный метод имеет целый ряд преимуществ: 1. Кроме того данный алгоритм подписи не допускает его использования в качестве алгоритма шифрования в отличии от RSA в котором шифрование и подпись суть одно и то же а следовательно не подпадает ни под какие экспортные ограничения из США.
28566. Проблема дискретного логарифмирования, аутентификация 86.42 KB
  Система строится из криптографических примитивов низкого уровня:групповой операции симметричного шифра функции хэширования и алгоритма вычисления кода аутентификации сообщенияимитовставки MAC. Код аутентификации сообщения позволяет пользователям обладающим общим секретным ключом выработать битовую строку для аутентификации и проверки целостности данных Пусть Msg = {01} пространство сообщений mKey = {01}mLen пространство ключей для вычисления MAC для некоторого mLen N Tag = {01}tLen включающее множество всех возможных...
28567. Система открытого шифрования RSA, атаки на RSA 15.87 KB
  В настоящее время наиболее развитым методом криптографической защиты информации с известным ключом является RSA названный так по начальным буквам фамилий ее изобретателей Rivest Shamir и Adleman и представляющую собой криптосистему стойкость которой основана на сложности решения задачи разложения числа на простые сомножители. Чтобы использовать алгоритм RSA надо сначала сгенерировать открытый и секретный ключи выполнив следующие шаги: выберем два очень больших простых числа p и q; определим n как результат умножения p на q n = p Ч...
28568. Система электронной подписи Эль Гамаля (EGSA - ElGamal Signature Algorithm) 16.07 KB
  Затем выбирается секретное число х и вычисляется открытый ключ для проверки подписи y=gxmod p Далее для подписи сообщения М вычисляется его хэшфункция т = hM. Выбирается случайное целое k:1 k p1 взаимно простое с р1 и вычисляется r=gkmod p. После этого с помощью расширенного алгоритма Евклида решается относительно s уравнение m=xrksmodp1. Получатель подписанного сообщения вычисляет хэшфункцию сообщения m=hM и проверяет выполнение равенства yrrs=gxrgks=gxrks=gmmod p.
28569. Система открытого шифрования Эль Гамаля 58 KB
  Для шифрования сообщения M проводится следующая процедура: Выбирается случайное число k kP1=1 Вычисляется G=AK mod P Вычисляется H=yK M mod P Пара G H является шифрованным сообщением M При расшифровании вычисляется: H GX mod P = yK M AXK mod P = M mod P Преимуществами системы ЭЦП и ОШ Эль Гамаля является простота генерации открытых и секретных ключей а так же то что параметры P и A могут быть общими для всех участников сети связи.
28570. Общая схема электронной подписи на основе дискретной экспоненты 14.29 KB
  Пусть DATA пеpедаваемое Александpом Боpису сообщение. Александp подписывает DATA для Боpиса пpи пеpедаче: Eebnb{Edana{DATA}}. Боpис может читать это подписанное сообщение сначала пpи помощи закpытого ключа Eebnb Боpиса с целью получения Edana{DATA}= Edbnb{ Eebnb{ Edana {DATA}}} и затем откpытого ключа EeAnA Александpа для получения DATA= Eeana{ Edana {DATA}}. Таким обpазом у Боpиса появляется сообщение DATA посланное ему Александpом.
28571. Однонаправленные хеш-функции Понятие хеш-функции 13.67 KB
  Изменения в тексте сообщения приводят к изменению значения хешфункции. На бесключевые хешфункции накладываются определенные условия. однонаправленность устойчивость к коллизиям устойчивость к нахождению второго прообраза Применение ключевых хэшфункций Ключевые хешфункции применяются в случаях когда стороны имеют общий секретный ключ доверяют друг другу.
28572. Примеры хеш-функций 14.18 KB
  Расширение исходного сообщения Собственно хеширование . Расширение исходного битового сообщения M длины L происходит следующим образом. Алгоритм хеширования работает циклами за один цикл обрабатывается блок исходного сообщения длины 512 бит. Цикл состоит из четырех раундов каждый из которых вычисляет новые значения переменных A B C D на основании их предыдущего значения и значения 64битного отрезка хешируемого 512битного блока исходного сообщения.