Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

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

Читайте также:
  1. I.Социальные функции физической культуры и спорта.
  2. II. Контрольная работа « Дифференцирование функции ».
  3. Quot;Ссылки. Встроенные функции MS Excel ".
  4. VI. Строение, обмен и функции липидов.
  5. WEB-браузер - назначение, основные функции, программная реализация, методы обмена информацией с расширениями сервера.
  6. WEB-сервер - назначение, основные функции, программная реализация, конкретные примеры
  7. А) какие функции выполняют жиры;
  8. А) Функции директора школы, заместителя директора по учебно-воспитательной работе, организатора внеклассной и внешкольной воспитательной работы.
  9. Автовокзалы и автостанции, основные функции и требования к ним.
  10. Алгоритм нахождения производной сложной функции

Оглавление

Глава 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’;

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




Дата добавления: 2015-04-11; просмотров: 39 | Поможем написать вашу работу | Нарушение авторских прав

<== 1 ==> | 2 | 3 | 4 | 5 |


lektsii.net - Лекции.Нет - 2014-2024 год. (0.006 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав