WWW.LIBRUS.DOBROTA.BIZ
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - собрание публикаций
 

«Линейная имплицента функции. Линейная конъюнктивная нормальная форма (ЛКНФ). Нахождение всех линейных имплицент функции. Проверка представимости ЛКНФ. Лектор Селезнева Светлана Николаевна ...»

Лекция 3. Полином Жегалкина .

Способы

построения полинома Жегалкина функции .

Линейная имплицента функции. Линейная

конъюнктивная нормальная форма (ЛКНФ) .

Нахождение всех линейных имплицент функции .

Проверка представимости ЛКНФ .

Лектор Селезнева Светлана Николаевна

selezn@cs.msu.ru

факультет ВМК МГУ имени М.В. Ломоносова

Лекции на сайте http://mk.cs.msu.ru

Полиномы Построение Алгоритм ЛКНФ Линейные имплиценты Построение ЛКНФ Представимость ЛКНФ

Монотонная ЭК ЭК, в которой не встречаются отрицания переменных, назовем монотонной ЭК, или мономом .

Т.е. монотонной ЭК называется выражение (формула) вида xi1 ·... · xir, где xi1,..., xir различные переменные, или константа 1 .

Например, x1, x1 x3 x4, 1 монотонные ЭК .

Полиномы Построение Алгоритм ЛКНФ Линейные имплиценты Построение ЛКНФ Представимость ЛКНФ Полином Жегалкина Полиномом Жегалкина длины l, l 1, называется сумма по модую два различных монотонных ЭК .

Полиномом Жегалкина длины 0 назовем константу 0 .

Т.е. полиномом Жегалкина называется выражение (формула) вида K1... Kl, где K1,..., Kl различные монотонные ЭК, или константа 0 .

Считаем, что два полинома Жегалкина совпадают, если они отличаются только порядком входящих в него ЭК .

Полиномы Построение Алгоритм ЛКНФ Линейные имплиценты Построение ЛКНФ Представимость ЛКНФ Приведение к полиному Жегалкина Отметим, что любую сумму по модулю два монотонных ЭК с коэффициентами из E2 при помощи тождественных преобразований алгебры логики можно привести к какому-то полиному Жегалкина .

Примем, что любая сумма по модулю два монотонных ЭК с коэффициентами из E2 всегда приведена к соответствующему полиному Жегалкина .

Полиномы Построение Алгоритм ЛКНФ Линейные имплиценты Построение ЛКНФ Представимость ЛКНФ Представление функций полиномами Жегалкина Каждый полином Жегалкина определяет какую-то функцию f P2 .

Каждая функция f P2 может быть представлена однозначным полиномом Жегалкина Pf .

Полиномы Построение Алгоритм ЛКНФ Линейные имплиценты Построение ЛКНФ Представимость ЛКНФ Критерий существенности переменной Утверждение 1. Переменная xi, 1 i n, встречается в (n) полиноме Жегалкина Pf функции f P2 тогда и только тогда, когда xi является существенной переменной функции f .

Доказательство .

1. Если переменная xi не встречается в полиноме Жегалкина Pf, то xi не может быть существенной переменной функции f .

Полиномы Построение Алгоритм ЛКНФ Линейные имплиценты Построение ЛКНФ Представимость ЛКНФ Критерий существенности переменной

2. Пусть переменная xi встречается в полиномеЖегалкина Pf .

Не ограничивая общности рассуждений, пусть i = 1. Тогда

–  –  –

(n) Если f P2, то ее полином Жегалкина Pf однозначно определяется своими коэффициентами при всех возможных монотонных ЭК над переменными x1,..., xn .

Полиномы Построение Алгоритм ЛКНФ Линейные имплиценты Построение ЛКНФ Представимость ЛКНФ

–  –  –

некоторым другим заданным множеством n переменных .

Каждый раз будет ясно над каким множеством переменных рассматриваются мономы .

Полиномы Построение Алгоритм ЛКНФ Линейные имплиценты Построение ЛКНФ Представимость ЛКНФ

–  –  –

Построение полинома Жегалкина Из теоремы 1 извлекаем следующий способ построения полинома Жегалкина функции f P2 по вектору ее значений .





Полиномы Построение Алгоритм ЛКНФ Линейные имплиценты Построение ЛКНФ Представимость ЛКНФ Построение полинома Жегалкина по вектору значений Пример. Построим по алгоритму 3 полином Жегалкина Pf функции f (x1, x2, x3 ) P2 по ее вектору значений

f = (0110 1001):

–  –  –

Приведение к ЛФ Отметим, что любую сумму по модулю два переменных с коэффициентами из E2 или констант при помощи тождественных преобразований алгебры логики можно привести к некоторой ЛФ .

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

Полиномы Построение Алгоритм ЛКНФ Линейные имплиценты Построение ЛКНФ Представимость ЛКНФ

ЛКНФ

Линейной конъюнктивной нормальной формой (ЛКНФ) длины l, l 1, назовем конъюнкцию l различных ЛФ .

Линейными конъюнктивными нормальными формами длины 0 назовем константы 0 и 1 .

Считаем, что две ЛКНФ совпадают, если они отличаются только порядком входящих в них ЛФ .

Полиномы Построение Алгоритм ЛКНФ Линейные имплиценты Построение ЛКНФ Представимость ЛКНФ Приведение к ЛКНФ Отметим, что любую конъюнкцию ЛФ или констант при помощи тождественных преобразований алгебры логики можно привести к некоторой ЛКНФ .

Полиномы Построение Алгоритм ЛКНФ Линейные имплиценты Построение ЛКНФ Представимость ЛКНФ Представимость ЛКНФ

–  –  –

Конъюнкция всех линейных имплицент функции Утверждение 2. Конъюнкция Lf всех линейных имплицент функции f P2 является ЛКНФ, представляющей эту функцию f, тогда и только тогда, когда функция f представима ЛКНФ .

Полиномы Построение Алгоритм ЛКНФ Линейные имплиценты Построение ЛКНФ Представимость ЛКНФ Конъюнкция всех линейных имплицент функции Доказательство .

(n) n

1. Пусть f P2 представима ЛКНФ и E2 .

1.1. Если f () = 0, то, т.к. функция f представима ЛКНФ, найдется какая-то линейная имплицента L функции f, что L() = 0 .

Но Lf содержит все линейные имплиценты функции f, поэтому L входит в Lf. Значит, Lf () = 0 .

1.2. Если же f () = 1, то ни одна линейная имплицента функции f не может принимать на наборе нулевое значение по определению линейной имплиценты функции. Поэтому Lf () = 1 .

Полиномы Построение Алгоритм ЛКНФ Линейные имплиценты Построение ЛКНФ Представимость ЛКНФ Конъюнкция всех линейных имплицент функции Доказательство .

2. Если f P2 не представима ЛКНФ, то конъюнкция всех ее линейных имплицент не может представлять эту функцию f, т.к. сразу появляется противоречие .

Полиномы Построение Алгоритм ЛКНФ Линейные имплиценты Построение ЛКНФ Представимость ЛКНФ Сокращенная ЛКНФ Если функция f P2 представима ЛКНФ, то конъюнкция Lf всех линейных имплицент функции f называется ее сокращенной ЛКНФ .

По определению для каждой функции f P2, представимой ЛКНФ, ее сокращенная ЛКНФ Lf единственна .

Полиномы Построение Алгоритм ЛКНФ Линейные имплиценты Построение ЛКНФ Представимость ЛКНФ Нахождение всех линейных имплицент функции

Правильность алгоритма 4 следует из следующего свойства:

ЛФ L является линейной имплицентой функции f P2 тогда и только тогда, когда L · f = f .

Отметим, что алгоритм 4 имеет полиномиальную сложность относительно N = n · l, где n число переменных функции f P2, а l длина полинома Жегалкина Pf .

Полиномы Построение Алгоритм ЛКНФ Линейные имплиценты Построение ЛКНФ Представимость ЛКНФ Нахождение всех линейных имплицент функции Пример. Найдем по алгоритму 4 все линейные имплиценты функции f P2 по ее полиному Жегалкина

–  –  –

найдены все ее линейные имплиценты: L1 = 1 и L2 = x1 x2 .

Несложно увидеть, что функция f не совпадает с конъюнкцией всех своих линейных имплицент, поэтому по утверждению 2 функция f не представима ЛКНФ .

Полиномы Построение Алгоритм ЛКНФ Линейные имплиценты Построение ЛКНФ Представимость ЛКНФ

3. P0 = 1 x2 x2 x3 = 1, поэтому ответ нет .

Полиномы Построение Алгоритм ЛКНФ Линейные имплиценты Построение ЛКНФ Представимость ЛКНФ Правильность алгоритма 5 Теорема 2. Алгоритм 5 работает правильно, т.е. он выдает да, если Pf = L1 ·... · Lm, и нет в противном случае .

Доказательство. Докажем утверждение теоремы индукцией по числу n существенных переменных функции f .

Базис индукции n = 0 верен .

Полиномы Построение Алгоритм ЛКНФ Линейные имплиценты Построение ЛКНФ Представимость ЛКНФ

Правильность алгоритма 5

Индуктивный переход: пусть для всех функций f P2, f = 0, c менее n существенными переменными, n 1, алгоритм 5 работает правильно .

(n) Пусть функция f P2, f = 0, существенно зависит от n переменных, Pf ее полином Жегалкина и L1,..., Lm какие-то ее линейные имплиценты, среди которых ЛФ L0 не равна константе 1 .

Полиномы Построение Алгоритм ЛКНФ Линейные имплиценты Построение ЛКНФ Представимость ЛКНФ Правильность алгоритма 5 Не ограничивая общности рассуждений, пусть

