Дискретна математика, лекція 14-2: алгебраїчні властивості булевих операцій; формули

Розглянуто такі питання:
-- алгебраїчні властивості булевих операцій (ідемпотентність, інволютивність, комутативність, асоціативність, дистрибутивність, правила поглинання, правила де Моргана тощо);
-- відповідність між булевими операціями та операціями над множинами;
-- доведення тверджень через таблиці істинності;
-- поняття суперпозиції функцій, визначення формул;
-- еквівалентні формули;
-- поняття нормальної форми.
Лектор: Сергій Яковлєв.
Дивіться у 720p, оскільки написи на дошці доволі дрібні.

[@hiddenhidden1656]

Скажите, пожалуйста, существует ли приоритет операций в булевой алгебре? Как правильно, например, прочитать следующее: (x, y, z - переменные; & - AND, v - OR, + - XOR, -> - implication) 1) x & y v не-z; 2) y + x & z; 3) не-x -> y & не-z? Ведь каждый из этих примеров я могу трактовать в 2 вариантах: 1. a) (x & y) v не-z; b) x & (y v не-z); 2. a) y + (x & z); b) (y + x) & z; 3. a) не-x -> (y & не-z) b) (не-x -> y) & не-z

[@MMIS_IPT]

Линейной шкалы приоритетов нет. Традиционно отрицание имеет наивысший приоритет, а в остальном ситуативно. В алгебраической нормальной форме AND имеет приоритет над XOR, и в других случаях, когда AND обозначается точкой, а не галочкой или амперсандом, подразумевается, что он приоритетнее остальных бинарных операций (как в традиционной записи СДНФ, например). Во всех прочих случаях операции выполняются последовательно, а приоритет задаётся скобками.

[@hiddenhidden1656]

Спасибо за лекцию! Верно ли утверждение, что каждое алгебраическое свойство операций над множествами верно для булевых функций и каждое алгебраическое свойство булевых операций верно для множеств?

[@MMIS_IPT]

Настолько прямолинейно -- нет, есть некоторые ограничения и несоответствия (например, _отношению_ включения множеств соответствует _операция_ импликации на булевых переменных). Опять же, множества не ограничиваются универсумом и пустым множеством, и поэтому на них можно строить более богатые структурные соотношения. Подразумевалось, что есть естественная аналогия (вплоть до построения прямых гомоморфизмов), которая позволяет выводить соотношения на битах из соотношений на множествах или наоборот; но эти соотношения всё равно надо строго доказывать.

[@hiddenhidden1656]

@@MMIS_IPT, спасибо за ответ! Все те свойства булевых операций, которые были на лекции (9 блоков), в алгебре множеств тоже присутствуют (если я изменю обозначения операций), правильно я понимаю?

[@MMIS_IPT]

Перечисленные на лекции - да)