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

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

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

2. Логика, высказывания

Логические основы компьютеров, 10 класс
2
Логика, высказывания
Логика (др.греч. λογικος) – это наука о том, как
правильно рассуждать, делать выводы,
доказывать утверждения.
Формальная логика отвлекается от
конкретного содержания, изучает только
истинность и ложность высказываний.
Аристотель
(384-322 до н.э.)
Логическое высказывание – это
повествовательное предложение, относительно
которого можно однозначно сказать, истинно оно
или ложно.

3. Высказывание или нет?

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

4. Логика и компьютер

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

5. Обозначение высказываний

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

6. Операция НЕ (инверсия)

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

7. Операция И

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

8. Операция И (логическое умножение, конъюнкция)

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

9. Операция ИЛИ (логическое сложение, дизъюнкция)

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

10. Операция ИЛИ (логическое сложение, дизъюнкция)

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

11. Операция «исключающее ИЛИ»

Логические основы компьютеров, 10 класс
11
Операция «исключающее ИЛИ»
Высказывание «A B» истинно тогда, когда истинно А
или B, но не оба одновременно (то есть A B).
«Либо пан, либо пропал».
A
B
А B
0
0
1
1
0
1
0
1
0
1
1
0
также:
A xor B (Паскаль),
A ^ B (Си)
арифметическое
сложение, 1+1=2
остаток
сложение по модулю 2: А B = (A + B) mod 2

12. Импликация («если …, то …»)

Логические основы компьютеров, 10 класс
12
Импликация («если …, то …»)
Высказывание «A B» истинно, если не
исключено, что из А следует B.
A – «Работник хорошо работает».
B – «У работника хорошая зарплата».
A
0
0
1
1
B
0
1
0
1
А B
1
1
0
1
A B A B

13. Эквивалентность («тогда и только тогда, …»)

Логические основы компьютеров, 10 класс
13
Эквивалентность («тогда и только тогда, …»)
Высказывание «A B» истинно тогда и только
тогда, когда А и B равны.
A
0
0
1
1
B
0
1
0
1
А B
1
0
0
1
A B A B A B A B

14. Базовый набор операций

Логические основы компьютеров, 10 класс
14
Базовый набор операций
С помощью операций И, ИЛИ и НЕ можно
реализовать любую логическую операцию.
И
ИЛИ
НЕ
базовый набор операций
? Сколько всего существует логических операций
с двумя переменными?

15. Диаграммы Венна (круги Эйлера)

Логические основы компьютеров, 10 класс
15
Диаграммы Венна (круги Эйлера)
A
A
A
B
B
A·B
A
A+B
A
A
A
B
B
A B
A B
B
A B

16. Диаграмма с тремя переменными

Логические основы компьютеров, 10 класс
16
Диаграмма с тремя переменными
Хочу
Могу
3
2
1
5
6
4
7
8
1 M X H
5 M X H
2 M X H
6 M X H
3 M X H
7 M X H
4 M X H
8 M X H
Надо
3 4 M X H M X H
3 4 X H
! Логические выражения можно упрощать!

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

Логические основы компьютеров, 10 класс
17
Логические элементы компьютера
значок инверсии
A
A
A
&
A
A B
B
НЕ
B
И
A
&
B
A B
ИЛИ
A
1
B
И-НЕ
1
ИЛИ-НЕ
A B
A B

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

Логические основы компьютеров, 10 класс
18
Логические элементы компьютера
Любое логическое выражение можно реализовать на
элементах И-НЕ или ИЛИ-НЕ.
И: A B A B
НЕ: A A A A A
A
&
ИЛИ:
A
A
B
A
&
& A B
A
A B A B
&
B
&
&
B
A B
A B

19. Составление схем

Логические основы компьютеров, 10 класс
19
Составление схем
последняя операция - ИЛИ
X A B A B C
И
A
B
C
A
B
&
A
B
& A B
A B
A B C
C
&
1
X

20. Триггер (англ. trigger – защёлка)

Логические основы компьютеров, 10 класс
20
Триггер (англ. trigger – защёлка)
Триггер – это логическая схема, способная хранить
1 бит информации (1 или 0). Строится на 2-х
элементах ИЛИ-НЕ или на 2-х элементах И-НЕ.
set, установка
S
1
1
R
reset, сброс
вспомогательный
выход
Q
S R Q Q
режим
0 0 Q Q
хранение
обратные связи
0 1
0
1
сброс
Q
1 0
1 1
1
0
0
0
установка 1
основной
выход
запрещен

21. Триггер – таблица истинности

Логические основы компьютеров, 10 класс
21
Триггер – таблица истинности
S
1
0
Q
0
Q
R
0
1
1
1
Q
0
Q
0
Q
S R Q Q
режим
0 0 Q Q
хранение
обратные связи
0 1 0
1
сброс
Q
1 0 1
1 1 0
0
0
установка 1
1
запрещен

22. Полусумматор

Логические основы компьютеров, 10 класс
22
Полусумматор
Полусумматор – это логическая схема, способная
складывать два одноразрядных двоичных числа.
A
S сумма
A B
P
S
Σ
B
P перенос
P A B
S A B A B A B
A
B
A
B
& A B
& A B
& A B
1
0
0
0
0
0
1
0
1
1
0
0
1
1
1
1
0
S A B A B
P
на 4-х
? Схема
элементах?

23. Сумматор

Логические основы компьютеров, 10 класс
23
Сумматор
Сумматор – это логическая схема, способная
складывать два одноразрядных двоичных числа с
переносом из предыдущего разряда.
A
B
перенос C
Σ
A
B
C
P
S
0
0
0
0
0
S сумма
0
0
1
0
1
P перенос
0
1
0
0
1
0
1
1
1
0
1
0
0
0
1
1
0
1
1
0
1
1
0
1
0
1
1
1
1
1

24. Многоразрядный сумматор

Логические основы компьютеров, 10 класс
24
Многоразрядный сумматор
это логическая схема, способная складывать два
n-разрядных двоичных числа.
A
an-1 an-2 a0
B
bn-1 bn-2 b0
C p cn-1 cn-2 c0
перенос
a0
b0
0
c0
Σ
p1
a1
b1
Σ
c1
p2
an-1
Σ
bn-1
pn-1
cn-1
p
перенос

25. Метод рассуждений

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

26. Табличный метод

Логические основы компьютеров, 10 класс
26
Табличный метод
Задача 2. Дочерей Василия Лоханкина зовут Даша, Анфиса и Лариса. У
них разные профессии и они живут в разных городах: одна в Ростове,
вторая – в Париже и третья – в Москве. Известно, что
• Даша живет не в Париже, а Лариса – не в Ростове,
• парижанка – не актриса,
• Много вариантов.
• в Ростове живет певица,
• Есть точные данные.
• Лариса – не балерина.
Париж
Ростов
Москва
0
1
0
1
0
0
0
0
1
Певица
Балерина
Актриса
1
0
0
0
1
0
0
0
1
Даша
Анфиса
Лариса
! В каждой строке и в каждом столбце может
быть только одна единица!

27. Задача Эйнштейна

Логические основы компьютеров, 10 класс
Задача Эйнштейна
Условие: Есть 5 домов разного цвета, стоящие в ряд. В каждом доме живет по одному
человеку отличной от другого национальности. Каждый жилец пьет только один
определенный напиток, курит определенную марку сигарет и держит животное.
Никто из пяти человек не пьет одинаковые напитки, не курит одинаковые сигареты
и не держит одинаковых животных.
Известно, что:
1. Англичанин живет в красном доме.
2. Швед держит собаку.
3. Датчанин пьет чай.
4. Зеленой дом стоит слева от белого.
5. Жилец зеленого дома пьет кофе.
6. Человек, который курит Pallmall, держит птицу.
7. Жилец среднего дома пьет молоко.
8. Жилец из желтого дома курит Dunhill.
9. Норвежец живет в первом доме.
10. Курильщик Marlboro живет около того, кто держит кошку.
11. Человек, который содержит лошадь, живет около того, кто курит Dunhill.
12. Курильщик Winfield пьет пиво.
13. Норвежец живет около голубого дома.
14. Немец курит Rothmans.
15. Курильщик Marlboro живет по соседству с человеком, который пьет воду.
Вопрос: У кого живет рыба?
27