Построения СКНФ

1)_Для каждого нулевого набора переменных выписываем дизъюнкцию всех переменных.

2)_Над теми переменными, которые в этом наборе равны 1, ставим отрицание.

3)_Все такие дизъюнкции соединяем конъюнкциями.

СКНФ – (x Ú y) & (ùx Ú ùy)

Преобразование ДНФ в СДНФ:

1) Выбир. неполн. конъюнкции A.

2) Если в A нет n перем., вып. конъюнкции единиц n раз.

3) Единицы представ. по св-ву дополнения как & недостающей переменной и ее отрицания.

4) Раскр. скобки (дистр.), примен. иденп.

Преобразование КНФ в СКНФ:

1) Выбир. неполн. дизъюнкции A.

2) Если в A нет n перем., вып. дизъюнкции нулей n раз.

3) Нули представ. по св-ву дополнения как Ú недостающей переменной и ее отрицания.

4) Раскр. скобки (дистр.), примен. иденп.

53. Полиномы Жигалкина. Построение полиномов Жигалкина.

__Каждую логическую функцию можно представить в виде полинома Жигалкина, представляющего собой элементарные конъюнкции соединены операцией исключающего или Å. Например: f(x,y,z) = (y & z) Å (x & z) Å (x & y & z)

___Процедура построения Полинома Жигалкина

1) По таблице истинности строим СДНФ.

2) СДНФ приводим к минимальной ДНФ

3) Выражаем дизъюнкции Ú и отрицания ù через операции конъюнкции & и исключающего или Å.

x Ú y = x Å y Å (x & y) ù x = x Å 1

4) Раскрываем скобки используя дистрибутивность x & (y Å z) = (x & y) Å (x & z), (x Å y) & z = (x & z) Å (y & z). В результате могут получится формула двух видов (xa & xb &...) Å... Å (xc & xd &...) или (xa & xb &...) Å... Å (xc & xd &...) Å 1

5) Сокращаются повторяющиеся элементы внутри скобок при помощи a&a=a, a&1=a, 1&a=a

6) Сокращаются одинаковые скобки при помощи поглощения aÅa=0, aÅ0=a, 0Åa=a.

ПОСТРОЕНИЕ::::::

n Пусть для функции получена минимальная ДНФ:

f(x,y,z) = (ù x & y & z) Ú (x & ù z)

n Используя ù a = a Å 1 заменим отрицание:

f(x,y,z) = ((x Å 1) & y & z) Ú (x & (z Å 1))

n Используя a Ú b = a Å b Å (a & b) заменим дизъюнкцию:

f(x,y,z) = ((x Å 1) & y & z) Å (x & (z Å 1)) Å ((x Å 1) & y & z & x & (zÅ1))

n Используя дистрибутивность раскроем скобки:

f(x,y,z) = (x & y & z) Å (1 & y & z) Å (x & z) Å (x & 1) Å
Å (x & y & z & x & z) Å (1 & y & z & x & z) Å
Å (x & y & z & x & 1) Å (1 & y & z & x & 1)

n Применим законы поглощения внутри скобок:

f(x,y,z) = (x & y & z) Å (y & z) Å (x & z) Å x Å (y & x & z) Å

Å (y & x & z) Å (y & z & x) Å (y & z & x)

n Применим законы поглощения для одинаковых скобок

f(x,y,z) = (x & y & z) Å (y & z) Å (x & z)Åx

54. Классы логических функций: сохраняющие 0, сохраняющие 1, монотонные, линейные, двойственные, самодвойственные. Критерий поста.

___Класс S0: Функции «сохраняющие 0» - это логические функции, значение которых равны 0, если все аргументы равны 0: f(0,0,...,0)=0. Например Ú

___Класс S1: Функции «сохраняющие 1» - это логические функции, значение которых равны 1, если все аргументы равны 1: f(1,1,...,1)=1. Например &

___Класс M: "Монотонные" функции -это логические функции, которые можно выразить через & и Ú.

Монотонную функцию можно распознать по ее таблице истинности. Для этого нужно взять все пары наборов переменных в порядке возрастания их гомеров, которые отличаются всего в одном столбце. Например: 0,0 и 0,1; 0,1 и 1,1. Нельзя, чтобы значение функции при этих наборах было "1", а потом "0" соответственно.

____ Класс L:"Линейные" функции – это логические функции, которые можно выразить через Å, 0 и 1.

Чтобы узнать, линейна ли функция, надо выразить ее через полином Жегалкина и посмотреть, не встречается ли там операция &. Если нет, то функция линейна.

____ Класс D: «Двойственные» функции f и g, т.е. функции

удовлетворяющие условию f(ù x1, ù x2,..., ù xN) = ù g(x1,x2,...,xN)

Двойственные функции легко обнаружить с помощью простого приема. Надо заменить в таблице истинности все "0" на "1", а все "1" на "0". Полученная таблица истинности и будет таблицей двойственной функции. Пример & и Ú.

____ Класс S:"Самодвойственные" функции, т.е. функции, которые двойственны сами себе:

f(ù x1, ù x2,..., ù xN) = ù f(x1, x2,..., xN).

КРИТЕРИЙ ПОСТА::::::::

___Система булевых функций F является полной тогда и только тогда, когда она не содержится ни в одном из классов S0, S1, S, L, M. T.е. когда в ней имеется хотя бы одна функция, не сохраняющая 0, хотя бы одна функция, не сохраняющая 1, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.

55. Упрощение СДНФ при помощи Карты Карно. Булева алгебра и коммутационные схемы. Анализ и синтез коммутационных схем. Проектирование полубитного сумматора.

__Карта Карно – это таблица каждый элемент которой является элементарной конъюнкцией

___Для 2 переменных p, q возможны 4 элементарные конъюнкции pq, pùq, ùpq, ùpùq, которые являются элементами следующей таблицы

___Для представления картой Карно, высказывания в виде СДНФ с двумя переменными, необходимо отметить клетки соответствующие элементарным конъюнкциям. Например высказыванию pq Ú pùq, соответствуют следующие отметки.

___Если высказыванию соответствуют две соседние (вертикальные или горизонтальные) отметки, то выражение можно упростить оставив их общий элемент. Так в приведенном примере

выражение соответствует общему элементу р.

___Это же можно получить

используя эквивалентные

Соотношения

pq Ú pùq = p(q Úùq)=р&1=p

Дата добавления: 2015-11-16