Описание слайда:

§ 2. ОСНОВНЫЕ ПОЛОЖЕНИЯ БУЛЕВОЙ АЛГЕБРЫ

Описание слайда:

2.1. БУЛЕВА АЛГЕБРА И ЕЕ ПРИМЕНЕНИЕ 2.1.1. Определение булевой алгебры

Описание слайда:

Название этого раздела математики связано с именем его основателя – Джорджа Буля . БУЛЬ (Boole) Джон английский математик и логик, один из основоположников математической логики. Разработал алгебру логики (булеву алгебру) («Исследование законов мышления», 1854), основу функционирования цифровых компьютеров.

Описание слайда:

Используя классическое понятие алгебры, булеву алгебру можно определить как систему А=(В,φ 1 ,φ 2 ,…, φ n ) , в которой несущим множеством является двухэлементное множество двоичных чисел В={0,1}, а Ώ={ φ 1 ,φ 2 ,…, φ n } – заданные на этом множестве логические операции, сущность которых рассмотрим позднее.

Описание слайда:

Основные логические операции, - дизъюнкция , конъюнкция и отрицание , - можно интерпретировать как операции, введенные в теории множеств: свойства указанных операций аналогичны свойствам операций объединения, пересечения и дополнения множеств соответственно. Однако логические операции имеют несколько иной смысл; они позволяют формировать простые и сложные высказывания. Все множество логических операций обозначается Е 2 .

Описание слайда:

Как правило, существует логическая интерпретация элементов множества В : 1 – истинно; 0 – ложно. В ряде случаев такой смысл не придается, и в качестве элемента множества рассматривается двоичная переменная (ее называют также логическая или булева переменная ) x , которая принимает значения x = 0 или x = 1.

Описание слайда:

2.1.2. Области применения булевой алгебры

Описание слайда:

Булева алгебра применяется: 1) как средство алгоритмического описания в языках программирования для определения логических условий; 2) как средство формирования логических высказываний в математической логике, лингвистике, теории искусственного интеллекта; 3) как средство разработки и описания дискретных технических систем; 4) как формальная модель лежащая в основе языков программирования.

Описание слайда:

Алгебра логики позволяет производить анализ и синтез логических устройств. Анализ – это поиск аналитического выражения, которое описывает работу системы. Синтез – обратная задача: создание технического устройства на основе математического описания средствами булевой алгебры.

Описание слайда:

2.1.3. Высказывания

Описание слайда:

Одним из базовых понятий в булевой алгебре является понятие высказывания . Высказывание – это любое повествовательное предложение, в отношении которого имеет смысл утверждение о его истинности или ложности. Обычно высказывания обозначаются буквами латинского алфавита: . Для каждого высказывания вводится значение истинности , которое может принимать одно из двух возможных: значений 1 – истина, 0 – ложь.a b c A B C , , , , ,

Описание слайда:

Пример. Рассмотрим справедливость утверждений: а) число 4 – четное; b ) снег – красный; с) 2*2=5 . Значения истинности данных высказываний следующие: a=1, b=0, c=0 .

Описание слайда:

Два высказывания A и B называются эквивалентными , если их значения истинности совпадают. Значение истинности может быть постоянным либо изменяется в зависимости от обстоятельств. Изменяемое высказывание может рассматриваться как переменный параметр – двоичная переменная, принимающая одно из двух значений (обозначается x, y, z ).

Описание слайда:

2.2. ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ

Описание слайда:

2. 2 . 1 . Понятие функции и способы ее задания

Описание слайда:

Пусть имеется n двоичных переменных x 1 , x 2 , …, x n . Каждая из них в некотором конкретном случае может принимать значение 0 или 1 . Полученный набор элементов есть двоичный вектор длины n . Каждому конкретному набору можно поставить в соответствии одно из значений 0 или 1 .

Описание слайда:

Функция f , задающая однозначное отображение множества всевозможных наборов значений двоичных переменных x 1 , x 2 , …, x n во множество {0,1} называется функцией алгебры логики (или логической функцией, булевой функцией, переключательной функцией): Таким образом, логическая функция – это зависимость, которая устанавливает связь между сочетанием значений входных двоичных переменных и двоичным значением этой функции.    f x x x y y y n 1 2 0 1 , ,..., ;    или

Описание слайда:

Способы задания функции. Логическая функция может быть задана: 1) математическим выражением (формулой); 2) таблицей. Таблица является наиболее общим и универсальным способом задания функции. В её левой части перечисляют всевозможные наборы значений двоичных переменных, а в правой — значения функции на этих наборах. Такие таблицы, описывающие функции, называют таблицами истинности . В таблицах 2.1 и 2.2 приведены примеры таблиц истинности.

Описание слайда:

Описание слайда:

Оценим число возможных наборов (число строк входных переменных). Конкретный набор – это вектор значений Количество наборов – это мощность прямого произведения n двухэлементных множеств B : где n – число входных элементов. nb b b ...,, , 2 1 a B B n n n    2

