02Глава21-22 (561019), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Двоичный эквивалент индекса для минтерма может быть определен из записи минтерма подстановкой вместо прямых форм переменных цифры 1, а вместо инверсных – цифры 0.

Пример. - минтерм ранга 4;

1010 – двоичный эквивалент индекса.

= m₁₀.

При этом не следует забывать, что при переходе от индексной записи минтерма к аналитической следует восстановить все переменные, входящие в данную запись.

Пример. m₅ – ранга 4 имеет запись ; m₅ – ранга 3 имеет запись .

Аналогично при записи макстерма используется буква М с индексом, двоичная запись которого содержит 1, если соответствующая переменная входит в аналитическую запись макстерма в прямой форме, и 0, если в инверсной.

Пример. =М₁₁₀₀= М₁₂.

Между минтермами и макстермами существует следующая связь:

_i = M₂ⁿ_-i-1; _i = m₂ⁿ_-i-1.

Булева сумма всех минтермов ранга n равна единице:

2ⁿ-1

m_i =1.

i=0

Это следует из того, что число различных минтермов ранга n равно 2ⁿ, т.е. числу различных наборов n переменных, а функция, принимающая на всех наборах значение 1, есть константа 1.

Используя теорему де Моргана, можно показать, что произведение всех макстермов ранга n равно нулю:

2ⁿ-1

Λ M_i =0.

i=0

Из этих уравнений следует

m_im_j =0 при i≠j;

M_i + M_j =1 при i≠j.

Равенства очевидны, если вспомнить, что минтерм – это конституента единицы, а макстерм – конституента нуля.

§3. Основная теорема.

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

Таблица 8. Составим таблицу функций и найдем булево

A B C f(ABC) выражение для данной функции. Из табл.8 видно,

0 0 0 0= α₀ что функция равна единице, только на наборах,

0 0 1 1= α₁ равных 001, 101, 111, что соответствует минтер-

0 1 0 0= α₂ мам .

0 1 1 0= α₃ Это значит, что данная функция может быть

1 0 0 0= α₄ дизъюнкцией этих минтермов, т.е.

1 0 1 1= α₅ = m₁ + m₅+ m₇.

1 1 0 0= α₆ Чтобы убедиться в сказанном, запишем дан-

1 1 1 1= α₇ ную функцию в виде суммы произведений значений функции на соответствующие минтермы:

f(ABC)= α₀ m₀ + α₁ m₁ + α₂ m₂ + α₃ m₃ + α₄ m₄ + α₅ m₅ + α₆ m₆ + α₇ m₇ =

= 0m₀ + 1m₁ + 0m₂ + 0m₃ + 0m₄ + 1m₅ + 0m₆ + 1m₇ ,

где α_i – значение данной функции на i –ом наборе.

Следовательно, справедлива запись:

2ⁿ-1

f(x₁ x₂ … x_n)= α _i m_i .

i=0

Применив формулу де Моргана, найдем выражение

2ⁿ-1

( x₁ x₂ … x_n)= _i m_i .

i=0

2ⁿ-1 2ⁿ-1 2ⁿ-1 2ⁿ-1

f (x₁ x₂ … x_n)= (x₁ x₂ … x_n)= _i m_i = Λ ( _i m_i)= Λ (α _i + _i)= Λ (α _i +M₂ⁿ_-i-1).

i=0 i=0 i=0 i=0

Основная теорема:

2ⁿ-1 2ⁿ-1

f(x₁ x₂ … x_n)= α _i m_i = Λ (α _i +M₂ⁿ_-i-1).

i=0 i=0

Для аналитических записей булевых функций существуют следующие определения:

Булева сумма элементарных произведений называется дизъюнктивной нормальной формой (ДНФ).

- ДНФ;

- не является ДНФ.

Булево произведение элементарных сумм называется конъюнктивной нормальной формой (КНФ).

- КНФ;

-не является КНФ.

ДНФ функции n переменных, состоящая из элементарных произведений ранга n (т.е. из минтермов), называется совершенной дизъюнктивной нормальной формой функции (СДНФ).

КНФ функции n переменных, состоящая из элементарных сумм ранга n (т.е. из макстермов), называется совершенной конъюнктивной нормальной формой функции (СКНФ).

Основная теорема содержит запись СДНФ и СКНФ функций.

Из теоремы следует, что запись СДНФ (или СКНФ) булевой функции единственна.

§4. Выражение функции в СДНФ и СКНФ с помощью аналитических преобразований.

Для получения СДНФ функции аналитическим способом используется следующий прием:

1. аналитическое выражение функции приводится к бесскобочной записи в форме дизъюнкции каких-либо конъюнкций;

2. каждая конъюнкция, имеющая число сомножителей меньше n, умножается на выражение «1» через все недостающие переменные ( );

3. раскрываются скобки и приводятся подобные члены.

Пример. Найти СДНФ функции f(ABCD)= .

m₁₅ + m₁₄ + m₁₃ + m₁₂ + m₁₁ + m₉ + m₈ + m₃ +m₁.

Для получения СКНФ функции без использования табличной записи следует применять процедуру вида:

1. аналитическое выражение функции приводится с помощью соотношения AB+C=(A+C)(B+C) к конъюнктивной записи со скобками, причем в скобках должны стоять дизъюнкции отдельных переменных в прямой или инверсной форме;

2. к каждой дизъюнкции добавляется выражение 0 через все недостающие переменные ( );

3. вновь используется дистрибутивный закон вида и приводятся подобные члены.

Пример. Найти СКНФ функции

=М₁₅ М₁₃ М₁₁ М₁₀ М₉ М₈ М₅

Рассмотрим расширение сокращенной записи элементарного произведения до суммы минтермов.

Пусть , представим данную запись в виде

A B C D

- - 0 1

Затем, не меняя значений известных цифр в записи индекса минтерма, подставляем все возможные комбинации цифр соответствующих разрядов:

0 0 0 1

0 1 0 1

1 0 0 1

1 1 0 1

Полученные цифры соответствуют индексам минтермов, содержащихся в СДНФ исходной функции, т.е.

f(ABCD)=m₁+m₅+m₉+m_13.

§5. Способы выявления равносильности булевых функций.

Как табличная запись функции, так и запись функции в СДНФ и в СКНФ являются единственными, поэтому для доказательства равносильности булевых функций используются следующие способы:

1. Сравнение табличных записей функций по всем возможным наборам переменных.

Пример. Доказать тождество f₂₄₈(ABC)= (табл. 9,10).

Таблица 9 Таблица 10

A B C f₂₄₈(ABC) A B C B↓C

0 0 0 1 0 0 0 1 0 1

0 0 1 1 0 0 1 0 1 1

0 1 0 1 0 1 0 0 1 1

0 1 1 1 0 1 1 0 1 1

1 0 0 1 1 0 0 1 0 1

1 0 1 0 1 0 1 0 1 0

1 1 0 0 1 1 0 0 1 0

1 1 1 0 1 1 1 0 1 0

248=128+64+32+16+8=2⁷+2⁶+2⁵+2⁴+2³=11111000₂.

Так как значение функций на всех наборах совпадает, то f₂₄₈(ABC)= и тождество доказано.

Способ доказательства равносильности функций по таблицам очень нагляден, но при большом числе n затруднителен.

1. Сравнение СДНФ и СКНФ функций.

Пример. Доказать тождество f₁₉₆(ABC)= ;

196₁₀=128+64+4=2⁷+2⁶+2²=11000100₂.

В индексе функции единиц меньше, чем нулей, следовательно, СДНФ функции имеет более короткую запись, чем СКНФ:

f₁₉₆(ABC)= m₀+m₁+m₅;

= m₀+m₁+m₅.

СДНФ функций совпадают, следовательно, тождество доказано.

Пример. Доказать тождество

F₂₃₇(ABC)= ;

237₍₁₀₎=128+64+32+8+4+1=2⁷+2⁶+2⁵+2³+2²+2⁰=11101101₍₂₎,

так как нулей мало, используем СКНФ:

f₂₃₇(ABC)= М₄ М₁ ;

СКНФ функций совпадают, тождество доказано.

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

Пример. Доказать тождество ;

Тождество доказано.

§6. Свойства функций сложения по модулю 2.

Основные соотношения для функции: :

ассоциативный закон

коммутативный закон

дистрибутивный закон относительно функции конъюнкции

а также

x при n нечетном;

0 при n четном.

n

В справедливости этих соотношений можно убедиться, если вместо подставить СДНФ этой функции:

Пример. Доказать равносильность функций

а) аналитически

б) с помощью таблиц истинности (табл.11,12) функций:

Таблица 11 Таблица 12

x y xy x y x+y

0 0 0 0 0 0 0 0

0 1 0 1 1 0 1 1

1 0 0 0 1 1 0 1

1 1 1 0 1 1 1 1

Пример. Доказать равносильность функций с помощью таблиц истинности (табл.13, 14).

Таблица 13 Таблица 14

x y x y xy

0 0 1 0 0 0 0 0

0 1 0 0 0 0 1 0

1 0 1 1 0 1 0 0

1 1 0 0 1 1 1 1

Теорема Жегалкина: любая булева функция может быть представлена в виде многочлена

f(x₁ x₂ … x_n)= α₀ α₁ x₁ α₂ x₂ … α_n x_n α_n+1

x₁ x₂ α_n+2 x₁ x₃ … α_N x₁ x₂ … x_n ,

где α₀, α₁, … , α_N - некоторые константы, равные 0 или 1.

Для доказательства воспользуемся основной теоремой, утверждающей, что любую булеву функцию можно записать в виде 2ⁿ-1

f(x₁ x₂ … x_n)= α _i m_i .

i=0

Для любого конкретного набора < x₁ x₂ … x_n > из тех наборов, на которых функция принимает значение 1, только один минтерм обращается в единицу, а остальные равны нулю. Поэтому справедлива запись 2ⁿ-1

f(x₁ x₂ … x_n)= α _i m_i .

i=0

От этой формы записи можно перейти к функции в виде полинома через операции и , пользуясь соотношением .

Пример. .

Таким образом, после приведения подобных членов функция f(x₁ x₂ … x_n) будет записана в виде многочлена, при построении которого используются только операции конъюнкции и сложения по mod 2.

Теорема доказана.

Алгоритм построения.

Характеристики

Список файлов книги