Понятия элементарного логического произведения и элементарной логической суммы. Минимизация логических функций.

 

  Логическое произведение любого числа переменных из конечного набора п переменных называется элементарным, когда сомножителями в нем являются либо переменные, либо их отрицания.

   Например,  является элементарным, а  не являются элементарными.

  Количество сомножителей в элементарном произведении называется его рангом. Ранг будем обозначать буквой r.

   Так для   r = 4, а для   r = 2.

 

   Логическое произведение, являющееся функцией всех п переменных, от которых зависит логическая функция, называется конституентой единицы (составляющей единицы).

   Смысл этого термина будет пояснен позже.

     Для п переменных существует 2 ^п конституент единицы.

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

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

  Количество слагаемых в элементарной сумме называется ее рангом r. Так для    r = 4.

        

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

      Для п переменных существует 2 ^п   конституент нуля.

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

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

 

   

Правила склеивания

    Правило склеивания для элементарных произведений следует из распределительного закона первого рода, закона дополнительности и закона универсального множества:

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

    Пример.

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

Пример.

                                                                        

 

    Правила поглощения.

    Правило поглощения для суммы двух элементарных произведений следует из распределительного закона первого рода и законов универсального множества:

 

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

Пример:

    Правило поглощения для произведения элементарных сумм следует из распределительного закона второго рода и законов нулевого множества: