Математическая логика Ненашев Дмитрий Александрович Кафедра высшей математики Научный руководитель: Денискина Е.А. Факультет двигателей летательных аппаратов. - презентация

1 Математическая логика Ненашев Дмитрий Александрович Кафедра высшей математики Научный руководитель: Денискина Е.А. Факультет двигателей летательных аппаратов

2 Цель работы Познакомиться с алгеброй логики и изучить алгоритм минимизации посредством карт Карно.

3 ВысказыванияАлгебра логики Числовая алгебра Мат логика дизъюнкция, || «+»«или» конъюнкция, & «х»«и» отрицаниеĀ, ¬«-»«не» Алгебра логики Базовыми элементами в алгебре логики являются высказывания: отрицание (унарная операция), конъюнкция (бинарная), дизъюнкция (бинарная), а также константы - логический ноль 0 и логическая единица 1

4 Таблицы истинности Таблица истинности- это таблица, показывающая истинность сложного высказывания при всех возможных значениях входящих переменных

5 Основные тождества Для упрощения логических выражений существует 25 основных тождеств. Рассмотрим элементарный пример такого тождества: Ā A= 1 и Ā A= = 1 и 1 0= 0

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

7 Конъюнктивная нормальная форма(КНФ) Конъюнктивной совершенной нормальной формой (КСНФ) Конъюнктивные формы

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

9 Алгоритм для карт Карно 1. Привести булеву функцию к ДНФ. 2. Нанести единицы на карту Карно. 3. Объединить соседние единицы контурами, охватывающими 2^т клеток (т - 0, 1, 2, 3..). 4. Провести упрощения. Оставить отдельно по столбцам и по строкам общие переменные. 5. Объединить оставшиеся члены (по одному в каждом контуре) дизъюнкцией. 6. Записать полученное упрощенное булево выражение.

10 Пример минимизации посредством карт Карно f(ABC) = Ā B Ā BC AB ABC 1. Найдем наборы, при которых функция равна Составим карту Карно и расставим в ней 1, согласно таблице истинности. Обведем контурами соседние клетки, содержащие 1. Такое действие соответствует заключению в скобки слагаемых: Ā B v Ā BC и AB v ABC 3. Рассмотрим объединение двух соседних единиц. f(AВС) = Ā В v AB = В (Ā v A)=В Ответ: f(A, В, С) = В NABCF FĀĀ BABA C

11 Вывод С помощью минимизации методом карт Карно мы смогли упросить функцию из вида: f(ABC) = Ā B Ā BC AB ABC в вид: f(AВС) = В.

12 Завершение Все компьютеры работают в двоичной системе исчисления, в которой вся информация закодирована определенным набором из 0 и 1, где за 1 в двоичном коде принимается «истинна», а за 0- «ложь». Нетрудно заметить, что количество операций существенно уменьшилось, это отлично видно визуально. А в месте с этим увеличилась производительность конкретной программы. Благодаря данному методу можно быстро и эффективно преобразовывать и упрощать логические выражения.

13 Спасибо за внимание