Упражнения.

1. Определить проекции v: пр₁ v, пp₃ v, пp_1,3 v, если:

a) v = (2,3,1,1); б) v = (2,2,3,1).

2. Определить проекции множества векторов V: пр₁ V, пp₃ V, пp_1,3 V, если:

а) {(2, 3,1,1), (2,2,3,1), (1,2, 3,1)};

б) {(1,3, 5), (2, 4, 6), (3,5, 7)}.

3. Пусть X = {а,с}, Y = {a,d,f}. Найти X Y, Y², Y X Y.

4.Проиллюстрировать на конкретном примере справед­ливость соотношения А (В С) = (А В) (A x C).

5.Пусть A_l = А₂ = {a,b,с}, А₃ = А₄ = {d,е} и V=A₁ A₂ А₃ A_n. Найти: пр₁ V, пр_1,3 V.

6. Сравнить векторные оценки множества V = {(3,1,2,3), (2,2,1,3), (1,2,3,2), (3,1,2,2), (1,2,2,3), (3,2,3,2), (2,2,2,2), (2,3,1,3)} с использованием правила 1 сравне­ния векторов по предпочтению и определить подмножество V ’ наилуч-ших – парето-оптимальных – векторных оценок, V ’ V [см. пример 7].

2. Алгебра логики

2.1. Функции алгебры логики

Будем рассматривать функции f(u_i1, u_i2, …, u_in) (u_ik≠u_im при k≠m), аргументы которых определены на множестве E₂={0; 1} и такие, что f(α₁, α₂, …, α_n)εE₂, если α_iεE₂. Эти функции называются функциями алгебры логики или булевыми функциями.

Чтобы избежать двойной индексации, будем употреблять символы x, y, z, … с индексами или без них, т.е. f(x₁, x ₂, …, x _n). Из определения функции f(x₁, …, x _n) следует, что для ее задания достаточно указать, какое значение функции соответствует каждому из наборов значений аргументов, т.е. выписать таблицу.

Таблица 1

X1	…	xn-1	xn	f(x1, x 2, …, x n-1, x n)
0	…	0	0	f(0, …, 0, 0)
0	…	0	1	f(0, …, 0, 1)
0	…	1	0	f(0, …, 1, 0)
…	…	…	…	…
1	…	1	1	f(1, …, 1, 1)

Нетрудно видеть, что набор из n переменных принимает 2ⁿ значений. Для удобства употребляется стандартное расположение наборов: если набор рассматривается как запись числа в двоичной системе исчисления, то расположение наборов соответствует порядку следования чисел 0, 1, …, 2ⁿ-1.

Обозначим через Р₂ систему всех функций алгебры логики над алфавитом U={ u₁, u₂, …, u_m, …}, содержащую также константы

0 и 1.

Если фиксировать n переменных x₁, x ₂, …, x _n, то различные таблицы будут различаться только значениями правого столбца.

Имеет место следующая теорема.

Теорема. Число p₂(n) всех функций из P₂ , зависящих от n переменных x₁, x ₂, …, x _n, равно .

Замечание I. Число функций алгебры логики, зависящих от n аргументов конечно, поэтому изучить их в принципе можно перебором, однако p₂(1)=4; p₂(2)=16; p₂(3)=256; p₂(4)=65536; …, следовательно при больших n (n≥6) перебор становится практически невозможным даже с использованием вычислительной техники.

Замечание II. С ростом n таблица, задающая функцию, сильно усложняется, так при n=10 в ней уже 1024 строки, а при n=20 она практически необозрима.

Введенное выше определение функции имеет существенный недостаток: оно не позволяет рассматривать функции от меньшего числа аргументов. Для устранения этого недостатка введем следующее определение.

Определение. Функция f(x₁, …, x _i-1, x _i, x _i+1, …, x _n) из P₂ зависит существенным образом от аргумента x_i, если найдутся такие значения α₁, …, α _i-1, α _i, α _i+1, …, α _n переменных x₁, …, x _i-1, x _i, x _i+1, …, x _n, что f(α₁, …, α _i-1, 0, α _i+1, …, α _n)≠ f(α₁, …, α _i-1, 1, α _i+1, …, α _n).

В этом случае переменная x_i называется существенной. Если переменная x_i не является существенной, то она называется несущественной или фиктивной.

Пусть x_i является фиктивной переменной. Возьмем таблицу для функции f(x₁, …, x _n) и по ней построим новую таблицу, вычеркивая все строки вида α₁, …, α _i-1, 1, α _i+1, …, α _n и столбец x_i. Полученная таблица будет определять некоторую функцию g(x₁, …, x _i-1, x_i+1, …, x _n).

Будем говорить, что g(x₁, …, x _i-1, x _i+1, …, x _n) получена из f(x₁, …, x _n) путем удаления фиктивной переменной x_i, а f получена из g путем введения фиктивной переменной x_i.

Определение. Функции f₁ и f₂ будем называть равными, если функцию f₂ можно получить из f₁ путем изъятия или добавления фиктивных аргументов.

Существуют 2 типа функций, не имеющих существенных переменных. Это 0 и 1. Ввиду этого целесообразно включить в рассмотрение константы 0 и 1, рассматривая их как функции от пустого множества переменных.

Рассмотрим примеры «элементарных» функций алгебры логики:

1) f₁(x)=0 – константа 0;

2) f₂(x)=1 – константа 1;

3) f₃(x)=x – тождественная функция;

4) f₄(x)= – отрицание х (читается «не х»);

5) f₅(x₁, x₂)= (x₁Λx₂) – конъюнкция x₁ и x₂ (читается «х₁ и x₂»). Вместо знака Λ употребляется знак “·”. Эту операцию называют логическим умножением.

6) f₆(x₁, x₂)= (x₁Vx₂) – дизъюнкция x₁ и x₂ (читается «х₁ или x₂»). Эту операцию называют логическим сложением.

7) f₇(x₁, x₂)= (x₁→x₂) – импликация x₁ и x₂ (читается «из х₁ следует x₂»). Эту операцию называют логическим следованием.

8) f₈(x₁, x₂)= (x₁+x₂) – сложение х₁ и x₂ по mod2.

9) f₉(x₁, x₂)= (x₁/x₂) – функция Шеффера (понимается как отрицание конъюнкции).

Функции f₁- f₄ – монарные функции, f₅- f₉ – бинарные функции.

Выпишем таблицы значений этих функций.

Таблица 2

х	0	1	х
0	0	1	0	1
1	0	1	1	0

Таблица 3

x1	x2	(x1Λx2)	(x1Vx2)	(x1→x2)	(x1+x2)	(x1/x2)
0	0	0	0	1	0	1
0	1	0	1	1	1	1
1	0	0	1	0	1	1
1	1	1	1	1	0	0

Заметим, что

(x₁Λx₂)= (x₁·x₂)= min(x₁, x₂);

(x₁Vx₂)= max(x₁, x₂).