🗊Презентация Основные положения булевой алгебры

Категория: Математика

Нажмите для полного просмотра!
Основные положения булевой алгебры, слайд №1Основные положения булевой алгебры, слайд №2Основные положения булевой алгебры, слайд №3Основные положения булевой алгебры, слайд №4Основные положения булевой алгебры, слайд №5Основные положения булевой алгебры, слайд №6Основные положения булевой алгебры, слайд №7Основные положения булевой алгебры, слайд №8Основные положения булевой алгебры, слайд №9Основные положения булевой алгебры, слайд №10Основные положения булевой алгебры, слайд №11Основные положения булевой алгебры, слайд №12Основные положения булевой алгебры, слайд №13Основные положения булевой алгебры, слайд №14Основные положения булевой алгебры, слайд №15Основные положения булевой алгебры, слайд №16Основные положения булевой алгебры, слайд №17Основные положения булевой алгебры, слайд №18Основные положения булевой алгебры, слайд №19Основные положения булевой алгебры, слайд №20Основные положения булевой алгебры, слайд №21Основные положения булевой алгебры, слайд №22Основные положения булевой алгебры, слайд №23Основные положения булевой алгебры, слайд №24Основные положения булевой алгебры, слайд №25Основные положения булевой алгебры, слайд №26Основные положения булевой алгебры, слайд №27Основные положения булевой алгебры, слайд №28Основные положения булевой алгебры, слайд №29Основные положения булевой алгебры, слайд №30Основные положения булевой алгебры, слайд №31Основные положения булевой алгебры, слайд №32Основные положения булевой алгебры, слайд №33Основные положения булевой алгебры, слайд №34Основные положения булевой алгебры, слайд №35Основные положения булевой алгебры, слайд №36Основные положения булевой алгебры, слайд №37Основные положения булевой алгебры, слайд №38Основные положения булевой алгебры, слайд №39Основные положения булевой алгебры, слайд №40Основные положения булевой алгебры, слайд №41Основные положения булевой алгебры, слайд №42Основные положения булевой алгебры, слайд №43Основные положения булевой алгебры, слайд №44Основные положения булевой алгебры, слайд №45Основные положения булевой алгебры, слайд №46Основные положения булевой алгебры, слайд №47Основные положения булевой алгебры, слайд №48Основные положения булевой алгебры, слайд №49Основные положения булевой алгебры, слайд №50Основные положения булевой алгебры, слайд №51Основные положения булевой алгебры, слайд №52Основные положения булевой алгебры, слайд №53Основные положения булевой алгебры, слайд №54Основные положения булевой алгебры, слайд №55Основные положения булевой алгебры, слайд №56Основные положения булевой алгебры, слайд №57Основные положения булевой алгебры, слайд №58Основные положения булевой алгебры, слайд №59Основные положения булевой алгебры, слайд №60Основные положения булевой алгебры, слайд №61Основные положения булевой алгебры, слайд №62Основные положения булевой алгебры, слайд №63Основные положения булевой алгебры, слайд №64Основные положения булевой алгебры, слайд №65Основные положения булевой алгебры, слайд №66Основные положения булевой алгебры, слайд №67Основные положения булевой алгебры, слайд №68Основные положения булевой алгебры, слайд №69Основные положения булевой алгебры, слайд №70Основные положения булевой алгебры, слайд №71Основные положения булевой алгебры, слайд №72Основные положения булевой алгебры, слайд №73Основные положения булевой алгебры, слайд №74Основные положения булевой алгебры, слайд №75Основные положения булевой алгебры, слайд №76Основные положения булевой алгебры, слайд №77Основные положения булевой алгебры, слайд №78Основные положения булевой алгебры, слайд №79Основные положения булевой алгебры, слайд №80Основные положения булевой алгебры, слайд №81Основные положения булевой алгебры, слайд №82Основные положения булевой алгебры, слайд №83Основные положения булевой алгебры, слайд №84Основные положения булевой алгебры, слайд №85Основные положения булевой алгебры, слайд №86Основные положения булевой алгебры, слайд №87Основные положения булевой алгебры, слайд №88Основные положения булевой алгебры, слайд №89Основные положения булевой алгебры, слайд №90Основные положения булевой алгебры, слайд №91Основные положения булевой алгебры, слайд №92Основные положения булевой алгебры, слайд №93Основные положения булевой алгебры, слайд №94Основные положения булевой алгебры, слайд №95Основные положения булевой алгебры, слайд №96Основные положения булевой алгебры, слайд №97Основные положения булевой алгебры, слайд №98Основные положения булевой алгебры, слайд №99Основные положения булевой алгебры, слайд №100Основные положения булевой алгебры, слайд №101Основные положения булевой алгебры, слайд №102Основные положения булевой алгебры, слайд №103Основные положения булевой алгебры, слайд №104Основные положения булевой алгебры, слайд №105Основные положения булевой алгебры, слайд №106Основные положения булевой алгебры, слайд №107Основные положения булевой алгебры, слайд №108Основные положения булевой алгебры, слайд №109Основные положения булевой алгебры, слайд №110Основные положения булевой алгебры, слайд №111Основные положения булевой алгебры, слайд №112Основные положения булевой алгебры, слайд №113Основные положения булевой алгебры, слайд №114Основные положения булевой алгебры, слайд №115Основные положения булевой алгебры, слайд №116Основные положения булевой алгебры, слайд №117Основные положения булевой алгебры, слайд №118Основные положения булевой алгебры, слайд №119Основные положения булевой алгебры, слайд №120Основные положения булевой алгебры, слайд №121Основные положения булевой алгебры, слайд №122Основные положения булевой алгебры, слайд №123Основные положения булевой алгебры, слайд №124Основные положения булевой алгебры, слайд №125Основные положения булевой алгебры, слайд №126Основные положения булевой алгебры, слайд №127Основные положения булевой алгебры, слайд №128Основные положения булевой алгебры, слайд №129Основные положения булевой алгебры, слайд №130Основные положения булевой алгебры, слайд №131Основные положения булевой алгебры, слайд №132Основные положения булевой алгебры, слайд №133Основные положения булевой алгебры, слайд №134Основные положения булевой алгебры, слайд №135Основные положения булевой алгебры, слайд №136Основные положения булевой алгебры, слайд №137Основные положения булевой алгебры, слайд №138

