книги из ГПНТБ / Алферова, З. В. Математическое обеспечение экономических расчетов с использованием теории графов

3. В. АЛФЕРОВА

МАТЕМАТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ЭКОНОМИЧЕСКИХ РАСЧЕТОВ С ИСПОЛЬЗОВАНИЕМ ТЕОРИИ ГРАФОВ

сСТАТИСТИКА» МОСКВА 1974

иИ £ я И О i С С С Р

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

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

С целью облегчения практической реализации методов решения указанных задач приводятся соответствующие алгоритмы в языке АЛГЭК-С, апробированные на машине «Минск-22».

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

© Издательство «Статистика», 1974 г.

ВВЕДЕНИЕ

щих машин ведет к подлинной революции не только в технологии производства, но и в экономике, планировании, учете, проектноконструкторских разработках и в самих научных исследовани* ях [1].

В Директивах XXIV съезда КПСС по пятилетнему плану раз' вития народного хозяйства СССР на 1971—1975 годы подчерки^ вается, что «совершенствование системы планирования и управле­ ния народным хозяйством в современных условиях требует широ­

3

§ 1. 1. ЭЛЕМЕНТЫ АЛГЕБРЫ ЛОГИКИ

В алгебре логики объектами, над которыми произво­ дятся операции, являются высказывания, принимающие значения «истинно» или «ложно».

Отрицание является одной из простейших операций над выска­ зываниями. Будем обозначать операцию отрицания, помещая знак отрицания над высказыванием. Так, если А есть истинное выска­ зывание, то А обозначает отрицание А и читается «не А».

Действие операции отрицания представляется таблицей:

Другой распространенной операцией алгебры логики является конъюнкция. Конъюнкция высказываний А и В будет обозначать­

5

Дизъюнкцией высказываний А и В называется операция AWB. Высказывание AVB истинно, если истинно хотя бы одно из выска­ зываний А или В или истинны оба высказывания.

Эта операция имеет следующую таблицу истинности:

6

Сложные логические высказывания строятся из простых вы­ сказываний с помощью логических операций.

При определении истинности сложного высказывания или уп­ рощении сложных логических выражений соблюдается следующий порядок выполнения логических операций: в первую очередь рас­ крываются скобки общепринятым порядком (от самых внутрен­ них к внешним), во вторую очередь выполняются операции логи­ ческого отрицания, в третью — конъюнкции, в четвертую — дизъ­ юнкции, в пятую — импликации, в шестую — эквивалентности. Внутри скобок действия выполняются в том же порядке.

Всякое сложное высказывание, составленное из некоторых ис­ ходных высказываний посредством применения рассмотренных логических операций, принято называть формулой алгебры выска­ зываний.

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

1.A V B = B V A

2.А Л В = ВАА

Эта формула означает, что для логического умножения спра­ ведлив распределительный закон по отношению к логическому сложению.

8.AW(BAC)^(AWB)A(AWC)

Эта формула означает, что в алгебре логики распределитель­ ный закон для логического сложения справедлив также по отно­ шению к логическому умножению, чего нет в обычной алгебое.

9.A V A = 1

10.ААА = А

11.А = А

12.A V 1 = 1

13.AV0 = A

14.А Л 1 = А

15.АЛ0==0

16.A A ( A V B ) = А

17.A V (АЛВ) = А

18. A A ( A V B ) = ААВ

7

2 1 . A V ( А Л В ) = = A V B

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

22. A V B = АЛВ

23. a 7 v b = a v b

24. A = d B = = A V B

25. ( A = B ) = ( A V B ) A ( A V B )

Приведенные формулы легко проверяются на основании таблиц истинности операций.

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

Различают нормально-дизъюнктивную и нормально-конъюнк­ тивную форму. Под нормально-дизъюнктивной формой понимается представление сложного логического высказывания в виде дизъ­ юнкции конъюнкций высказываний. Например, высказывание AABVCAAVBAC является сложным высказыванием, представ­ ленным в нормально-дизъюнктивной форме.

Под нормально-конъюнктивной формой понимается представ­ ление сложного логического высказывания в виде конъюнкции дизъюнкций высказываний. Примером нормально-конъюнктивной формы высказывания может служить высказывание (AVB)A A{AVB)A(AVB).

В нормально-дизъюнктивную или нормально-конъюнктивную форму можно привести сколь угодно сложное высказывание, поль­ зуясь следующими правилами:

1. В первую очередь заменяем операции импликации и эквива­ лентности операциями отрицания, дизъюнкции, конъюнкции в соответствии с формулами равносильности.

2. Затем производим преобразования, исключающие операцию

8

Формулы равносильности используются для приведения слож­ ного высказывания к виду, содержащему меньшее количество составляющих его простых высказываний.

Данный процесс получил название минимизации и широко ис­ пользуется при анализе электронных схем. В последнее время он начал применяться при минимизации состава экономической ин­ формации, например при определении минимального состава 'рек­ визитов в первичных документах.

§ 1. 2. ПОНЯТИЯ ЛИНЕЙНОЙ АЛГЕБРЫ

9