Описание слайда:

Оценим возможное количество вариантов логических функций от n переменных. Множество вариантов логической функции можно представить как прямое произведение: где B i – значение функции на наборе i . Таким образом, общее количество функций от n переменных где .M B B B B B i a a        1 2 ... ... m B Ba a a    2 a n  2

Описание слайда:

Наборы, на которых функция равна единице, называют единичными наборами, а наборы, на которых функция равна нулю, называют нулевыми . Если функция при любых значениях аргументов принимает значение 0 , то такую функцию называют нулевой или константой 0 ( тождественно ложная функция ). Функция, которая на всех наборах равна 1 , называется единичной или константой 1 ( тождественно истинная функция ). Если функция определена не на всех наборах аргументов, то она называется не полностью определенной или частично определенной .

Описание слайда:

Две булевы функции и называют равными , если для всех возможных наборов значений аргументов они принимают одинаковые значения и таким образом имеют одну и ту же таблицу истинности, и записывают:   f x x x n 1 2 , , ...,    x x x n 1 2 , , ...,     f x x x x x x n n 1 2 1 2 , , ..., , , ...,  

Описание слайда:

Говорят, что булева функция Существенно зависит от аргумента x i , если , хотя бы для одного набора остальных аргументов. В противном случае x i называется несущественной или фиктивной переменной (ее можно исключить).  f x x x n 1 2 , ,...,     f x x x x x f x x x x x i i n i i n 1 2 1 1 1 2 1 1 0 1 , ,..., , , ,..., , ,..., , , ,...,     

Описание слайда:

2.2.2. Элементарные логические операции

Описание слайда:

Из множества логических функций выделяется ряд наиболее простых операций, которые имеют ясную логическую интерпретацию: 1) отрицание (инверсия) (читается: не).   f x x 1  Отрицание – это функция, выражающая высказывание, которое истинно, если высказывание ложно, и ложно, если истинно .

Описание слайда:

2) дизъюнкция (логическое сложение) (читается: " x или y "). Дизъюнкция – это функция, выражающая высказывание, которое истинно тогда и только тогда, когда, по крайней мере, одно из высказываний x или y является истинным .  f x y x y 2 ,  

Описание слайда:

3) конъюнкция (логическое умножение) (читается: " x и y "). Для этой операции применяются также следующие формы записи: f 3 ( x , y )= xy = x & y . Конъюнкция – это функция, выражающая высказывание, которое истинно только в том случае, если истинны оба высказывания x и y  f x y x y 3 ,  

Описание слайда:

4) импликация (читается : “если x , то y ”). Функция f 4 принимает значение ложно только тогда, когда x истинно, а y ложно .  f x y x y 4 ,  

Описание слайда:

5) эквивалентность (равнозначность) (читается: “ x равно y ”). Функция f 5 =1 тогда и только тогда, когда значения обоих аргументов x и y совпадают   f x y x y 5 , ~ 

Описание слайда:

6) сложение по модулю два (неравнозначность) Функция f 6 истинна тогда и только тогда, когда значения аргументов различны, функция является обратной к f 5  f x y x y 6 ,  

Описание слайда:

7) штрих Шеффера Операция обратная по отношению к конъюнкции (функция ложна, только если оба аргумента истинны)   f x y x y 7 , 

Описание слайда:

8) стрелка Пирса Функция f 8 обратная к дизъюнкции ( f 8 истинно, только когда x и y ложны)   f x y x y 8 ,  

Описание слайда:

Наиболее важными функциями являются первые три. Остальные могут быть выражены через эти три функции. С использованием трех основных функций ( дизъюнкции , конъюнкции и отрицания ) могут образовываться более сложные функции. Поэтому можно дать еще одно определение булевой алгебры. Булевой алгеброй называется алгебра типа, несущим множеством которой является множество двоичных чисел, а операциями - конъюнкция, дизъюнкция и отрицание.  B , , ,  

Описание слайда:

2.2.3. Свойства основных логических функций

Описание слайда:

Основные логические функции обладают следующими свойствами: 1) коммутативность: 2) ассоциативность: 3) идемпотентность конъюнкции и дизъюнкции:a b b a    a b b a        a b c a b c      a b c a b c      ( ) ( ) a a a   a a a  

Описание слайда:

4) дистрибутивность: а) конъюнкции относительно дизъюнкции: б) дизъюнкции относительно конъюнкции: 5) двойное отрицание:       a b c a b a c             a b c a b a c       a a 

Описание слайда:

6) правило де Моргана: 7) правило склеивания: 8) правило поглощения: a b a b    a b a b    a b a b a    ( ) ( ) a b a b a     a ab a   a a b a    ( ) b a b a a    a a b a b     ( ) ;

Описание слайда:

9) действия с константами: Свойства основных булевых функций доказываются либо путем преобразования выражений , либо на основе сопоставления таблиц истинности правой и левой части равенства.a a   0 a   0 0 a   1 1 a a   1 a a   1 a a 0  

Описание слайда:

Пример. Доказать, что С учетом таблиц истинности элементарных логических операций определяем последовательно значения функций, указанных в верхней строке для всех возможных значений аргументов и , т.е. построим для них соответствующие им таблицы истинности a b a b   

Описание слайда:

Так как значения функций и на всех наборах совпадают, то эти функции равны.a b a b    a b  a b 

Описание слайда:

2.2.4. Задание функции формулой. Эквивалентные преобразования логических выражений

Описание слайда:

Понятие формулы вводится для формализации представления и записи простого или сложного высказывания. Формула рассматривается как некоторый способ реализации функции и вводится индуктивно в соответствии со следующим правилом: если А и В – высказывания (простые или сложные, постоянные или переменные), то запись значения истинности каждого из этих высказываний – есть формула; если А и В – формулы, то выражения « А * В » и « Ā » (где символ * обозначает знак одной из рассмотренных выше элементарных логических операций) – тоже формулы.

Описание слайда:

Таким образом, рассмотренные выше выражения, которыми описывались элементарные логические операции и свойства основных логических операций, - суть формулы . Применение по отношению к ним указанного правила позволяет получить новые формулы, соответствующие более сложным высказываниям. Новые формулы могут быть получены на основе использования понятия суперпозиции функций. Суперпозицией функций f 1 , f 2 , …, f n называется функция f , полученная путем подстановки функций f 1 , f 2 , …, f n друг в друга и переименования переменных.

Описание слайда:

Пусть имеется множество логических функций, заданных формулами Е={ f 1 , f 2 , …, f m } ; при этом говорят, что имеет место множество формул над Е . Тогда новую формулу можно получить используя следующее правило: Пусть – некоторая формула над E . Если – либо символы переменных, либо другие формулы над E , то – тоже формула над E .  n x ...,, x, x f 2 1 0 A A A n 1 2 , ,...,  n A ...,, A, A f 2 1 0

Описание слайда:

Пример. Пусть функция задана формулой , и при этом имеет место равенство Тогда новую формулу E над можно получить путем подстановки A 1 и A 2 в исходную формулу:   f z z z z 0 1 2 1 2 ,   3 2 2 2 1 1 1 , x A z x x A z          f x x x x x x 0 1 2 3 1 2 3 , ,   

Описание слайда:

Полученную формулу вновь представим как исходную, и, полагая далее делаем вновь подстановку. Тогда новая формула над E :  A f x x x A x A x x 1 0 1 2 3 2 3 3 1 2     , , , ,         f x x x x x x x x x 0 1 2 3 1 2 3 3 1 2 , ,      

Описание слайда:

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

Описание слайда:

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

Описание слайда:

Пример. Рассмотрим две формулы: и Несложно показать, что обе формулы представляют одну и ту же функцию, так как таблицы истинности у них одинаковы. Формулы, соответствующие одной и той же функции, называются эквивалентными или равносильными .  2121 , xxxxf    2 1 2 1, x x x x f  

Описание слайда:

Две формулы U и B называются эквивалентными ( равносильными ), если они реализуют одну и ту же функцию. При этом записывают: U=B . Эквивалентные преобразования логических выражений. Эквивалентные преобразования – это такие преобразования формул, при которых сохраняется их эквивалентность. Преобразование называется эквивалентным , если исходная формула и полученная в результате преобразования формула принимают одинаковые значения на каждом наборе значений аргументов .  U x x xn  1 2 , ,...,   B x x x n  1 2 , ,...,

Описание слайда:

Эквивалентное преобразование осуществляется на основе сопоставления таблиц истинности, либо на основе применения свойств основных логических операций. Покажем примеры эквивалентных преобразований, которые позволяют получить новые формулы для описания функций f 4 - f 8 (см. п. 1.2.2), используя только знаки операций конъюнкции, дизъюнкции и отрицания.

Описание слайда:

1.Преобразование формулы, описывающей функцию . Справедливость преобразования доказывается соответствующей таблицей истинности.b a b a: f    4

Описание слайда:

2 .Преобразование формулы, описывающей функцию . Справедливость преобразования доказывается соответствующей таблицей истинности.   a b b a b a ab b a f      ~ : 5

Описание слайда:

