Математичекие основы теории систем

10

1

0

1

0

*

*

*

*

*

*

*

8

11

1

0

1

1

*

*

*

*

*

*

*

9

12

1

1

1

0

*

*

*

*

*

*

*

10

13

1

1

1

1

*

*

*

*

*

*

*

11

14

1

0

0

0

*

*

*

*

*

*

*

14

15

1

0

0

1

*

*

*

*

*

*

*

12

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

2.2 Составление логических функций

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

2.2.1 Дизъюнктивная совершенная нормальная форма

Введем понятие логической степени, которою будем обозначать . Тогда, логическая степень будет определяться по формуле (2.1)

(2.1)

Любую функцию от n переменных можно представить в виде (см.(2.2))

(2.2)

означает, что коллективные члены формируются только для таких наборов (α1, α2,…, αn) для которых функция принимает единичное значение.

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

а) Выбрать в таблице истинности все наборы, в которых функция обращается в единицу.

б) Выписать конъюнкции, соответствующие этим наборам аргументов. При этом если аргумент хi входит в данный набор как «1», то он вписывается без изменения в конъюнкцию, соответствующую данному набору. Если же входит в данный набор как «0», то в соответствующую конъюнкцию вписывается его отрицание.

в) Все полученные конъюнкции объединяют знаком дизъюнкции.

Для функции у3 СДНФ будет иметь вид:

2.2.2 Конъюнктивная совершенная нормальная форма

Любую функцию от n переменных можно представить в виду:

f=

означает, что коллективные члены формируются только для таких наборов, (α1, α2, …, αn) для которых функция принимает нулевое значение.

Следующий алгоритм позволяет перейти от табличной записи функции к СКНФ:

а) Выбрать в таблице истинности все наборы, в которых функция обращается в «0».

б) Выписать дизъюнкции, соответствующие этим наборам аргументов. При этом если аргумент хi входит в данный набор как «0», то он вписывается без изменения в дизъюнкцию, соответствующую данному набору. Если же входит в данный набор как «1», то в соответствующую дизъюнкцию вписывается его отрицание.