рефераты конспекты курсовые дипломные лекции шпоры

  • Раздел Образование
  •  / 
  • Минимизация частично определенных функций

Реферат Курсовая Конспект

Минимизация частично определенных функций

Минимизация частично определенных функций - раздел Образование, УСМАНОВА Зинира Масгутовна Пусть Функция F(X1,…,XN) Частично ...

Пусть функция f(x1,…,xn) частично (не всюду) определена. Если f не определена на p наборах из 0 и 1, то существует 2p возможностей для доопределения функции f. Полностью определенная функция g (x1,…,xn) есть доопределение функции f, если g совпадает с f на тех наборах из 0 и 1, на которых f определена.

Задача минимизации частично определенной функции f сводится к отысканию такого доопределения g функции f, которое имеет простейшую (по числу букв ) минимальную форму.

Обозначим через f0(x1,…,xn) и f1(x1,…,xn) доопределения нулями и единицами соответсвенно частично определенной функции f(x1,…,xn).

Теорема. Минимальная ДНФ частично определенной функции f(x1,…,xn) есть дизъюнкция самых коротких импликант в сокращенной ДНФ доопределения f1(x1,…,xn), которые в совкупности накрывают все конституенты единицы доопределения f0(x1,…,xn).

Доказательство. Рассмотрим СДНФ некоторого доопределения g(x1,…,xn) функции f(x1,…,xn). Конституенты единицы, входящие в эту форму, войдут и в СДНФ доопределения f1. Поэтому любой простой импликант функции g будет совпадать с некоторым импликантом функции f1 или накрываться им. Самые короткие импликанты , накрывающие единицы функции f , есть импликанты функции f1. Доопределение f0 имеет минимальное количество конституент единицы в своей СДНФ , следовательно , и количество простых импликант функции f1 , потребных для накрытия этих конституент , будет наименьшим . ДНФ , составленная из самых коротких простых импликант в сокращенной ДНФ функции f1 , накрывающих все конституенты единицы функции f0 , будет самой короткой ДНФ, доопределяющей функцию f .

Так как единицы функции f1 составлены из единиц функции f и единиц на наборах , на которых f не определена , то построенная ДНФ , накрывая все единицы функции f0 ( а , следовательно , и все единицы функции f ) , совпадает с минимальной ДНФ некоторого доопределения g функции f .

 

Развернуть
Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

УСМАНОВА Зинира Масгутовна

АХМЕТОВА Наиля Абдулхамитовна УСМАНОВА Зинира... Замыкание и замкнутые классы...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Минимизация частично определенных функций

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

УСМАНОВА Зинира Масгутовна
    Дискретная математика Функции алгебры логики Учебное пособие   Редактор Г.Р. Орлова

Редакционно – издательский комплекс УГАТУ
450000, Уфа-центр, ул. К. Маркса, 12     Содержание Введение ………………………………………………………...............3 1. Элементы комбинаторики ……………………………………...

Перестановки. Размещения. Сочетания
  Пусть есть некоторое конечное множество элементов U={a1, a2, ..., an}. Рассмотрим набор элементов

Элементарные функции алгебры логики
Обозначения: E2={0,1}; Е= E

Теорема о замене подформул на эквивалентные
  Пусть NÎ<M> и имеет вид: N(x1, ..., xn) = g(G1, ...Gi, ...,Gm

Некоторые свойства элементарных функций
  1. Идемпотентность & и Ú: х&x=x , xÚx=x. 2. Коммутативность &,Ú,Å,|,~,

Принцип двойственности
Определение 1. Функции f*(x1, ..., xn) называется двойственной к функции f(x1, ..., xn

Принцип двойственности
Теорема: Пусть функция h(x1, ..., xn) реализована формулой h(x1, ..., xn) = =g

Лемма о несамодвойственной функции
  Подстановкой функций и

Разложение булевой функции по переменным
Обозначим xs= Посмотрим, чему равно xs при разных

Теорема о разложении функции по переменным
  Пусть f(x1, ..., xn) Î P2.

Полные системы
1. P2 – полная система. 2. Система M={x1&x2, x1Úx2,

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

Составим критериальную таблицу для другой полной системы функций из Р2: {0, 1, x1x2, x1Åx2}.
  Т0 Т1 L M S + -

Теорема о достаточности четырех функций.
Из любой полной в Р2 системы функций можно выделить полную подсистему, состоящую не более чем из четырех функций. Доказательство. Пусть {f

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

Минимизация нормальных форм
Минимальной ДНФ (МДНФ) функции f(x1, ... ,xn) называется ДНФ, реализующая функцию f и содержащая минимальное число символов пе

Алгоритм Квайна построения сокращенной ДНФ.
1. Получить СДНФ функции f. 2. Провести все операции неполного склеивания. 3. Провести все операции поглощения. Пример 1. Построим сокращенную

Метод Блейка
Метод Блейка для построения сокращенной ДНФ из произвольной ДНФ состоит в применении правил обобщенного склеивания и поглощения. Подразумевается, что правила применяются слева направо. На первом эт

Алгоритм построения сокращенной ДНФ с помощью КНФ
(метод Нельсона) Пусть f(x1, … , xn) есть некоторая функция алгебры логики. Построим для f некоторую КНФ. Осуществим дале

Построение всех тупиковых ДНФ.
Пусть f(x1, …, xn) есть функция алгебры логики. 1. Построим СДНФ функции f, и пусть P1, P2, …,P

Метод минимизирующих карт Карно
  При построении сокращенных ДНФ для функций, зависящих от небольшого числа (не более 4) переменных, используется метод карт Карно. Построение карт Карно основано на свойствах булева

Задачи по минимизации и доопределению булевых функций
1. Из заданного множества А элементарных конъюнкций выделить простые импликанты функции f : 1) A =

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

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги