Ведение в булеву алгебру. Основные законы булевой алгебры

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

Логическое произведение любого числа переменных из конечного набора n переменных называется элементарным, когда сомножителями в нем являются либо переменные, либо их отрицания. Например,  является элементарным, а (3+x2) 0,  не являются элементарными.

Количество сомножителей в элементарном произведении называется его рангом r. Так для x321x0 r = 4, а для x30 r = 2. Логическое произведение, являющееся функцией всех n переменных, называется конституентой единицы (составляющей единицы). Смысл этого термина будет пояснен позже. Для n переменных существует 2n конституент единицы, причем на данном конкретном наборе лишь одна конституента единицы будет равна 1, все другие будут равны 0.

Два элементарных произведения одинакового ранга r называются соседними, если они являются функциями одних и тех же переменных и отличаются только знаком инверсии лишь у одной переменной. Например, x210 и x21x0 являются соседними, а x210 и 21x0 нет.

Логическая сумма любого числа переменных из конечного набора n переменных называется элементарной, когда слагаемыми в ней являются либо переменные либо их отрицания. Например, сумма 3+x2+x1+0 является элементарной, а 3x2+x0; 3+ +x0 и x3++0 нет.

Количество слагаемых в элементарной сумме называется ее рангом r. Так для 3+x2+x1+0 r = 4, а для x3+0 r = 2. Логическая сумма, являющаяся функцией всех n переменных, называется конституентой нуля (составляющей нуля). Смысл этого термина будет пояснен позже. Для n переменных существует 2n конституент нуля, причем на данном конкретном наборе лишь одна конституента нуля будет равна 0, все остальные будут равны 1.

Две элементарные суммы одинакового ранга r называются соседними, если они являются функциями одних и тех же переменных и отличаются только знаком инверсии лишь у одной переменной. Например, суммы 2+x1+0 и x2+x1+0 являются соседними, а 2+x1+0 и 2+1+x0 нет.

Сформулируем теперь важнейшие следствия из основных законов булевой алгебры, представив их в виде правил.

Правило старшинства логических операций

Пусть требуется определить значение истинности функции y = 3x2+x3 на наборе 11 (одиннадцать). Представив десятичное число 11 в виде двоичного числа 1011, мы определяем, что x3 = 1; x2 = 0; x1 = x0 = 1. Возникает вопрос: в каком порядке выполнять различные логические операции в рассматриваемой функции? Из законов инверсии вытекает, что старшей (первой) операцией является операция отрицания. Это значит, что операции логического умножения сложения нельзя производить, игнорируя знак отрицания над переменными, т.е. операцию отрицания надо выполнять в первую очередь.

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

Итак, если в логическом выражении встречаются все три операции И, ИЛИ, НЕ то сначала выполняется операция НЕ над отдельными переменными, затем операция И и в конце ИЛИ. Действия под групповым знаком инверсии выполняются по этому