Способы представления ФАЛ. Переход от одной формы представления ФАЛ к другой

Пример 2.3

Пусть ФАЛ задана сокращенной записью СКНФ:

$$f(x,y,z)_{СКНФ} = \Pi (2,3,4,5,7)$$

Получить полную и сокращенную записи СДНФ этой функции.

Решение

Так как получение ТИ в данном примере не требуется, то можно использовать следующий подход.

Этап 1.

Получить сокращенную запись СДНФ этой функции. Для этого под знаком обобщенной дизъюнкции Σ перечислить все наборы, не входящие в сокращенную запись СКНФ:

$$f(x,y,z)_{СДНФ} = \sum (0,1,6)$$

Этап 2.

Получить полную запись СДНФ согласно указаниям примера 2.1. Результатом будет:

$$f(x,y,z)_{СДНФ} =\overline{x}\overline{y}\overline{z} \vee \overline{x}\overline{y} z \vee x y\overline{z}$$

Пример 2.4

Пусть ФАЛ задана в виде СДНФ:

$$f(x,y,z)_{СДНФ} =x \overline{y}\overline{z} \vee \overline{x}\overline{y} z \vee \overline{x} y\overline{z} \vee xyz$$

Получить полную и сокращенную записи СКНФ этой функции.

Решение

Получим сокращенную запись СДНФ функции, для чего сначала определим двоичные эквиваленты наборов, соответствующих каждому конъюнктивному члену в полной записи СДНФ этой функции, поставив 1 под переменными, входящими в запись в прямом виде, и 0 под переменными, представленными в инверсном виде:

Затем представим эти наборы в десятичном коде и перечислим их под знаком обобщенной дизъюнкции Σ:

$$f(x,y,z)_{СДНФ}=\sum (4,1,2,7)$$

По полученной сокращенной записи СДНФ функции получим сокращенную запись СКНФ, перечислив под знаком обобщенной конъюнкции Π номера наборов, не вошедших в сокращенную запись СДНФ:

$$f(x,y,z)_{СКНФ}=\Pi (0,3,5,6)$$

По сокращенной записи СКНФ получим ее полную запись согласно методике, изложенной в примере 2.1.

$$f(x,y,z)_{СКНФ} =(x \vee y \vee z) \And (x \vee \overline{y} \vee \overline{z}) \And (\overline{x} \vee y \vee \overline{z}) \And (\overline{x} \vee \overline{y} \vee z)$$

Пример 2.5

Пусть ФАЛ задана в виде СКНФ:

$$f(x,y,z)_{СКНФ} =(x \vee \overline{y} \vee z) \And (x \vee \overline{y} \vee \overline{z}) \And (\overline{x} \vee y \vee \overline{z})$$

Получить полную и сокращенную записи СДНФ этой функции.

Решение

Получим сокращенную запись СКНФ этой функции. Для этого сначала определим двоичные эквиваленты наборов, соответствующих каждому дизъюнктивному члену в полной записи СДНФ этой функции, поставив 0 под переменными, входящими в запись в прямом виде, и 1 под переменными, представленными в инверсном виде:

Затем представим эти наборы в десятичном коде и перечислим их под знаком обобщенной конъюнкции Π:

$$f(x,y,z)_{СКНФ}=\Pi (2,3,5)$$

По полученной сокращенной записи СКНФ функции получим сокращенную запись СДНФ, перечислив под знаком обобщенной дизъюнкции Σ номера наборов, не вошедших в сокращенную запись СКНФ:

$$f(x,y,z)_{СДНФ}=\sum (0,1,4,6,7)$$

По сокращенной записи СДНФ получим ее полную запись согласно методике, изложенной в примере 2.1:

$$f(x,y,z)_{СКНФ}=\overline{x}\overline{y}\overline{z} \vee \overline{x}\overline{y} z \vee x\overline{y}\overline{z} \vee x y\overline{z} \vee x y z$$

Пример 2.6

Пусть ФАЛ задана в виде дизъюнктивной нормальной формы, не являющейся совершенной. Например:

$$f(x,y,z)=x \vee xy \vee xyz$$

Получить полную и сокращенную записи СКНФ этой функции.

Решение

Для решения этой задачи можно сначала получить СДНФ функции.

Для получения СДНФ необходимо обеспечить зависимость каждого конъюнктивного терма от всех переменных, от которых зависит функция. Необходимые преобразования базируются на следующей эквивалентности:

$$a =a b \vee a\overline{b}$$

Тогда, последовательно повышая ранг для термов, зависящих не от всех переменных, получим:

$$\overline{x} =\overline{x} y \overline{x}\overline{y} =\overline{x}yz \vee \overline{x} y\overline{z} \vee \overline{x}\overline{y} z \vee \overline{x}\overline{y}\overline{z}$$ $$xy = xyz \vee x y\overline{z}$$ $$f(x,y,z) =\overline{x} \vee xy \vee x\overline{y}\overline{z} = \overline{x}yz \vee \overline{x} y\overline{z} \vee \overline{x}\overline{y} z \vee \overline{x}\overline{y}\overline{z} \vee xyz \vee x y\overline{z} \vee x y\overline{z}$$

После выполнения преобразования на основе эквивалентности

$$a \vee a = a$$

получим полную, а затем и сокращенную записи СДНФ:

