Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Минимизация булевых функций.

Интерпретация алгебры логики в исчисление высказываний. | Интерпретация алгебры логики в теории множеств. | Интерпретация алгебры логики в теории конечных автоматов. | Анализ простейших рассуждений. | Методы доказательств. | Предикаты. | Кванторы. | Формулы исчесления предикатов. | Операции логики высказываний над предикатами. | Равносильные формулы в исчислении предикатов. |


Читайте также:
  1. Геометрическое представление булевых функций.
  2. Если рассматривать общение вопределенной системе отношений, то можно выделить совокупность групп функций.
  3. Методы минимизации булевых функций.
  4. Непрерывность функции в точке.Точки разрыва функции и их классификация.Свойства непрерывных функций.Свойства функций,непрерывных на отрезке.
  5. Основные классы булевых функций.
  6. Понятия бесконечно малой и бесконечно большой функций. Сформулировать теоремы о свойстврх бесконечно малых функций.

А↔{P,O={,&,V,→,~}} – алгебра логики.

P↔{P1,...,Pn}.

Алгебра – есть объект с разрешенными операциями над ним.

 

1. Алгебра чисел.

А1↔{N,C,R,D,{+,-,*,/,...}}, где N, C, R, D – числовые объекты

{+, -, *, /,...} – операции над числами

N – натуральное, C – целое, R – рациональное, D – действительное.

Джордж Буль – английский математик (отец писательницы, написала книгу «Овод», рассмотрел алгебру, которую в честь его называют булевой).

Аб↔{{1,0},{,&,V,→,~,↓,∆,o}}, где {1,0} – объекты.

Буль предложил рассмотреть в качестве чисел только 2 числа 1 и 0, а разрешенные операции над ними не числовые, а логические.


Аб↔{{1,0},{,…o}} сопоставляем.

↓ ↓

А↔{{И,Л},{,…~}}

 

  x f0(x) f1(x) f2(x) f3(x)
1)          
2)          
    f0=0 “const 0” f1=1 “const 1” f2=x f3=x

Взяв 1 аргумент мы получаем 4 функции, которые принимают значение {1,0}.

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

f(x1,x2,...xi...xn) если

f(x1,x2,...0...xn)

f(x1,x2,...1...xn)

то говорят, что задана функция несуществующая зависящая от x.

xi – называется несуществующим аргументом.

 

  x1 x2 f0(x1,x2) f1 f2 f3 f4 f5
                 
                 
                 
                 
      f0↔0 f1↔1 f2=x1 f3=x2 f4=x1&x2 f5=x1Vx2

 

f6 f7 f8 f9 f10
         
         
         
         
f6=x1→x2 f7=x1~x2 f8=x1↓x2 f9=x1/x2 f10=x1∆x2

 

f8 → операция Вебба (x1ox2)

операция Пирса (x1↓x2) – чаще употребляется.

f9 – операция Шеффера (x1/x2)

f10 – операция по модулю 2(mod2) (x1∆x2).

В булевой алгебре при числе переменных n, то набор 2n, а число функций .

Эти функции (f0-f10) наряду с рассмотренными функциями для x1, называются простейшими элементарными функциями булевой алгебры.

Остальные симметрично относительно главной диагонали. Бинарные булевы операции подчиняются законам ассоциативности, коммутативности, дистрибутивности.

1) pVq↔qVp => x1Vx2↔x2Vx1

2) p&(qVr)↔(p&r)V(p&r) => x1&(x2Vx3)↔(x1&x2)V(x1&x3)

переписываем все ↔-ти алгебры логики на язык булевских функций.

В алгебре Буля можно указать каноническое или стандартное представление функции СДНФ, ДНФ, СКНФ, КНФ.

Рассмотрим базис логических операций в булевой алгебре:

{,&,V,~,→,∆,/,↓}

мы замечаем, что с первыми 5 операциями мы уже познакомились в алгебре логики, рассмотрим последние.

