lita_rk2_voprosy_i_otvety ([ЛиТА] Вопросы и ответы к РК2)

Определения:* +, определенное на множестве всех n-элементных• Булева функция от n переменных – произвольное отображение вида * +последовательностей нулей и единиц, и принимающее два возможных значения.Таблица булевой функции от n переменных – таблица, состоящая из двух столбцов истрок. В первом столбце перечисляются все наборы* + , во втором – значения функции на этих наборах.из̅̅̅̅̅()Булева переменная – переменная с областью значений {0,1}, булеву функцию можно задать как), если значение функции не зависит отпринимают два возможных значения.

Переменную xi называют фиктивной переменной б.ф. (значения этой переменной. Переменная x, не являющаяся фиктивной, называется существенной – функция f существенно зависит отпеременной x.• Булев куб размерности n – множество * + , являющееся носителем булевой алгебрыкак упорядоченное множество можно изобразить в виде диаграммы Хассе.(так же можно обозначать и сам куб). Булев куб• ДНФ, КНФ, СДНФ, СКНФЛитерал – формула, являющаяся либо переменной, либо отрицанием переменной, ̃Элементарная конъюнкция – конъюнкция литералов.

Дизъюнктивной нормальной формой от переменных̅̅̅̅̅̅ элементарная конъюнкция Ki содержит некоторые из литералов ̃вида, гдеопределяется конъюнктивная нормальная форма.̅̅̅̅̅̅Совершенной называется ДНФ (КНФ), в которой̃ ̃(̃̃)называется формула̅̅̅̅̅. Двойственно̅ +, состоящее из функций дизъюнкции, конъюнкции и отрицания. Формулами над• Стандартным базисом называется множество*СБ будет любое переменное, из которых (с использованием функций базиса) можно построить любую новую формулу.*+, в котором дизъюнкция представима с помощью базисных функций.• Базисом Жегалкина называют множество) ∑()(*+ *Полином Жегалкина – любая формула над базисом Жегалкина вида ()– коэффициенты 1 или 0.Линейная функция – функция, у которой полином Жегалкина не содержит конъюнкций переменных – т.е.

сводится к линейной части.(∑ ()()).+,• Задача минимизации: требуется для булевой функции n переменных построить ДНФ с минимально возможным числом дизъюнкций иминимально возможным числом вхождений литералов.Кратчайшая – ДНФ с наименьшей длиной, т.е. числом дизъюнкций. Минимальная – ДНФ с наименьшим числом литералов.Импликанта – элементарная конъюнкция в составе ДНФ; простая – если из неѐ нельзя удалить ни один литерал (путем склейки с другойимпликантой). Сокращенная – ДНФ, состоящая только из простых импликант.Ядро булевой функции – совокупность ядровых простых импликант; ЯПИ – покрывает некоторую элементарную конъюнкцию совершеннойДНФ, которая никакой другой простой импликантой не покрывается.

Тупиковая – ДНФ, не содержащая избыточных относительно себяимпликант (которые можно было бы удалить без потери равенства с исходной функцией).• Пусть дано множество булевых функций F. Формулой над этим множеством считается любая константа из F (если она там есть) и любая() – формулы над множеством F, а f – функция из F от n переменных, то () есть формулабулева переменная. Еслинад F; никаких других формул над F не существует.Замыкание [F] множества F – множество всех булевых функций, которые можно представить формулами над F.

F называется замкнутым,⋃если [F] = F. F называется полным, если [F] = P2, где( )• Классы Поста:T0 – функции, сохраняющие константу 0. {(̃)}T1 – функции, сохраняющие константу 1. {(̃)}( ̃)}S – самодвойственные функции. {̃ ( ̅̃ ) ̅̅̅̅̅̅M – монотонные функции. {L – линейные функции. *( ̃ ̃ ) .( ̃(∑(̃))(( ̃ )/}( ̃)))+– множество функций от всех переменных.1.

Теорема о представлении булевой функции в виде ДНФ и КНФ.~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~• Теорема: Любая булева функция, отличная от константы 0, может быть представлена в виде ДНФ. Любая булева функция, отличная отконстант 1, может быть представлена в виде КНФ.* ̃ ( ̃)+Доказательство: 1) Для функциивведем множество конституэнт единицы функции f:, т.к. функция). ̃ ( ̃)отлична от 0. Введѐм теперь конъюнкцию ̃̃ (, тогда и только тогда, когда ̃̃. Тогда можноопределить⋁̃̃ – дизъюнкция всех конъюнкций. Эта функция явлется совершенной ДНФ.Пусть теперь ( ̃)набор ̃, тогда ̃такой, что (⋁. Значит, соответствующая̃ )( ̃)2) Введем множество конституэнт нуля:случаю доказывается, что⋀̃̃̃, и ⋁̃̃. Наоборот, если ⋁ ̃̃, то существует такой( ̃)̃*̃( ̃)+ Определим дизъюнкцию̃̅̅̅̅̅̅̅̅.

