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

Множество логических переменных - высказываний о событиях {x1, x2, …, xn} в контексте некоторого приложения образует пространство событий размерности n. Точка этого пространства является ситуацией.

Можно записать произвольную композицию на основе заданного множества переменных-высказываний и логических операций, например, ¬

xyz,

(x

y) (yz). Почему первую композицию следует считать бессмысленной? По-видимому, потому, что она содержит конструкции, не определенные в терминах алгебры логики, и не может быть исчерпывающим образом преобразована в таковые на основе применения (1)-(10). Тогда вторая приведенная композиция имеет смысл, т.к. полностью подвержена основным определениям операций алгебры логики и правилам преобразования в ней.

Высказывания (о событиях) в качестве переменных могут входить в состав сложных формирований - логических функций, принимающих (булевы) значения 1 (ИСТИНА) или 0 (ЛОЖЬ).

Определение 3. Имеющая смысл линейно-скобочная композиция операций ¬,

, над переменными-высказываниями x1, x2, …, xn, образующими пространство событий, задает логическую функцию f(x1, x2, …, xn), принимающую для различных ситуаций, т.е. наборов значений переменных, значения 0 или 1.

Таким образом, логическая функция является булевой функцией ситуаций.

В классической теории булевых функций [1] показывается, что каждая такая функция может быть представлена дизъюнктивной и (или) конъюнктивной нормальной формой. В первом случае ее структура выражается как дизъюнкция конъюнкций, во втором - как конъюнкция дизъюнкций.

Рассмотрим две логические функции

Y = x1

(x2x1 x3) и

Z = (x1

x2)( x3 x2).

Выражение Y представлено дизъюнктивной нормальной формой (ДНФ). Выражение Z соответствует конъюнктивной нормальной форме (КНФ), практически не применяемой.

Преобразуем

Z = (x1

x3)(x1 x2)(x2x3). (Учитывается, что x2x2 = 0.)

Это - дизъюнктивная нормальная форма.

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

(1.11)

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

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

0	0	0	0	1
0	0	1	0	0
0	1	0	0	0
0	1	1	1	0
1	0	0	1	1
1	0	1	1	0
1	1	0	1	1
1	1	1	1	1

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



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

, что совпадает с видом Y.

Аналогично,



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



Из табл. 1.1 видно, что все значения Z и Z* от одних и тех же наборов значений переменных совпадают. Однако Z* образуется только двумя "слагаемыми" Z. Конъюнкция x1x3 оказалась "лишней", не влияющей на результат. Это говорит о том, что формирование аналитического вида логической функции по ее табличному заданию, с помощью СДНФ, позволяет получить простейшее (лаконичное) представление, без лишних конструкций, не влияющих на результаты вычислений.

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




Содержание раздела

---

---

---

Главная сайта

---