3. Функция f 6 4. Функция f 7 = 5. Функция f 8 =) ( ) ( ~ b a b a b a ab b a ab b a b a           b a a b a b  a b 

Описание слайда:

Формулы, из которых построена некоторая исходная формула, называются подформулами . Чаще всего эквивалентные преобразования основаны на замене подформул на эквивалентные им подформулы. Если в формуле U заменить подформулу B на эквивалентную ей под формулу B’ , то формула перейдет U в эквивалентную ей формулу U’ .

Описание слайда:

2.2.5. Двойственные функции

Описание слайда:

Логическая функция , равная , называется двойственной по отношению к функции . Очевидно свойство взаимности двойственных функций:  f x x x n * , , ..., 1 2   n x x x f ...,, , 2 1   f x x x n 1 2 , , ...,     f x x x f x x x n n ** , ,..., , , ..., 1 2 1 2 

Описание слайда:

Теорема 2.1. Если некоторая формула Ф реализует функцию f , то формула , реализующая двойственную функцию , может быть получена из Ф путем замены всех подформул на двойственные им. То есть если то * f *           n k n n n x x x f x x x f x x x f f x x x ...,, , ...,, ...,, , , ...,, , ...,, , 2 1 2 1 2 2 1 1 2 1             . ...,, , ...,, ...,, , , ...,, , ...,, , 2 1 * 2 1 * 2 2 1 * 1 * 2 1 * n k n n n x x x f x x x f x x x f f x x x  

Описание слайда:

В частном случае из теоремы 2.1 вытекает следующее правило. Если формула Ф содержит только операции и константы 0, 1 , то для получения формулы , двойственной к Ф , необходимо, сохраняя порядок выполнения операций, везде заменить 0 на 1 ( 1 на 0 ), операцию  на & (операцию & на  ).   , ,  *

Описание слайда:

Можно сформулировать следующие принципы двойственности для формул: 1) если две формулы эквивалентны, то есть , то эквивалентны и отрицания этих формул ; 2) если формулы Ф 1 и Ф 2 эквивалентны, то и двойственные им функции тоже эквивалентны ;    n n x x x x x x ...,, , ...,, , 2 1 2 2 1 1       n n x x x x x x ...,, , ...,, , 2 1 2 2 1 1        n n x x x x x x ...,, , ...,, , 2 1 * 2 2 1 * 1   

Описание слайда:

3) если две формулы эквивалентны, то будут эквивалентны и формулы, полученные из исходных путем замены аргументов на их отрицания       1 1 2 2 1 2 x x x x x x n n , ,..., , ,..., 

Описание слайда:

2.3. СПЕЦИАЛЬНЫЕ РАЗЛОЖЕНИЯ ЛОГИЧЕСКИХ ФУНКЦИЙ 2.3.1. Конъюнктивная и дизъюнктивная нормальные формы

Описание слайда:

Любая функция булевой алгебры может быть представлена некоторыми формулами специального вида. Нормальные формы – это некоторое стандартное представление функции с помощью элементарных конъюнкций и элементарных дизъюнкций. Элементарной дизъюнкцией (ЭД) называют дизъюнкцию нескольких переменных или их отрицаний. Например, .3 2 1 i a a a d   

Описание слайда:

Элементарной конъюнкцией (ЭК) называют конъюнкцию нескольких переменных или их отрицаний. Например, . Дизъюнктивной нормальной формой (ДНФ) некоторой заданной функции называется формула, которая имеет вид дизъюнкции элементарных конъюнкций. Например, . Конъюнктивной нормальной формой (КНФ) некоторой заданной функции называется формула, которая имеет вид конъюнкции элементарных дизъюнкций.3 2 1 i a a a k    3 2 1 3 2 1 a a a a a a 

Описание слайда:

Если заданная функция уже представлена некоторой формулой, то путем эквивалентных преобразований эта формула может быть приведена к равносильной ей формуле в соответствующей нормальной форме (КНФ или ДНФ). Порядок действий, при приведении исходной формулы к нормальной форме, следующий: 1) все функции выражаются через дизъюнкцию, конъюнкцию и отрицание;

Описание слайда:

2) если в выражении над несколькими элементами имеются знаки отрицания, то следует, используя формулы де Моргана, изменить выражение так, чтобы отрицание относилось только к одной переменной; 3) дальнейшее преобразование производится с использованием свойств элементарных операций. Пример.            ) )( ( ) )( ( ) ( N M C A AB N M C B A M C B A N . N C A M C A AB ABM N    

Описание слайда:

Упрощение логических формул на основе применения понятий тождественно истинных и тождественно ложных форм. После приведения к нормальной форме можно существенно упрощать выражения логических функций. Утверждение 1. Для того чтобы элементарная дизъюнкция была тождественно истинной, необходимо и достаточно, чтобы среди её слагаемых нашлась хотя бы одна переменная и её отрицание ( ).1 x x i i  

Описание слайда:

Утверждение 2. Для того чтобы элементарная конъюнкция была тождественно ложной, необходимо и достаточно, чтобы среди её сомножителей оказалась хотя бы одна переменная и её отрицание ( ).0 x x ii  &

Описание слайда:

Указанные два утверждения используются для упрощения выражений следующим образом: В случае принадлежности логической формулы к КНФ рассматривается каждый ее сомножитель, и если в какой-то из них входят вместе и , то он равен единице и его можно исключить. Если все сомножители равны единице, то такая функция тождественно истинна. В случае принадлежности формулы к ДНФ рассматривается каждое слагаемое. Если в каком-либо слагаемом встречается произведение , то это слагаемое равно нулю и его можно исключить.x i x i i i x x 

Описание слайда:

Пример. Установить характер истинности формулы                Q Q P P Q Q P P Q Q P P Q Q P P ) ( ) ( ) ( )) ( (     P Q Q 1

Описание слайда:

2 .3.2. Совершенно нормальные конъюнктивная и дизъюнктивная формы

Описание слайда:

Понятие совершенно нормальных конъюнктивных и дизъюнктивных форм. Пусть имеется n переменных: Будем формировать из них строки так, чтобы выполнялись три условия: 1) в каждую строку входят все n переменных; 2) каждая переменная входит в строку только один раз; 3) в строку входит либо сама переменная, либо её отрицание, но не одновременно то и другое. Число таких строк .x x x n 1 2 , ,..., n 2