Вы можете ознакомиться и скачать презентацию на тему Основные положения булевой алгебры. Доклад-сообщение содержит 138 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.


Слайды и текст этой презентации

Слайд 1







§2. ОСНОВНЫЕ ПОЛОЖЕНИЯ БУЛЕВОЙ АЛГЕБРЫ
Описание слайда:
§2. ОСНОВНЫЕ ПОЛОЖЕНИЯ БУЛЕВОЙ АЛГЕБРЫ

Слайд 2






2.1. БУЛЕВА АЛГЕБРА И ЕЕ ПРИМЕНЕНИЕ

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

Слайд 3




	 Название этого раздела математики связано с именем его основателя – Джорджа Буля.
Описание слайда:
Название этого раздела математики связано с именем его основателя – Джорджа Буля.

Слайд 4




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

Слайд 5




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

Слайд 6




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

Слайд 7







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

Слайд 8




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

Слайд 9




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

Слайд 10







2.1.3. Высказывания
Описание слайда:
2.1.3. Высказывания

Слайд 11




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

Слайд 12




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

Слайд 13




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

Слайд 14







2.2. ФУНКЦИИ  АЛГЕБРЫ ЛОГИКИ
Описание слайда:
2.2. ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ

Слайд 15







2.2.1. Понятие функции и способы ее задания
Описание слайда:
2.2.1. Понятие функции и способы ее задания

Слайд 16




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

Слайд 17




	Функция f, задающая однозначное отображение множества всевозможных наборов значений двоичных переменных x1, x2, …, xn во множество {0,1}  называется функцией алгебры логики (или логической функцией, булевой функцией, переключательной функцией):

	Таким образом, логическая функция – это зависимость, которая устанавливает связь между сочетанием значений входных двоичных переменных и двоичным значением этой функции.
