Главная Случайная страница


Полезное:

Как сделать разговор полезным и приятным Как сделать объемную звезду своими руками Как сделать то, что делать не хочется? Как сделать погремушку Как сделать неотразимый комплимент Как сделать так чтобы женщины сами знакомились с вами Как сделать идею коммерческой Как сделать хорошую растяжку ног? Как сделать наш разум здоровым? Как сделать, чтобы люди обманывали меньше Вопрос 4. Как сделать так, чтобы вас уважали и ценили? Как сделать лучше себе и другим людям Как сделать свидание интересным?

Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






Лемма о нелинейной функции





Если F(X) нелинейна, то из нее путем подстановки вместо аргументов-констант переменных (x, y, not x, not y) иожно получить: конъюнкцию этих переменных, дизъюнкцию этих переменных, отрицание конъюнкции, отрицание дизъюнкции.

F = 1 + x1+x3+x1x3+x1x2x3 = x1x3(1+x2) +x3+x1+1

F(x1,0,x3) = x1x3+x3+1

___

F(x0y) = (xy)


Лекция 9: «Продолжение темы Классы функций»

 

Доказательство леммы 3

 

F(x1…xn) = x1x2 (f1(x1…xn)) + x1f2(x1…xn) + x2f3(x1…xn) + f4(x1…xn)

 

Вместо x1…xn ставим константы a1…an, такие, что

f1(a1…an) = 1

 

1. A = B = 0

F(x1x2…a3…an) = x1x2 + C = {x1x2, если с = 0 и NOT(x1x2, если с = 1)

Аналогично получаем дизъюнкцию и ее отрицание.

 

Теорема Поста.

Система функций полна тогда и только тогда, когда она не находится ни в одном из пяти важнейших замкнутых классов, а именно S, M, L, T0, T1.

1. Необходимо.

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

Доказательство следует из того факта, что по определению и по тому, что мы доказали, что все важнейшие классы замкнуты. Если предположить, что система целиком входит в один из замкнутых классов, то

 

[S] = [B] = B

 

Но S - множество всех булевых функций, а B – не всех.

Получили противоречие.

 

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

Дано

S Ë {S, M, L, T0, T1}

 

Каждая функция (f с индексами 1…5) не принадлежит каждому соответствующему ей важнейшему замкнутому классу.

1. Получение констант.

F1(00…0) = 1

a) F(111) = 1

b) F(111) = 0

F(xxxx) = 1

F2(111) = 0

2. Получение отрицаний

Из F4 по лемме 2 мы можем получить отрицание.

3. Используя F5 по лемме 3 получаем xy, x V y, not(xy), not(x V y)

 

 

Лекция 10: «Функциональные элементы. Логические схемы»

 

F
Функциональный элемент с n упорядоченными входами и одним выходом



.

 

При подаче на выходы любой комбинации двоичных сигналов, на выходе также возникает сигнал.

Каждый вход – аргумент функции.

Выход – булева функция от аргументов.

 

Из функциональных элементов можно строить по правилам их соединения схемы (логические сети).

 

Два и более входов можно отождествлять.

 

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

 

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

Число функциональных переменных считаем сколь угодно большим.

 

Базис называется полным, если с его помощью можно реализовать любую булеву функцию в виде схемы.

 

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

 

Пример полного базиса.

 
 
&


- Конъюнктор

 

 

 
 
V


- Дизъюнктор

 


- Инвертор

Чтобы построить минимальную функциональную схему для функции на конъюнкторах, дизъюнкторах и инверторах, которая реализует эту функцию, нужно

1. Найти минимальную ДНФ.

2. Для любой из минимальных ДНФ (их может быть много) попробовать упростить формула с помощью вынесения за скобки общего множителя.








Date: 2015-04-23; view: 1680; Нарушение авторских прав

mydocx.ru - 2015-2021 year. (0.009 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию