Основы теории логических преобразований

Сентябрь 13, 2022

Главная
Математика
Основы теории логических преобразований

Содержание

2. Основы теории логических преобразований Математическая логика Логические операции и элементы Преобразование логических выражений
3. 1) Логика оказала влияние на развитие математики, прежде всего теории множеств, функциональных систем, алгоритмов, рекурсивных функций.
4. АЛГЕБРА ЛОГИКИ (ВЫСКАЗЫВАНИЙ) - РАЗДЕЛ МАТЕМАТИЧЕСКОЙ ЛОГИКИ, ИЗУЧАЮЩИЙ ВЫСКАЗЫВАНИЯ И ЛОГИЧЕСКИЕ ОПЕРАЦИИ НАД НИМИ.
5. Основные понятия Высказывание Простое и сложное высказывание
6. ИНВЕРСИЯ (ЛОГИЧЕСКОЕ ОТРИЦАНИЕ) - ПРИСОЕДИНЕНИЕ ЧАСТИЦЫ «НЕ» К СКАЗУЕМОМУ ДАННОГО ПРОСТОГО ВЫСКАЗЫВАНИЯ ИЛИ ПРИСОЕДИНЕНИЕ СЛОВ «НЕВЕРНО
7. 0 вых
8. ДИЗЪЮНКЦИЯ (ЛОГИЧЕСКОЕ СЛОЖЕНИЕ) - СОЕДИНЕНИЕ ДВУХ ВЫСКАЗЫВАНИЙ А И В В ОДНО С ПОМОЩЬЮ СОЮЗА «ИЛИ»,
10. Строгая дизъюнкция А+В – А*В Элемент “Исключающее ИЛИ”
11. КОНЪЮНКЦИЯ (ЛОГИЧЕСКОЕ УМНОЖЕНИЕ) - СОЕДИНЕНИЕ ДВУХ ВЫСКАЗЫВАНИЙ А И В В ОДНО С ПОМОЩЬЮ СОЮЗА «И».
12. Вх1- А*В
13. ИМПЛИКАЦИЯ - ЛОГИЧЕСКАЯ ОПЕРАЦИЯ, СООТВЕТСТВУЮЩАЯ СОЮЗУ «ЕСЛИ . . . , ТО . . .» ИМПЛИКАЦИЯ
14. 1 – А+А+В А – посылка В – следствие
15. ЭКВИВАЛЕНЦИЯ - ЛОГИЧЕСКАЯ ОПЕРАЦИЯ, СООТВЕТСТВУЮЩАЯ СОЮЗУ «ТОГДА И ТОЛЬКО ТОГДА, КОГДА …» ЭКВИВАЛЕНЦИЯ ДВУХ ВЫСКАЗЫВАНИЙ ИСТИННА
16. 1 – (А – В)2 1 – (А – В)2
17. Логические элементы в EW
18. Логические функции Логической (булевой) функцией называют функцию Y=f(Х1, Х2 ..., Хn), аргументы которой Х1, Х2 ...,
19. СНДФ и СКНФ Если логическая функция представлена дизъюнкцией, конъюнкцией и инверсией, то такая форма представления называется
20. Совершенная дизъюнктивная нормальная форма (СДНФ)отвечает следующим требованиям: 1) в ней нет двух одинаковых элементарных конъюнкций; 2)
22. Алгоритм образования СДНФ по таблице истинности. 1. Выделить в таблице истинности все наборы переменных, на которых
24. Аналитическое представление ЛФ: 1. В СДНФ – Y=X1*X2*X3+X1*X2*X3+X1*X2*X3+X1*X2*X3 2. В СКНФ -Y=(X1+X2+X3)*(X1+X2+X3)*(X1+X2+X3)*(X1+X2+X3) Пример3
25. Минимизация логических функций Цель минимизации ЛФ заключается уменьшение стоимости ее технической реализации при сохранении заданных характеристик.
26. Основные законы логики
27. Основные законы логики
30. ВЫСКАЗЫВАНИЕ - ЭТО ПОВЕСТВОВАТЕЛЬНОЕ ПРЕДЛОЖЕНИЕ, О КОТОРОМ МОЖНО СКАЗАТЬ, ЧТО ОНО ИСТИННО ИЛИ ЛОЖНО. 1) Земля
31. ВЫСКАЗЫВАНИЕМ НЕ ЯВЛЯЕТСЯ: 1) ВОСКЛИЦАТЕЛЬНЫЕ И ВОПРОСИТЕЛЬНЫЕ ПРЕДЛОЖЕНИЯ. 2) ОПРЕДЕЛЕНИЯ. 3) ПРЕДЛОЖЕНИЯ ТИПА: «ОН СЕРОГЛАЗ» «X2-4X+3=0»
33. Скачать презентацию

Слайд 2

Основы теории логических преобразований
Математическая логика
Логические операции и элементы
Преобразование логических выражений

Слайд 3

1) Логика оказала влияние на развитие математики, прежде всего теории множеств,

функциональных систем, алгоритмов, рекурсивных функций.
2) Идеи и аппарат логики используется в кибернетике, ВТ и электротехнике (построены компьютеры на основе законов математической логики).
3) В гуманитарных науках (логика, криминалистика).
4) Математическая логика является средством для изучения деятельности мозга - для решения этой самой важной проблемы биологии и науки вообще.

Слайд 4

АЛГЕБРА ЛОГИКИ (ВЫСКАЗЫВАНИЙ) -
РАЗДЕЛ МАТЕМАТИЧЕСКОЙ ЛОГИКИ, ИЗУЧАЮЩИЙ ВЫСКАЗЫВАНИЯ И ЛОГИЧЕСКИЕ ОПЕРАЦИИ

НАД НИМИ.

Слайд 5

Основные понятия
Высказывание
Простое и сложное высказывание

Слайд 6

ИНВЕРСИЯ (ЛОГИЧЕСКОЕ ОТРИЦАНИЕ) - ПРИСОЕДИНЕНИЕ ЧАСТИЦЫ «НЕ» К СКАЗУЕМОМУ ДАННОГО

ПРОСТОГО ВЫСКАЗЫВАНИЯ ИЛИ ПРИСОЕДИНЕНИЕ СЛОВ «НЕВЕРНО ЧТО. . .» КО ВСЕМУ ВЫСКАЗЫВАНИЮ.

ИНВЕРСИЯ ЛОГИЧЕСКОЙ ПЕРЕМЕННОЙ ИСТИННА, ЕСЛИ САМА ПЕРЕМЕННАЯ ЛОЖНА, И, НАОБОРОТ, ИНВЕРСИЯ ЛОЖНА, ЕСЛИ ПЕРЕМЕННАЯ ИСТИННА.

Слайд 7

0

вых

Слайд 8

ДИЗЪЮНКЦИЯ (ЛОГИЧЕСКОЕ СЛОЖЕНИЕ) -
СОЕДИНЕНИЕ ДВУХ ВЫСКАЗЫВАНИЙ
А И В
В ОДНО

С ПОМОЩЬЮ СОЮЗА «ИЛИ»,
УПОТРЕБЛЯЕМОГО В НЕИСКЛЮЧАЮЩЕМ ВИДЕ.

ДИЗЪЮНКЦИЯ ДВУХ
ЛОГИЧЕСКИХ ВЫСКАЗЫВАНИЙ
ЛОЖНА ТОГДА И ТОЛЬКО ТОГДА, КОГДА ОБА ВЫСКАЗЫВАНИЯ
ЛОЖНЫ.

Слайд 9

Слайд 10

Строгая дизъюнкция
А+В – А*В
Элемент “Исключающее ИЛИ”

Слайд 11

КОНЪЮНКЦИЯ (ЛОГИЧЕСКОЕ УМНОЖЕНИЕ) -
СОЕДИНЕНИЕ ДВУХ ВЫСКАЗЫВАНИЙ А И В
В ОДНО

С ПОМОЩЬЮ СОЮЗА «И».

КОНЪЮНКЦИЯ ДВУХ
ЛОГИЧЕСКИХ ВЫСКАЗЫВАНИЙ
ИСТИННА ТОГДА И ТОЛЬКО ТОГДА,
КОГДА ОБА ВЫСКАЗЫВАНИЯ
ИСТИННЫ.

Слайд 12

Вх1-
А*В

Слайд 13

ИМПЛИКАЦИЯ -
ЛОГИЧЕСКАЯ ОПЕРАЦИЯ, СООТВЕТСТВУЮЩАЯ СОЮЗУ «ЕСЛИ . . . , ТО

. . .»