Описание слайда:
Функция f, задающая однозначное отображение множества всевозможных наборов значений двоичных переменных x1, x2, …, xn во множество {0,1} называется функцией алгебры логики (или логической функцией, булевой функцией, переключательной функцией): Таким образом, логическая функция – это зависимость, которая устанавливает связь между сочетанием значений входных двоичных переменных и двоичным значением этой функции.

Слайд 18




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

Слайд 19
Основные положения булевой алгебры, слайд №19
Описание слайда:

Слайд 20




	Оценим число возможных наборов (число строк входных переменных).
	Конкретный набор – это вектор  значений                                                                   

	
	Количество наборов – это мощность  прямого произведения   n двухэлементных множеств B:                                    



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

Слайд 21




	Оценим возможное количество вариантов логических функций от n переменных. Множество вариантов логической функции можно представить как прямое произведение: 


где  Bi    – значение функции на наборе  i.
	Таким образом, общее количество функций от   n переменных
                           

где                .
Описание слайда:
Оценим возможное количество вариантов логических функций от n переменных. Множество вариантов логической функции можно представить как прямое произведение: где Bi – значение функции на наборе i. Таким образом, общее количество функций от n переменных где .

Слайд 22




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

Слайд 23




	Две булевы функции 
                            и                           называют равными, если для всех возможных наборов значений аргументов они принимают одинаковые значения и таким образом имеют одну и ту же таблицу истинности, и записывают:
Описание слайда:
Две булевы функции и называют равными, если для всех возможных наборов значений аргументов они принимают одинаковые значения и таким образом имеют одну и ту же таблицу истинности, и записывают:

Слайд 24




	Говорят, что булева функция  
Существенно зависит от аргумента    xi , если 

                                                                                              ,

хотя бы для одного набора остальных аргументов. В противном случае xi называется несущественной или фиктивной переменной (ее можно исключить).
Описание слайда:
Говорят, что булева функция Существенно зависит от аргумента xi , если , хотя бы для одного набора остальных аргументов. В противном случае xi называется несущественной или фиктивной переменной (ее можно исключить).

Слайд 25







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

Слайд 26




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

Слайд 27




	2) дизъюнкция (логическое сложение)
                                                  (читается: " x или y ").
Описание слайда:
2) дизъюнкция (логическое сложение) (читается: " x или y ").

Слайд 28




	3) конъюнкция (логическое умножение)
                                                      (читается: " x и y").
	Для этой операции применяются также следующие формы записи: f3(x,y)=xy=x&y.
Описание слайда:
3) конъюнкция (логическое умножение) (читается: " x и y"). Для этой операции применяются также следующие формы записи: f3(x,y)=xy=x&y.

Слайд 29




	4) импликация 
                                                 (читается : “если x, то y”).
Описание слайда:
4) импликация (читается : “если x, то y”).

Слайд 30




	5) эквивалентность (равнозначность)
                                               (читается:  “x равно y ”).
Описание слайда:
5) эквивалентность (равнозначность) (читается: “x равно y ”).

Слайд 31




	6) сложение по модулю два (неравнозначность)
Описание слайда:
6) сложение по модулю два (неравнозначность)

Слайд 32




	7) штрих Шеффера
Описание слайда:
7) штрих Шеффера

Слайд 33




	8) стрелка Пирса
Описание слайда:
8) стрелка Пирса

Слайд 34




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

Слайд 35







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

Слайд 36




	Основные логические функции обладают следующими свойствами:
1) коммутативность:                                                      

2) ассоциативность: 


3) идемпотентность конъюнкции и дизъюнкции:
Описание слайда:
Основные логические функции обладают следующими свойствами: 1) коммутативность: 2) ассоциативность: 3) идемпотентность конъюнкции и дизъюнкции:

Слайд 37




	4) дистрибутивность:

а) конъюнкции относительно дизъюнкции: 


б) дизъюнкции относительно конъюнкции:     


	5) двойное отрицание:
