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

Презентация:



Advertisements
Похожие презентации
Нормальные формы ХНУРЭ, кафедра ПО ЭВМ, Тел , Лекция 6 Н.В. Белоус Факультет компьютерных наук Кафедра ПО ЭВМ,
Advertisements

Логика в информатике Решение уравнений. Логические основы ПЭВМ.
Нормальные формы в математической логике Подготовил: Шинкарёв Г. Г. ГИП-104.
ГБПОУ «МСС УОР 2» Москомспорта Преподаватель информатики Володина М.В г.
Логические функции. Логической (булевой) функцией называют функцию F(x 1,x 2,...,x n ), аргументы которой x 1,x 2,...,x n (независимые переменные) и сама.
Историческая справка Основы формальной логики заложил Аристотель ( гг. до н.э.)- древнегреческий философ и учёный.
1 Совершенная дизъюнктивная нормальная форма и совершенная конъюнктивная нормальная форма Логические основы ЭВМ 10 класс Белоусова Елена Ивановна, учитель.
ФОРМЫ ПРЕДСТАВЛЕНИЯ ВЫСКАЗЫВАНИЙ Элементарной дизъюнкцией называется выражение вида: Элементарной конъюнкцией называется выражение вида: Где A i - либо.
Логика – это наука о формах и законах человеческой мысли, о законах доказательных рассуждений, изучающая методы доказательств и опровержений, т. е. методы.
содержание 1определение 1.определение 2.логическоеотрицание 2.логическое отрицание 3.логическое сложение 4.логическое умножение 5логическоеследование.
Алгебра логики. Логика Логика – это наука о формах и законах человеческой мысли, о законах доказательных рассуждений, изучающая методы доказательств и.
7.3. Основы логической алгебры. Составление цифровых электронных схем. Рассмотрим еще раз таблицы истинности для схем «И», «ИЛИ», «НЕ». X 1 X 2 Y
ЛОГИЧЕСКИЕ ЭЛЕМЕНТЫ 33. Упрощённо можно представить работу компьютера как некоторого устройства, производящего обработку двоичных сигналов, соответствующих.
Логические выражения могут быть простыми и сложными. Простое логическое выражение состоит из одного высказывания и не содержит логические операции. В.
4. Минимизация логических функций. Карты Карно. Задача минимизации логической функции заключается в том, чтобы найти наиболее компактное её представление.
Построение таблиц истинности логических выражений.
1 Кубенский А.А. Дискретная математика. Глава 2. Элементы математической логики Исчисление высказываний Высказывание – утверждение о математических.
Алексеева Е.В., учитель информатики и ИКТ, МОУ «Сланцевская СОШ 3» Основы логики.
СДНФ и СКНФ Формы булевых функций. Дополнительные операции Импликация Эквивалентность Сложение по модулю 2 Стрелка Пирса (ИЛИ-НЕ) Штрих Шеффера (И-НЕ)
ОСНОВЫ ЛОГИКИ Кривенцов Леонид Александрович, учитель информатики и ИКТ МОУ-СОШ 4 г. Асино томской области.
Транксрипт:

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

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

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

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

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

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

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

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

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

Пример минимизации посредством карт Карно 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

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

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

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