1 Совершенная дизъюнктивная нормальная форма и совершенная конъюнктивная нормальная форма Логические основы ЭВМ 10 класс Белоусова Елена Ивановна, учитель.

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



Advertisements
Похожие презентации
Элементы математической логики. Высказывание Объект изучения – высказывание. Высказывание – предложение (сообщение) об объективно существующей действительности,
Advertisements

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

1 Совершенная дизъюнктивная нормальная форма и совершенная конъюнктивная нормальная форма Логические основы ЭВМ 10 класс Белоусова Елена Ивановна, учитель информатики МОУ «СОШ 75», г. Чусовой, Пермский край

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

3 Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция простых конъюнкций. ДНФ можно построить для всякой формулы (путем преобразования).

4 Простой дизъюнкцией (элементарной) называется дизъюнкция одной или нескольких переменных, при этом каждая переменная входит не более одного раза (либо сама, либо ее отрицание). Не соответствует правилу

5 Конъюнктивной нормальной формой (КНФ) называется конъюнкция простых дизъюнкций. КНФ можно построить для всякой формулы (путем преобразования).

6 Задача Пусть дана таблица истинности для некоторой логической функции F(X,Y). Перейти от таблицы истинности к формуле, а на ее основе построить функциональную схему. XYF

7 Логическая функция ФОРМУЛА ТАБЛИЦА ИСТИННОСТИ ПРОБЛЕМА Как от таблицы истинности перейти к формуле, чтобы построить функциональную схему? СХЕМА

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

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

10 Любую функцию можно представить в виде СДНФ, так и СКНФ, кроме константы 0 и константы 1 Теорема алгебры логики

11 Алгоритм получения СДНФ по таблице истинности 1.Отметить те строки таблицы истинности, в последнем столбце которых стоят 1: F(X,Y)YX 1* *1* Выписать для каждой отмеченной строки конъюнкцию всех переменных следующим образом: если значение в данной строке равно 1, то в конъюнкцию включать саму эту переменную, если равно 0, то ее отрицание : для 1-й строки, для 3-строки, для 4-строки 3. Все полученные конъюнкции связать в дизъюнкцию:

12 Алгоритм получения СКНФ по таблице истинности 1.Отметить те строки таблицы истинности, в последнем столбце которых стоят 0: F(X,Y)YX * Выписать для каждой отмеченной строки дизъюнкцию всех переменных следующим образом: если значение в данной строке равно 0, то в дизъюнкцию включать саму эту переменную, если равно 1, то ее отрицание : - для 2-й строки. 3. Все полученные дизъюнкции связать в конъюнкцию:

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

14 Проверка Покажем, что полученные по двум алгоритмам СДНФ и СКНФ эквивалентны. СДНФ и СКНФ Можем проверить, построив таблицу истинности по найденной формуле. XY

15 Логическая схема v F X Y

16 Задача уровня В Представить функцию в виде СДНФ, построить логическую схему этой функции abc =