Описание слайда:
4) дистрибутивность: а) конъюнкции относительно дизъюнкции: б) дизъюнкции относительно конъюнкции: 5) двойное отрицание:

Слайд 38




	6) правило де Моргана:   

	7) правило склеивания: 

	8) правило поглощения:
Описание слайда:
6) правило де Моргана: 7) правило склеивания: 8) правило поглощения:

Слайд 39




	9) действия с константами:






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

Слайд 40




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

Слайд 41




	







Так как значения функций       и       на всех наборах совпадают, то эти функции равны.
Описание слайда:
Так как значения функций и на всех наборах совпадают, то эти функции равны.

Слайд 42







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

Слайд 43




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

Слайд 44




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

Слайд 45




	Пусть имеется множество логических функций, заданных формулами  Е={ f1, f2, …, fm };  при этом говорят, что имеет место множество формул над Е. Тогда новую формулу можно получить используя следующее правило:
	Пусть                       – некоторая формула над  E. Если                   – либо символы переменных, либо другие формулы над E, то                   – тоже формула над E.
Описание слайда:
Пусть имеется множество логических функций, заданных формулами Е={ f1, f2, …, fm }; при этом говорят, что имеет место множество формул над Е. Тогда новую формулу можно получить используя следующее правило: Пусть – некоторая формула над E. Если – либо символы переменных, либо другие формулы над E, то – тоже формула над E.

Слайд 46




	Пример. Пусть функция задана формулой
                              , и при этом имеет место равенство 


Тогда новую формулу E над  можно получить путем подстановки  A1 и A2 в исходную формулу:
Описание слайда:
Пример. Пусть функция задана формулой , и при этом имеет место равенство Тогда новую формулу E над можно получить путем подстановки A1 и A2 в исходную формулу:

Слайд 47




	Полученную формулу вновь представим как исходную, и, полагая далее

 делаем вновь подстановку.
	Тогда новая формула над E :
Описание слайда:
Полученную формулу вновь представим как исходную, и, полагая далее делаем вновь подстановку. Тогда новая формула над E :

Слайд 48




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

Слайд 49




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

Слайд 50




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

Слайд 51




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

Слайд 52




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

Слайд 53




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

Слайд 54




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

Слайд 55




	3. Функция f6	

	4. Функция f7
                       =
	5. Функция f8
                       =
Описание слайда:
3. Функция f6 4. Функция f7 = 5. Функция f8 =

Слайд 56




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

Слайд 57







2.2.5. Двойственные функции
Описание слайда:
2.2.5. Двойственные функции

Слайд 58




	Логическая функция                                    , равная                               , называется двойственной по отношению к функции                                       .
	Очевидно свойство взаимности двойственных функций:
Описание слайда:
Логическая функция , равная , называется двойственной по отношению к функции . Очевидно свойство взаимности двойственных функций:

Слайд 59




	Теорема 2.1. Если некоторая формула Ф  реализует функцию f, то формула      , реализующая двойственную функцию      ,  может быть получена из Ф путем замены всех подформул на двойственные им. То есть если

 то
Описание слайда:
Теорема 2.1. Если некоторая формула Ф реализует функцию f, то формула , реализующая двойственную функцию , может быть получена из Ф путем замены всех подформул на двойственные им. То есть если то

Слайд 60




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

Слайд 61




	Можно сформулировать следующие принципы двойственности для формул:
	1) если две формулы эквивалентны, то есть 
                                                                               ,
то эквивалентны и отрицания этих формул 
                                                                                ;
	2) если формулы Ф1 и Ф2 эквивалентны, то и двойственные им функции тоже эквивалентны 
                                                                                  ;
Описание слайда:
Можно сформулировать следующие принципы двойственности для формул: 1) если две формулы эквивалентны, то есть , то эквивалентны и отрицания этих формул ; 2) если формулы Ф1 и Ф2 эквивалентны, то и двойственные им функции тоже эквивалентны ;

Слайд 62




	3) если две формулы эквивалентны, то будут эквивалентны и формулы, полученные из исходных путем замены аргументов на их отрицания
