Презентация на тему "Дискретная математика"

Содержание

• 
  Слайд 1

  Дискретная математика

  Лекция 5. Разложение функции по переменным, совершенные дизъюнктивная и конъюнктивная нормальные формы

• 
  Слайд 2

  Разложение Шеннона

  Рассмотрим разложение булевой функции f (x1, x2, ... , xn) по переменной xi. Разложение Шеннона: f (x1, x2, ... , xn)= xi f(x1, ..., xi -1,1, xi+1,... , xn) xi f(x1,...,xi -1, 0, xi+1,... , xn). Доказательство (не умоляя общности, для i =1). Если x1 = 0, то f(0, x2, ... , xn) = 0 f (1,x2, ... , xn)  1f(0, x2, ... , xn) = f (0,x2, ... ,xn). Если x1 = 1, то f(1, x2, ... , xn) =1f(1,x2, ... , xn) 0 f(1, x2, ... , xn) = f(0,x2,...,xn). ЧТД Пример. Булеву функцию f (x,  y, z) = x y /y z , разложим по переменной z:f (x,  y, z)= z(x y /y  1) z (x y /y  0)= [по свойствам 0 и 1] = zz (xy /y ). Сомножитель f (x1, ..., xi -1, 1, xi+1,... , xn) в формуле Шеннона называется коэффициентом разложения функции f (x1, x2, ... , xn) попеременной xi при xi, а сомножитель f (x1, ..., xi -1, 0, xi+1,... , xn) — коэффициентом разложения функции f (x1, x2, ... , xn) по   xi при xi. Пример. f (x, y, z) = x y /y = y ( x 1 / 0) y ( x  0 / 1).x  1 / 0 — коэффициент разложения функции  f (x, y, z)по y при y ; x  0 / 1 — коэффициент разложения функции  f (x, y, z)по y при y.

• 
  Слайд 3

  Разложение функции по двумпеременным

  Рассмотрим булеву функцию f (x1, x2, ... , xn) и, используя формулу Шеннона, последовательно разложим функцию по первой переменной,по двум первым переменным, по k первым переменным. [раскроем скобки по закону дистрибутивности] Введем обозначения: х=х1, =х0. Тогда разложение в свернутом виде:  

• 
  Слайд 4

  Разложение функции по k переменным

  Доказательство. Подставим в левую и правую части равенства произвольный набор a1a2... an: Упростим правую часть, рассуждая следующим образом. Нетрудно проверить, что 1, если и только если ai= ci (в самом деле: 0 0 = 1, 11 = 1, но 0 1 = 0 и 10 = 0 ), поэтому конъюнкция равна единице лишь в единственном случае, когда наборы a1a2... ak и с1 с2 ... сkсовпадают. А это значит, что она не обращает в ноль лишь одно слагаемое правой части — то, для которого a1a2... ak= с1с2... сk и в котором сама обращается в единицу. Подставив в ставшееся слагаемое a1a2... akвместо с1с2... сk, получим

• 
  Слайд 5

  Совершенная дизъюнктивная нормальная форма (СовДНФ)

  Применив формулу разложения булевой функции f (x1, x2, ... , xn) по k переменным при   k = n, получим: Поскольку коэффициентами разложения f (c1, c2, ... , cn) в этой формуле являются значения функции f (x1, x2, ... , xn) на всевозможных наборах c1 c2 ... cn, то возможны два случая: еслинабор c1 c2 ... cnM 0( f ), то f (c1,c2,...,cn) = 0 и поэтому обращается в 0 соответствующее слагаемое правой части; еслинабор c1 c2 ...cnM1(f), то f(c1,c2,...,cn)=1и слагаемое упрощается. В результате имеем: Совершенная дизъюнктивная нормальная формабулевой функции,илиСовДНФ, — это формула вида:

• 
  Слайд 6

  Утверждениео единственности СовДНФ

  Любая булева функция, кроме константы 0, представима cовершеннойдизъюнктивной нормальной формой, и она единственна для данной функции. Алгоритм построения СовДНФ (по таблице истинности) вытекает из определения СовДНФ и состоит в циклическом выполнении следующего шага: в  ­векторе - столбце значений функции выбирается очередная 1 и по набору значений аргументов этой строки формируется конъюнкция всех аргументов с соблюдением следующего правила: если i‑я компонента набора равна 0, то переменная xiвходит в конъюнкцию в степени 0 (с инверсией), иначе в степени 1 (без инверсии); полученная конъюнкция добавляется в формулу как очередное слагаемое. Пример. Обратим внимание на тот факт, что нам впервые удалось от табличного способа задания функции перейти к формульному !

• 
  Слайд 7

  Совершенная конъюнктивная нормальная форма (СовКНФ)

  Пусть дана функция f (x1, x2, ... , xn). Представим ее инверсию СовДНФ: Ивертируем обе части этого равенства: По законам двойного отрицания и де Моргана имеем: [заметив, что, так как при c = 0 , а при c = 1x  =x, получим] Определение. Совершенная дизъюнктивная нормальная форма функции f (x1, x2, ... , xn),или СовКНФ, — это формула вида:  

• 
  Слайд 8

  Утверждение о единственности СовКНФ

  Любая булева функция, кроме константы 1, представима cовершенной конъюнктивной нормальной формой , и она единственна для данной функции. Алгоритм построения СовКНФ по таблице истинности вытекает из определения СовКНФ и состоит в циклическом выполнении следующего шага: в ­векторе - столбце значений функции выбирается очередной 0 и по набору значений аргументов этой строки формируется дизъюнкция всех аргументов с соблюдением следующего правила: если i‑я компонента набора равна 0, то переменная xi входит в дизъюнкцию в степени 1 (без инверсии), иначе в степени 0 (с инверсией); полученная дизъюнкция добавляется в СовКНФ как очередной сомножитель. Пример.

• 
  Слайд 9

  Дискретная математика

  Дизъюнктивная нормальная форма (ДНФ)

• 
  Слайд 10

  Элементарная конъюнкция и ДНФ

  Рассмотрим множество переменных x1,x2,...,xn. Элементарной конъюнкцией назовем конъюнкцию, в которую каждая переменная входит не более одного раза (с инверсией или без инверсии). Примеры. x1x 2 x3 x4,x1x 2 x4 , x3 — элементарные конъюнкции, x1x 2 x2 x4, x1x 1 x3 — неэлементарные. В частности, 1 — это элементарная конъюнкция, не содержащая ни одной переменной. Число переменных, образующих элементарную конъюнкцию, назовем ее рангом. Пример. Ранг элементарной конъюнкции x1x 2 x4 равен трем. Полной конъюнкциейназовем элементарную конъюнкцию, состоящую из всех переменных, т.е. конъюнкцию ранга n. Пример. При n = 4 конъюнкция x1x 2 x3 x4 — полная. Дизъюнктивной нормальной формой (ДНФ) назовем дизъюнкцию различных элементарных конъюнкций. Пример.x1x 2 x4x1x 2 x3 x4 x3— ДНФ. Очевидно, что совершенная ДНФ является частным случаем ДНФ. Длиной ДНФ назовем число конъюнкций в данной ДНФ. Рангом ДНФ назовем сумму рангов ее конъюнкций. Пример.Длина ДНФ из предыдущего примера равна трем, а ранг — восьми.