Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

СТРАТЕГИЧЕСКИЙ МЕНЕДЖМЕНТ.

Читайте также:
  1. Антикризисный менеджмент. Характеристики антикризисного управления
  2. В реальной практике стратегический и оперативный контроллинг достаточно тесно взаимодействуют друг с другом в процессе реализа­ций функций менеджмента (Приложение 4). СХЕМА
  3. Внешняя и внутренняя среда в стратегическом менеджменте. Стратегический анализ является базой для принятия стратегических решений по управлению предприятием.
  4. Классификация налогов. Налоговый менеджмент.
  5. Лекция 11. Стратегический менеджмент. Основные подходы к выбору стратегии
  6. по направлению 38.03.02 –менеджмент. Общий профиль
  7. Понятия: Военно-стратегический паритет; денонсация.
  8. Понятия: Стратегический паритет; разрядка международной на­пряженности; Совещание по безопасности и сотрудничест­ву в Европе; программа СОИ.
  9. Самоменеджмент.
  10. Стратегический и оперативно-тактический финансовый менеджмент. Управление обеспечением финансовыми ресурсами

 

Появляется возможность упрощать и преобразовывать БФ к требуемому виду.

 

§ 2. Нормальные формы БФ.

 

Введем некоторые стандартные виды БФ, к которым будем их преобразовывать.

Определение: Выражение вида (отрицание может стоять на любых местах) называется элементарной конъюнкцией (ЭК).

Определение: ЭК называется правильной, если в ней переменные не повторяются.

ЭК называется полной, если в ней участвуют все n переменных.

Пример:

x,y,z – три переменные. Тогда

- Э К (правильна, но не полна).

- ЭК (правильна и полна).

- ЭК (не правильная, но полная)

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

Примеры:

x,y,z,t – четыре переменные. Тогда

– ДНФ (не совершенная).

– СДНФ.

Теорема: Всякая БФ может быть представлена в виде СДНФ и притом единственным образом.

Доказывается с помощью таблицы истинности произвольной БФ.

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

Для этого разработан естественный алгоритм:

1. Добьёмся, чтобы в формуле остались только дизъюнкции, конъюнкции и отрицания над аргументами (с помощью тождеств 1–8).

2. Раскроем скобки по тождеству 9 и получаем ДНФ.

3. Делаем все ЭК правильными (с помощью вторых частей тождеств 10 и 11).

4. Делаем все ЭК полными (если нет Х, то введём его искусственно, домножив на

число согласно тождеству 11).

Возвращаемся к шагу 2.

5. Через конечное число циклов получим СДНФ.

6. Ликвидируем одинаковые члены (с помощью тождества X Ú X=X, то есть из двух или нескольких одинаковых ЭК оставляем одну).

 

Аналогично вводится другая нормальная форма – СКНФ.

Определение. Выражение вида (отрицание может стоять на любых местах) называется элементарной дизъюнкцией (ЭД).

Конъюнкция нескольких ЭД называется КНФ.

Если к тому же все ЭД правильны и полны, то она называется СКНФ.

Пример:

x,y,z,t – четыре переменные. Тогда

– КНФ (не совершенная).

– СКНФ.

Мы научимся получать СКНФ с помощью СДНФ, не используя ни таблиц истинности, ни новых алгоритмов. Единственная идея – превращать дизъюнкции в конъюнкции и наоборот.

 

§ 3. Двойственность БФ.

 

Определение: Пусть дана БФ f(x1, …,xn). Двойственной к ней называется БФ f*, заданная формулой .

Сразу же заметим, что из тождества 1 вытекает, что всегда , то есть двойственную к двойственной БФ искать уже не надо – она всегда равна исходной функции.

Примеры вычисления двойственных БФ:

1) Для будет .

 

Двойственной к дизъюнкции является конъюнкция.

Так как (f*)*=f, то верно и обратное: двойственной к конъюнкции является дизъюнкция.

2) Для будет .

Итак, отрицание само себе двойственно (как говорят, самодвойственно).

3) Для будет .

Теорема: (закон двойственности) Двойственная к композиции БФ (т.е. сложной функции) - есть соответствующая композиция двойственных функций.

Пример: Пусть f=g Ú h – композиция g, h и дизъюнкции.

Тогда по закону двойственности f*=g* Ù h*.

 

Следствие 1: Композиция самодвойственных функций также самодвойственна.

Следствие 2: Если БФ является композицией дизъюнкций, конъюнкций и отрицаний, то для получения двойственной достаточно заметить дизъюнкции на конъюнкции и наоборот.

Пример: Если , то ..

Следствие 3: Двойственная к СДНФ является СКНФ.

Вывод: Чтобы получить СКНФ для данной функции f, следует

1. Найти двойственную БФ f*.

2. Привести f* к СДНФ.

3. Ещё раз взять двойственную, так как (f*)*=f, то получим СКНФ для f.

 

§4.5 Арифметический подход к БФ.

 

Мы уже заменили конъюнкцию умножением, попытаемся ввести сложение:

Ясно, что 0+0=1, 0+1=1, 1+0=1, но чему равно 1+1?

Альтернатива: либо принять 1+1=1, либо 1+1=0.

В первом случае мы получим дизъюнкцию,

Во втором – исключающее «или».

Исторически победил второй подход

Итак:

 

x y x+y
     
     
     
     

 

То есть x+y=x Δ y.

Такое сложение совпадает с известным в теории чисел сложением по модулю 2:

X+Y mod 2 – это остаток деления на числа x+y на 2.

Заметим, что всегда x+x=0, f+f=0.

 

Определение: Любая композиция сложения, умножения и констант называется многочленом.

Примеры: x+y+1, xy+x+1, xyz+xy+z, x+x+y+y, xy+yx+1, 1x+0=x.

Определение: Многочленом Жегалкина называется функция вида , где суммирование ведётся по некоторому множеству различных наборов (i1, i2, …, ik),

в каждом из которых ни один индекс не повторяется.

Пример: xxy+xyy+x – не многочлен Жегалкина;

x+y+1 – многочлен Жегалкина.

 

Теорема: Всякая БФ может быть представлена в виде многочлена Жегалкина и притом единственным образом.

Доказательство:

Мы уже знали, что любую БФ можно выразить через основные логические операции (отрицание, дизъюнкция и конъюнкция). Представим основные логические операции в виде многочленов Жегалкина:

xy – готовый многочлен Жегалкина;

– многочлен Жегалкина;

– многочлен Жегалкина.

 

Поскольку любая БФ есть композиция основных логических операций, подставив вместо них многочлены, получим композицию многочленов т. е новый многочлен.

Упрощая его получим многочлен Жегалкина.

 

СТРАТЕГИЧЕСКИЙ МЕНЕДЖМЕНТ.




Дата добавления: 2014-12-20; просмотров: 24 | Поможем написать вашу работу | Нарушение авторских прав




lektsii.net - Лекции.Нет - 2014-2024 год. (0.012 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав