Логические основы компьютеров

Сентябрь 2, 2022

Главная
Алгебра
Логические основы компьютеров

Содержание

2. Булева алгебра Двоичное кодирование – все виды информации кодируются с помощью 0 и 1. Задача –
3. Логические высказывания Логическое высказывание – это повествовательное предложение, относительно которого можно однозначно сказать, истинно оно или
4. Обозначение высказываний A – Сейчас идет дождь. B – Форточка открыта. простые высказывания (элементарные) Составные высказывания
5. Операция НЕ (инверсия) Если высказывание A истинно, то "не А" ложно, и наоборот. 1 0 0
6. Операция И (логическое умножение, конъюнкция) 1 0 также: A·B, A ∧ B, A and B (Паскаль),
7. Операция ИЛИ (логическое сложение, дизъюнкция) 1 0 также: A+B, A ∨ B, A or B (Паскаль),
8. Операция "исключающее ИЛИ" Высказывание "A ⊕ B" истинно тогда, когда истинно А или B, но не
9. A ⊕ A = (A ⊕ B) ⊕ B = Свойства операции "исключающее ИЛИ" A ⊕
10. Импликация ("если …, то …") Высказывание "A → B" истинно, если не исключено, что из А
11. Эквиваленция ("тогда и только тогда, …") Высказывание "A ↔ B" истинно тогда, когда А и B
12. Базовый набор операций С помощью операций И, ИЛИ и НЕ можно реализовать любую логическую операцию.
13. Логические формулы Система имеет три датчика и может работать, если два из них исправны. A –
14. Составление таблиц истинности Логические выражения могут быть: тождественно истинными (всегда 1, тавтология) тождественно ложными (всегда 0,
15. Составление таблиц истинности
16. Логические основы компьютеров Диаграммы
17. Диаграммы Вена (круги Эйлера) A·B A+B A⊕B A→B A↔B
18. Диаграмма МХН (Е.М. Федосеев) Хочу Могу Надо 1 2 3 4 5 6 7 8
19. Логические основы компьютеров Преобразование логических выражений
20. Законы алгебры логики
21. Упрощение логических выражений Шаг 1. Заменить операции ⊕→↔ на их выражения через И, ИЛИ и НЕ:
22. Упрощение логических выражений раскрыли → формула де Моргана распределительный исключения третьего повторения поглощения
23. Логические уравнения A=0, B=1, C – любое 2 решения: (0, 1, 0), (0, 1, 1) или
24. Логические основы компьютеров Синтез логических выражений
25. Синтез логических выражений Шаг 1. Отметить строки в таблице, где X = 1. Шаг 2. Для
26. Синтез логических выражений (2 способ) Шаг 1. Отметить строки в таблице, где X = 0. Шаг
27. Синтез логических выражений
28. Синтез логических выражений (2 способ)
29. Логические основы компьютеров Логические элементы компьютера
30. Логические элементы компьютера НЕ И ИЛИ ИЛИ-НЕ И-НЕ значок инверсии
31. Логические элементы компьютера Любое логическое выражение можно реализовать на элементах И-НЕ или ИЛИ-НЕ. И: НЕ: ИЛИ:
32. Составление схем последняя операция - ИЛИ & И
33. Триггер (англ. trigger – защёлка) Триггер – это логическая схема, способная хранить 1 бит информации (1
34. Полусумматор Полусумматор – это логическая схема, способная складывать два одноразрядных двоичных числа. 0 0 0 1
35. Сумматор Сумматор – это логическая схема, способная складывать два одноразрядных двоичных числа с переносом из предыдущего
36. Многоразрядный сумматор это логическая схема, способная складывать два n-разрядных двоичных числа. перенос перенос
37. Логические основы компьютеров Логические задачи
38. Метод рассуждений Задача 1. Министры иностранных дел России, США и Китая обсудили за закрытыми дверями проекты
39. Табличный метод Задача 2. Дочерей Василия Лоханкина зовут Даша, Анфиса и Лариса. У них разные профессии
40. Задача Эйнштейна Условие: Есть 5 домов разного цвета, стоящие в ряд. В каждом доме живет по
41. Использование алгебры логики Задача 3. Следующие два высказывания истинны: 1. Неверно, что если корабль A вышел
43. Скачать презентацию

Слайд 2

Булева алгебра
Двоичное кодирование – все виды информации кодируются с помощью 0

и 1.
Задача – разработать оптимальные правила обработки таких данных.
Джордж Буль разработал основы алгебры, в которой используются только 0 и 1 (алгебра логики, булева алгебра).
Почему "логика"? Результат выполнения операции можно представить как истинность (1) или ложность (0) некоторого высказывания.

Слайд 3

Логические высказывания
Логическое высказывание – это повествовательное предложение, относительно которого можно однозначно

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

Слайд 4

Обозначение высказываний
A – Сейчас идет дождь.
B – Форточка открыта.
простые высказывания (элементарные)
Составные

высказывания строятся из простых с помощью логических связок (операций) "и", "или", "не", "если … то", "тогда и только тогда" и др.

A и B
A или не B
если A, то B
не A и B
A тогда и только
тогда, когда B

Сейчас идет дождь и открыта форточка.
Сейчас идет дождь или форточка закрыта.
Если сейчас идет дождь, то форточка открыта.
Сейчас нет дождя и форточка открыта.
Дождь идет тогда и только тогда, когда открыта форточка.

Слайд 5

Операция НЕ (инверсия)
Если высказывание A истинно, то "не А" ложно, и

наоборот.

таблица истинности операции НЕ

также: , not A (Паскаль), ! A (Си)

Таблица истинности логического выражения Х – это таблица, где в левой части записываются все возможные комбинации значений исходных данных, а в правой – значение выражения Х для каждой комбинации.

Слайд 6

Операция И (логическое умножение, конъюнкция)
1
0
также: A·B, A ∧ B, A and B

(Паскаль), A && B (Си)

конъюнкция – от лат. conjunctio — соединение

A ∧ B

Высказывание "A и B" истинно тогда и только тогда, когда А и B истинны одновременно.

Слайд 7

Операция ИЛИ (логическое сложение, дизъюнкция)
1
0
также: A+B, A ∨ B, A or B

(Паскаль), A || B (Си)

дизъюнкция – от лат. disjunctio — разъединение

Высказывание "A или B" истинно тогда, когда истинно А или B, или оба вместе.

Слайд 8

Операция "исключающее ИЛИ"
Высказывание "A ⊕ B" истинно тогда, когда истинно А

или B, но не оба одновременно.

также: A xor B (Паскаль), A ^ B (Си)

сложение по модулю 2: А ⊕ B = (A + B) mod 2

арифметическое сложение, 1+1=2

остаток

Слайд 9

A ⊕ A =
(A ⊕ B) ⊕ B =
Свойства операции "исключающее

ИЛИ"

A ⊕ 0 =
A ⊕ 1 =

Слайд 10

Импликация ("если …, то …")
Высказывание "A → B" истинно, если не

исключено, что из А следует B.
A – "Работник хорошо работает".
B – "У работника хорошая зарплата".

Слайд 11

Эквиваленция ("тогда и только тогда, …")
Высказывание "A ↔ B" истинно тогда,

когда А и B равны.

Слайд 12

Базовый набор операций
С помощью операций И, ИЛИ и НЕ можно реализовать

любую логическую операцию.

Слайд 13

Логические формулы
Система имеет три датчика и может работать, если два из

них исправны.
A – "Датчик № 1 неисправен".
B – "Датчик № 2 неисправен".
C – "Датчик № 3 неисправен".
Аварийный сигнал:
X – "Неисправны два датчика".

X – "Неисправны датчики № 1 и № 2" или
"Неисправны датчики № 1 и № 3" или
"Неисправны датчики № 2 и № 3".

логическая формула

Слайд 14

Составление таблиц истинности
Логические выражения могут быть:
тождественно истинными (всегда 1, тавтология)
тождественно ложными

(всегда 0, противоречие)
вычислимыми (зависят от исходных данных)

Слайд 15

Составление таблиц истинности

Слайд 16

Логические основы компьютеров
Диаграммы

Слайд 17

Диаграммы Вена (круги Эйлера)
A·B
A+B
A⊕B
A→B
A↔B

Слайд 18

Диаграмма МХН (Е.М. Федосеев)
Хочу
Могу
Надо
1
2
3
4
5
6
7
8

Слайд 19

Логические основы компьютеров
Преобразование логических выражений

Слайд 20

Законы алгебры логики

Слайд 21

Упрощение логических выражений
Шаг 1. Заменить операции ⊕→↔ на их выражения через

И, ИЛИ и НЕ:
Шаг 2. Раскрыть инверсию сложных выражений по формулам де Моргана:
Шаг 3. Используя законы логики, упрощать выражение, стараясь применять закон исключения третьего.

Слайд 22

Упрощение логических выражений
раскрыли →
формула де Моргана
распределительный
исключения третьего
повторения
поглощения

Слайд 23

Логические уравнения
A=0, B=1, C – любое
2 решения: (0, 1, 0), (0,

1, 1)

или

A=1, B=0, C=1

K=1, L=1,
M и N – любые
4 решения

M=1, L=1, N=1,
K – любое
2 решения

K=1, L=1, M=0,
N – любое
2 решения

Слайд 24

Логические основы компьютеров
Синтез логических выражений

Слайд 25

Синтез логических выражений
Шаг 1. Отметить строки в таблице, где X =

1.
Шаг 2. Для каждой из них записать логическое выражение, которое истинно только для этой строки.
Шаг 3. Сложить эти выражения и упростить результат.

распределительный

исключения третьего

распределительный

Слайд 26

Синтез логических выражений (2 способ)
Шаг 1. Отметить строки в таблице, где

X = 0.
Шаг 2. Для каждой из них записать логическое выражение, которое истинно только для этой строки.
Шаг 3. Сложить эти выражения и упростить результат, который равен .
Шаг 4. Сделать инверсию.

Слайд 27

Синтез логических выражений

Слайд 28

Синтез логических выражений (2 способ)

Слайд 29

Логические основы компьютеров
Логические элементы компьютера

Слайд 30

Логические элементы компьютера
НЕ
И
ИЛИ
ИЛИ-НЕ
И-НЕ
значок инверсии

Слайд 31

Логические элементы компьютера
Любое логическое выражение можно реализовать на элементах И-НЕ или

ИЛИ-НЕ.

И:

НЕ:

ИЛИ:

Слайд 32

Составление схем
последняя операция - ИЛИ
&
И

Слайд 33

Триггер (англ. trigger – защёлка)
Триггер – это логическая схема, способная хранить

1 бит информации (1 или 0). Строится на 2-х элементах ИЛИ-НЕ или на 2-х элементах И-НЕ.

основной
выход

вспомогательный
выход

reset, сброс

set, установка

обратные связи

Слайд 34

Полусумматор
Полусумматор – это логическая схема, способная складывать два одноразрядных двоичных числа.
0

0 1

1 0

Слайд 35

Сумматор
Сумматор – это логическая схема, способная складывать два одноразрядных двоичных числа

с переносом из предыдущего разряда.

сумма

перенос

Слайд 36

Многоразрядный сумматор
это логическая схема, способная складывать два n-разрядных двоичных числа.
перенос
перенос

Слайд 37

Логические основы компьютеров
Логические задачи

Слайд 38

Метод рассуждений
Задача 1. Министры иностранных дел России, США и Китая обсудили

за закрытыми дверями проекты договора, представленные каждой из стран. Отвечая затем на вопрос журналистов: "Чей именно проект был принят?", министры дали такие ответы:
Россия — "Проект не наш (1), проект не США (2)";
США — "Проект не России (1), проект Китая (2)";
Китай — "Проект не наш (1), проект России (2)".
Один из них оба раза говорил правду; второй – оба раза говорил неправду, третий один раз сказал правду, а другой раз — неправду. Кто что сказал?

проект России (?)

–

проект США (?)

–

проект Китая (?)

–

Слайд 39

Табличный метод
Задача 2. Дочерей Василия Лоханкина зовут Даша, Анфиса и Лариса.

У них разные профессии и они живут в разных городах: одна в Ростове, вторая – в Париже и третья – в Москве. Известно, что
Даша живет не в Париже, а Лариса – не в Ростове,
парижанка – не актриса,
в Ростове живет певица,
Лариса – не балерина.

Много вариантов.
Есть точные данные.

Слайд 40

Задача Эйнштейна
Условие: Есть 5 домов разного цвета, стоящие в ряд. В

каждом доме живет по одному человеку отличной от другого национальности. Каждый жилец пьет только один определенный напиток, курит определенную марку сигарет и держит животное. Никто из пяти человек не пьет одинаковые напитки, не курит одинаковые сигареты и не держит одинаковых животных.
Известно, что:
Англичанин живет в красном доме.
Швед держит собаку.
Датчанин пьет чай.
Зеленой дом стоит слева от белого.
Жилец зеленого дома пьет кофе.
Человек, который курит Pallmall, держит птицу.
Жилец среднего дома пьет молоко.
Жилец из желтого дома курит Dunhill.
Норвежец живет в первом доме.
Курильщик Marlboro живет около того, кто держит кошку.
Человек, который содержит лошадь, живет около того, кто курит Dunhill.
Курильщик Winfield пьет пиво.
Норвежец живет около голубого дома.
Немец курит Rothmans.
Курильщик Marlboro живет по соседству с человеком, который пьет воду.
Вопрос: У кого живет рыба?

Слайд 41

Использование алгебры логики
Задача 3. Следующие два высказывания истинны:
1. Неверно, что если

корабль A вышел в море, то корабль C – нет.
2. В море вышел корабль B или корабль C, но не оба вместе.
Определить, какие корабли вышли в море.

… если корабль A вышел в море, то корабль C – нет.

1. Неверно, что если корабль A вышел в море, то корабль C – нет.

2. В море вышел корабль B или корабль C, но не оба вместе.

Решение:

Логические основы компьютеров

Содержание

Булева алгебраДвоичное кодирование – все виды информации кодируются с помощью 0

Логические высказыванияЛогическое высказывание – это повествовательное предложение, относительно которого можно однозначно

Обозначение высказыванийA – Сейчас идет дождь.B – Форточка открыта.простые высказывания (элементарные)Составные

Операция НЕ (инверсия)Если высказывание A истинно, то "не А" ложно, и

Операция И (логическое умножение, конъюнкция)10также: A·B, A ∧ B, A and B

Операция ИЛИ (логическое сложение, дизъюнкция)10также: A+B, A ∨ B, A or B

Операция "исключающее ИЛИ"Высказывание "A ⊕ B" истинно тогда, когда истинно А

A ⊕ A =(A ⊕ B) ⊕ B =Свойства операции "исключающее

Импликация ("если …, то …")Высказывание "A → B" истинно, если не

Эквиваленция ("тогда и только тогда, …")Высказывание "A ↔ B" истинно тогда,

Базовый набор операцийС помощью операций И, ИЛИ и НЕ можно реализовать

Логические формулыСистема имеет три датчика и может работать, если два из

Составление таблиц истинностиЛогические выражения могут быть:тождественно истинными (всегда 1, тавтология)тождественно ложными

Составление таблиц истинности

Логические основы компьютеров Диаграммы

Диаграммы Вена (круги Эйлера)A·BA+BA⊕BA→BA↔B

Диаграмма МХН (Е.М. Федосеев)ХочуМогуНадо12345678

Логические основы компьютеров Преобразование логических выражений

Законы алгебры логики

Упрощение логических выраженийШаг 1. Заменить операции ⊕→↔ на их выражения через

Упрощение логических выраженийраскрыли →формула де Морганараспределительныйисключения третьегоповторенияпоглощения

Логические уравненияA=0, B=1, C – любое2 решения: (0, 1, 0), (0,

Логические основы компьютеров Синтез логических выражений

Синтез логических выраженийШаг 1. Отметить строки в таблице, где X =

Синтез логических выражений (2 способ)Шаг 1. Отметить строки в таблице, где