Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364139
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62791)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21319)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21692)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8692)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3462)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20644)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Реферат: Булевы Функции Функциональная полнота

Название: Булевы Функции Функциональная полнота
Раздел: Рефераты по математике
Тип: реферат Добавлен 02:52:44 24 июня 2011 Похожие работы
Просмотров: 97 Комментариев: 12 Оценило: 2 человек Средний балл: 5 Оценка: неизвестно     Скачать

Булевы Функции: Функциональная полнота.

В алгебре булевых функций P2=<P2;S>

S – Операцией является подстановка функции в функцию, суперпозиция.

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

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

Система функций полна, если через неё можно выразить любую булеву функцию. Примеры полных систем:

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

{&, v, not}. Конъюнкцию с помощью законов Деморгана можно выразить через остальные элементы системы:

X&Y=not (not(X) v not(Y)) – поэтому система {v, not}. Аналогично по другому закону Деморгана можно получить v через &, not поэтому (&, not).

Импликация выражается через Дизъюнкцию и Отрицание: X v Y = not(X) - Y, следовательно {-, not} также полная.

Через сложение (по модулю 2), умножение и 1 можно выразить основные логические операции:

1) X&Y=X*Y

2) X v Y=X+Y+XY

3) Not(X)=X+1

4) X -- Y=X+Y+1

Поэтому {+,*,1} система полна, и каждую булеву функцию в виде многочлена от Н переменных, который в честь автора Полином И.И. Жегалкина.

Представление функции в форме Полинома Жегалкина. Следовательно, можно говорить о линейных булевых функциях, то есть функции вида f(X1,…,Xn)=A1X1+…+AnXn+B, обозначим буквой L множество всех линейных функций данного вида.

Система булевых функций полна, если через нее можно выразить какую-нибудь полную систему. Не пустое, собственное подмножество множество P2, замкнутое относительно суперпозиции образует под-алгебру.

F,g1,…,gn€H=>f(g1,g2,…,gn)€H, H<P2

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

Любая подсистема, целиком лежащая в некоторой под алгеброй, неполна.

Примеры под алгебр:

1) Множество линейных функций L образует под алгебру. L – замкнутая относительно суперпозиции. Любое множество линейных функций не образует полную систему: линейные функции порождают снова линейные функции. Поэтому, например система {0,1,+, not, --} не полна.

2) Функция f сохраняет ноль если f(0,…,0). Множество C0 всех таких функций образует под алгебру. Любое множество функций целиком лежащее в С0 не образует полную систему. Например {&, v, +, 0}.

3) Функция F сохраняет 1 если f(1,1,…,1)=1 Любое множество функций сохраняющих единицу не когда не образуют полную группу.

4) Функция называется монотонной если для любых наборов. Множество М всех монотонных функций образует под алгебру. Любое множество монотонных функций не является полной системой.

5) NotF(notX1, notX2,…,notXn) называется двойственной для функции Х. Например & и v. Отображение F|-notF согласованно с суперпозицией. Значит что отображение. Функция самодвойственная если F=notF. Множество Д самодвойственных функций образует подалгебру.

Теорема (Поста): Система функций полна тогда и только тогда когда она не содержится целиком не в одной из под алгебр.

1) Множество линейных функций L образует под алгебру. L – замкнутая относительно суперпозиции. Любое множество линейных функций не образует полную систему: линейные функции порождают снова линейные функции. Поэтому, например система {0,1,+, not, --} не полна.

2) Функция f сохраняет ноль если f(0,…,0). Множество C0 всех таких функций образует под алгебру. Любое множество функций целиком лежащее в С0 не образует полную систему. Например {&, v, +, 0}.

3) Функция F сохраняет 1 если f(1,1,…,1)=1 Любое множество функций сохраняющих единицу не когда не образуют полную группу.

4) Функция называется монотонной если для любых наборов. Множество М всех монотонных функций образует под алгебру. Любое множество монотонных функций не является полной системой.

5) NotF(notX1, notX2,…,notXn) называется двойственной для функции Х. Например & и v. Отображение F|-notF согласованно с суперпозицией. Значит что отображение. Функция самодвойственная если F=notF. Множество Д самодвойственных функций образует подалгебру.

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

Упр1. Полна и независима???? Кто??? Для доказательство полноты достаточно выразить отрицание. Для доказательства независимости достаточно указать разделяющую под алгебру. Наименьшее число в полной системе = 1.

Упр2. X|Y = not(x) v not(y) Шефферт . Доказать что {|}{⬇} - полные системы

Упр3. Выяснить Существуют ли полные системы отличные от Стрелки Пирса и Штриха Шефферта.(будем искать функцию с помощью ее таблицы значений)

X

Y

0

0

1

1

1

1

0

1

0

0

1

1

1

0

0

1

0

1

1

1

0

0

0

0

Стр(207) Задача 2.1 Выясните при каких значениях а и в функции f(x,y)=not((x v a)v(a&b)) g(x,y)=(x v b)-(a & y) – в зависимости от значений а и в возникают 4 случая, если одна из функций является штрихом шейфера то независимо от другой система полна, если из полученной системы можно получить какую либо полную, то полна. Если она целиком содержится в одной из подалгебрах

F(x,y,z)=x+y+z

{0,1,*,f} – полна и независима

Not(x)=X+1+0=f(x,1,0)

Покажем что С1.

Пусть система булевых функций удовлетворяет условию теоремы, те там найдется покрайней мере одна функция не попавшая в особые под алгебры. В частности там найдется функция не принадлежащая С0. Перенумеруем переменные в этой функции обозначив их одной буквой Х. Таким образом мы получаем функцию f(x) такая что f(0)=1 - F(1)=0 & 1. Аналогично из данной системы можно получить функцию G(x) такую что G(1)=0 и G(0)=0 & 1.

Случай 1.

X

F

G

0

1

0

1

0

0

F(x)=not(x), G(x)=0 - В этом случае имеем {not(x),x,0,1}.

Случай 2.

X

F

G

0

1

1

1

0

0

F(x)=g(x)=not(x) - {not(x),x}

Случай 3.

X

F

G

0

1

0

1

1

0

{1,0}

Случай 4.

X

F

G

0

1

1

1

1

0

{1,not(x),x,0}

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

Упр.1

Доказать что с помощью not и не самодвойственной функции можно получить константу(Указания: С(x) является константой если С(not(x)), случай 2 сводится к случаю 1).

Упр.2

Доказать что через не монотонные функции можно получить отрицание(Указание: T(x1,x2,…,xn) не монотонная если существуют наборы J1,j2,…jn; B1,B2,…,Bn так чтоб f(J)>f(B), тк функция дискретна изменение функции осуществляется скачком за счет изменения лишь одного значения элемента.)

Упр.3

Итак, во всех четырех случаях мы получаем набор {not(x),x,0,1} . Доказать что с помощью нашего множества и не линейной функции можно получить умножение(Указание: Пусть функция S(x1,x2,…,xn), то есть в ее полиноме Жигалкина есть одночлены выше первой степени, пусть для определенности переменные x1,x2 создают эту степень, вынесем x1,x2 из всех одночленов затем вынесем Х1, а затем Х2, в результате мы получим представление S(x1,x2,…,xn)=x1,x2,g1(x3,…,xn)+x1,g2(x3,…,xn)+x2g3(X3,…,xn)+g4(x3,…,xn) ) g1(x3,…,xn) – не является 0, те при определенном наборе таким образом из нашей системы можно получить систему.

Замечание: Теорема Поста, означает что C0,C1,D,M,L – все максимальные под алгебры от P2. В P2 любая под алгебра содержится в максимальной под алгебре; поэтому результат Поста улучшить нельзя.

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Привет студентам) если возникают трудности с любой работой (от реферата и контрольных до диплома), можете обратиться на FAST-REFERAT.RU , я там обычно заказываю, все качественно и в срок) в любом случае попробуйте, за спрос денег не берут)
Olya02:41:05 27 августа 2019
.
.02:41:05 27 августа 2019
.
.02:41:04 27 августа 2019
.
.02:41:03 27 августа 2019
.
.02:41:02 27 августа 2019

Смотреть все комментарии (12)
Работы, похожие на Реферат: Булевы Функции Функциональная полнота

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

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



Результаты(258379)
Комментарии (3470)
Copyright © 2005-2020 BestReferat.ru support@bestreferat.ru реклама на сайте

Рейтинг@Mail.ru