Файл: Diskretnaya_matematika.doc

Класс самодвойственных функций

Функция f(х₁,..., х_n) называется самодвойственной, еслиf(х₁, ..., х_n) =f(х₁, ...,х_n).

Пример.f(х) = х,f(х) =х – самодвойствен­ные функ­ции;f(х₁, х₂) = х₁• х₂,f(х₁, х₂) = х₁Úх₂– несамо­двой­ственные.

Лемма 3. Из самодвойственных функций суперпози­цией можно получить только самодвойственные функции.

Следствие. Полная система функций должна содер­жать хотя бы одну несамодвойственную функцию.

Класс монотонных функций

Набор  = (₁, ..., _n) предшествует набору  = (₁, ..., _n), если _i  _i (i = l, 2, ..., n). Это обозначаем как   . Наборы, которые находятся в отношении  называются сравнимыми.

Функция f(х₁, ..., х_n) называется монотонной, если для любой пары наборов a и b таких, что при   : f()  f().

Пример.f(х) = х,f(х₁, х₂) = х₁ • х₂,f(х₁, х₂) = х₁Úх₂– монотонные функции, аf(х) =х – немо­нотонная функция.

Лемма 5. Из монотонных функций суперпозицией мож­но получить только монотонные функции.

Следствие. Полная система функций должна содер­жать хотя бы одну немонотонную функцию.

Класс линейных функций

Функция f(х₁, ..., х_n) называется линейной, если полином Жегалкина этой функции имеет линейный вид:

f(х₁, ..., х_n) = а₀Åа₁x₁Å…Åа_n x_n,

где а_i  {0,1} (i = 0, l, ..., n).

Пример.f(х) = х,f(х) =х = хÅ 1 – линейные функции;f(х₁, х₂) = х₁ Úх₂= х₁Å х₂Å х₁•х₂– нелинейная функция.

Лемма 7. Из линейных функций суперпозицией можно полу­чить только линейные функции.

Следствие. Полная система функций должна содержать хотя бы одну нелинейную функцию.

Таблица 2.6. Свойства функций двух переменных

В таблице 2.6 дается полезная информация о свойствах всех функций двух переменных. Пользуясь этой таблицей можно проверить полноту заданной системы функций, а также построить другие базисы.

2.4. Задача минимизации днф

2.4.1. Основные определения

Теорема о полноте даёт ответ на вопрос, из какой системы функций можно получить в виде суперпозиции любую функцию. Но в практических задачах нужна не столько возможность, сколько правила, пользуясь которыми можно получить представление, оп­тимальное в некотором смысле. Каждое представление функции в виде суперпозиции можно охарактеризовать некоторым числом, которое называется сложностью данного представления(напри­мер, число применений операции суперпозиции) и зависит от кон­кретной задачи. Тогда можно поставить задачу об отыскании пред­ставления логической функции наименьшей сложности. В принципе, такую задачу всегда можно решить последовательным перебором различных суперпозиций функций системы.

Рассмотрим теперь су­перпозиции над булевой системой функций, содержащей лишь конъюнкцию, дизъюнкцию и отрицание. Именно для этих суперпозиций методы минимизации разработаны достаточно хорошо. Чтобы дать точную формулировку задачи, приведем некоторые определения.

Минимальной ДНФфункцииf(x₁, ...,x_n) называется ДНФ N =U₁U₂...U_k, представляющая функциюf(x₁, ...,x_n) и содер­жащая наименьшее количество букв по сравнению с другими ДНФ, то есть число букв в N равно, гдеr_i– ранг конъюнкцииU_i, а минимизация проводится по всем ДНФ функцииf(x₁, ...,x_n).

Тогда задача об отыскании представления функции наименьшей сложности формулируется так: для всякой функции найти представление в виде минимальной ДНФ.

Прежде чем описать метод решения задачи дадим ещё несколь­ко определений.

Импликантом функции f(x₁, ..., x_n) называется эле­мен­тарная конъюнкция если выполнено соотношение U_i  f(x₁, ..., x_n)  1. Это означает, что если на некотором наборе импликант U_i обращается в единицу, то функция f(x₁, ..., x_n) на этом наборе тоже обращается в единицу. Любая элементарная конъюнк­ция произвольной СДНФ является импликантом данной функции.

Простым импликантомфункцииf(x₁, ...,x_n) называ­ется им­пликант функцииf(x₁, ...,x_n), если элементарная конъюнкция, полу­чающаяся из него удалением любой буквы, не является импликан­том функции.

Сокращенной ДНФ функции f(x₁, ..., x_n) называется дизъюнк­ция всех простых импликантов функции f(x₁, ..., x_n).

Теорема 5(без доказательства). Сокращённая ДНФ представляет функциюf(x₁,...,x_n).

