Логические нейронные сети


Логические функции высказываний - часть 2


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

 \begin{array}{rl} f=&f(0, 0, 0) \wedge (\overline{x_1}\wedge\overline{x_2}\wedge\overline{x_3}) \vee f(0, 0, 1) \wedge (\overline{x_1}\wedge\overline{x_2}\wedge x3)\vee\\ & f(0, 1, 0)\wedge (\overline{x_1}\wedge x_2 \wedge \overline{x_3}) \vee f(0, 1, 1)\wedge (\overline{x_1}\wedge x2\wedge x3)\vee\\ & f(1, 0, 0)\wedge (x1 \wedge \overline{x_2}\wedge\overline{x_3}) \vee f(1, 0, 1)\wedge (x1\wedge \overline{x_2}\wedge x3)\vee \\ & f(1, 1, 0) \wedge (x1 \wedge x2 \wedge \overline{x_3}) \vee f(1, 1, 1) \wedge (x1 \wedge x2 \wedge x3)\end{array}

(1.11)

Для всех значений переменных рассчитаем значения приведенных выше логических функций Y и Z (табл. 1.1).

Таблица 1.1. Значения логических функций

x1x2x3YZ
00001
00100
01000
01110
10011
10110
11011
11111

Попытаемся построить приведенные выше функции Y и Z на основе их СДНФ, т.е. проверим правильность такого подхода:

Y^* = \overline{x_1}\wedge x_2 \wedge x_3 \vee x_1 \wedge \overline{x_2}\wedge \overline{x_3} \vee x_1 \wedge \overline{x_2}\wedge x_3 \vee x_1 \wedge x_2 \wedge \overline{x_3}\vee x_1 \wedge x_2 \wedge x_3

После эквивалентных преобразований (начинающихся с вынесения x1 "за скобку") получим

Y^* = \overline{x_1}\wedge x_2 \wedge x_3 \vee x_1
, что совпадает с видом Y.

Аналогично,

 Z^* = \overline{x_1}\wedge \overline{x_2} \wedge \overline{x_3} \vee x_1 \wedge \overline{x_2}\wedge\overline{x_3} \vee x_1 \wedge x_2 \wedge \overline{x_3} \vee x_1 \wedge x_2 \wedge x_3

После эквивалентных преобразований находим

Z^* = (\overline{x_2} \wedge \overline{x_3}) \vee (x_1 \wedge x_2)

Из табл. 1.1 видно, что все значения Z и Z* от одних и тех же наборов значений переменных совпадают. Однако Z* образуется только двумя "слагаемыми" Z. Конъюнкция x1

x3 оказалась "лишней", не влияющей на результат. Это говорит о том, что формирование аналитического вида логической функции по ее табличному заданию, с помощью СДНФ, позволяет получить простейшее (лаконичное) представление, без лишних конструкций, не влияющих на результаты вычислений.

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

f = f(x_1\wedge x_2\wedge 0\wedge 0)\wedge \overline{x_3} \wedge \overline{x_4} \vee f(x_1\wedge x_2\wedge 0\wedge 1)\wedge\\ \wedge \overline{x_3}\wedge x_4 \vee f(x_1\wedge x_2\wedge 1\wedge 0)\wedge x_3\wedge _ \vee f(x_1\wedge x_2\wedge 1\wedge 1) \wedge x_3 \wedge x_4.




Начало  Назад  Вперед



Книжный магазин