logo
ГОСы - ответы [2012]

Бинарные функции

При n = 2 число булевых функций равно 22² = 24 = 16.

Таблица значений булевых функций от двух переменных:

x

y

0

x↓y

x←y

x̅

x→y

y̅

x⊕y

x|y

x&y

x≡y

y

x→y

x

x←y

x∨y

1

0

0

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

1

0

0

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1

1

1

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

2.1.5 Основные булевы тождества.

  1. (ассоциативность)

  2. (коммутативность)

  3. (свойство нуля)

  4. (закон поглощения для 1)

  5. (ассоциативность)

  6. (коммутативность)

  7. (свойство нуля по умножению)

  8. (свойство нейтральности 1 по умножению)

  9. (дистрибутивность)

  10. (дистрибутивность 2)

  11. (закон поглощения)

  12. ( Законы

  13. де Моргана)

  14. (закон снятия двойного отрицания)

  15. (tertium non datur – третьего не дано)

  16. (ассоциативность)

  21. (Свойства

  22. идемпотентности)

Совершенные нормальные формы (СДНФ и СКНФ) записи булевых выражений

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

F = `A`В`С + `А В`С + А В`С + А В С.

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

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

F = (`А + В +`С ) (`А + В + С ) ( А +`В + С ) ( А + В + С ).

Так же, как и СДНФ, СКНФ является явно избыточной.

Билет 15

  1. Методы безусловной оптимизации нелинейного программирования

  2. Классификация центральных процессоров Intel и соответствующих локальных и системных шин ПЭВМ типа IBM PC.

  3. Реалистическая графика. Обратная трассировка луча.

1. Методы безусловной оптимизации нелинейного программирования

Математическая постановка задачи оптимизации Математическая постановка задачи оптимизации включает в себя целевую функцию f0(X), Х=(х1, х2, ...., хn), представляющую собой количественную оценку качества решения, и допустимое множество Xd, представляющее собой множество допустимых вариантов решения. Решением задачи оптимизации является такой вектор Х* Хd, который минимизирует или максимизирует целевую функцию f0(X). Очевидно, что всякую задачу максимизации f0(X) можно заменить задачей минимизации функции –f0(Х), поэтому в дальнейшем будем рассматривать оптимизационные задачи вида

f0(Х)→min (2.1)

при XXd.

Если допустимое множество Хd лежит в евклидовом пространстве Rn, то задачи вида (2.1) называют конечномерными оптимизационными задачами, а теорию и методы решения конечномерных задач - математическим программированием.

Классификацию задач оптимизации можно проводить по нескольким признакам в зависимости от вида функции f0(X) и допустимого множества Xd.