Теорема 6 (без доказательства). Минимальная ДНФ функции f(x₁, ..., x_n) получается из ее сокращённой ДНФ удалением некото­рых элементарных конъюнкций.

2.4.2. Этапы минимизации днф

В силу теоремы 6 получение минимальной ДНФ мож­но разбить на два этапа

1. Нахождение сокращенной ДНФ.

2. Нахождение тупиковых ДНФ (таких, из которых нельзя уда­лить ни одного простого импликанта) путём удаления подмно­жества элементарных конъюнкций из сокращённой ДНФ. Вы­бор минимальной из полученных тупиковых ДНФ.

Рассмотрим первый этап получения минимальной ДНФ. Ме­тод получения сокращённой ДНФ функции f(x₁, ...,x_n) из ее совер­шенной ДНФ состоит в применении следующих эквивалентных преобразо­ваний:

а) операции полного склеивания, которая состоит в замене выражения А х  Ах на А, так как

А х  Ах  А (х х)  A • 1  A;

б) операции неполного склеивания, которая состоит в замене А х  Ах на А х  Ах  А, так как

А х  Ах  А  А (х х)  А  А•1 A = A;

в) операции поглощения, которая состоит в замене АВ  А на А, так как

АВ  А  А (В  1)  А.

Здесь А и В – произвольные элементарные конъ­юнк­ции.

Теорема 7(без доказательства). Сокращённую ДНФ функ­цииf(x₁, ...,x_n) можно получить из ее совершенной ДНФ, применяя все возможные операции неполного склеивания, а затем операции поглощения.

Пример 1. Построить сокращённую ДНФ функцииf(x₁,x₂) =x₁х₂ из ее СДНФ:

f(x₁, x₂) =х₁х₂ х₁ х₂  х₁х₂ =х₁х₂ х₁х₂ х₁  х₁х₂ =

=х₁х₂ х₁х₂ х₁  х₁х₂  х₂ = х₁  х₂.

Теперь перейдем ко второму этапу получения минимальной ДНФ.

Пусть дана сокращённая ДНФ функции f(x₁, ...,x_n):

N = U₁  U₂  …  U_k. Простой импликант называется ядерным (входящим в ядро функции f(x₁, ..., x_n)), если

≢1.

Эта запись означает, что простой импликант U_iявляется ядер­ным импликантом функцииf(x₁, ...,x_n), если существует набор= (₁, ...,_n), на котором импликантU_iобращается в 1, а все ос­тальные импликанты сокращённой ДНФ – в ноль.

Пример 2. Найти ядерные импликанты функцииf(x₁, ...,x_n), заданной своей сокращённой ДНФ:

х₂х₄х₁х₄х₁х₂х₂х₃х₄х₁х₃х₄х₁х₂х₃.

Простой импликант х₂х₄ является ядерным, так как на наборе (0,0,0,0) х₂х₄ = 1, а дизъюнкция оставшихся импликантов:

х₁х₄  х₁ х₂  х₂ х₃ х₄ х₁ х₃ х₄ х₁х₂ х₃ = 0.

Простой импликант х₁х₄– неядерный, так как он равен еди­нице на наборах {1,0,0,0}, {1,0,1,0}, {1,1,0,0}, {1,1,1,0}, но на этих же наборах:

х₂х₄х₁х₂х₂х₃х₄х₁х₃х₄х₁х₂х₃=1,

следовательно

х₁х₄х₂х₄х₁х₂х₂х₃х₄х₁х₃х₄х₁х₂х₃1.

Простой импликант х₁х₂– ядерный, т.к. на {1,1,0,1}: х₁х₂= 1, ах₂х₄х₁х₄х₂х₃х₄х₁х₃х₄х₁х₂х₃= 0.

Простой импликант х₂х₃х₄– неядерный, так как на наборах {0,1,1,1}, {1,1,1,1}:

х₂х₄  х₁х₄  х₁ х₂ х₁ х₃ х₄ х₁х₂ х₃ = 1.

Простой импликант х₁х₃х₄– неядерный, так как на наборах {0,0,1,1}, {0,1,1,1}:

х₂х₄  х₁х₄  х₁ х₂  х₂ х₃ х₄ х₁х₂ х₃ = 1.

Простой импликант х₁х₂х₃– неядерный, так как на наборах {0,0,1,0}, {0,0,1,1}:

х₂х₄  х₁х₄  х₁ х₂  х₂ х₃ х₄  х₁ х₃ х₄ = 1.

Теорема 8(без доказательства). Простой импликантU_iвходит во все тупиковые ДНФ тогда и только тогда, когдаU_iвходит в ядро функцииf(x₁, ...,x_n), то есть тогда и только тогда, когда он явля­ется ядерным.

Следствие. Пусть ядро f(x₁, ..., x_n) состоит из импли­кантов U_l1, ... ,U_lm тогда импликант U_l, для которого выпол­нено соотношение:  1.