Оглавление

Глава 1. Булевы функции………………………………………..5

§1.1. Булевы функции и их свойства…………………………5

Вопросы и упражнения для самостоятельной работы………9

§1.2. Нормальные формы булевых функций……………….10

Вопросы и упражнения для самостоятельной работы……..12

§1.3. Важнейшие замкнутые классы булевых функций…...13

Вопросы и упражнения для самостоятельной работы……..16

§1.4. Полные системы. Теорема Поста……………………..17

Вопросы и упражнения для самостоятельной работы…….19

Глава 2. Функции выбора……………………………………...20

§2.1. Понятие функции выбора……………………………...20

Вопросы и упражнения для самостоятельной работы……..24

§2.2. Характеристические векторы подмножеств конечного множества……………………………………………….……….....25

Вопросы и упражнения для самостоятельной работы……..29

§2.3. Логическое представление функций выбора…………29

Вопросы и упражнения для самостоятельной работы……..34

§2.4. Турнирный выбор………………………………………36

Вопросы и упражнения для самостоятельной работы……..39

Глава 3. Графы……………………………………………….....41

§3.1. Основные понятия……………………………………...41

Вопросы и упражнения для самостоятельной работы……..51

§3.2. Деревья……………………………………………….....56

Вопросы и упражнения для самостоятельной работы……..60

§3.3. Доминирование в графах. Внутренняя и внешняя устойчивость. Ядро…………………………………………………...62

Вопросы и упражнения для самостоятельной работы……..67

Ответы…………………………………………………………..69

Литература………………………………………………………72

1. Булевы функции

§1.1. Булевы функции и их свойства

Переменная x, принимающая значения 0 или 1 (x{0,1} ), называетсябулевой переменной.

Функция от одной или нескольких булевых переменных, принимающая значения в множестве {0,1}, называется булевой функцией.

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

x0 1

---------------------

g₀0 0

g₁0 1

g₂1 0

g₃1 1

Здесь используются обозначения:

g₀(x)=0 – функция, тождественно равная нулю;

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

g₂(x)=1–x– функция, заменяющая значение аргументаxна его отрицаниеx’, т.е.g₂(x)=x’;

g₃(x)=1 – функция, тождественно равная единице.

x₁0 0 1 1

x₂0 1 0 1

-------------------------------

f₀0 0 0 0 0тождественный ноль

f₁0 0 0 1,умножение, конъюнкция

f₂0 0 1 0

f₃0 0 1 1x₁

f₄0 1 0 0

f₅0 1 0 1x₂

f₆0 1 1 0сложениепомодулю2

f₇0 1 1 1дизъюнкция

f₈1 0 0 0стрелкаПирса

f₉1 0 0 1эквивалентность

f₁₀1 0 1 0

f₁₁1 0 1 1обратнаяимпликация

f₁₂1 1 0 0

f₁₃1 1 0 1импликация

f₁₄1 1 1 0 |штрихШеффера

f₁₅1 1 1 1 1тождественнаяединица

Используемые обозначения приведены справа. Например, для конъюнкции f₁(x₁,x₂) =x₁x₂=x₁x₂, а для стрелки Пирсаf₈(x₁,x₂) =x₁x₂.

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

Законы поглощения: x(xy) =x;x(xy) =x;

Законы расщепления: (xy)(xy’) =x; (xy)(xy’) =x;

Дистрибутивность:x(yz) = (xy)(xz);x(yz) = (xy)(xz);

Законы нуля и единицы:xx’ = 0;xx’ = 1; 0x =x; 1x=x; 0x=x; 1x =x;

Законы де Моргана: (xy)’ = x’y’; (xy)’ =x’y’;

Устранение импликации:x→y =x’y.