Описание слайда:
3) если две формулы эквивалентны, то будут эквивалентны и формулы, полученные из исходных путем замены аргументов на их отрицания

Слайд 63






2.3. СПЕЦИАЛЬНЫЕ РАЗЛОЖЕНИЯ ЛОГИЧЕСКИХ ФУНКЦИЙ

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

Слайд 64




	Любая функция булевой алгебры может быть представлена некоторыми формулами специального вида. 
	Нормальные формы – это некоторое стандартное представление функции с помощью элементарных конъюнкций и элементарных дизъюнкций.
	Элементарной дизъюнкцией (ЭД) называют дизъюнкцию нескольких переменных или их отрицаний. 
	Например,                             .
Описание слайда:
Любая функция булевой алгебры может быть представлена некоторыми формулами специального вида. Нормальные формы – это некоторое стандартное представление функции с помощью элементарных конъюнкций и элементарных дизъюнкций. Элементарной дизъюнкцией (ЭД) называют дизъюнкцию нескольких переменных или их отрицаний. Например, .

Слайд 65




	Элементарной конъюнкцией (ЭК) называют конъюнкцию нескольких переменных или их отрицаний. 
	Например,                                .
	Дизъюнктивной нормальной формой (ДНФ) некоторой заданной функции называется формула, которая имеет вид дизъюнкции элементарных конъюнкций.
	Например,                                .
	Конъюнктивной  нормальной формой (КНФ) некоторой заданной функции называется формула, которая имеет вид конъюнкции элементарных дизъюнкций.
Описание слайда:
Элементарной конъюнкцией (ЭК) называют конъюнкцию нескольких переменных или их отрицаний. Например, . Дизъюнктивной нормальной формой (ДНФ) некоторой заданной функции называется формула, которая имеет вид дизъюнкции элементарных конъюнкций. Например, . Конъюнктивной нормальной формой (КНФ) некоторой заданной функции называется формула, которая имеет вид конъюнкции элементарных дизъюнкций.

Слайд 66




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

Слайд 67




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

Слайд 68




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

Слайд 69




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

Слайд 70




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

Слайд 71




	Пример.  Установить характер истинности формулы
Описание слайда:
Пример. Установить характер истинности формулы

Слайд 72







2.3.2. Совершенно нормальные 
конъюнктивная и дизъюнктивная формы
Описание слайда:
2.3.2. Совершенно нормальные конъюнктивная и дизъюнктивная формы

Слайд 73




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

Слайд 74




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

Слайд 75




	Совершенной дизъюнктивной нормальной формой (СДНФ) логической функции  
называют представление её в виде дизъюнкции минтермов, построенных из аргументов :

	Совершенной конъюнктивной нормальной формой (СКНФ) логической функции  
называют представление её в виде конъюнкции макстермов, построенных из аргументов рассматриваемой функции:
Описание слайда:
Совершенной дизъюнктивной нормальной формой (СДНФ) логической функции называют представление её в виде дизъюнкции минтермов, построенных из аргументов : Совершенной конъюнктивной нормальной формой (СКНФ) логической функции называют представление её в виде конъюнкции макстермов, построенных из аргументов рассматриваемой функции:

Слайд 76




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

Слайд 77




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

Слайд 78




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

Слайд 79




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

Слайд 80




	

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

Слайд 81




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

Слайд 82




	Пример. Рассмотрим пример приведения заданной логической функции к форме СДНФ, с использованием обоих известных способов.
Описание слайда:
Пример. Рассмотрим пример приведения заданной логической функции к форме СДНФ, с использованием обоих известных способов.

Слайд 83
Основные положения булевой алгебры, слайд №83
Описание слайда:

Слайд 84




	Пример. Рассмотрим пример приведения заданной логической функции к форме СКНФ, с использованием обоих известных способов.
Описание слайда:
Пример. Рассмотрим пример приведения заданной логической функции к форме СКНФ, с использованием обоих известных способов.

Слайд 85
Основные положения булевой алгебры, слайд №85
Описание слайда:

Слайд 86






2.4. МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ 

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

Слайд 87




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

Слайд 88




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

