Основные соотношения, правила и теоремы

Совокупность конкретных значений логических переменных, от которых зависит булева функция, называется наборомлогическихпеременных. Если булева функция зависит, например, от трех переменных x₂,x₁ и x₀, тогда x₂ = 0, x₁ = 1, x₀ = 1 является набором. Наборы могут быть представлены различными способами. Тот же набор можно представить как 0,1,1 или просто 011. Рассматривая последнее представление как двоичное число, можно записать его в виде десятичного эквивалента 3 = 0^.2²+1^.2¹+1^.2⁰. Отсюда видно, что логическим переменным, как и разрядам двоичного числа, можно условно присвоить “веса”: для x₀ вес будет 2⁰ = 1, для x₁ - 2¹ = 2, для x₂ - 2² = 4 и т.д. Именно поэтому логические переменные удобно обозначать индексированными буквами, начиная с индекса 0 для младшей переменной, 1 для следующей переменной и т.д. до индекса n-1, если функция зависит от n переменных. При таком обозначении индекс переменной совпадает с показателем степени основания двоичной системы счисления, т.е. характеризует вес переменной. Так для переменной x₅ вес будет равен 2⁵ = 32.

Если функция алгебры логики зависит от n переменных, то всего для них существует 2ⁿ наборов, так как добавление одной переменной увеличивает число наборов в два раза. Одна переменная имеет два набора: 0 и 1, две переменные - четыре: 0 = 00, 1= 01, 2 =10, 3 = 11 и т.д. Десятичный эквивалент набора логических переменных называется номеромнабора. Наборы можно рассматривать как двоичныевекторы Хi, где i- номер набора, однако надо помнить, что они не являются векторами в классическом смысле, так как над ними нельзя выполнять векторные операции. Число переменных, имеющих в наборе значение 1, называется весом набора (не нужно путать с двоичным весом переменных). Вес набора удобно изображать римскими цифрами, так для n = 3 имеем: набор 000 с весом 0; наборы 001, 010, 100 с весом I; наборы 011, 101, 110 с весом II и набор 111 с весом III [2,3].

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

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

Логическая сумма любого числа переменных из конечного набора n переменных называется элементарной, когда слагаемыми в ней являются либо переменные, либо их отрицания. Например, сумма ₃+x₂+x₁+₀ является элементарной, а ₃x₂+x₀; ₃+ +x₀ и x₃++₀ нет.

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

Две элементарные суммы одинакового ранга r называются соседними, если они являются функциями одних и тех же переменных и отличаются только знаком инверсии лишь у одной переменной [7,9].