ИМПЛИКАЦИЯ ВЫСКАЗЫВАНИЙ
ЛОЖНА ЛИШЬ В СЛУЧАЕ, КОГДА А
ИСТИННО, А В ЛОЖНО.

Слайд 14

1 – А+А+В
А – посылка
В – следствие

Слайд 15

ЭКВИВАЛЕНЦИЯ -
ЛОГИЧЕСКАЯ ОПЕРАЦИЯ, СООТВЕТСТВУЮЩАЯ СОЮЗУ «ТОГДА И ТОЛЬКО ТОГДА, КОГДА …»

ЭКВИВАЛЕНЦИЯ ДВУХ
ВЫСКАЗЫВАНИЙ ИСТИННА В ТОМ И ТОЛЬКО ТОМ СЛУЧАЕ,
КОГДА ОБА ЭТИ
ВЫСКАЗЫВАНИЯ ИСТИННЫ
ИЛИ ЛОЖНЫ.

Слайд 16

1 – (А – В)2
1 – (А – В)2

Слайд 17

Логические элементы в EW

Слайд 18

Логические функции
Логической (булевой) функцией называют функцию Y=f(Х1, Х2 ..., Хn), аргументы

которой Х1, Х2 ..., Хn (независимые переменные) и сама функция (зависимая переменная) принимают значения 0 или 1.
Логические функции могут быть заданы табличным способом или аналитически — в виде соответствующих формул.
Таблицу, показывающую, какие значения принимает логическая функция при всех сочетаниях значений ее аргументов, называют таблицей истинности. Таблица истинности логической функции п аргументов содержит 2n строк, п столбцов значений аргументов и 1 столбец значений функции.
Одной переменной Y= f (X)

Слайд 19

СНДФ и СКНФ
Если логическая функция представлена дизъюнкцией, конъюнкцией и инверсией, то

такая форма представления называется НОРМАЛЬНОЙ.
Элементарная конъюнкция — конъюнкция конечного множества логических переменных и их инверсий.
Элементарная дизъюнкция — дизъюнкция конечного множества логических переменных и их инверсий.
Число аргументов, образующих элементарную дизъюнкцию или конъюнкцию, называется ее рангом.
Пример 1. Х1 *X2*X3 , Х1* X2* X3 — элементарные конъюнкции третьего ранга. X1+ X2, Х1+X2— элементарные дизъюнкции второго ранга.
Дизъюнктивная нормальная форма (ДНФ) содержит элементарные конъюнкции, связанные между собой операцией дизъюнкции.
Конъюнктивная нормальная форма (КНФ) содержит элементарные дизъюнкции, связанные между собой операцией конъюнкции.
Одну и ту же логическую функцию можно представить разными ДНФ и КНФ.
Для исключения неоднозначности записи логические функции могут быть представлены в совершенных дизъюнктивной и конъюнктивной нормальных формах.

Слайд 20

Совершенная дизъюнктивная нормальная форма (СДНФ)отвечает следующим требованиям:
1) в ней нет двух

одинаковых элементарных конъюнкций;
2) ни одна элементарная конъюнкция не содержит двух одинаковых переменных;
3) ни одна элементарная конъюнкция не содержит переменную вместе с ее инверсией;
4) все конъюнкции имеют один и тот же ранг.
Аналогичным требованиям подчиняется и совершенная конъюнктивная нормальная форма (СКНФ).
Пример 2. Если логическая функция содержит конъюнкции разных рангов, то для получения СДНФ следует повысить ранг младших конъюнкций, используя закон исключения третьего(A+A=1).
F(X,Y,Z)= (X* Y) +(X*Y*Z) = (X*Y)* (Z+Z) +(X*Y*Z) =

=(X* Y* Z)+(X* Y*Z) + (X* Y* Z).

Слайд 21

Слайд 22

Алгоритм образования СДНФ по таблице истинности.
1. Выделить в таблице истинности все

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

Слайд 23

Слайд 24

Аналитическое представление ЛФ:
1. В СДНФ – Y=X1X2X3+X1X2X3+X1X2X3+X1X2X3
2. В СКНФ -Y=(X1+X2+X3)(X1+X2+X3)(X1+X2+X3)*(X1+X2+X3)
Пример3

Слайд 25

Минимизация логических функций

Цель минимизации ЛФ заключается уменьшение стоимости ее

