Презентация на тему: Логика и алгебра логики

Логика и алгебра логики
Логика и алгебра логика
Высказывания
Примеры высказываний
Примеры высказываний
Булева алгебра
Булева алгебра
Булева алгебра
Обозначение высказываний
Логические операции
Логические выражения
Таблица истинности
Таблица истинности
Основные логические операции
Логика и алгебра логики
Логика и алгебра логики
Логика и алгебра логики
Логика и алгебра логики
Логика и алгебра логики
Построение таблицы истинности логического выражения
Логика и алгебра логики
Приоритетность выполнения логических операций
Правила подсказки
Пример таблицы истинности
Равносильность логических выражений
Способы установления равносильности двух логических выражений
Определение равносильности логических выражений с помощью сравнения таблиц истинности
Определение равносильности логических выражений с помощью сравнения таблиц истинности
Определение равносильности логических выражений с помощью сравнения таблиц истинности
Определение равносильности логических выражений с помощью сравнения таблиц истинности
Законы алгебры логики
Определение равносильности логических выражений приведением одного логического выражения к другому на основе доказанных законов алгебры логики
Определение равносильности двух логических выражений приведением обоих выражений к одному выражению
Задача 1
Решение
Решение
Решение
Решение
Решение
Задача 2
Решение
Домашнее задание
Задачи для Самостоятельного решения
Логические операции импликация, эквиваленция, исключающее ИЛИ
Логическая операция импликация
Логическая операция импликация
Логическая операция импликация
Пример импликации
Пример импликации
Пример импликации
Пример импликации
Пример импликации
Операция импликации через основные логические выражения
Операция эквиваленция
Операция эквиваленция
Примеры истинных высказываний, построенных с использованием операции эквивалентности
Операция эквиваленции через основные логические операции
Операция исключающее ИЛИ
Операция исключающее ИЛИ
Операция исключающее ИЛИ
Операция исключающее ИЛИ через основные логические операции
Операция исключающее ИЛИ через основные логические операции
Взаимосвязь операций исключающего ИЛИ и эквивалентности
1/63
Средняя оценка: 4.2/5 (всего оценок: 44)
Код скопирован в буфер обмена
Скачать (3679 Кб)
1

Первый слайд презентации: Логика и алгебра логики

Информатика для СПО

Изображение слайда
2

Слайд 2: Логика и алгебра логика

Логика – это наука о законах и формах правильного мышления Описание логических преобразований алгебраическими методами выполняется с помощью алгебры логики Основными объектами алгебры логики являются высказывания. 2

Изображение слайда
3

Слайд 3: Высказывания

Высказывание – это утверждение, которое является истинным или ложным Высказывания рассматриваются с точки зрения не их содержания, а из значения: « истина » или « ложь ». Истина обозначается – 1, ложь – 0. 3

Изображение слайда
4

Слайд 4: Примеры высказываний

Первый элемент таблицы Менделеева – кислород Сила тока в участке цепи прямо пропорциональна напряжению 5=6 Все на сбор макулатуры! Сейчас идет дождь. 4

Изображение слайда
5

Слайд 5: Примеры высказываний

Жирафы летят на север. История – интересный предмет. У квадрата – 10 сторон и все разные. Красиво! В городе N живут 2 миллиона человек. Который час? 5

Изображение слайда
6

Слайд 6: Булева алгебра

Алгебра логики изучает высказывания и способы установления их истинности с помощью алгебраических методов. Ее также называют алгеброй Буля или булевой алгеброй, по имени английского математика Джорджа Буля, разработавшего ее в XIX веке. 6

Изображение слайда
7

Слайд 7: Булева алгебра

Алгебра логики абстрактна и, следовательно, применима к объектам любой природы, которые могут быть рассмотрены с точки зрения значений «истина» или «ложь». 7

Изображение слайда
8

Слайд 8: Булева алгебра

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

Изображение слайда
9

Слайд 9: Обозначение высказываний

A – Сейчас идет дождь. B – Форточка открыта. простые высказывания (элементарные) Составные высказывания строятся из простых с помощью логических связок (операций) « и», « или», « не», « если … то», « тогда и только тогда» и др. Любое высказывание может быть ложно (0) или истинно (1). ! A и B A или не B если A, то B A тогда и только тогда, когда B Сейчас идет дождь и открыта форточка. Сейчас идет дождь или форточка закрыта. Если сейчас идет дождь, то форточка открыта. Дождь идет тогда и только тогда, когда открыта форточка. 9

Изображение слайда
10

Слайд 10: Логические операции

Логическая операция – действие, которое создает из одного или нескольких высказываний новое высказывание и устанавливает его истинность по некоторому правилу. 10

Изображение слайда
11

Слайд 11: Логические выражения

Высказывание, которое построено с помощью логических операций, может быть записано методами алгебры логики как логические выражения, в которых задается логическая функция и ее аргументы – логические переменные. F(A, B, …, Z) Логическая функция Логические переменные 11

Изображение слайда
12

Слайд 12: Таблица истинности

Значения логической функции для сочетаний аргументов задается специальной таблицей, называемой таблицей истинности. А не А 1 0 0 1 12

Изображение слайда
13

Слайд 13: Таблица истинности

В левой части таблицы истинности указывается набор всех возможных сочетаний значений аргументов, а в правой – значения функции, соответствующие этим сочетаниям. Размер таблицы определяется по формуле 2 n где n – количество аргументов. А не А 1 0 0 1 13

Изображение слайда
14

Слайд 14: Основные логические операции

В качестве основных логических операций в логических выражениях используются: инверсия (логическое отрицание, НЕ) дизъюнкция (логическое сложение, ИЛИ) конъюнкция (логическое умножение, И) Логические операции «инверсия», «дизъюнкция», «конъюнкция» являются основными, потому что любые другие логические операции могут быть заменены комбинацией данных операций 14

Изображение слайда
15

Слайд 15

Операция НЕ ( инверсия) Если высказывание A истинно, то « не А» ложно, и наоборот. А не А 1 0 0 1 таблица истинности операции НЕ Таблица истинности логического выражения Х – это таблица, где в левой части записываются все возможные комбинации значений исходных данных, а в правой – значение выражения Х для каждой комбинации. также,, not A ( Паскаль ), ! A ( Си) 15

Изображение слайда
16

Слайд 16

Операция И Высказывание « A и B » истинно тогда и только тогда, когда А и B истинны одновременно. 220 В A и B A B 16

Изображение слайда
17

Слайд 17

Операция И ( логическое умножение, конъюнкция) A B А и B 1 0 также: A·B, A  B, A and B ( Паскаль ), A && B ( Си) 0 0 0 1 1 0 1 1 0 1 2 3 0 0 конъюнкция – от лат. conjunctio — соединение A  B 17

Изображение слайда
18

Слайд 18

18 Операция ИЛИ ( логическое сложение, дизъюнкция) Высказывание « A или B » истинно тогда, когда истинно А или B, или оба вместе. 220 В A или B A B 18

Изображение слайда
19

Слайд 19

Операция ИЛИ ( логическое сложение, дизъюнкция) A B А или B 1 0 также: A + B, A  B, A or B ( Паскаль ), A || B ( Си) 0 0 0 1 1 0 1 1 1 1 дизъюнкция – от лат. dis junctio — разъединение 19

Изображение слайда
20

Слайд 20: Построение таблицы истинности логического выражения

Для построения таблицы истинности логического выражения следует: Определить количество логических переменных; Заполнить левую часть таблицы истинности сочетаниями значений логических переменных; в правой части таблицы истинности разместить, если необходимо, промежуточные вычисления с учетом приоритетности выполнения логических операций и значений логической функций 20

Изображение слайда
21

Слайд 21

Задачи В таблице приведены запросы к поисковому серверу. Расположите номера запросов в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу. Для обозначения логической операции «ИЛИ» в запросе используется символ |, а для логической операции «И» – &. 1) принтеры & сканеры & продажа 2) принтеры & продажа 3) принтеры | продажа 4) принтеры | сканеры | продажа 1 2 3 4 21

Изображение слайда
22

Слайд 22: Приоритетность выполнения логических операций

операции в скобках инверсия (НЕ) конъюнкция (И) дизъюнкция (ИЛИ) 22

Изображение слайда
23

Слайд 23: Правила подсказки

При составлении таблиц истинности можно применять простые подсказки Для конъюнкции (логического умножения, И): если среди логических переменных есть хотя бы одна со значением ложь (0), то результат – ложь (0); Для дизъюнкции (логического сложения, ИЛИ): если среди логических переменных есть хотя бы одна со значением (1), то результат – истина (1). 23

Изображение слайда
24

Слайд 24: Пример таблицы истинности