Описание слайда:

Элементарная дизъюнкция, сформированная в соответствии с указанными требованиями, образует логическую конструкцию вида и называется макстермом . Элементарная конъюнкция образует логическую конструкцию вида и называется минтермом .n 3 2 1 i x x x x d      ... n 3 2 1 i x x x x k      ...

Описание слайда:

Совершенной дизъюнктивной нормальной формой (СДНФ) логической функции называют представление её в виде дизъюнкции минтермов, построенных из аргументов : Совершенной конъюнктивной нормальной формой (СКНФ) логической функции называют представление её в виде конъюнкции макстермов, построенных из аргументов рассматриваемой функции:  f x x xn 1 2 , ,..., x x x n 1 2 , ,...,   f x x x x x x x x x x x x x x x n n n n n 1 2 1 2 1 2 1 2 1 2 , ,..., ... ... ... ... ...              f x x xn 1 2 , ,...,         f x x x x x x x x x x x x n n n n 1 2 1 2 1 2 1 2 , ,..., ... ... ... ...             

Описание слайда:

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

Описание слайда:

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

Описание слайда:

1. Логическая формула приводится к дизъюнктивной нормальной форме При этом каждое слагаемое представляет собой конъюнкцию некоторого числа переменных, но не обязательно всех. 2. Пусть слагаемое не содержит ни , ни . В этом случае к нему конъюнктивно присоединяют тождественно-истинную форму :   f x x xn 1 2 , ,...,       f x x x x x x x x x n n n 1 2 1 1 2 2 1 2 , ,..., , ,..., , ,..., ...         j nx x x 1 2, , . . . , xi xi   x x i i             j n i i j n i j n i x x x x x x x x x x x x x 1 2 1 2 1 2 , ,..., , ,..., , ,...,    

Описание слайда:

Если отсутствуют несколько переменных, то операцию нужно повторить для всех отсутствующих сомножителей. По окончании слагаемое будет удовлетворять первому условию . 3. Если в каком-либо слагаемом имеется несколько одинаковых сомножителей, то из них оставляется один. 4. Если слагаемое содержит , то это слагаемое можно исключить. 5. Если среди всех слагаемых окажется два или несколько одинаковых, то они заменяются одним. В результате указанных операций формула будет приведена к СДНФ.i i x x 

Описание слайда:

При приведении к совершенной конъюнктивной нормальной форме последовательность действий остается той же, но все действия заменяются на двойственные.i i x x 

Описание слайда:

Существует еще один метод приведения функции к совершенной нормальной форме. Выражение в форме СКНФ включает столько сомножителей, сколько в таблице истинности содержится наборов, на которых функция равна нулю. Каждый сомножитель содержит дизъюнкцию всех входных переменных. При этом если – набор, где функция равна нулю, то в элементарную дизъюнкцию включают , если a i = 0 и , если a i = 1 . Правила для построения совершенной дизъюнктивной нормальной формы аналогичны, только значения заменяются на двойственные.a a a n 1 2 , ,..., x i i x

Описание слайда:

Пример. Рассмотрим пример приведения заданной логической функции к форме СДНФ, с использованием обоих известных способов. z&y&xz&y&x z&y&xz&y&xz&y&xz&y&xz&y&x z&y&xz&y&xz&y&x)zz(&y&x)zz(&y&x z&y&xy&xy&xz&y&xy&xy&xy&x z&y&xy&xyxyxx&z&xz&y&xy&x )yx(&)yx()xy(&z&xx&y)yx()z,y,x(f      

Описание слайда:

. xyz z xy z y x z y x x,y,z f          

Описание слайда:

Пример. Рассмотрим пример приведения заданной логической функции к форме СКНФ, с использованием обоих известных способов.). )( )( ( & &) )( )( ( ) )( )( )( ( & &) )( )( )( )( ( ) )( ( & &) )( )( ( ) )( )( )( )( ( ) )( )( )( ( ) )( )( ( ) , , ( z y x y z x z y x z y x z y x z y x z y x z y x y z x y z x z y x y x z y x z y x z y x z zz y x yy z x z y x yy x z yy x z y x z x z y x x z x z zy x z y x x z x z zy x x z y x z z y x f                                                              

Описание слайда:

) z y x )( y z x )( z y x )( z y x )( z y x )( z y x ( ) z, y,x (f             

Описание слайда:

2.4. МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ 2.4.1. Понятие минимизации

Описание слайда:

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

Описание слайда:

Для минимизации булевых функций в целях получения самых простых выражений используется ряд методов, среди которых наибольшее применение находят: 1) метод неопределенных коэффициентов; 2) метод Квайна-Мак Класки; 3) метод карт Карно.