технической
реализации при сохранении заданных характеристик.
Критерии:
Для ЦУ на дискретных элементах – минимизация их числа.
Для ЦУ на БИС и СБИС – площадь схемы на кристалле и как следствие, регулярность внутренней структуры и минимизация числа межсоединений.
Способы:
Аналитический – путем тождественных преобразований на основе законов алгебры логики.
Пример: ЛФ представлена в виде СДНФ:
Y=A B C+ A B C+ A B C+ A B C
Элементарные конъюнкции называются соседними (логически смежными), если они отличаются только одной переменной, применение к ним операции «склеивания» понижает их ранг на единицу. Здесь соседние 1 и 2, а также 3 и 4 кон.
Y=A B (C + C) + A B (C + C)= A B + A B= A ( B + B ) = A
2. Использование специальных методов.

Слайд 26

Основные законы логики

Слайд 27

Основные законы логики

Слайд 28

Слайд 29

Слайд 30

ВЫСКАЗЫВАНИЕ - ЭТО ПОВЕСТВОВАТЕЛЬНОЕ ПРЕДЛОЖЕНИЕ, О КОТОРОМ МОЖНО СКАЗАТЬ, ЧТО ОНО

ИСТИННО ИЛИ ЛОЖНО.
1) Земля - планета Солнечной системы.
2) 2+8<5
3) 5 •5=25
4) Всякий квадрат есть параллелограмм
5) Каждый параллелограмм есть квадрат
6) 2•2 =5

Слайд 31

ВЫСКАЗЫВАНИЕМ
НЕ ЯВЛЯЕТСЯ:
1) ВОСКЛИЦАТЕЛЬНЫЕ И ВОПРОСИТЕЛЬНЫЕ ПРЕДЛОЖЕНИЯ.
2) ОПРЕДЕЛЕНИЯ.
3) ПРЕДЛОЖЕНИЯ ТИПА:

«ОН СЕРОГЛАЗ»
«X2-4X+3=0»

Основы теории логических преобразований

Содержание

Основы теории логических преобразованийМатематическая логикаЛогические операции и элементыПреобразование логических выражений

1) Логика оказала влияние на развитие математики, прежде всего теории множеств,

АЛГЕБРА ЛОГИКИ (ВЫСКАЗЫВАНИЙ) -РАЗДЕЛ МАТЕМАТИЧЕСКОЙ ЛОГИКИ, ИЗУЧАЮЩИЙ ВЫСКАЗЫВАНИЯ И ЛОГИЧЕСКИЕ ОПЕРАЦИИ

Основные понятияВысказываниеПростое и сложное высказывание

ИНВЕРСИЯ (ЛОГИЧЕСКОЕ ОТРИЦАНИЕ) - ПРИСОЕДИНЕНИЕ ЧАСТИЦЫ «НЕ» К СКАЗУЕМОМУ ДАННОГО

0 вых

ДИЗЪЮНКЦИЯ (ЛОГИЧЕСКОЕ СЛОЖЕНИЕ) -СОЕДИНЕНИЕ ДВУХ ВЫСКАЗЫВАНИЙ А И В В ОДНО

Строгая дизъюнкция А+В – А*ВЭлемент “Исключающее ИЛИ”

КОНЪЮНКЦИЯ (ЛОГИЧЕСКОЕ УМНОЖЕНИЕ) -СОЕДИНЕНИЕ ДВУХ ВЫСКАЗЫВАНИЙ А И В В ОДНО

Вх1-А*В

ИМПЛИКАЦИЯ -ЛОГИЧЕСКАЯ ОПЕРАЦИЯ, СООТВЕТСТВУЮЩАЯ СОЮЗУ «ЕСЛИ . . . , ТО

1 – А+А+ВА – посылкаВ – следствие

ЭКВИВАЛЕНЦИЯ -ЛОГИЧЕСКАЯ ОПЕРАЦИЯ, СООТВЕТСТВУЮЩАЯ СОЮЗУ «ТОГДА И ТОЛЬКО ТОГДА, КОГДА …»

1 – (А – В)2 1 – (А – В)2

Логические элементы в EW

Логические функцииЛогической (булевой) функцией называют функцию Y=f(Х1, Х2 ..., Хn), аргументы

СНДФ и СКНФЕсли логическая функция представлена дизъюнкцией, конъюнкцией и инверсией, то

