Логика Буля.ppt - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

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

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

Слайд 1

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

Булевы переменные и булевы функции

Слайд 2

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

Возвращаясь к диаграмме Эйлера-Венна для двух множеств , с точки зрения логики, вместо одной предметной переменной х удобно ввести две логические переменные а и b, определяемые областями множеств соответственно А и В. Возвращаясь к диаграмме Эйлера-Венна для двух множеств , с точки зрения логики, вместо одной предметной переменной х удобно ввести две логические переменные а и b, определяемые областями множеств соответственно А и В. Эти переменные могут принимать только два логических значения: 1 – истина, т.е. принадлежность множеству, или 0 – ложь. Тогда подмножества С0, С1, С2 и С3 определят следующие значения логических переменных: С0 - а = 0, b = 0; С1 - а = 1, b = 0; С2 - а = 0, b = 1; С3 - а = 1, b = 1.

Слайд 3

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

Аппарат логики Буля оперирует с логическими (Булевыми) переменными, которые могут принимать только два значения: Аппарат логики Буля оперирует с логическими (Булевыми) переменными, которые могут принимать только два значения: 0 и 1. Логические переменные определяют некую логическую зависимость, которую принято называть булевой функцией. Множество всех булевых функций и операций над ними образует булеву алгебру или алгебру логики. Булевы функции могут принимать тоже только два взаимно исключающих значения 0 и 1. Логические величины 0 и 1 нельзя трактовать как числа, над ними нельзя производить арифметические действия, поскольку алгебра логики – это не алгебра чисел, а алгебра состояний.

Слайд 4

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

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

Слайд 5

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

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

Слайд 6

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

Булевых функций одной переменной всего четыре. Булевых функций одной переменной всего четыре. Нулевая (const”0”) – значение функции равно нулю, каким бы ни было значение входной переменной. Инверсия (не) – значение функции инверсно значению входной переменной. Повторение (да) – значение функции повторяет значение входной переменной. Единичная (const”1”) – значение функции равно единице при любом значении входной переменной.

Слайд 7

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

Функции двух переменных 1. - конъюнкция, логическое «и»; 2. - дизъюнкция, логическое «или»; 3. - штрих Шеффера, логическое «и-не»; 4. - стрелка Пирса (функция Вебба), логическое «или - не»; 5. - запрет b, «а, но не b» 6. - импликация b, «если а, то b»

Слайд 8

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

7. - запрет а, «b, но не а» 7. - запрет а, «b, но не а» 8. - импликация а, «если b, то а» 9. - эквивалентность, равнозначность 10. - неравнозначность, «сумма по модулю 2».

Слайд 9

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

Из всех функций двух переменных десять являются самостоятельными и зависят как от переменной а, так и от переменной b. Из всех функций двух переменных десять являются самостоятельными и зависят как от переменной а, так и от переменной b. Притом функции Y5 ,Y6 отличаются от соответствующих им Y7 ,Y8 лишь порядком расположения аргументов. Таким образом, лишь восемь из 16-ти булевых функций двух переменных являются оригинальными.

Слайд 10

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

Постулаты (аксиомы) логики Буля Постулаты (аксиомы) логики Буля Если x ≠ 1, то = 0; если x = 0, то = 1 (аксиома взаимоисключения); 0 0 = 0; 0 0 = 0; 0 1 = 0; 0 1 = 1; (1 0 = 0; 1 0 = 1); 1 1 = 1; 1 1 = 1; ; (инверсии); ; (двойной инверсии).

Слайд 11

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

В качестве основных законов алгебры Буля чаще других используют следующие : В качестве основных законов алгебры Буля чаще других используют следующие : Нулевого множества: 0  a = 0; 0  a  b  …  x= 0; 0  a = a 2. Универсального множества: 1  a = a; 1  a = 1; 1  a  b  c  …  x = 1; 3. Идемпотентности (повторения): a  a  a  …  a = a; a  a  a  …  a = a; 4. Дополнительности (противоречия): a  a= 0; a  a = 1; = 5. Двойной инверсии: а = a ;

Слайд 12

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

6. Коммутативности(переместительный): 6. Коммутативности(переместительный): a  b = b  a; a  b = b  a; 7. Ассоциативности (сочетательный): a  (b  c) = (a  b)  c; a  (b  c) = (a  b)  c; 8. Дистрибутивности (распределительный): a  (b  c) = (a  b)  (a  c); 9. Поглощения: a  (a  b) = a; a  (a  b) = a;

Слайд 13

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

