Зарипова, Э.Р. Дискретная математика Часть II. Математическая логика

36 Последняя таблица 7.5 дает следующие минимальные представления исходной функции: а) –000 10-0 -011 б) 0-00 10-0 -011 и т.д. Данный пример показывает, что иногда сложно перебрать все варианты с помощью таблиц. Эта задача может быть решена также следующим образом. Обозначим импликанты через a,b,c,d,e,f,g . Тогда из таблицы следует, что элементарная конъюнкция ( 0000 ) покрывается импликантами a или b ( a  b ), элементарная конъюнкция ( 0100 ) – импликантами a или g ( a  g ) и т.д. Имеем: (a  b)(a  g)(b  c)(d  e)g(c  f)(d  f)(e  g)= =(a  ag  ab  bg)(bd  be  cd  ce)(cd  cf  df  f)(e  g)g=(a  bg)(bd  be  cd  ce)(f  cd)g= =(abd  abe  acd  ace  bdg beg  bcdg  bceg)(f  cd)g= =(abdf  abef  acdf  acef  bdgf  bgef abcd  abcde  acd  acde  bcdg  bcdge)g=abdfg  abefg  acefg  bdgf  bgef  acdg  bcdg Получаем 7 различных неизбыточных представлений исходной функции. Из них минимальными являются последние четыре. Заметим, что в любое представление входит импликант g , т.к. он является ядром. Ответ. Минимальными являются следующие 7 функции: 1) f x y z t yzt yzt xy xyz     ( , , , ) 2) f x y z t yzt xy xzt xyz     ( , , , ) 3) … 4) … Остальные функции в качестве упражнения предлагается выписать читателю самостоятельно.