Совершенная дизъюнктивная нормальная форма (СДНФ)отвечает следующим требованиям:1) в ней нет двух

Алгоритм образования СДНФ по таблице истинности.1. Выделить в таблице истинности все

Аналитическое представление ЛФ:1. В СДНФ – Y=X1*X2*X3+X1*X2*X3+X1*X2*X3+X1*X2*X32. В СКНФ -Y=(X1+X2+X3)*(X1+X2+X3)*(X1+X2+X3)*(X1+X2+X3)Пример3

Минимизация логических функций Цель минимизации ЛФ заключается уменьшение стоимости ее

Основные законы логики

Основные законы логики

ВЫСКАЗЫВАНИЕ - ЭТО ПОВЕСТВОВАТЕЛЬНОЕ ПРЕДЛОЖЕНИЕ, О КОТОРОМ МОЖНО СКАЗАТЬ, ЧТО ОНО

ВЫСКАЗЫВАНИЕМ НЕ ЯВЛЯЕТСЯ:1) ВОСКЛИЦАТЕЛЬНЫЕ И ВОПРОСИТЕЛЬНЫЕ ПРЕДЛОЖЕНИЯ. 2) ОПРЕДЕЛЕНИЯ.3) ПРЕДЛОЖЕНИЯ ТИПА:

Похожие презентации

Основы теории логических преобразований
Математическая логика
Логические операции и элементы
Преобразование логических выражений

АЛГЕБРА ЛОГИКИ (ВЫСКАЗЫВАНИЙ) -
РАЗДЕЛ МАТЕМАТИЧЕСКОЙ ЛОГИКИ, ИЗУЧАЮЩИЙ ВЫСКАЗЫВАНИЯ И ЛОГИЧЕСКИЕ ОПЕРАЦИИ

Основные понятия
Высказывание
Простое и сложное высказывание

0

вых

ДИЗЪЮНКЦИЯ (ЛОГИЧЕСКОЕ СЛОЖЕНИЕ) -
СОЕДИНЕНИЕ ДВУХ ВЫСКАЗЫВАНИЙ
А И В
В ОДНО

Строгая дизъюнкция
А+В – А*В
Элемент “Исключающее ИЛИ”

КОНЪЮНКЦИЯ (ЛОГИЧЕСКОЕ УМНОЖЕНИЕ) -
СОЕДИНЕНИЕ ДВУХ ВЫСКАЗЫВАНИЙ А И В
В ОДНО

Вх1-
А*В

ИМПЛИКАЦИЯ -
ЛОГИЧЕСКАЯ ОПЕРАЦИЯ, СООТВЕТСТВУЮЩАЯ СОЮЗУ «ЕСЛИ . . . , ТО

1 – А+А+В
А – посылка
В – следствие

ЭКВИВАЛЕНЦИЯ -
ЛОГИЧЕСКАЯ ОПЕРАЦИЯ, СООТВЕТСТВУЮЩАЯ СОЮЗУ «ТОГДА И ТОЛЬКО ТОГДА, КОГДА …»

1 – (А – В)2
1 – (А – В)2

Логические функции
Логической (булевой) функцией называют функцию Y=f(Х1, Х2 ..., Хn), аргументы

СНДФ и СКНФ
Если логическая функция представлена дизъюнкцией, конъюнкцией и инверсией, то

Совершенная дизъюнктивная нормальная форма (СДНФ)отвечает следующим требованиям:
1) в ней нет двух

Алгоритм образования СДНФ по таблице истинности.
1. Выделить в таблице истинности все

Аналитическое представление ЛФ:
1. В СДНФ – Y=X1X2X3+X1X2X3+X1X2X3+X1X2X3
2. В СКНФ -Y=(X1+X2+X3)(X1+X2+X3)(X1+X2+X3)*(X1+X2+X3)
Пример3

Минимизация логических функций

Цель минимизации ЛФ заключается уменьшение стоимости ее

ВЫСКАЗЫВАНИЕМ
НЕ ЯВЛЯЕТСЯ:
1) ВОСКЛИЦАТЕЛЬНЫЕ И ВОПРОСИТЕЛЬНЫЕ ПРЕДЛОЖЕНИЯ.
2) ОПРЕДЕЛЕНИЯ.
3) ПРЕДЛОЖЕНИЯ ТИПА: