Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Лекция № 10. Булевы алгебры и теория множеств.Содержание книги
Похожие статьи вашей тематики
Поиск на нашем сайте
Определение. Функция называется двойственной к функции , если . Если взять отрицание обеих частей равенства и подставить вместо переменных , то получится . Это означает, что функция двойственна к функции , и, таким образом, отношение двойственности является симметричным. Из определения двойственности ясно, что для любой функции двойственная ей функция определяется однозначно. В частности, может оказаться, что функция двойственна самой себе. В этом случае она называется самодвойственной. Пример 1. Если рассматривать логические функции, то, очевидно, дизъюнкция двойственна конъюнкции и наоборот (непосредственно следует из правил Де Моргана). Отрицание является самодвойственной функцией. Функция-константа двойственна функции . Ещё один традиционный пример самодвойственной функции – функция . Пользуясь определением двойственности нетрудно доказать следующее утверждение, называемое принципом двойственности. Теорема 10.1. Если в формуле , представляющей функцию , все знаки функций заменить соответственно на знаки двойственных им функций, то полученная формула будет представлять функцию , двойственную функции . В булевой алгебре принцип двойственности имеет более конкретный вид, вытекающий из ранее приведённых примеров: если в формуле , представляющей функцию , все конъюнкции заменить дизъюнкциями и наоборот, все единицы заменить нулями и наоборот, то получим формулу , представляющую функцию , двойственную функции . Если функции равны, то двойственные им функции также равны. Это позволяет с помощью принципа двойственности получать новые эквивалентные соотношения, переходя от равенства с помощью указанных замен к равенству . Примером могут служить соотношения и , которые могут быть получены друг из друга по указанному принципу.
Ранее были описаны булевы алгебры множеств, то есть алгебры вида , где - булеан множества , то есть множество всех его подмножеств. Общий термин “булева алгебра” для алгебр множеств и логических функций не является случайным. Определение. Всякая алгебра типа называется булевой алгеброй, если её операции удовлетворяют соотношениям 1 – 10 (см. предыдущую лекцию). В алгебре множеств элементами являются подмножества фиксированного универсального множества . В этой алгебре операция пересечения соответствует конъюнкции, операция объединения соответствует дизъюнкции, а операция дополнения соответствует отрицанию. Само множество является единицей, а пустое множество – нулём. Справедливость соотношений 1 – 10 для этой алгебры можно доказать непосредственно, рассматривая в них переменные как множества, а знаки логических функций – как соответствующие операции над множествами. В одной из предыдущих лекций отмечалось взаимно однозначное соответствие между множеством , где и множеством двоичных векторов длины . Каждому подмножеству соответствует двоичный вектор , где , если , и , если . Операции над векторами в булевой алгебре определяются следующим образом. Пусть даны два вектора и из множества . Тогда: , , . Поскольку компоненты (координаты) векторов принимают значения 0 или 1, то указанные операции – это просто логические операции над двоичными переменными, поэтому операции над векторами естественно назвать покомпонентными логическими операциями над двоичными векторами. Пример 2. Даны векторы и . Найти . Решение: . Заметим, что подобные операции (наряду с логическими операциями над переменными) входят в систему команд любой современной ЭВМ. Теорема 10.2. Если мощность множества равна , то булева алгебра изоморфна булевой алгебре . Эта простая по содержанию теорема имеет огромное значение в математике. Она позволяет заменить теоретико-множественные операции над системой подмножеств данного множества поразрядными логическими операциями над двоичными векторами. Похожая по формулировке, но значительно отличающаяся по смыслу теорема существует для множества всех логических функций переменных . Обозначим это множество . Оно замкнуто относительно операций и, следовательно, образует конечную булеву алгебру , которая является подалгеброй булевой алгебры логических функций. Теорема 10.3. Если мощность множества равна , то булева алгебра изоморфна булевой алгебре функций . Теорема 10.3 указывает на тесную связь между множествами и логическими функциями и позволяет переходить от операций над множествами к операциям над функциями и обратно. В частности, они позволяют непосредственно производить операции над функциями, заданными не формулами, а таблицами. Пример приведён в следующей таблице, содержащей две функции трёх переменных и и результаты операций над ними:
Теоретико-множественная интерпретация булевой алгебры предлагает очень удобный язык для изучения дизъюнктивных нормальных форм (ДНФ) и построения методов их упрощения. Рассмотрим кратко основные понятия, связанные с ДНФ. Введём следующее обозначение: обозначим через множество всех единичных наборов функции . Тогда набор (вектор) из множества принадлежит тогда и только тогда, когда . Множество называется единичным множеством функции , а функция называется характеристической функцией множества . Легко показать, что соответствие между функциями и их единичными множествами является изоморфизмом. Если функция представляется элементарной конъюнкцией всех переменных, то множество содержит ровно один элемент множества . Если же функция – элементарная конъюнкция переменных , то содержит двоичных наборов. Это объясняется тем, что в таком случае переменных, не входящих в эту конъюнкцию несущественны для функции . Тогда они принимают значений, не изменяя значения . Множество такой функции называется интервалом. Пример 3. Рассмотрим функцию и найдём её интервал. Прежде всего, заметим, что две переменных являются несущественными. Это позволяет сразу определить количество единичных наборов, содержащихся в множестве (иначе говоря, его мощность). Поскольку в данном случае , то получим . Далее, очевидно, что только при значениях . При этом переменные могут принимать любые значения. Теперь перечислим все единичные наборы для данной функции: . Итак, . В рассматриваемом случае говорят, что конъюнкция (или, точнее, интервал ) покрывает множество и все его подмножества. Представление некоторой функции в виде ДНФ соответствует представлению её единичного множества в виде объединения интервалов; в совокупности все конъюнкции ДНФ покрывают всё единичное множество функции . Обратное также верно: если все элементы некоторого интервала принадлежат , то существует ДНФ данной функции, содержащая конъюнкцию . Назад, в начало конспекта.
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2016-04-26; просмотров: 729; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.142.174.8 (0.006 с.) |