F(A,B) = Логические переменные Промежуточные результаты Значение функции А B F(A,B) = 0 0 1 1 0 1 0 1 1 1 1 0 1 0 0 0 0 1 1 1 0 1 1 0 Логические переменные Промежуточные результаты Значение функции А B 0 0 1 1 0 1 0 1 1 1 1 0 1 0 0 0 0 1 1 1 0 1 1 0 24

Изображение слайда
25

Слайд 25: Равносильность логических выражений

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

Изображение слайда
26

Слайд 26: Способы установления равносильности двух логических выражений

Установить равносильность двух логических выражений можно одним из следующих способов: Сравнить таблицы истинности логических выражений; Привести одно логическое выражение к другому, применяя доказанные законы алгебры логики Преобразовать логические выражение к одному выражению. 26

Изображение слайда
27

Слайд 27: Определение равносильности логических выражений с помощью сравнения таблиц истинности

Пример 1. Какое из перечисленных графических выражений равносильно выражению Укажите номер правильного варианта ответа. 1) 2) 3) 4)  B 27

Изображение слайда
28

Слайд 28: Определение равносильности логических выражений с помощью сравнения таблиц истинности

Решение. Построим таблицу истинности для исходного выражения и логических выражений, предложенных в вариантах ответа Логические переменные Значение функции Варианты ответа 1 2 3 4 A B  B 0 0 0 0 1 1 1 0 1 1 1 1 0 1 1 0 0 0 1 0 0 1 1 0 0 0 0 1 Логические переменные Значение функции Варианты ответа 1 2 3 4 A B 0 0 0 0 1 1 1 0 1 1 1 1 0 1 1 0 0 0 1 0 0 1 1 0 0 0 0 1 28

Изображение слайда
29

Слайд 29: Определение равносильности логических выражений с помощью сравнения таблиц истинности

Решение. Как видно из таблицы, значения логического выражения для первого варианта полностью совпадают со значениями исходного выражения. Логические переменные Значение функции Варианты ответа 1 2 3 4 A B  B 0 0 0 0 1 1 1 0 1 1 1 1 0 1 1 0 0 0 1 0 0 1 1 0 0 0 0 1 Логические переменные Значение функции Варианты ответа 1 2 3 4 A B 0 0 0 0 1 1 1 0 1 1 1 1 0 1 1 0 0 0 1 0 0 1 1 0 0 0 0 1 29

Изображение слайда
30

Слайд 30: Определение равносильности логических выражений с помощью сравнения таблиц истинности

Решение. Таким образом доказана равносильность выражений и. Ответ – 1. Логические переменные Значение функции Варианты ответа 1 2 3 4 A B  B 0 0 0 0 1 1 1 0 1 1 1 1 0 1 1 0 0 0 1 0 0 1 1 0 0 0 0 1 Логические переменные Значение функции Варианты ответа 1 2 3 4 A B 0 0 0 0 1 1 1 0 1 1 1 1 0 1 1 0 0 0 1 0 0 1 1 0 0 0 0 1 30

Изображение слайда
31

Слайд 31: Законы алгебры логики

название для И ( , ) для ИЛИ ( +, ) двойного отрицания исключения третьего операции с константами повторения поглощения переместительный сочетательный распределительный законы де Моргана Поглощения отрицания A ( +B)=AB A+( B )=A+B название для И ( , ) для ИЛИ ( +, ) двойного отрицания исключения третьего операции с константами повторения поглощения переместительный сочетательный распределительный законы де Моргана Поглощения отрицания 31

Изображение слайда
32

Слайд 32: Определение равносильности логических выражений приведением одного логического выражения к другому на основе доказанных законов алгебры логики

Пример 2. Какое логическое выражение равносильно выражению ? Решение Ответ: 32

Изображение слайда
33

Слайд 33: Определение равносильности двух логических выражений приведением обоих выражений к одному выражению

Являются ли равносильными логические выражения A  и Z=  ? Решение F= A  = A =A ; Z=  =A = A. 33

Изображение слайда
34

Слайд 34: Задача 1

Для таблицы истинности функции F известны значения нескольких ячеек: 34 x 1 x 2 x 3 x 4 F 1 0 1 0 1 1 1 0 0 0 1 0 Каким выражением может быть F?  

Изображение слайда
35

Слайд 35: Решение

Смысл решения – по очереди «примерять» каждый из предложенных вариантов ответа к таблице истинности и смотреть: если при указанных в ней значениях переменных хоть в какой-нибудь строке не получается требуемое значение F, то данное значение не подходит. Если же для всех строк таблицы истинности и всех имеющихся в ней значений переменных требуемое значение F получается, то мы считаем, что такое логическое выражение может соответствовать этой таблице и, соответственно является решением задачи. 35