Описание слайда:

2.4.2. Метод неопределенных коэффициентов

Описание слайда:

Сущность метода заключается в представлении функции в самом общем виде в ДНФ и введении коэффициентов a i , значения которых ( 0 или 1 ) подбираются таким образом, чтобы формула была минимальной. Пусть дана функция трех переменных. Представим формулу этой функции в виде ДНФ самого общего вида:

Описание слайда:

Термы, содержащие k переменных, будем называть термами ранга k . В выражении (2.1) представлены все возможные формы термов. Если записать уравнение (2.1) для всех возможных значений аргументов , то получим систему уравнений (в нашем случае n=3 ): x x x 1 2 3 , , 2 n

Описание слайда:

Описание слайда:

Для заданной конкретной функции конкретные значения левой части (2.2) нам известны. Если набор такой, что функция на нем принимает значение 0 , то все коэффициенты в правой части равны 0 . Эти нулевые коэффициенты вычеркиваются и в остальных уравнениях. В каждом оставшемся уравнении приравниваем единице коэффициент, определяющий конъюнкцию наименьшего ранга (ранг – число переменных), а остальные коэффициенты в правой части уравнения приравниваем нулю с учетом ранее сделанных подстановок. После подстановки коэффициентов в уравнение (2.1) получаем результирующее выражение булевой функции. x x x 1 2 3 , ,

Описание слайда:

Пример. Минимизировать заданное выражение

Описание слайда:

Описание слайда:

2.4.3. Метод Квайна – Мак Класки

Описание слайда:

Метод Квайна . При минимизации методом Квайна исходная функция задается в СДНФ. Сущность метода состоит в поэтапном упрощении выражений на основе операций склеивания.

Описание слайда:

Шаг 1. Нахождение первичных импликант. Все термы сравниваются между собой попарно. Если два терма имеют вид , а (где a – конъюнкция нескольких переменных), тогда вместо m i и m j выписываются a , которые являются термом (n-1) порядка. Исключаемые термы помечаются. Далее сравниваются все полученные термы (n-1) ранга. В результате склеивания выписываются термы (n-2) ранга. Процесс продолжается до тех пор, пока дальнейшее склеивание становится невозможным. Не исключенные в процессе выполнения указанной процедуры термы исходной функции, а также термы, которые были получены в результате склеивания, будем называть первичными или простыми импликантами .m ax i i  i j x a m  mi

Описание слайда:

Пример. Пусть задано следующее выражение в форме СДНФ

Описание слайда:

Описание слайда:

Шаг 2. Составление таблицы. В колонках записываем термы исходного выражения (они обозначены порядковыми номерами), а в строках - простые импликанты.

Описание слайда:

Шаг 2. Составление таблицы. В колонках записываем термы исходного выражения (они обозначены порядковыми номерами), а в строках - простые импликанты. Если в исходный терм входит какой-либо импликант, то на пересечении соответствующего столбца и строки ставится метка.

Описание слайда:

Шаг 3. Нахождение существенных импликант. Если в каком-либо из столбцов таблицы имеется одна метка, то импликанта, соответствующая этой строке, является существенной. Она обязательно входит в конечный результат. Из таблицы для дальнейшего анализа исключаются строки, соответствующие существенным импликантам, и покрываемые ими столбцы. Шаг 4. Вычеркивание лишних столбцов. Из двух столбцов, имеющих метки в одинаковых строках, один вычеркивается (в нашем примере таких нет).

Описание слайда:

Описание слайда:

Шаг 5. Вычеркивание лишних импликант. Если после шага 4 в таблице появятся строки, в которых нет ни одной метки, то импликанты, соответствующие этим строкам, из рассмотрения исключаются (в нашем примере нет). Результате выполнения описанных выше действий приведены в таблице

Описание слайда:

Шаг 6. Выбор конечного результата. В результирующее выражение включается совокупность импликант, которые имеют метки во всех столбцах. Предпочтение отдается тому варианту, в котором минимально суммарное число литер (букв), входящих в конечный результат. Выбирая 1 -ю и 4 -ю импликанты, которые в совокупности покрывают все столбцы, окончательно получаем:   4 2 1 4 3 1 3 2 4 3 2 1 x x x x x x x x x x x x f    , , ,

Описание слайда:

Метод Мак Класки. Мак Класки предложил модернизировать метод Квайна следующим образом: 1) все термы кодируются в виде двоичных последовательностей: переменной соответствует 1 ; ее отрицанию – 0 , например, ; 2) все последовательности разбиваются на группы по числу единиц в последовательности (в i -ю группу попадает терм, который имеет i единиц); 3) при сравнении сопоставляются только соседние группы, т.к. только они имеют отличие в одном разряде;101 x x x 3 2 1 