10. Склеивания: 10. Склеивания: (a  b)  (a b) = a; (a  b)  (a b) = a ; a  (a b) = a  b; a  (a  b) = a  b ; 11. Инверсии (теорема де-Моргáнa): a  b  c =a  b  c; a  b  c =a  b  c; 12. Теорема Шеннона: для того, чтобы получить инверсию некоторой ФАЛ, необходимо взять инверсии переменных и заменить операции дизъюнкции на конъюнкции и наоборот: если существует Y = f (a,b,c,...,x, , ), то Y = f (a,b,c,...,x, , ).

Слайд 14

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

13. Разложения: 13. Разложения: f (a, b, c,..., x) = [a  f (1,b,c,...,x)]  [a f (0,b,c,...,x)]; f (a, b, c,..., x) = [a  f (0,b,c,...,x)]  [a  f (1,b,c,...,x)]. Законы и теоремы булевой алгебры необходимы для преобразования и упрощения логических функций, для доказательства тождественности и равносильности функций, а также для представления булевых функций в различных формах.

Слайд 15

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

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

Слайд 16

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

Дизъюнкция любого числа элементарных конъюнкций называется дизъюнктивной нормальной формой (ДНФ), например: Дизъюнкция любого числа элементарных конъюнкций называется дизъюнктивной нормальной формой (ДНФ), например: (a  b c )(b  c )d илиa bc +b c +d . Конъюнкция любого числа элементарных дизъюнкций называется конъюнктивной нормальной формой (КНФ), например: (a  b c )  (a c  d)  (b d ) или (a + b + c ) (a +c + d) (b +d ) (далее для упрощения восприятия булевых функций будем использовать второй вид записи).

Слайд 17

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

Теоремы разложения можно применить ко всем переменным, определяющим булеву функцию, тогда, например, используя первую теорему разложения для функции трех переменных f(a,b,c), получим: Теоремы разложения можно применить ко всем переменным, определяющим булеву функцию, тогда, например, используя первую теорему разложения для функции трех переменных f(a,b,c), получим: f(a,b,c) = a · b · c · f(1,1,1) +a ·b · c· f (0,1,1) + a·b· c · f(1,0,1) + a · b·c · f(1,1,0) +a ·b · c · f(0,0 ,1) + a ·b·c · f(0,1,0 ) + a·b ·c · f(1,0,0) +a ·b ·c · f(0,0,0). Нетрудно заметить, что по закону нулевого множества элементы с нулевым значением функции обратятся в ноль и останутся лишь наборы переменных при единичном значении функции, которые далее будем называть конституентами разложения единицы, или минтермами.

Слайд 18

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

