Функционально полные системы логических функций. Алгебраический подход

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

    ____

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

    Пример  Развернуть элементарную конъюнкцию f(x₁,x₂,x₃,x₄) = x₁x₃ в логическую сумму конституент единицы.

    Решение. Ранг конституенты единицы для данной функции равен 4. Производим развертывание  исходной конъюнкции поэтапно в соответствии с правилом развертывания:

    1-й  этап- f(x₁,x₂,x₃,x₄) = x₁1x₃1.

    2-й  этап-- f(x₁,x₂,x₃,x₄) =

    3-й  этап-- f(x₁,x₂,x₃,x₄)=

    = что и требовалось получить.

    Если  членами преобразуемого выражения  являются элементарные дизъюнкции, то переход от них к конституентам  нуля производится также в три  этапа по следующему правилу:

    в развертываемую элементарную дизъюнкцию ранга r в качестве дополнительных слагаемых вводится п-r нулей;

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

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

    Пример. Развернуть элементарную дизъюнкцию f(x₁,x₂,x₃,x₄) = x₃x₄ в логическое произведение конституент нуля.

    Решение. Ранг конституенты нуля п = 4. Далее производим развертывание исходной дизъюнкции поэтапно в соответствии с правилом развертывания:

    1-й  этап -- f(x₁,x₂,x₃,x₄) =00x₃x₄;

    2-й  этап -- f(x₁,x₂,x₃,x₄) =

    3-йэтап--f(x₁,x₂,x₃,x₄)=

    что и требовалось получить.

    Проверить правильность проведенных преобразований можно при помощи правила склеивания.

    3. Функционально полные системы логических функций. Анализ принадлежности переключательных функций замкнутым классам показывает, что существуют две переключательные функции f₈ и f₁₄, не принадлежащие ни одному классу. Согласно теореме о функциональной полноте, каждая из этих функций образует функционально полную систему логических связей и используя только одну из них можно представить любую, сколь угодно сложную переключательную функцию.

    Операция  Пирса (стрелка Пирса) реализует  функцию, которая принимает значение, равное единице только в том случае, когда все ее аргументы равны 0 (ИЛИ-НЕ), что может быть записано в ОФПС для функции двух переменных следующим образом:

    (7)

    Используя операции суперпозиции и подстановки  можно показать, что операция Пирса  может быть реализована для  n аргументов:

    (8)

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

    представить переключательную функцию f в конъюнктивной нормальной форме;

    полученное  выражение представить в виде (поставить два знака отрицания);

    применить правило Де Моргана.

    Например, для того чтобы представить функцию 

    в базисе Пирса, необходимо выполнить  следующие преобразования:

    Для представления полученного выражения  в базисе Пирса воспользуемся  соотношением (7):

    _____________.

    Операция  Шеффера (штрих Шеффера) реализует  функцию, которая принимает значение, равное нулю, только в том случае, когда все ее аргументы равны 1 (И-НЕ), что может быть записано в ОФПС для функции двух переменных следующим образом:

    (9)

    Используя операции суперпозиции и подстановки, можно показать, что операция Пирса  может быть реализована для  n аргументов:

    f(x₁,x₂,…,x_n)= x₁x₂…x_n = (10)

    Для представления переключательной функции  в базисе Шеффера необходимо выполнить  следующие действия:

    представить переключательную функцию f в дизъюнктивной нормальной форме;

    полученное  выражение представить в виде (поставить два знака отрицания);

    применить правило Де Моргана.

    Например, для того чтобы представить функцию 

    в базисе Шеффера, необходимо выполнить  следующие преобразования:

    Для представления полученного выражения  в базисе Шеффера воспользуемся  соотношением (9):

    f(x₁,x₂,x₃,x₄)=(x₄x₂)(x₃x₁).

    4. Таблица истинности

    Любая логическая функция нескольких переменных однозначно задается в виде таблицы истинности, в левой части которой выписаны все возможные наборы значений её аргументов x1, …, xn, а правая часть представляет собой столбец значений функций, соответствующих этим наборам. Набор значений переменных, на котором функция принимает значение f = 1, называется единичным набором функции f; множество всех единичных наборов – единичным множеством функции f. Аналогично набор значений, на котором f = 0, называется нулевым набором функции f, а множество нулевых наборов – нулевым множеством. В общем случае таблица истинности для функции от п переменных должна иметь 2n строк.

    Логические операции и таблицы истинности.

    4. 1 Логическое умножение или конъюнкция:

    Конъюнкция - это сложное логическое выражение, которое считается истинным в том и только том случае, когда оба простых выражения являются истинными, во всех остальных случаях данное сложное выражение ложно. 
Обозначение: F = A & B.

    Таблица истинности для конъюнкции

 

    4.2 Логическое сложение или дизъюнкция:

    Дизъюнкция - это сложное логическое выражение, которое истинно, если хотя бы одно из простых логических выражений истинно и ложно тогда и только тогда, когда оба простых логических выражения ложны. 
Обозначение: F = A + B.

    Таблица истинности для дизъюнкции

 

    4.3 Логическое отрицание или инверсия:

    Инверсия - это сложное логическое выражение, если исходное логическое выражение истинно, то результат отрицания будет ложным, и наоборот, если исходное логическое выражение ложно, то результат отрицания будет истинным. Другими простыми слова, данная операция означает, что к исходному логическому выражению добавляется частица НЕ или слова НЕВЕРНО, ЧТО.

    Таблица истинности для инверсии

 

    4.4 Логическое следование или импликация:

    Импликация - это сложное логическое выражение, которое истинно во всех случаях, кроме как из истины следует ложь. То есть данная логическая операция связывает два простых логических выражения, из которых первое является условием (А), а второе (В) является следствием.

    Таблица истинности для импликации

 

    4.5 Логическая равнозначность или эквивалентность:

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

    Таблица истинности для эквивалентности

 

    Порядок выполнения логических операций в сложном логическом выражении:

1) Инверсия; 
2) Конъюнкция; 
3) Дизъюнкция; 
4) Импликация; 
5) Эквивалентность.

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

 

ЛИТЕРАТУРА

    1. Белоусов А.И., Ткачев С.Б. Дискретная математика: Учебник для ВУЗов / Под ред. В.С. Зарубина, А.П. Крищенко.- М.: изд-во МГТУ им. Н.Э. Баумана, 2001.- 744 с. (Сер. Математика в техническом университете; Вып XIX).