$$f(x,y,z)_{СДНФ} =\overline{x}yz \vee \overline{x} y\overline{z} \vee \overline{x}\overline{y} z \vee \overline{x}\overline{y}\overline{z} \vee xyz \vee x y\overline{z}$$ $$f(x,y,z)_{СДНФ} = \sum (3,2,1,0,7,6)$$

Последующие шаги по решению поставленной задачи рассмотрены ранее.

В результате получим:

$$f(x,y,z)_{СКНФ} = \Pi (4,5)$$ $$f(x,y,z)_{СКНФ} = (\overline{x} \vee y \vee z) \And (\overline{x} \vee y \vee \overline{z})$$

Пример 2.7

Пусть ФАЛ задана в виде конъюнктивной нормальной формы, не являющейся совершенной. Например:

$$f(x,y,z)= (\overline{x} \vee y) \And (\overline{x} \vee \overline{z} )$$

Получить полную и сокращенную записи СДНФ этой функции.

Решение

Решение этой задачи аналогично предыдущей.

Для получения СКНФ необходимо использовать следующие эквивалентности:

$$a = (a \vee b) \And (a \vee \overline{b})$$ $$a \And a = a$$

Тогда получим:

$$\overline{x}Vy = (\overline{x} \vee y \vee z) \And (\overline{x} \vee y \vee \overline{z})$$ $$\overline{x} \vee \overline{z} = (\overline{x} \vee y \vee \overline{z}) \And (\overline{x} \vee \overline{y} \vee \overline{z})$$ $$f(x,y,z) = (\overline{x} \vee y \vee z) \And (\overline{x} \vee y \vee \overline{z}) \And (\overline{x} \vee y \vee \overline{z}) \And (\overline{x} \vee \overline{y} \vee \overline{z})$$ $$f(x,y,z)_{СКНФ} = (\overline{x}VyVz) \And (\overline{x}VyV\overline{z}) \And (\overline{x} \vee \overline{y} \vee \overline{z})$$ $$f(x,y,z)_{СКНФ} = \Pi (4,5,7)$$

Исходя из полученной СКНФ функции, определим ее СДНФ:

$$f(x,y,z)_{СДНФ} = \sum (0,1,2,3,6)$$ $$f(x,y,z)_{СДНФ} =\overline{x}\overline{y}\overline{z} \vee \overline{x}\overline{y} z \vee \overline{x} y\overline{z} \vee \overline{x} y z \vee x y\overline{z}$$

Пример 2.8

$$Пусть ФАЛ задана в виде совершенной дизъюнктивной нормальной формы:$$ $$f(x,y,z)_{СДНФ} =\overline{x}\overline{y} z \vee x\overline{y} z \vee \overline{x} y\overline{z}$$

Представить запись этой функции в базисе "Штрих Шеффера".

Решение

Для перехода от представления ФАЛ в виде СДНФ к базису "Штрих Шеффера" необходимо выполнить следующее.

Этап 1.

Заменить все знаки дизъюнкции и конъюнкции на знак функции "Штрих Шеффера". При этом вследствие невыполнения для данной функции ассоциативного закона (см. (1.32)) каждый конъюнктивный член должен быть заключен в скобки:

$$f(x,y,z) = (\overline{x} /\overline{y} / z ) / (x /\overline{y} / z) / (x / y /\overline{z})$$

Этап 2.

Выразить функцию отрицания через функцию "Штрих Шеффера" согласно (1.29), также заключая эту операцию в скобки:

$$f(x,y,z) = ((x / x) / (y / y) / z) / (x / (y / y) / z) / (x / y / (z / z))$$

Пример 2.9

Пусть ФАЛ задана в виде:

$$f(x,y,z)_{СДНФ} = x \vee x\overline{y} \vee \overline{x} y\overline{z}$$

Представить запись этой функции в базисе "Штрих Шеффера".

Решение

Особенность выполнения первого этапа обусловлена наличием в записи функции члена x, не являющегося конъюнкцией каких-либо переменных. Для приведения этой функции к дизъюнктивной нормальной форме воспользуемся выражением (1.10):

$$f(x,y,z)_{СДНФ} = xx \vee x\overline{y} \vee \overline{x} y\overline{z}$$

Дальнейшие действия в этом примере полностью совпадают с примером 2.8.

Результатом выполнения этапа 1 будет

$$f(x,y,z) = (x / x) / (x /\overline{y}) / (\overline{x} / y /\overline{z}),$$

а окончательный результат:

$$f(x,y,z) = (x / x) / (x / (y / y)) / ((x / x) / y / (z / z))$$

Краткие итоги

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

Контрольные вопросы и упражнения

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

Каким образом составляется таблица истинности ФАЛ?

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

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

Как можно получить совершенную дизъюнктивную нормальную форму, используя таблицу истинности этой ФАЛ?

Представьте СДНФ функции "суммы по модулю 2".

Как можно получить совершенную конъюнктивную нормальную форму, используя таблицу истинности этой ФАЛ?

Как можно получить совершенную конъюнктивную нормальную форму, используя таблицу истинности ФАЛ на основе ее совершенной дизъюнктивной нормальной формы?

Получите СДНФ ФАЛ, СКНФ которой выглядит следующим образом: f(a,b,c,d) = Π(2, 4, 6, 7, 8, 10 , 11, 14).

Составьте таблицу истинности логической функции, совершенная дизъюнктивная форма которой имеет вид: f(x, y, z) = Σ(1, 2, 6, 7).