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

Тема 8.5. Булева алгебра и теория множеств

Тема 6.1. Понятие кортежа. Декартово произведение множеств | Тема 6.2. Определения и свойства | Тема 6.3. Типы отношений | Тема 6.5. Решётки | Тема 7.1. Понятие высказывания, простые и составные высказывания | Тема 7.2. Операции на множестве высказываний | Штрих Шеффера | Тема 8.1. Формулы Булевой алгебры | Тема 8.2. Законы и тождества Булевой алгебры | Тема 8.3. Составление формулы по заданной таблице истинности |


Читайте также:
  1. E) Метатеория чудес
  2. А стоит ли читать модную «молитву задержания»? В молитвословах, изданных Патриархией, ее нет, но множество листовок призывает с помощью этой молитвы задержать приход антихриста.
  3. АЗБУКА, ТЕОРИЯ, ФИЛОСОФИЯ 1 страница
  4. АЗБУКА, ТЕОРИЯ, ФИЛОСОФИЯ 10 страница
  5. АЗБУКА, ТЕОРИЯ, ФИЛОСОФИЯ 11 страница
  6. АЗБУКА, ТЕОРИЯ, ФИЛОСОФИЯ 12 страница
  7. АЗБУКА, ТЕОРИЯ, ФИЛОСОФИЯ 13 страница

Ранее были описаны булевы алгебры множеств, то есть алгебры вида , где – булеан множества, то есть множество всех возможных его подмножеств. Общий термин «булева алгебра» для алгебр множеств и логических функций не является случайным. Всякая алгебра называется булевой алгеброй, если её операции удовлетворяют соотношениям, приведённым в пункте 8.2.

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

Очевидно взаимно однозначное соответствие между множеством , где и множеством двоичных векторов длины . Каждому подмножеству соответствует двоичный вектор , где , если , и , если . Операции над векторами в булевой алгебре определяются следующим образом.

Пусть даны два вектора и из множества . Тогда:

Поскольку компоненты (координаты) векторов принимают значения 0 или 1, то указанные операции – это просто логические операции над двоичными переменными, поэтому операции над векторами естественно назвать покомпонентными логическими операциями над двоичными векторами.

Пример 8.6: Даны векторы и . Найти .

Решение:

.

Заметим, что подобные операции (наряду с логическими операциями над переменными) входят в систему команд любой современной ЭВМ.

Теорема: Если мощность множества равна , то булева алгебра изоморфна булевой алгебре .

Эта простая по содержанию теорема имеет огромное значение в математике. Она позволяет заменить теоретико-множественные операции над системой подмножеств данного множества поразрядными логическими операциями над двоичными векторами.

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

Теорема: Если мощность множества равна , то булева алгебра изоморфна булевой алгебре функций .

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


Дата добавления: 2015-10-28; просмотров: 240 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Тема 8.4. Двойственность| Тема 8.6. ДНФ, интервалы и покрытия

mybiblioteka.su - 2015-2024 год. (0.006 сек.)