Л е к ц и я 2

Задание двоичных функций формулами

Геометрический способ задания

Табличный способ задания

Л е к ц и я 1

ВВЕДЕНИЕ

Данное учебное пособие является основой для преподавания курса «Математическая логика и теория алгоритмов». Этот курс преподается студентам третьего курса факультета «Информационная безопасность» МИФИ в рамках специальности «Комплексное обеспечение информационной безопасности автоматизированных систем» (шифр 075500).

В этом пособии отражены, по мнению авторов, теоретические результаты, лежащие в основе создания устройств криптографической защиты информации и оценки их стойкости. Так, например, один из подходов к анализу и обоснованию стойкости алгоритмов криптографической информации состоит в оценке вычислительной сложности соответствующих преобразований. Кроме того, большое число криптографических алгоритмов строятся на основе преобразований, которые реализованы с помощью булевых функций. Естественным образом возникает необходимость наличия у специалистов в области информационной безопасности навыков использования аппарата булевых функций и теории сложности вычисления для анализа криптографических преобразований. Теоретические основы для возможности реализации этих навыков приведены в данном учебном пособии.

Излагаемый материал представлен в виде 18 лекций. Объем лекций различен. Это, прежде всего, связано с тем, что определенные разделы курса предназначены для самостоятельного изучения. Так, например, весьма обширно представлены результаты, связанные с реализацией вычислительных процедур на таких моделях вычислительных устройств, как машины Тьюринга и МПД-машины. При этом изложение этих результатов, в целом, носит описательный характер и в полной мере доступен для успешной самостоятельной работы студентов. В учебном пособии приведено большое количество результатов, связанных с изучением конкретных вычислительных задач, что также может быть изучено самостоятельно.

Основные способы задания двоичных функций

Определение 1.1. Двоичной функцией от n (n ³ 1) переменных называется функция , аргументы и значения которой выбираются из множеств , т.е.

f: ,

где

, .

Замечание 1.2. Двоичные функции от n переменных также называют булевыми (булевскими) функциями от n переменных или n -местными булевыми функциями.

На множестве определим так называемый лексикографический порядок, т.е. для любого двоичного набора определим его номер

.

Тогда двоичная функция однозначно может быть задана табл.1.1 (называемой таблицей истинности).

Таблица 1.1

Номер набора	x 1 … xn -1 xn	f (x 1,..., xn)
	0... 0 0	f (0,..., 0,0)
	0... 0 1	f (0,..., 0,1)
...	...	...
2 ^n – 2	1... 1 0	f (1,..., 1,0)
2 ^n – 1	1... 1 1	f (1,..., 1,1)

При указанной договоренности о расположении наборов из функция однозначно определяется набором — столбцом значений. Отсюда непосредственно вытекает справедливость следующего утверждения.

Утверждение 1.3. Число двоичных функций от n переменных равно .

Перечислим все двоичные функции от одной и двух переменных. Имеется четыре функции от одной переменной (табл.1.2).

Таблица 1.2

x 1 \ f	f 0	f 1	f 2	f 3
Условное обозначение

Функции и не зависят от значения переменной и называются константными (, ). Функция называется тождественной функцией, а функция называется отрицанием.

Функций от двух переменных — шестнадцать (табл.1.3).

Таблица 1.3

, \ f	f 0	f 1	f 2	f 3	f 4	f 5	f 6	f 7
0 0
0 1
1 0
1 1
Обозначение		x 1× x 2		x 1		x 2	x 1Å x 2	x 1Ú x 2

Продолжение табл.1.3

x 1, x 2\ f	f 8	f 9	f 10	f 11	f 12	f 13	f 14	f 15
0 0
0 1
1 0
1 1
Обозначение	x 1¯ x 2	x 1 ~ x 2				x 1 ® x 2	x 1½ x 2

Важнейшими из них являются: — конъюнкция (x ₁ x ₂, x ₁ & x ₂, x ₁ x ₂), — сложение по модулю 2 (x ₁ x ₂), — дизъюнкция (x ₁ x ₂), — функция Пирса (x ₁ x ₂), — импликация (x ₁ x ₂), — функция Шеффера (x ₁| x ₂).

Определение 1.4. Переменная x_i, или i -я переменная двоичной функции f (x ₁,..., x_n) называется существенной переменной функции f (т.е. функция f существенно зависит от x_i), если существует набор (a ₁,..., a_{i -1}, a_{i +1},..., a_n) Î , такой, что

f (a ₁,..., a_{i -1}, 0, a_{i +1},..., a_n) ¹ f (a ₁,..., a_{i -1}, 1, a_{i +1},..., a_n).

В противном случае переменная x_i называется несущественной (фиктивной) переменной функции f.

Так, среди функций от двух переменных имеется ровно десять функций, существенно зависящих от всех своих переменных.

Число двоичных функций от n переменных растет с увеличением n чрезвычайно быстро. В табл.1.4 приведена зависимость функций от своих переменных при n £ 8.

Таблица 1.4

n	Число функций от n переменных
	> 1.8 ×10^19
	> 3.4 ×10^38
	> 1.1 ×10^77

С табличным заданием функции непосредственно связан такой ее параметр, как вес.