Описание слайда:

4) при исключении переменной вместо нее записывается прочерк. Порядок формирования минимизированного выражения логической функции такой же, как в методе Квайна.

Описание слайда:

2.4.4. Метод карт Карно

Описание слайда:

Карта Карно – это графическое представление таблицы истинности. Она представляет собой совокупность ячеек, определяемых системой вертикальных и горизонтальных координат; каждой ячейке соответствует набор значений входных переменных. Запись в ячейке – это значение функции на соответствующем наборе. Таким образом, имеется взаимно однозначное соответствие между ячейками Карно и строками таблицы истинности.

Описание слайда:

Пример. Функции соответствуют представленные ниже таблица истинности и карта Карно.xz z y x z y x f    ) ( ) , , (

Описание слайда:

Сущность метода заключается в выделении в карте Карно прямоугольных ячеек (блоков), содержащих одно и то же значение функции. Любой блок может иметь размер , где a, b – целые. Правила формирования выражения минимальной булевой функции. Основные правила заключаются в следующем: 1) каждая ячейка, содержащая единицу, должна войти в какой-то из блоков; 2) результат записывается в виде логической суммы термов, соответствующих сформированным блокам;b a 2 2 

Описание слайда:

3) терм, описывающий блок, записывается в форме произведения тех переменных, которые на координатной сетке не изменяют свое значение в пределах блока; если координата равна нулю, то соответствующая ей переменная входит в терм с отрицанием, а если - единице, то без отрицания. Степень сложности булевой функции оценивается числом слагаемых и числом букв (литер). Выражение, которое получено с применением метода карт Карно, на основе термов, сформированных из групп с единичным значением логической функции, при минимальном количестве литер называется минимальной суммой (минимальная ДНФ) .b a 2 2 

Описание слайда:

При формировании групп для получения минимальных сумм необходимо руководствоваться двумя принципами: 1) группа должна быть как можно больше; 2) число групп должно быть как можно меньше. Карту Карно следует рассматривать как трехмерную, представляя ее в виде тора (склеивая правую и левую, а так же нижнюю и верхнюю границы).

Описание слайда:

Общая последовательность действий при минимизации: 1) в таблице Карно выбирается ячейка с единицей, не являющаяся подмножеством уже сформированного блока; 2) формируется наибольшая группа, содержащая эту ячейку; 3) выбирается следующая ячейка, не вошедшая в предшествующие группы, и для нее повторяются те же действия; 4) процесс повторяется, пока не останутся единицы, не включенные в какие-либо группы; 5) записывается выражение минимальной функции по правилу, которое было установлено выше.

Описание слайда:

Пример. Карте Карно, представленной на рисунке, соответствует функция.yz x z x z y x w f   ) , , , (

Описание слайда:

Пример. Карте Карно, представленной на рисунке, соответствует функция.z x z y w y x z y x w f    ) , , , (

Описание слайда:

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

Описание слайда:

4) при исключении переменной вместо нее записывается прочерк. Минимизация частично определенных булевых функций. В случае, если некоторые входные наборы невозможны либо значение функции на них несущественно, то говорят о недоопределенных условиях . При этом особенность использования карт Карно следующая: недоопределенное условие на карте Карно обозначается прочерком и его можно либо присоединить, либо не присоединить к любой группе.

Описание слайда:

Пример. Карте Карно, представленной на рисунке, соответствует функция.y x w z y z y x w f   ) , , , (

Описание слайда:

2.5. ПОЛНОТА И ЗАМКНУТОСТЬ МНОЖЕСТВА БУЛЕВЫХ ФУНКЦИЙ 2.5.1. Понятие функционально полной системы

Описание слайда:

Система функций называется функционально полной , если любая булева функция может быть записана в виде формул через функции этой системы. Одним из способов получения полных систем является использование некоторых существующих, ранее выявленных полных систем. Теорема . Пусть даны две системы функций: и . Относительно этих функций известно, что B – полная система и каждая ее функция может быть выражена в виде формул через функции второй системы. В этом случае система D – тоже полная.  f f fn 1 2 , ,...,   B f f fn  1 2 , ,...,   D q q q m  1 2 , ,...,

Описание слайда:

Доказательство. Пуст h – это произвольная функция. В силу полноты B функция h может быть выражена в виде формул над B , т.е. . Но любая из функций B по условию может быть выражена через функции D , т.е. Следовательно, Таким образом, произвольная функция h может быть выражена через функции системы D . Поэтому система D – полная.  h F f f fn  1 2 , ,...,     f q q f q q 1 1 1 2 2 2 1 2     , , ... , , , ...         h F q q q q F q q q n     1 1 2 2 1 2 1 2 , ,... , , ,... , ,...,

Описание слайда:

Доказанную теорему можно использовать для доказательства полноты двух следующих систем: Известно, что – полная система (это вытекает из того факта, что любую булеву функцию можно представить в КНФ и ДНФ).    S S 1 2     , , и   S 0   , ,

Описание слайда:

Для доказательства полноты S 1 и S 2 нужно установить, что недостающая относительно S 0 операция (в S 1 – дизъюнкция, в S 2 – конъюнкция) может быть выражена через две остальные. Такое подтверждение дают правила де Моргана и двойного отрицания: Следовательно, S 1 и S 2 — полные системы и их называют соответственно конюнктивным и дизъюнктивным базисом Буля .2 1 2 1 x x x x    2 1 2 1 x x x x   

Описание слайда:

Полной является также система , которая сводится к конъюнктивному базису S 1 , т.к. отрицание в может быть выражено через операции S 3 следующим образом: Это легко проверяется по таблице истинности.   S 3 1    , , x x 1  

Описание слайда:

2.5.2. Алгебра Жегалкина

Описание слайда:

Алгебра над множеством логических функций с двумя бинарными операциями (конъюнкция и сложение по модулю два) называется алгеброй Жегалкина. В этой алгебре выполняются следующие соотношения: Для подтверждения полноты алгебры Жегалкина представим дизъюнкцию через функции этой алгебры: y x xy y x y x      

Описание слайда:

Полученная формула, имеющая вид суммы произведений, называется полиномом по модулю два или полиномом Жегалкина . Для каждой логической функции может быть получен полином Жегалкина, причем единственный для данной функции. Для этого следует привести заданное выражение к форме СДНФ, исключить операции дизъюнкции, отрицания и раскрыть скобки. В частном случае, если , то . Пример. x y   0 x y x y            )1 )(1 ( 2 1 2 1 2 1 2 1 x x x x x x x x x x x x 2 1 2 1 1 1 2 1 2 1         x x x x x x x x 2 1 2 1

Описание слайда:

Существует ещё один способ приведения функции к полиному Жегалкина. Запишем предполагаемый результат в виде выражения общего вида с неопределенными коэффициентами. Пример . . Для определения значений коэффициентов вычислим левую и правую часть для четырех возможных наборов входных переменных:d cx bx x ax x x x x 2 1 2 1 2 1 2 1     

Описание слайда:

2.5.3. Замыкание и замкнутые классы

Описание слайда:

Замыканием множества функции M называют множество всех булевых функций, представляемых в виде формул через функции множества M . Замыкание множества будем обозначать [ M ] . Очевидно, что . Множество M называют замкнутым классом , если при замыкании M не происходит его дальнейшее расширение, то есть [ M ] = M . Ответ на вопрос, какую систему булевых функций можно считать функционально полной, дают две теоремы.  M M 

Описание слайда:

4) при исключении переменной вместо нее записывается прочерк. Теорема о функциональной полноте. Для того чтобы система функций B была полной, необходимо и достаточно, чтобы она не содержалась полностью ни в одном из пяти замкнутых классов: T 0 , T 1 , S , L , M , где T 0 – класс замкнутых булевых функций, сохраняющих константу 0 , т.е. функций, для которых T 1 – замкнутый класс булевых функций, сохраняющих константу 1 , т.е. таких функций, что ;   f 0 0 0 0 , ,...,    f 1 1 1 1 , ,..., 

Описание слайда:

S – замкнутый класс всех самодвойственных функций, т.е. функций, для которых ; L – замкнутый класс всех линейных функций. Линейной функцией называется функция, у которой полином Жегалкина имеет вид , где c 0 и c i – коэффициенты (равны 1 или 0 ). В линейной функции отсутствует произведение переменных. M – замкнутый класс всех монотонных функций; Функция называется монотонной, если из условия следует , где и – наборы переменных , и введено отношение порядка <= , означающее , если n n i i 0 x c x c x c x c c       ..... ..... 2 2 1 1   f x x xn 1 2 , ,...,          f f     n     ...,, , 2 1   n     ...,, , 2 1           1 1 2 2    , ,..., n n     n 2 1 n 2 1 x ,..., x, x f x ,..., x, x f 

Описание слайда:

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

Описание слайда:

Примеры функционально полных базисов. Класс функций N из E 2 называется предполным , если он неполный, а для любой функции f , такой, что , класс – полный. Система B называется полной, если любая функция может быть представлена в виде суперпозиций функций этой системы, и она называется базисом , если теряется полнота при удалении хотя бы одной функции. f E f N   2 , но   N f  f E  2

Описание слайда:

Состав систем, которые относятся к базису, можно определить на основе следующей таблицы

Описание слайда:

Символом «+» обозначается факт непринадлежности функции к замкнутому классу. Согласно теореме Поста, к базису можно отнести минимальный набор функций, строки которого будут содержать хотя бы один символ «+» в каждом столбце ( T 0 , T 1 , S , L , M , ). Из предшествующей таблицы видно, что к функционально полным системам можно отнести, например, системы         , , , ,