67606
Разложение булевых функций по переменным
Лекция
Математика и математический анализ
Это представление называется разложением функции по m переменным x1xm. Разложение по одной переменной 1 Разложение по всем n переменным 2 При Опр. Это разложение называется совершенной дизъюнктивной нормальной формой представления функции fx1xn.
Русский
2014-09-12
174.5 KB
8 чел.
Лекция №15
Разложение булевых функций по переменным.
Возникают вопросы:
1) всякая ли функция может быть записана с помощью формулы?
2) как это сделать?
Совершенная дизъюнктивная нормальная форма.
Обозначим, где равен либо 0, либо 1. Тогда
.
Поскольку
,
то x=1 x=.
Теорема о разложении функции по переменным || Каждую функцию Булевой алгебры при любом можно представить в следующей форме:
,
где дизъюнкция берется по всем наборам значений переменных . ||
опр || Это представление называется разложением функции по m переменным x1,…xm.||
Доказательство.
- Рассмотрим произвольный набор значений . Левая часть равенства имеет вид . Правая часть
(в сумме только одно произведение отлично от нуля: то в котором )
.
Теорема доказана.
Разложение по одной переменной
1)
Разложение по всем n переменным
2)
При
Опр. Это разложение называется совершенной дизъюнктивной нормальной формой представления функции f(x1,…,xn).
Теорема || Каждая функция алгебры логики может быть выражена в виде формулы, содержащей только отрицание, конъюнкцию и дизъюнкцию. ||
Доказательство ||
1) Если , то
2) Если , то
Примеры
1)
|
x1 |
x2 |
f |
|
0 |
0 |
1 |
|
0 |
1 |
1 |
|
1 |
0 |
0 |
|
1 |
1 |
1 |
(это СДНФ; теперь преобразуем)
2) Следующий пример. Дана таблица
|
x1 |
x2 |
x3 |
f |
|
0 |
0 |
0 |
1 |
|
0 |
0 |
1 |
1 |
|
0 |
1 |
0 |
0 |
|
0 |
1 |
1 |
0 |
|
1 |
0 |
0 |
0 |
|
1 |
0 |
1 |
1 |
|
1 |
1 |
0 |
0 |
|
1 |
1 |
1 |
1 |
3)
|
x1 |
x2 |
x3 |
x4 |
f |
|
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
1 |
1 |
|
0 |
0 |
1 |
0 |
0 |
|
0 |
0 |
1 |
1 |
0 |
|
0 |
1 |
0 |
0 |
1 |
|
0 |
1 |
0 |
1 |
0 |
|
0 |
1 |
1 |
0 |
0 |
|
0 |
1 |
1 |
1 |
0 |
|
1 |
0 |
0 |
0 |
1 |
|
1 |
0 |
0 |
1 |
1 |
|
1 |
0 |
1 |
0 |
0 |
|
1 |
0 |
1 |
1 |
0 |
|
1 |
1 |
0 |
0 |
0 |
|
1 |
1 |
0 |
1 |
0 |
|
1 |
1 |
1 |
0 |
1 |
|
1 |
1 |
1 |
1 |
0 |
4) Аналитический способ
5)
Пусть . Согласно теореме двойственности
Это разложение называется совершенной конъюнктивной нормальной формой.
Примеры
1)
2)
|
x1 |
x2 |
f |
|
0 |
0 |
0 |
|
0 |
1 |
1 |
|
1 |
0 |
1 |
|
1 |
1 |
0 |
3)
|
x1 |
x2 |
x3 |
f |
|
0 |
0 |
0 |
0 |
|
0 |
0 |
1 |
1 |
|
0 |
1 |
0 |
1 |
|
0 |
1 |
1 |
1 |
|
1 |
0 |
0 |
1 |
|
1 |
0 |
1 |
0 |
|
1 |
1 |
0 |
1 |
|
1 |
1 |
1 |
1 |
4)
|
x1 |
x2 |
x3 |
x4 |
|
|
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
1 |
1 |
|
0 |
0 |
1 |
0 |
0 |
|
0 |
0 |
1 |
1 |
0 |
|
0 |
1 |
0 |
0 |
1 |
|
0 |
1 |
0 |
1 |
0 |
|
0 |
1 |
1 |
0 |
0 |
|
0 |
1 |
1 |
1 |
0 |
|
1 |
0 |
0 |
0 |
1 |
|
1 |
0 |
0 |
1 |
1 |
|
1 |
0 |
1 |
0 |
0 |
|
1 |
0 |
1 |
1 |
0 |
|
1 |
1 |
0 |
0 |
0 |
|
1 |
1 |
0 |
1 |
0 |
|
1 |
1 |
1 |
0 |
1 |
|
1 |
1 |
1 |
1 |
0 |
5)
А также другие работы, которые могут Вас заинтересовать | |||
| 83806. | Рассмотрение жалобы и принятие решения по ней. Последствия подачи жалобы | 39.84 KB | |
| Вышестоящий орган или вышестоящее должностное лицо в месячный срок со дня получения жалобы обязаны ее рассмотреть и принять одно из сле6дующих решений: оставить жалобу без удовлетворения; отменить акт налогового органа и назначить дополнительную проверку; отменить решение и прекратить производство по делу о налоговом правонарушении; изменить решение или вынести новое решение по суще6ству обстоятельств дела. Законодательством РФ предусмотрены следующие способы судебной защиты прав налогоплательщиков: признание неконституционным... | |||
| 83807. | Административный порядок защиты нарушенных прав налогоплательщиков | 40.72 KB | |
| Вместе с тем административный порядок не отрицает возможности обращения в последствии за защитой в суд либо предоставляется альтернативный порядок защиты прав субъектов налоговых правоотношений. Вместе с тем НК РФ устанавливает два условия соблюдение которых необходимо для защиты нарушенных прав налогоплательщиков или налоговых агентов: ненормативные акты налоговых органов а также действия бездействие должностных органов этих органов должны по мнению налогоплательщика или налогового агента нарушать их права; нормативные правовые... | |||
| 83808. | Судебный порядок защиты нарушенных прав налогоплательщиков | 39.8 KB | |
| Законодательством РФ предусмотрены следующие способы судебной защиты прав налогоплательщиков: признание неконституционным законодательного акта полностью или в части Конституционным Судом РФ; признание арбитражными судами или судами общей юрисдикции недействительным нормативного либо ненормативного акта налогового органа иного государственного органа или органа местного самоуправления противоречащего закону и нарушающего право и законные интересы налогоплательщика; отмена арбитражными судами или судами общей юрисдикции не... | |||
| 83809. | Современные тенденции совершенствования налоговой системы Российской Федерации | 39.76 KB | |
| Основные направления налоговой политики принимаются ежегодно Основные направления бюджетной политики на 2015 год и на плановый период 2016 и 2017 годов принимаются и рассматриваются одновременно с проектом закона о федеральном бюджете на текущий период 3 года и утверждаются на заседании правительства РФ. Политики: Поддержка инвестиций Развитие человеческого капитала Повышение предпринимательской активности. | |||
| 83810. | Налоговое администрирование. Структура налоговых органов РФ, их полномочия и функции | 41.21 KB | |
| Структура налоговых органов РФ их полномочия и функции. Нет единой точки зрение на определение налогового администрирования Налоговое администрирование система управления налоговыми правоотношениями или всем комплекс налоговых отношений Титов Налог.администрирование деятельность и управление налоговых органов по осуществлению контроля за соблюдением налогового законодательства. Однако все определения условно можно объединить в 3 блока: Связанные с управлением Не связанные с управлением Опровергающие существование самого этого понятия... | |||
| 83811. | Правовое положение, функции и полномочия Министерства финансов РФ в налоговой сфере | 41.23 KB | |
| Министерство финансов Российской Федерации Минфин России является федеральным органом исполнительной власти осуществляющим функции по выработке государственной политики и нормативноправовому регулированию в сфере бюджетной налоговой страховой валютной банковской деятельности государственного долга аудиторской деятельности бухгалтерского учета и бухгалтерской отчетности производства переработки и обращения драгоценных металлов и драгоценных камней таможенных платежей определения таможенной стоимости товаров и транспортных... | |||
| 83812. | Правовое положение Федеральной налоговой службы и её органов (структурных подразделений) | 40.57 KB | |
| Основные функции возложенные на ФНС России по контролю и надзору: за соблюдением законодательства РФ о налогах и сборах; за правильностью исчисления полнотой своевременностью внесения в соответствующий бюджет налогов и сборов и иных обязательных платежей; за производством и оборотом этилового спирта спиртосодержащей алкогольной и табачной продукции; за соблюдением валютного законодательства в пределах компетенции налоговых органов; за информированием налогоплательщиков по вопросам налогового законодательства и разъяснением системы... | |||
| 83813. | Анализ действующей налоговой системы, современного налогового законодательства и направления налоговой реформы | 40.05 KB | |
| Основные направления налоговой политики принимаются ежегодно Основные направления бюджетной политики на 2015 год и на плановый период 2016 и 2017 годов принимаются и рассматриваются одновременно с проектом закона о федеральном бюджете на текущий период 3 года и утверждаются на заседании правительства РФ. Политики: Поддержка инвестиций Развитие человеческого капитала Повышение предпринимательской активности. | |||
| 83814. | Правовое регулирование налога на добавленную стоимость: налогоплательщики и основные элементы налога | 44.09 KB | |
| НДС это косвенный налог. Плательщиками НДС признаются: организации в том числе некоммерческие предприниматели Условно всех налогоплательщиков НДС можно разделить на две группы: налогоплательщики внутреннего НДС т. НДС уплачиваемого при реализации товаров работ услуг на территории РФ налогоплательщики ввозного НДС т. НДС уплачиваемого при ввозе товаров на территорию РФ Освобождение от исполнения обязанностей плательщиков НДС Организации и предприниматели у которых за 3 предшествующих последовательных календарных месяца сумма... | |||
