Читайте также:
|
Оглавление
Глава 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
Булевы функции
Булевы функции и их свойства
Переменная x, принимающая значения 0 или 1 (x Î{0,1}), называется булевой переменной.
Функция от одной или нескольких булевых переменных, принимающая значения в множестве {0,1}, называется булевой функцией.
Любую булеву функцию можно задать с помощью таблицы истинности. Следующие ниже две таблицы перечисляют все булевы функции одной и двух переменных.
x 0 1
---------------------
g 0 0 0
g 1 0 1
g 2 1 0
g 3 1 1
Здесь используются обозначения:
g 0(x)=0 – функция, тождественно равная нулю;
g 1(x)= x – тождественная функция;
g 2(x)=1– x – функция, заменяющая значение аргумента x на его отрицание x’, т.е. g 2(x)= x’;
g 3(x)=1 – функция, тождественно равная единице.
x 1 0 0 1 1
x 2 0 1 0 1
-------------------------------
f 0 0 0 0 0 0 тождественный ноль
f 1 0 0 0 1 ×, Ù умножение, конъюнкция
f 2 0 0 1 0
f 3 0 0 1 1 x 1
f 4 0 1 0 0
f 5 0 1 0 1 x 2
f 6 0 1 1 0 Å сложение по модулю 2
f 7 0 1 1 1 Ú дизъюнкция
f 8 1 0 0 0 ¯ стрелка Пирса
f 9 1 0 0 1 «эквивалентность
f 10 1 0 1 0
f 11 1 0 1 1 обратная импликация
f 12 1 1 0 0
f 13 1 1 0 1 ® импликация
f 14 1 1 1 0 | штрих Шеффера
f 15 1 1 1 1 1 тождественная единица
Используемые обозначения приведены справа. Например, для конъюнкции f 1(x 1, x 2) = x 1 x 2 = x 1Ù x 2, а для стрелки Пирса f 8(x 1, x 2) = x 1¯ x 2.
Суперпозиции указанных функций позволяют строить более сложные функции многих переменных, при этом свойства отрицания, конъюнкции, дизъюнкции и импликации подобны тем, которыми обладают соответствующие логические операции. Например:
Законы поглощения: 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; 0 x = x; 1 x = x; 0Ú x = x; 1Ú x = x;
Законы де Моргана: (xy) ’ = x’ Ú y’; (x Ú y) ’ = x’y’;
Устранение импликации: x → y = x’ Ú y.
Дата добавления: 2015-04-11; просмотров: 118 | Поможем написать вашу работу | Нарушение авторских прав |