(↓) – стрелка Пирса и (/) – операция Шеффера связаны законами де Моргана.

1. это аналоги законов де Моргана.

2.

3. если ,

(↓) и (/) называются универсальными, т.к. одной из этих операций можно представить любую булевскую функцию.

(возникает вопрос:)

функций от n – аргументов

Аn – число функций существующих, зависящих от

число сочетаний, бином Ньютона.

При n=2, A2=10.

{-,&,V, →,~,∆,↓,/} – базис булевых операций.

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

Пусть задано R-множество булевских функций. И задано конечное множество функций вида {f1,...fm}.

Df1. Тогда говорят, что система функции {f1,...fm} является базисом, если с помощью этих функций (применяя операции переименования переменных или суперпозиции) мы можем описать любую функцию f из множества .

Если мы какую-то функцию fi опустим, мы уже не получим нужное количество функций для описания f из R.

Базис называется минимизированным, если ин содержит наименьшее число функций для описания функции .

Базис является максимальным, если все множество R не что иное как сами функции.

Стрелка Пирса и оператор Шеффера могут с помощью самих себя описать любую булевскую функцию {/}, {↓}.

Максимальным базисом от функции n-аргументов является полный набор из функций.

По аналогии с ФАЛ мы можем представить булевы функции в каноническом виде, т.е. в СКНФ или СДНФ, либо в КНФ или ДНФ.

f(x1,x2,x3)ДНФ=x1V(x2&x3)

f(x1,x2,x3)КНФ=x1&(x2Vx3)

, таких выражений будет

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

 

  x1 x2 F1  
        10&x20= х1&x2
        10&x21= х1&x2
        11&x20= х1&x2
        11&x21= х1&x2

 


V

1. исходная функция должна быть представлена в виде таблицы своих значений.

2. в таблице значений функций отмечаются те наборы аргументов, на которых функция равна 1 (в данном случае это 1,2,4).

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

, если αi=1

, если αi=0 – конкретное значение переменной.

4. собираем из знаков дизъюнкции

В СДНФ можно представить любую функцию, кроме функции тождественно-равной 0.

В CКНФ мы не можем представить лишь функцию ↔ И.

1. Исходная функция должна быть представлена в виде таблицы своих значений.

2. В таблице значений функций отложим те наборы аргументов, где функция принимает нулевое значение.

3. Каждое из нулевых значений распишем в виде элементарной дизъюнкции, по следующему правилу:

, если αi=0

, если αi=1

и получим элементарную V соединенную знаком &.

Рассмотрим по предыдущей переменной:

Пример:

(&) заменим на (.)

добавим для доказательства

т.к. при этом ничего не изменится (xVx↔x)

 

объединяем 1-ую и 2-ую, 3-ую и 4-ую,

5-ую и 6-ую.

Мы рассмотрели задачу минимизации на примере, а теперь рассмотрим формально. Задачу минимизации будем рассматривать в классе ДНФ.

Df1. рангом элементарной конъюнкции называется членом, который раньше мы называли длиной.

Df2. ДНФ функция называют ее представленной в базисе {,&,V} с помощью дизъюнкции элементарной конъюнкций ранга ≤ R.

Df3. длиной ДНФ называют число элементарной конъюнкции ранга ≤ n.

Df4. CДНФ есть ДНФ, где все элементы конъюнкции имеют ранг = n.

Df5. 1. минимизация ДНФ (сокращено МДНФ) называют такое представление булевых функций, которое содержит min число букв для описания исходной булевой функции (см. предыдущий пример, где последняя запись x1Vx2x3 – есть МДНФ).

2. постановка задачи min является сокращение числа логических операций.

3. постановка – является сокращение одновременно и числа букв и числа операций, это постановка получила название абсолютной минимизации.

Замечания:

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


Дата добавления: 2015-09-01; просмотров: 67 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Подходы к построению выводов.| Геометрическое представление булевых функций.

mybiblioteka.su - 2015-2024 год. (0.013 сек.)