Изображение слайда
36

Слайд 36: Решение

Чтобы ускорить решение, вспомним: для логической операции И «критическим» значением является нуль: если хотя бы одна переменная равна нулю, то и все выражение равно нулю. Аналогично, для логической операции ИЛИ «критическим» значением является единица: если хотя бы одна переменная равна единице, то и все выражение тоже равно единице. Разумеется, нужно не забывать заменять нуль на единицу и единицу на нуль при отрицании. 36

Изображение слайда
37

Слайд 37: Решение

Поэтому достаточно при проверке вариантов ответа проверять только часть строк таблицы истинности: - если логическое выражение составлено из операций И, то прежде всего проверим строки таблицы истинности, в которых F=1 : если хотя бы в одной ячейке, соответствующей «обычной» переменной, записан 0, а в ячейке, соответствующей переменной с НЕ, записана 1, то такой вариант ответа можно отбросить сразу; 37

Изображение слайда
38

Слайд 38: Решение

- если логическое выражение составлено из операций ИЛИ, то прежде всего проверим строки таблицы истинности, в которых F= 0: если хотя бы в одной ячейке, соответствующей «обычной» переменной, записана 1, а в ячейке, соответствующей переменной с НЕ, записан 0, то такой вариант ответа можно отбросить сразу. 38

Изображение слайда
39

Слайд 39: Решение

39 Выражение Операция Проверяемые строки таблицы Комментарий  И F=1 =0 ( строка 1)  ИЛИ F=0 =1 (строка 3) И F=1 Все соответствует ИЛИ F=0 =1 (строка 4) Выражение Операция Проверяемые строки таблицы Комментарий И F=1 ИЛИ F=0 И F=1 Все соответствует ИЛИ F=0 x 1 x 2 x 3 x 4 F 1 0 1 0 1 1 1 0 0 0 1 0

Изображение слайда
40

Слайд 40: Задача 2

Логическая функция задана выражением (  a  b  c  a  c . Имеется также фрагмент таблицы истинности этой логической функции, где показаны все возможные наборы значений переменных, при которых функция истинна. Требуется определить какие переменные соответствуют каждому столбцу таблицы истинности. Для этого в качестве ответа надо записать подряд без пробелов и разделителей буквы a, b, c по порядку их записи в столбцах таблицы слева направо. Например, так: « abc ». 40 ??? ??? ??? 0 0 0 1 1 0 0 1 1 1 0 1

Изображение слайда
41

Слайд 41: Решение

Построим полную таблицу истинности заданного выражения: 41 a b c (  a  b  c   a  c  Результат 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0 0 1 1 0 1 1 1 0 1 1 0 0 0 0 0 1 0 1 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 b c a 0 0 0 1 1 0 0 1 1 1 0 1

Изображение слайда
42

Слайд 42: Домашнее задание

Логическая функция задана выражением ( x  y  z  y   z. Определите какому столбцу таблицы истинности функции F соответствует каждая переменная. В ответе напишите названия переменных в том порядке, в котором идут соответствующие столбцы. 42 ? ? ? F 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1

Изображение слайда
43

Слайд 43: Задачи для Самостоятельного решения

1. Составьте таблицы истинности для логического выражения: 1) 2) ; 3) ; 4) ; 5) ; 6) A B ; 7) ; 8) A C. 2. Какое логическое выражение равносильно выражению ? 1) ; 2) ; 3) ; 4) 43 ? ? ? F 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1

Изображение слайда
44

Слайд 44: Логические операции импликация, эквиваленция, исключающее ИЛИ

Изображение слайда
45

Слайд 45: Логическая операция импликация

Логическая операция импликация А В имеет следующую таблицу истинности: A B А  B 0 0 0 1 1 0 1 1 1 1 1 0

Изображение слайда
46

Слайд 46: Логическая операция импликация

Логическую переменную А принято называть посылкой, а логическую переменную В – следствием. A B А  B 0 0 0 1 1 0 1 1 1 1 1 0

Изображение слайда
47

Слайд 47: Логическая операция импликация

Из таблицы истинности видно, что операция «импликация» ложна в единственном случае: если посылка истина, а следствие – ложно. A B А  B 0 0 0 1 1 0 1 1 1 1 1 0

Изображение слайда
48

Слайд 48: Пример импликации