Разложения функции на конституенты нуля: Разложения функции на конституенты нуля: f(a,b,c)=[a + b + c + f(0,0,0) ]·[a + b + c + f(1,0,0)]· [a+b +c + f(0,1,0]·[a + b+c +f(0,0,1)]·[a +b +c + f(1,1,0)] ·[a + b +c +f(1,0,1)]·[a+b +c + f(0,1,1)] ·[a +b +c f(1,1,1)]. Здесь, по закону универсального множества, каждая элементарная дизъюнкция с единичным значением функции принимает также единичное значение, и в результате остаются только те дизъюнкции переменных, инверсные значения которых определяют нулевое значение функции. Эти дизъюнкции называются конституентами разложения нуля, или макстермами.

Слайд 19

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

Раскладывая булевы функции на конституенты, мы получаем совершенные формы представления функций. Таким образом, совершенной дизъюнктивной формой (СДНФ) называется дизъюнкция конституентов единицы (минтермов), а совершенной конъюнктивной формой (СКФ) конъюнкция конституентов нуля (макстермов). Раскладывая булевы функции на конституенты, мы получаем совершенные формы представления функций. Таким образом, совершенной дизъюнктивной формой (СДНФ) называется дизъюнкция конституентов единицы (минтермов), а совершенной конъюнктивной формой (СКФ) конъюнкция конституентов нуля (макстермов).

Слайд 20

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

Для перехода из ДНФ в СДНФ необходимо следующее: 1. Ввести недостающие переменные в каждую конъюнкцию умножением ее на дополнительность вида (х +x), где х – недостающая переменная. 2. Раскрыть скобки. 3. Избавиться от повторяющихся конъюнкций на основании закона повторения. Например: Y =a ·b ·c + b · c +a =a ·b ·c + b·c ·(a +a ) + ·(b +b )·(c +c ) =a ·b ·c + a · b · c + a · b · c +a · b · c +a ·b · c +a ·b ·c +a ·b ·c =a ·b ·c + a · b · c + a ·b · c +a ·b·c +a ·b ·c +a ·b ·c.

Слайд 21

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

Алгоритм перехода из КНФ в СКНФ 1. Ввести недостающие переменные в каждую дизъюнкции, используя закон дополнительности х ·x = 0, где х – недостающая переменная. 2. Произвести преобразования, используя законы ассоциативности и дистрибутивности: a + (b · c) = (a + b) · (a + c). 3. Избавиться от повторяющихся дизъюнкций на основании закона повторения. Например: Y = (a+b+c)·(a +b )·a = (a+b+c)·(a +b + c·c) (a + b ·b + c·c ) = (a + b + c)·(a +b + c)· (a +b +c )·(a + b + c·c)(a + b + c·c) = (a+b+c)· (a +b + c) ·(a +b +c ) (a + b + c)·(a +b+c)· (a +b + c) ·(a +b +c ) = (a + b + c)·(a +b + c)·(a +b +c )·(a + b + c)·(a + b +c).

Слайд 22

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

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

Слайд 23

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

Такие значения функции называются фиктивными (Ф). Пример задания не полностью определенной функции представлен в табл. 2. Такие значения функции называются фиктивными (Ф). Пример задания не полностью определенной функции представлен в табл. 2.

Слайд 24

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

Десятичное число, соответствующее двоичному набору логических переменных, называется десятичным эквивалентом. Таким образом, булеву функцию можно представить с помощью десятичных эквивалентов: Десятичное число, соответствующее двоичному набору логических переменных, называется десятичным эквивалентом. Таким образом, булеву функцию можно представить с помощью десятичных эквивалентов: Y1 = { 0,1,3,5,8} ; Y0 = {2,7,9,13,15}. Оставшиеся наборы, не заданные таблицей истинности, по всей вероятности, будут фиктивными YФ = {4,6,10,11,12,14}.

Слайд 25

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

По таблице истинности можно получить совершенные формы записи булевых функций. Так, для записи в виде СДНФ нужно из таблицы выбрать единичные наборы переменных, представить их в виде конституентов единицы и произвести их дизъюнкцию. По таблице истинности можно получить совершенные формы записи булевых функций. Так, для записи в виде СДНФ нужно из таблицы выбрать единичные наборы переменных, представить их в виде конституентов единицы и произвести их дизъюнкцию. СДНФ: Y =abcd + abc d +ab c d +a bc d + abcd .

Слайд 26

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

Для записи в форме СКНФ нужно выбрать из таблицы нулевые наборы переменных, проинвертировать переменные в каждом из этих наборов, представить в виде конституентов нуля и произвести их конъюнкцию. Для записи в форме СКНФ нужно выбрать из таблицы нулевые наборы переменных, проинвертировать переменные в каждом из этих наборов, представить в виде конституентов нуля и произвести их конъюнкцию. СКНФ: Y=(a + b+c + d)(a+b +c +d)(a + b + c +d)(a +b + c +d)(a +b +c +d). Аналогично можно составить СДНФ и СКНФ по десятичным эквивалентам, определяющим булеву функцию.

Слайд 27

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

Число единиц в таблице истинности всегда будет совпадать с числом заштрихованных областей на диаграмме Эйлера-Венна. Если же функция имеет фиктивные состояния, тогда в этой диаграмме соответствующие области должны отсутствовать. Таким образом, по таблице истинности можно построить для заданной функции диаграмму Эйлера-Венна, а также можно поставить обратную задачу, т.е. по диаграмме составить совершенные формы представления булевой функции. Число единиц в таблице истинности всегда будет совпадать с числом заштрихованных областей на диаграмме Эйлера-Венна. Если же функция имеет фиктивные состояния, тогда в этой диаграмме соответствующие области должны отсутствовать. Таким образом, по таблице истинности можно построить для заданной функции диаграмму Эйлера-Венна, а также можно поставить обратную задачу, т.е. по диаграмме составить совершенные формы представления булевой функции.

Слайд 28

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

Матрица Карно представляет собой специально организованные таблицы соответствия, обладающие тем замечательным свойством, что любые две соседние клетки матрицы определяют «соседние» наборы переменных, т.е. наборы, отличающиеся значением только одной переменной. Клетки, расположенные по краям матрицы, также являются соседними и обладают этим свойством. Это достигается благодаря кодированию столбцов и строк матрицы специальным циклическим кодом Грея. Матрица Карно представляет собой специально организованные таблицы соответствия, обладающие тем замечательным свойством, что любые две соседние клетки матрицы определяют «соседние» наборы переменных, т.е. наборы, отличающиеся значением только одной переменной. Клетки, расположенные по краям матрицы, также являются соседними и обладают этим свойством. Это достигается благодаря кодированию столбцов и строк матрицы специальным циклическим кодом Грея.

Слайд 29

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

Еще одним свойством матриц Карно является то, что при увеличении количества переменных на единицу, матрица увеличивается вдвое, поскольку число клеток матрицы определяется показательной функцией «2n». Еще одним свойством матриц Карно является то, что при увеличении количества переменных на единицу, матрица увеличивается вдвое, поскольку число клеток матрицы определяется показательной функцией «2n».