Логика в информатике Решение уравнений. Логические основы ПЭВМ.

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



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

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

Логика в информатике Решение уравнений. Логические основы ПЭВМ.

Логическое уравнение Логическое уравнение – равенство двух высказываний, в котором присутствует логическая переменная, которая представляет некоторую логическую функцию. Пример: Где корень: X = F (A, B)

Решение уравнения 1.Перейти к префиксной форме записи уравнения, заменив обозначения отрицаний на ¬ 2.Построить заголовок таблицы истинности специального вида 3.Заполнить строки таблицы истинности для всех сочетаний А и В, подставляя вместо X - 0 или 1. 4.Сформировать таблицу истинности для X = F (А,B) 5.По таблице истинности определить вид функции X, при необходимости воспользовавшись методами построения СКНФ и СДНФ, которые будут рассмотрены ниже.

Переход к префиксной форме Обычная форма: Префиксная форма:

Построение таблицы истинности специального вида ¬((А+B)·(X A·B))=¬(B+¬(X A))

Таблица истинности X=F(A, B) ABX Соответствует отрицанию импликации В в А ОТВЕТ:

Комбинационные схемы логических устройств Базисные элементы (ГОСТ ): 1 А В Дизъюнкция А В Эквивалентность & А В Конъюнкция M2 А В XOR

Комбинационные схемы логических устройств Базисные элементы (ГОСТ ): 1 А В Импликация & А В Элемент Шеффера & А В Коимпликация 1 А В Элемент Вебба

Расшифровка элемента & А В Коимпликация Вход 1 Вход 2 Отрицание Действие Выход А · В

Пример схемы F 1 & 1 & & 1M2 B A

Решение схем 1 Вариант – преобразование схемы в сложное логическое выражение и затем – упрощение его по законам логики. 2 Вариант – построение таблицы истинности а затем, при необходимости, построение через СКНФ или СДНФ (см. ниже). Рассмотрим второй вариант, как более простой и понятный.

Построение таблицы истинности AB A + B + · B B · A + A B A + · ·

Таблица истинности F(A, B) ABX Соответствует отрицанию импликации В в А ОТВЕТ:

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

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

Алгоритм получения СДНФ по таблице истинности 1.Отметить строки таблицы истинности в последнем столбце которых стоят 1. 2.Выписать для каждой отмеченной строки конъюнкцию всех переменных следующим образом: если значение переменной в данной строке равно 1, то в конъюнкцию включать саму эту переменную, если равно 0, то ее отрицание. 3.Все полученные конъюнкции связать в дизъюнкцию.

Пример построения СДНФ XY F(X,Y) Отметить единицы 2. Конъюнкции: X · Y 3. Дизъюнкция: X · Y + X · Y

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

Пример построения СKНФ XY F(X,Y) Отметить нули 2. Дизъюнкции: X + Y 3. Конъюнкция: (X + Y) · (X + Y)