Контрольные вопросы по теме 3

1. Укажите способы задания бинарного отношения.

2. Для какого отношения  всегда выполняется условие  = ^–1?

3. Для какого отношения  всегда выполняется условие    .

4. Ввести отношения эквивалентности и частичного порядка на множестве всех прямых на плоскости.

5. Укажите способы задания функций.

6. Какое из следующих утверждений справедливо?

а) Всякое бинарное отношение есть функция.

б) Всякая функция есть бинарное отношение.

7. Привести пример отношения

   • не рефлексивного, не симметричного и транзитивного;

   • не симметричного, но рефлексивного и транзитивного;

   • транзитивного, рефлексивного и антисимметричного.

8. Привести пример отношения эквивалентности.

9. Будет ли отношением эквивалентности на множестве действительных чисел отношение x y, задаваемое равенством

   • x² + y² = 25;

   • x = 2y;

   • x + y = 100.

10. Привести пример функции f(x), отображающей множество действительных чисел R во множество действительных чисел (R® R) и

    • не являющейся сюръективной, инъективной, биективной;

    • являющейся сюръективной, но не инъективной;

    • не являющейся сюръективной, инъективной, биективной.

    • являющейся сюръективной, но не инъективной.

Тема 4. Булевы функции.

1. Определение булевой функции

Булевой функцией f(x₁, x₂, ... , x_n) называется произвольная функция n переменных, аргументы которой x₁, x₂, ... , x_n и сама функция f принимают значения 0 или 1, т. е. x_i {0, 1}, i = 1, 2, ... , n; f(x₁, x₂, ... , x_n) {0, 1}.

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

Любая булева функция может быть представлена таблицей, в левой части которой перечислены все возможные наборы переменных (их 2ⁿ), а в правой части – значения функции на соответствующем наборе. Пример такого задания представлен в таблице 6.

Таблица 6

x1 x2 x3	f(x1, x2, x3)
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1	0 0 0 1 0 1 1 1

Для формирования столбца значений переменных удобен лексико-графический порядок, в соответствии с которым каждый последующий набор значений получается из предыдущего прибавлением 1 в двоичной системе счисления, например, 100 = 011+ 1.

Всего существует различных булевых функций n переменных.

Функции одной переменной – f₀=0 ; f₁(x)=x; x)=x; (x)=1.

Функции f₀, f₃ – константы, f₁ – тождественная функция, f₂ - функция «отрицание x» (обозначается ). Она представлена в таблице 7.

Таблица 7

0 1	1 0

Функции двух переменных – представлены в таблице 8. Их существует всего 16 (2² при n = 2).

Таблица 8

x1 x2	f0	f1	f2	f3	f4	f5	f6	f7	f8	f9	f10	f11	f12	f13	f14	f15
0 0 0 1 1 0 1 1	0 0 0 0	0 0 0 1	0 0 1 0	0 0 1 1	0 1 0 0	0 1 0 1	0 1 1 0	0 1 1 1	1 0 0 0	1 0 0 1	1 0 1 0	1 0 1 1	1 1 0 0	1 1 0 1	1 1 1 0	1 1 1 1

Рассмотрим перечисленные функции подробнее.

f₀=0; f₁= x₁ x₂ – конъюнкция; f₂= ; f₃=x₁; f₄=

f₅=x₂; f₆= x₁+ x₂ – сложение по модулю 2;

f₇=x₁Vx₂ – дизъюнкция;

f₈= = x₁¯x₂ – стрелка Пирса;

f₉= x₁~x₂ – эквивалентность; f₁₀= x₂; f₁₁= x₂~x₁; f₁₂= x₁; f₁₃= ;

f₁₄= = x₁ï x₂ – штрих Шеффера

f₁₅=1