Логические основы компьютерной техники. Булева алгебра

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

Логические основы компьютерной техники. Булева алгебра, слайд №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

Содержание ▲

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

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

Слайд 1

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

ЛОГИЧЕСКИЕ ОСНОВЫ КОМПЬЮТЕРНОЙ ТЕХНИКИ Парамонов А.И.

Слайд 2

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

Что такое Булева алгебра !? АЛГЕБРА – … ??? БУЛЕВА АЛГЕБРА – … ???

Слайд 3

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

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

Слайд 4

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

Операция дизъюнкции Аксиомы: 0+0 = 0; 0+1 = 1; 1+0 = 1; 1+1 = 1.

Слайд 5

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

Операция конъюнкции Аксиомы: 0•0 = 0; 0•1 = 0; 1•0 = 0; 1•1 = 1.

Слайд 6

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

Инверсия Аксиомы:

Слайд 7

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

Полный список аксиом :

Слайд 8

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

Формы представления булевых функций Булевы формулы могут быть записаны либо в виде дизъюнкции, либо в виде конъюнкции каких-либо выражений. В первом случае говорят о ДИЗЪЮНКТИВНОЙ ФОРМЕ, во втором— о КОНЪЮНКТИВНОЙ ФОРМЕ.

Слайд 9

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

Формы представления булевых функций ЭЛЕМЕНТАРНАЯ КОНЪЮНКЦИЯ (ЭК) – логическое произведение любого конечного числа различных между собой булевых переменных, взятых со знаком инверсии или без него. ЭЛЕМЕНТАРНАЯ ДИЗЪЮНКЦИЯ (ЭД) – логическая сумма любого конечного числа различных между собой булевых переменных, взятых со знаком инверсии или без него.

Слайд 10

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

Нормальные формы ДИЗЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА (ДНФ) – булева формула, которая записана в виде дизъюнкции выражений, каждое из которых представляет собой либо отдельный аргумент (с инверсией или без инверсии), либо конъюнкцию некоторых аргументов. – дизъюнкция конечного числа ЭК.

Слайд 11

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

Нормальные формы КОНЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА (КНФ) – булева формула, которая записана в виде конъюнкции выражений, каждое из которых представляет собой либо отдельный аргумент (с инверсией или без инверсии), либо дизъюнкцию некоторых аргументов. – конъюнкция конечного числа ЭД.

Слайд 12

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

Инвертирование сложных выражений Правило: Чтобы найти инверсию, необходимо знаки умножения заменить знаками сложения, а знаки сложения — знаками умножения и поставить инверсии над каждой переменной. (независимо от того, есть над переменными знаки отрицания или нет)

Слайд 13

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

МИНТЕРМЫ Функции, которые принимают единичное значение только на одном наборе называются минимальными термами, или — МИНТЕРМАМИ (иногда конституентами единицы).

Слайд 14

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

МИНТЕРМЫ Минтермом n переменных называется такая их конъюнкция, в которую каждая переменная входит только один раз в прямой или инверсной форме. Обозначаются минтермы буквой m с десятичным индексом, являющимся номером минтерма.

Слайд 15

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

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

Слайд 16

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

МАКСТЕРМЫ Макстермом n переменных называется такая их дизъюнкция, в которую каждая переменная входит только один раз в прямой или инверсной форме. Макстерм (конституента нуля) — это булева функция, которая принимает единичное значение на всех наборах, за исключением одного.

Слайд 17

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

МАКСТЕРМЫ Макстермы обозначают большой буквой M с десятичными индексами (по аналогии с обозначением минтермов). СВОЙСТВО: дизъюнкция любых двух различных макстермов, зависящих от одних и тех же аргументов, равна единице.

Слайд 18

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

Связь между индексами минтермов и макстермов :

Слайд 19

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

Совершенные нормальные формы СОВЕРШЕННАЯ КОНЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА (СКНФ) СОВЕРШЕННАЯ ДИЗЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА (СДНФ)

Слайд 20

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

СОВЕРШЕННАЯ ДИЗЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА – это ДНФ, в которой все конъюнкции имеют ранг n дизъюнкция минтермов n аргументов дизъюнкцию простых конъюнкций

Слайд 21

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

y =  х1δ1 х2δ2 х3δ3... х(n–1)δ(n–1) хnδn ,

Слайд 22

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

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

Слайд 23

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

СОВЕРШЕННАЯ КОНЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА – это КНФ, в которой все дизъюнкции имеют ранг n конъюнкция макстермов n аргументов конъюнкция простых дизъюнкций.

Слайд 24

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

y =  ( х1δ1 + х2δ2 +х3δ3 + ... + х(n–1)δ(n–1) + хnδn),

Слайд 25

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

Карта Вейча её модификацию называют диаграммой Карно На рис.1 приведены минтермы функции от двух переменных А и В. На рис.2 указаны десятичные номера минтермов.

Слайд 26

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

Карта Вейча для 3-х аргументов

Слайд 27

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

Карта Вейча для 4-х аргументов

Слайд 28

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

Карта Вейча для 5-х аргументов

Слайд 29

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

Нанесение функций на карту Вейча Пусть есть функция: f (A,B,C) = A + BC Ей соответствует представление на карте Вейча:

Слайд 30

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

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

Слайд 31

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

Импликанта булевой функции Функция g(x1, …, xn) называется импликантой функции f(x1, …, xn), если для любого набора аргументов, на котором g=1, справедливо что f=1.

Слайд 32

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

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

Слайд 33

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

Пример импликант: Пусть дана функция: f = AB + BC. Представим её в СДНФ: f = (3,6,7) . Эта функция содержит три минтерма. Из них можно образовать семь различных функций, каждая из которых является импликантой функции f.

Слайд 34

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

Импликанты ф-ции f = AB + BC

Слайд 35

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

Методы минимизации функций алгебры логики минимизация методом Квайна; минимизация с использованием карт Карно; минимизация не полностью определенных (частичных) функций; минимизация КНФ; минимизация методом кубического задания функций алгебры логики; минимизация методом Квайна–Мак–Класски; минимизация с использованием алгоритма извлечения (Рота); минимизация ФАЛ методом преобразования логических выражений.

Слайд 36

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

минимизация методом Квайна Основу метода составляет теорема склеивания, которая применяется к каждой паре минтермов заданной функции. Например: f (A,B,C,D) = (0, 1, 3, 6, 7, 8, 12, 13, 14, 15)

Слайд 37

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

Слайд 38

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

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

Слайд 39

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

Для всякой булевой функции существует единственная сокращённая ДНФ

Слайд 40

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

Найти методом Квайна минимальное выражение для функции y

Слайд 41

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

1–й этап

Слайд 42

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

2–й этап - Импликантная таблица

Слайд 43

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

Получение минимальной ДНФ

Слайд 44

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

Минимальная ДНФ из 3-х импликант

Слайд 45

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

Граф-схема булевой функции

Слайд 46

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

Формы булевых функций

Слайд 47

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

Литература по теме: Лысиков Б. Г. Арифметические и логические основы цифровых автоматов // Минск: Высшая школа, 1980. – 268 с. Савельев А. Я. Прикладная теория цифровых автоматов: учебник для вузов по специальности ЭВМ // М.: Высшая школа, 1987. – 462 с. Шевелев Ю. П. Дискретная математика. Ч. 1: Теория множеств. Булева алгебра Автоматизированная технология обучения «Символ»): Учебное пособие // Томск. гос. ун-т систем управления и радиоэлектроники, 2003. — 118 с.