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

78 I В выражении (3.25) в качестве дизъюнктивного члена содержатся все простые импликанты, тогда при некотором i: СрСк , но тогда Ск должна поглощаться членом С,: " C vCi=C; уСл'&С/~С, : В результате получим, что : f —CjVC^v... VCii-]VCk+i V...VC„. Получили д.н.ф., которая содержит меньше вхождений переменных, чем ^ в (3.25), что противоречит минимальности (3.25). Это противореаде и доказывает, что все слагаемые минимальной д.н.ф. являются простыми импликантами. : Очевидно, что минимальная д.н.ф. не содержит лишних имплшсант. Итак, минимальная д.н.ф. содержит только простые импликанты, ни одну из которых исключить нельзя, следовательно, она есть тупиковая д.н.ф. Теорема доказана. Теорема показывает, что для отыскания минимальной д.н.ф, достаточно получить все тупиковые формы заданной функции и выбрать среди них минимальную. Заметим, что т^'пиковая д.н.ф. является частью сокращенной ^ д.н.ф. Процедура нахождения сокращенной д.н.ф. из совершенной д.н.ф. известна (см. предыдущий параграф). Для отыскания тупиковых, следовательно, и минимальных д.н.ф. существует несколько методов. § 16, Метод импликантных матриц - Метод имлликантных матриц применяется для нахождения тупиковых и минимальных д.н.ф. Поясним этот метод на примере. Требуется найти минимальную д.н.ф. для функции f(x ,y,z) ^x&y&z ly&z V 1х& ly&z v ]х &у& ]z v ]x& ly& Iz vx &y& Iz. Найдем для этой функции все простые импликанты, что равносильно i отысканию сокращенной д.н.ф. Построим таблицу, вертикальными входами ; которой являются конституенты единицы исходной функции; во втором ее столбце будем записывать результаты, пол>'чающиеся при склеивании | конституенты единицы; при этом звездочкой помечаем склеивающиеся | конституенты. п./п Результаты, получающиеся при склеивании Конституенты единицы x&y &z 7y&z 1х&у& Iz 1х& 1у& Ъ Iz 1 2 3 4 5 6 1 X&Z * * 2 х &у 4J 3 ly&z * * 4 }х& ]v * * 5 h&iz t. 6 у& Iz