Рассмотрим высказывание «Если идет дождь, то на улице сыро». «Идет дождь» - посылка, «на улице сыро» - следствие.

Изображение слайда
49

Слайд 49: Пример импликации

Если не идет дождь и не сыро на улице, то результат импликации – истина. A B А  B 0 0 1 0 1 1 1 0 0 1 1 1

Изображение слайда
50

Слайд 50: Пример импликации

Если идет дождь и на улице сыро, то операция импликации – истина. A B А  B 0 0 1 0 1 1 1 0 0 1 1 1

Изображение слайда
51

Слайд 51: Пример импликации

На улице может быть сыро без дождя, например когда прошла поливальная машина или дождь прошел накануне, результат импликации – истина A B А  B 0 0 1 0 1 1 1 0 0 1 1 1

Изображение слайда
52

Слайд 52: Пример импликации

Результат операции ложен лишь тогда, когда дождь идет, а на улице не сыро. A B А  B 0 0 1 0 1 1 1 0 0 1 1 1

Изображение слайда
53

Слайд 53: Операция импликации через основные логические выражения

А В = Так как их таблицы истинности совпадают для всех значений логических переменных А и В A B А В 0 0 1 1 1 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 A B А В 0 0 1 1 1 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1

Изображение слайда
54

Слайд 54: Операция эквиваленция

Операция эквиваленция А В (АВ, АВ, АВ) имеет следующую таблицу истинности A B А  B 0 0 1 0 1 0 1 0 0 1 1 1

Изображение слайда
55

Слайд 55: Операция эквиваленция

Логическое выражение А В истинно тогда, когда значения логических переменных А и В совпадают. A B А  B 0 0 1 0 1 0 1 0 0 1 1 1

Изображение слайда
56

Слайд 56: Примеры истинных высказываний, построенных с использованием операции эквивалентности

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

Изображение слайда
57

Слайд 57: Операция эквиваленции через основные логические операции

Операцию эквиваленции можно заменить выражением, состоящим из комбинации основных логических операций – дизъюнкции, конъюнкции и инверсии А  В=(  А B )  (А B )= (  А B )  (А B ) так каких таблицы истинности совпадают для всех значений логических переменных А и В

Изображение слайда
58

Слайд 58: Операция исключающее ИЛИ

Операция исключающее ИЛИ А XOR B ( A B ) имеет следующую таблицу истинности A B А  B 0 0 также: A xor B ( Паскаль ), A ^ B ( Си) 0 0 0 1 1 0 1 1 1 1

Изображение слайда
59

Слайд 59: Операция исключающее ИЛИ

Логическая операция исключающее ИЛИ истинно только тогда, когда значения логических переменных А и В различны A B А  B 0 0 0 0 0 1 1 0 1 1 1 1

Изображение слайда
60

Слайд 60: Операция исключающее ИЛИ

Операцию исключающее ИЛИ называют также суммой по модулю 2, так как по таблице истинности видно, что функция выполняет операцию суммирования аргументов без формирования переноса, если аргументы рассматриваются как двоичные числа. сложение по модулю 2: А  B = ( A + B) mod 2 арифметическое сложение, 1+1=2 остаток

Изображение слайда
61

Слайд 61: Операция исключающее ИЛИ через основные логические операции

Операцию исключающее ИЛИ можно заменить выражением, состоящим из комбинации основных логических операций - дизъюнкции, конъюнкции и инверсии: А XOR В=(  А B )  (А B )= (  А B )  (А B )

Изображение слайда
62

Слайд 62: Операция исключающее ИЛИ через основные логические операции

А XOR В=( B )  (А  )= (  )  (А B ) так как их таблицы истинности совпадают для всех значений логических переменных А и В A B А XOR В ( B )  (А  ) (  )  (А B ) 0 0 0 0 0 0 1 1 1 1 1 0 1 1 1 1 1 0 0 0 A B А XOR В 0 0 0 0 0 0 1 1 1 1 1 0 1 1 1 1 1 0 0 0

Изображение слайда
63

Последний слайд презентации: Логика и алгебра логики: Взаимосвязь операций исключающего ИЛИ и эквивалентности

Операция исключающее ИЛИ является отрицанием эквивалентности А XOR В= A B А XOR В А XOR В= 0 0 0 0 0 1 1 1 1 0 1 1 1 1 0 0 A B А XOR В 0 0 0 0 0 1 1 1 1 0 1 1 1 1 0 0

Изображение слайда