Слайд 89







2.4.2. Метод неопределенных коэффициентов
Описание слайда:
2.4.2. Метод неопределенных коэффициентов

Слайд 90




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

Слайд 91




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

Слайд 92
Основные положения булевой алгебры, слайд №92
Описание слайда:

Слайд 93




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

Слайд 94




	Пример. Минимизировать заданное выражение
Описание слайда:
Пример. Минимизировать заданное выражение

Слайд 95
Основные положения булевой алгебры, слайд №95
Описание слайда:

Слайд 96








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

Слайд 97




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

Слайд 98




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

Слайд 99




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

Слайд 100
Основные положения булевой алгебры, слайд №100
Описание слайда:

Слайд 101




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

Слайд 102




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

Слайд 103




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

Слайд 104
Основные положения булевой алгебры, слайд №104
Описание слайда:

Слайд 105




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

Слайд 106




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

Слайд 107




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

Слайд 108




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

Слайд 109








2.4.4. Метод карт Карно
Описание слайда:
2.4.4. Метод карт Карно

Слайд 110




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

Слайд 111




	Пример. 
Функции                     
соответствуют представленные ниже таблица истинности и карта Карно.
Описание слайда:
Пример. Функции соответствуют представленные ниже таблица истинности и карта Карно.

Слайд 112




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

Слайд 113




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

Слайд 114




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

Слайд 115




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

Слайд 116




	Пример.  Карте Карно, представленной на рисунке, соответствует функция.
Описание слайда:
Пример. Карте Карно, представленной на рисунке, соответствует функция.

Слайд 117




	Пример.  Карте Карно, представленной на рисунке, соответствует функция.
Описание слайда:
Пример. Карте Карно, представленной на рисунке, соответствует функция.

Слайд 118




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

Слайд 119




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

Слайд 120




	Пример.  Карте Карно, представленной на рисунке, соответствует функция.
Описание слайда:
Пример. Карте Карно, представленной на рисунке, соответствует функция.

Слайд 121






2.5. ПОЛНОТА И ЗАМКНУТОСТЬ МНОЖЕСТВА 
БУЛЕВЫХ  ФУНКЦИЙ

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

Слайд 122




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

Слайд 123




	Доказательство. Пуст h – это произвольная функция. В силу полноты  B функция  h может быть выражена в виде формул над  B, т.е.                           . 
Но любая из функций  B по условию может быть выражена через функции D , т.е. 

	Следовательно, 

	Таким образом, произвольная функция  h может быть выражена через функции системы D. Поэтому система  D –  полная.
Описание слайда:
Доказательство. Пуст h – это произвольная функция. В силу полноты B функция h может быть выражена в виде формул над B, т.е. . Но любая из функций B по условию может быть выражена через функции D , т.е. Следовательно, Таким образом, произвольная функция h может быть выражена через функции системы D. Поэтому система D – полная.

Слайд 124




	
	Доказанную теорему можно использовать для доказательства полноты двух следующих систем: 

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

Слайд 125




	
	Для доказательства полноты S1 и S2 нужно установить, что недостающая относительно S0  операция (в S1 – дизъюнкция, в S2 – конъюнкция) может быть выражена через две остальные. Такое подтверждение дают правила де Моргана и двойного отрицания: 

	
	Следовательно, S1 и S2  — полные системы и их называют соответственно конюнктивным и дизъюнктивным базисом Буля.
Описание слайда:
Для доказательства полноты S1 и S2 нужно установить, что недостающая относительно S0 операция (в S1 – дизъюнкция, в S2 – конъюнкция) может быть выражена через две остальные. Такое подтверждение дают правила де Моргана и двойного отрицания: Следовательно, S1 и S2 — полные системы и их называют соответственно конюнктивным и дизъюнктивным базисом Буля.

Слайд 126




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


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

Слайд 127








2.5.2. Алгебра Жегалкина
Описание слайда:
2.5.2. Алгебра Жегалкина

Слайд 128




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




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

Слайд 129




	Полученная формула, имеющая вид суммы произведений, называется полиномом по  модулю два или полиномом Жегалкина. 
	Для каждой логической функции может быть получен полином Жегалкина, причем единственный для данной функции. 
	Для этого следует привести заданное выражение к форме СДНФ, исключить операции дизъюнкции, отрицания и раскрыть скобки. В частном случае, если                  , то                            .
	Пример.
Описание слайда:
Полученная формула, имеющая вид суммы произведений, называется полиномом по модулю два или полиномом Жегалкина. Для каждой логической функции может быть получен полином Жегалкина, причем единственный для данной функции. Для этого следует привести заданное выражение к форме СДНФ, исключить операции дизъюнкции, отрицания и раскрыть скобки. В частном случае, если , то . Пример.

Слайд 130




	Существует ещё один способ приведения функции к полиному Жегалкина. Запишем предполагаемый результат в виде выражения общего вида с неопределенными коэффициентами.
	Пример.                                                            .
	Для определения значений коэффициентов вычислим левую и правую часть для четырех возможных наборов входных переменных:
Описание слайда:
Существует ещё один способ приведения функции к полиному Жегалкина. Запишем предполагаемый результат в виде выражения общего вида с неопределенными коэффициентами. Пример. . Для определения значений коэффициентов вычислим левую и правую часть для четырех возможных наборов входных переменных:

Слайд 131








2.5.3. Замыкание и замкнутые классы
Описание слайда:
2.5.3. Замыкание и замкнутые классы

Слайд 132




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

Слайд 133




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

Слайд 134




	 S – замкнутый класс всех самодвойственных функций, т.е. функций, для которых                                                              ;
	 L – замкнутый класс всех линейных функций. 
	Линейной функцией называется функция, у которой полином Жегалкина имеет вид                                                      , где  c0 и ci –   коэффициенты (равны 1 или 0). В линейной функции отсутствует произведение переменных.
	M – замкнутый класс всех монотонных функций; 
	Функция                                   называется монотонной, если из условия                  следует                        , где       и        – наборы переменных                     ,                          и введено отношение порядка    <=    , означающее                   , если
Описание слайда:
S – замкнутый класс всех самодвойственных функций, т.е. функций, для которых ; L – замкнутый класс всех линейных функций. Линейной функцией называется функция, у которой полином Жегалкина имеет вид , где c0 и ci – коэффициенты (равны 1 или 0). В линейной функции отсутствует произведение переменных. M – замкнутый класс всех монотонных функций; Функция называется монотонной, если из условия следует , где и – наборы переменных , и введено отношение порядка <= , означающее , если

Слайд 135




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


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

Слайд 136




	Примеры функционально полных базисов. Класс  функций N из E2 называется предполным, если он неполный, а для любой функции  f, такой, что                                    , класс                       – полный.
	Система  B  называется полной, если любая функция            может быть представлена в виде суперпозиций функций этой системы, и она называется базисом, если теряется полнота при удалении хотя бы одной функции.
Описание слайда:
Примеры функционально полных базисов. Класс функций N из E2 называется предполным, если он неполный, а для любой функции f, такой, что , класс – полный. Система B называется полной, если любая функция может быть представлена в виде суперпозиций функций этой системы, и она называется базисом, если теряется полнота при удалении хотя бы одной функции.

Слайд 137




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

Слайд 138




	Символом «+» обозначается факт непринадлежности функции к замкнутому классу.
	Согласно теореме Поста, к базису можно отнести минимальный набор функций, строки которого будут содержать хотя бы один символ «+» в  каждом столбце (T0, T1, S, L, M, ).
	Из предшествующей таблицы видно, что к функционально полным системам можно отнести, например, системы
Описание слайда:
Символом «+» обозначается факт непринадлежности функции к замкнутому классу. Согласно теореме Поста, к базису можно отнести минимальный набор функций, строки которого будут содержать хотя бы один символ «+» в каждом столбце (T0, T1, S, L, M, ). Из предшествующей таблицы видно, что к функционально полным системам можно отнести, например, системы



Похожие презентации
Mypresentation.ru
Загрузить презентацию