Аналогично предыдущему2. Леммы о несамодвойственной, немонотонной, нелинейной функциях.~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~• Лемма 1 (несамодвойственность): если не самодвойственная, то обе константы могут быть представлены формулами над {̅}( ̃)( ( ̃)( ̅̃ )) ̃ (). Определим ( ). Отсюда{̅.̅() и докажем что это константа. ( )()(̅̅̅( ̅̃ ) ( )()( ̃).

Следовательно,̅̅̅̅)( )( )Противоположную константу можно представить с помощью отрицания.̃ ) ( ( ̃)• Лемма 2 (I-я лемма о немонотонности): Еслине монотонная, то ( ̃ ̃ )( ̃( ̃)).̃̃̃Доказательство: так как функция немонотонна, то существует пара наборов ( ̃ )( ̃) ( ( ̃)( ̃)) ̃() (*+)()Теперь строим последовательность наборов ̃̃̃̃.

Таким образом, каждый следующий набор отличается от предыдущего ровно в одной позиции, (̃)̅̅̅̅̅̅̅̅̅̅ Тогда можно полагать, что ̃ ̃ ̃ ̃(̃)(̃)()+.• Лемма 3 (II-я лемма о немонотонности): Если, то отрицание можно представить формулой над *̃ , т.е. ̃ () ̃ (Доказательство: Пусть ̃ ̃̃) отличаются только в i-й позиции. ( ̃)()поэтому ̅̅}• Лемма 4 (о нелинейной функции): еслито конъюнкция может быть представлена формулой над базисом {Доказательство: ПустьВ еѐ полиноме Жегалкина есть нелинейное слагаемое, содержащее конъюнукцию несколькихлитералов. Выбираем в ПЖ этой функции самое короткое нелинейное слагаемое()Определим новую функциюТаким образом,.*+)Обозначим (.Тогда,)∑ ()∑()(1) (())Значит, конъюнкцию можно представить в видеДействительно, в (1) подставим: (()()()()Таким образом, ()Доказательство:{3.

Теорема о замкнутости классов Поста.~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~• Теорема: каждый класс Поста есть замкнутое множество булевых функций.4. Теорема Поста (леммы сформулировать без доказательства).~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~• Теорема: Множество F булевых функций полно тогда и только тогда, когда F не содержится ни в одном из классов Поста.Доказательство:*+1) Необходимость. Пусть F полно, но существует. Тогда, в силу замкнутости каждого класса Поста, замыкание, . Тогда, формулой над F нельзя представить ни одну из функций, не принадлежащих никакому классу Поста (например штрихШеффера), что противоречит условию полноты.2) Достаточность. Возьмѐм множество (базис){ ̅ }.)(). В первом варианте можно представить() при этом1 случай: (()().

Обе константы представленны, а по Лемме 2 (1я о немонотонности), ̅()()Второй вариант рассматривается аналогично.) (). В данном случае, ̅()()()2 случай: ((̅̅̅̅ ̅̅̅̅).5. Алгоритм Куайна-Макклоски построения минимальной ДНФ.~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~• Алгоритм Куайна-Макклоски предполагает получение из совершеной ДНФ множества кратчайших ДНФ (с наименьшей длиной), изкоторых затем выбирается минимальная (с наименьшим число литералов).

Алгоритм работает в четыре этапа.На первом происходит построение сокращенной ДНФ путем склейки всех пар элементов̅; сокращенная ДНФ состоит изпростых импликант.На втором этапе происходит определение ядра сокращѐнной ДНФ – совокупности ядровых простых импликант – покрывающих некоторуюэлементарную конъюнкцию СДНФ, которая не покрывается никакой другой ЯПИ. Если ЯПИ в совокупности закрывают все единичныеклетки на карте Карно, то процедура заканчивается, и ДНФ из ЯПИ – единственная минимальная.На третьем этапе происходит перечисление тупиковых ДНФ – которые не содержат избыточных импликант. Это делается с помощьювспомогательной формулы Патрика, переменные которой обозначают неядровые простые импликанты.

Элементарные конъюнкции,остающиеся в формуле Патрица, добавляются к ядру, после чего получают тупиковые ДНФ.Наконец на четвертом этапе из тупиковых ДНФ выбирают кратчайшие, а из них – минимальные по числу литералов..