–  –  –

Но L0 линейная имплицента функции f. Поэтому f () = 0 .

Значит, равенство Pf = L1 ·... · Lm выполняется на всех n наборах из E2 тогда и только тогда, когда оно выполняется на всех наборах из E .

Полиномы Построение Алгоритм ЛКНФ Линейные имплиценты Построение ЛКНФ Представимость ЛКНФ Проверка представимости ЛКНФ Отметим, что алгоритм 5 имеет полиномиальную сложность относительно N = n · (l + m), где n число переменных функции f P2, l длина полинома Жегалкина Pf, а m число линейных имплицент функции f .

Полиномы Построение Алгоритм ЛКНФ Линейные имплиценты Построение ЛКНФ Представимость ЛКНФ Проверка представимости ЛКНФ Пример. При помощи алгоритмов 4 и 5 выяснить, представима ли ЛКНФ функция f P2,

–  –  –

Мы исключаем L3, т.к. L3 = 1.




Похожие работы:

«ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР ПО СТАНДАРТАМ СВЕРДЛОВСКИЙ ФИЛИ АЛ ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ВСЕСОЮЗНОГО НАУЧНО-ИССЛЕДОВАТЕЛЬСКОГО ИНСТИТУТА МЕТРОЛОГИИ им . Д. И. МЕНДЕЛЕЕВА (СФ ВНИИМ] МЕТОДИКА ПОВЕРКИ А В ТО М А ТИ Ч ЕС КИ Х П РО М Ы Ш Л ЕН Н Ы Х ГА ЗО А Н А Л И ЗА ТО РО В Н А М ИКРО КО НЦЕНТРАЦ И И С ЕРН...»

«свящ. Геннадий Егоров, проректор по учебной работе ПСТГУ, декан ФДО ПСТГУ 2004О профессиональной составляющей подготовки выпускника по программе "Теология" ФДО. Доклад на заседании кафедры Теологии ФДО Концепция, положенная в основание всех последующих рассуждений, может быть сформулир...»

«RU Инструкция пользователя TuneBase™ FM для iPod Вступление Ваш TuneBase FM может заряжать, проигрыавть и удерживать Ваш во время вождения. Эта инструкция объяснит как Вы сможете использовать Ваш TuneBase FM, чтобы получить максимум от iPod где бы Вы не находились. Ни в коем случае не настраивайте Tunebase FM во время вождения...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ "УРАЛЬСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ ИМЕНИ ПЕРВОГО ПРЕЗИДЕНТА РОССИИ Б. Н. ЕЛЬЦИНА" ИНСТИТУ...»

«MH_C9000 ЗАРЯДНОЕ УСТРОЙСТВО Описание МН-С9000;Данное устройство позволяет заряжать, определять состояние и восстанавливать независимо друг от друга от одной до четырех АА или ААА батареек.Большой LCD дисплей с подсветкой...»

«Приложение 1 Утверждено Наблюдательным советом Банка ВТБ (ПАО) (Протокол от "09" апреля 2018 № 4) ПОЛОЖЕНИЕ о закупках товаров, работ, услуг Банка ВТБ (ПАО) Оглавление Термины и определения Общие положения 1. Организация и информационное обеспечение закупочной деятельности 2.2.1. Организация заку...»

«AM9800001,1525(20)_91 Препринт ЕфИ ЕРЕВАНСКИЙ ФИЗИЧЕСКИЙ ИНСТИТУТ YEREVAN PHYSICS INSTITUTE А.Э.АВЕТИСЯН,Ф.В.АДА1.5ЯН,А.В.АЙРА11ЕТНН,Г.Г.АКШЯН, А.Ю.БУНЯТЯН.А.Г.ВАРТАПВТЯН.В.Г.ВОЛЧИНСКИЙ.Й.П.ВЭТСШОВ, П.И.ГАЛУМЯН.В.О.ГРАБСКИЙ.Г.В.КАРАНЕТЯН.Г-.С.КОРДОНСКИЙ, Р.0.0ГАНЕ30В.В....»

«Л 1. А. Герм ан К осм ические м ет оды и сслед о ва ни я в м ет еорологии Допущено Министерством высшего и среднего специального образования СССР в качестве учебника для студентов вузов, обучающихся по специальности "Метеорология" Г ш/ Ленинград Гидрометеоиздат 1985 У Д К [5 5 1.5 0 1 : 6 2 9,7 8 3 ] (0 7 5.8...»

«"КАМАЗ" сегодня Основные сведения Группа компаний "КАМАЗ" — крупнейшая автомобильная корпорация Российской Федерации. ОАО "КАМАЗ" занимает 11-е место среди ведущих мировых производителей тяжелых грузовых автомобилей и 8-е место в м...»







 
2019 www.librus.dobrota.biz - «Бесплатная электронная библиотека - собрание публикаций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.