Определение 1.5. Множество двоичных наборов {(a ₁,..., a_n) Î Î | f (a ₁,..., a_n) = 1}, на которых функция f принимает значение 1, называется областью истинности функции f. Мощность области истинности функции f называется весом функции f и обозначается || f ||.

Очевидно, что 0 £ || f || £ 2 ⁿ, причем равенства достигаются лишь для функций-констант 0 и 1. Если || f || = 2 ^{n -1}, то функция f называется равновероятной.

Для двоичных функций используются и другие способы задания, приспособленного для рассматриваемой в каждом конкретном случае задачи, которые будут рассмотрены далее.

Под геометрическим способом задания двоичной функции f (x ₁,..., x_n) понимается выделение тех вершин n -мерного двоичного куба, на наборах координат которых функция принимает единичное значение. На рис.1.1 приведены двоичные кубы размерностей n = 0, 1, 2, 3.

Рис.1.1

Выделим среди множества вершин n -мерного куба те, на наборе координат которых функция принимает единичное значение. Например, функции, заданной табл.1.5 соответствует геометрическое задание, изображенное на рис.1.2.

Таблица 1.5

x 1	x 2	x 3	f

Рис.1.2	Рис.1.3

Часто по геометрическому заданию функции строят граф связности вершин n-мерного куба, соответствующий данной функции. Для этого сначала отмечают те ребра, у которых оба конца выделены, т.е. соответствующие вершины лежат в области истинности. Затем все остальные ребра и вершины, не лежащие в области истинности, отбрасывают. Так функции, изображенной на рис.1.2, соответствует граф связанности, приведенный на рис.1.3.

Пусть имеется некоторый класс (т.е. множество) двоичных функций K. Он может быть как конечным, так и бесконечным. Обозначим через f ₁, f ₂,..., входящие в него функции, и пусть X = { x ₁, x ₂,...} — множество двоичных переменных. Дадим индуктивное определение формулы над классом K:

символ переменной x_i, x_i Î X есть формула над K;

если f — обозначение некоторой функции от m переменных из класса K и Ф₁,..., Ф _m — формулы над K, то запись Ф = f (Ф₁,..., Ф _m) есть формула над K.

Таким образом, формулы — это записи, в которых используются символы переменных и функций из K. Если необходимо подчеркнуть, от каких переменных зависит формула Ф, то используют обозначение Ф(x ₁,..., x_n), где x ₁,..., x_n — все переменные, участвующие в задании формулы Ф.

Установим теперь связь между формулами и двоичными функциями. Сначала заметим, что для произвольного набора значений переменных, входящих в формулу, можно, используя индуктивный характер определения, вычислять ее значение на этом наборе. Действительно, если значение формул Ф₁,..., Ф _m, входящих в формулу Ф = f (Ф₁,..., Ф _m), уже подсчитаны и равны соответственно b ₁,..., b_m, b_i Î F ₂, то значение формулы Ф равно значению функции f (b ₁,..., b_m). Поставим в соответствие каждой формуле Ф(x ₁,..., x_n) функцию f _Ф(x ₁,..., x_n), зависящую от тех же переменных, значения которой при всех значениях переменных совпадают со значениями формулы Ф(x ₁,..., x_n).

Легко видеть, что одна и та же формула может быть использована для записи целого ряда функций. Например, формула x ₁ соответствует функциям

x 1	f 1

x 1	x 2	f

x 1	x 2	x 3	f

и т.д. Поэтому естественным оказывается следующее определение.

Определение 1.6. Под функциями, реализуемыми формулой Ф понимается функция f _Ф, а также все функции, которые получаются из f _Ф удалением или добавлением несущественных переменных.

С другой стороны, одной функции может соответствовать множество различных формул. Например, рассматриваемые выше функции могут быть заданы любой из следующих формул:

x ₁, , , ,....

Чтобы учесть эту неоднозначность, введем понятие равносильности формул.

Определение 1.7. Две формулы Ф₁ и Ф₂ называются равносильными (обозначается Ф₁ = Ф₂), если они реализуют одинаковые множества функций.

Замечание 1.8. Заметим, что для проверки равносильности формул Ф₁ и Ф₂ достаточно добавить к функции те переменные, которые входят в Ф₂, но не входят в формулу Ф₁, а к функции добавить переменные из Ф₁, которые не входят в формулу Ф₂, а затем сравнить таблицы полученных функций.

Приведем два свойства, облегчающих проверку равносильности формул. Для их формулировки нам потребуется понятие подформулы.

Определение 1.9. Подформулой формулы Ф называется сама формула Ф; подформулой формулы f (Ф₁,..., Ф _m) называется она сама, а также все подформулы формул Ф₁,..., Ф _m.

Свойство 1.10. Если Ф₁ — подформула формулы Ф, и Ф₁ равносильна Ф₂, то подформула Ф¢, полученная из Ф путем замены Ф₁ на Ф₂ будет равносильна формуле Ф.

Свойство 1.11. Если формулы Ф₁ и Ф₂ равносильны, то, подставив одновременно в них вместо некоторых переменных любые формулы, получим в результате также равносильные формулы.

Основные способы задания

двоичных функций (продолжение)

Дата добавления: 2014-12-29