Похожие презентации:
Логика_Поляков
1. Логические основы компьютеров
1Логические основы
компьютеров
3.1 Логика и компьютер
3.2 Логические операции
3.3 Диаграммы
3.4 Упрощение логических выражений
3.5 Синтез логических выражений
3.6 Предикаты и кванторы
3.7 Логические элементы компьютера
3.8 Логические задачи
Задачи ЕГЭ
2. Логические основы компьютеров
2Логические
основы
компьютеров
3.1 Логика и компьютер
3. Логика, высказывания
Логические основы компьютеров3
Логика, высказывания
Логика (др.греч. λογικος) – это наука о том, как
правильно рассуждать, делать выводы,
доказывать утверждения.
Формальная логика отвлекается от
конкретного содержания, изучает только
истинность и ложность высказываний.
Аристотель
(384-322 до н.э.)
Логическое высказывание – это
повествовательное предложение, относительно
которого можно однозначно сказать, истинно оно
или ложно.
4. Высказывание или нет?
Логические основы компьютеровВысказывание или нет?
Сейчас идет дождь.
Жирафы летят на север.
История – интересный предмет.
У квадрата – 10 сторон и все разные.
Красиво!
В городе N живут 2 миллиона человек.
Который час?
4
5. Логика и компьютер
Логические основы компьютеровЛогика и компьютер
Двоичное кодирование – все виды информации
кодируются с помощью 0 и 1.
Задача – разработать оптимальные правила
обработки таких данных.
Почему «логика»?
Результат выполнения операции можно
представить как истинность (1) или ложность (0)
некоторого высказывания.
Джордж Буль разработал основы алгебры,
в которой используются только 0 и 1
(алгебра логики, булева алгебра).
5
6. Логические основы компьютеров
6Логические
основы
компьютеров
3.2 Логические операции
7. Обозначение высказываний
Логические основы компьютеров7
Обозначение высказываний
A – Сейчас идет дождь.
B – Форточка открыта.
}
простые высказывания
(элементарные)
! Любое высказывание может быть ложно (0)
или истинно (1).
Составные высказывания строятся из простых с
помощью логических связок (операций) «и», «или»,
«не», «если … то», «тогда и только тогда» и др.
AиB
Сейчас идет дождь и открыта форточка.
A или не B
Сейчас идет дождь или форточка закрыта.
если A, то B
Если сейчас идет дождь, то форточка открыта.
A тогда и только
тогда, когда B
Дождь идет тогда и только тогда, когда открыта
форточка.
8. Операция НЕ (инверсия)
Логические основы компьютеров8
Операция НЕ (инверсия)
Если высказывание A истинно, то «не А» ложно, и
наоборот.
также A , A ,
А
не А
0
1
1
0
not A (Паскаль),
! A (Си)
таблица
истинности
операции НЕ
Таблица истинности логического выражения Х – это
таблица, где в левой части записываются все
возможные комбинации значений исходных данных,
а в правой – значение выражения Х для каждой
комбинации.
9. Операция И
Логические основы компьютеров9
Операция И
Высказывание «A и B» истинно тогда и только тогда,
когда А и B истинны одновременно.
AиB
A
B
220 В
10. Операция И (логическое умножение, конъюнкция)
Логические основы компьютеров10
Операция И (логическое умножение, конъюнкция)
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 — соединение
11. Операция ИЛИ (логическое сложение, дизъюнкция)
Логические основы компьютеров11
Операция ИЛИ (логическое сложение, дизъюнкция)
Высказывание «A или B» истинно тогда, когда
истинно А или B, или оба вместе.
A или B
A
B
220 В
12. Операция ИЛИ (логическое сложение, дизъюнкция)
Логические основы компьютеров12
Операция ИЛИ (логическое сложение, дизъюнкция)
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 — разъединение
13. Задачи
Логические основы компьютеровЗадачи
В таблице приведены запросы к поисковому серверу.
Расположите номера запросов в порядке возрастания
количества страниц, которые найдет поисковый
сервер по каждому запросу. Для обозначения логической
операции «ИЛИ» в запросе используется символ |, а для
логической операции «И» – &.
1) принтеры & сканеры & продажа
2) принтеры & продажа
3) принтеры | продажа
4) принтеры | сканеры | продажа
1234
13
14. Операция «исключающее ИЛИ»
Логические основы компьютеров14
Операция «исключающее ИЛИ»
Высказывание «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
15. Свойства операции «исключающее ИЛИ»
Логические основы компьютеров15
Свойства операции «исключающее ИЛИ»
A A= 0
(A B) B = ?
A 0= A
A 1= A
A B A B A B
A
0
0
1
1
B
0
1
0
1
A B
A B A B A B А B
0
0
1
0
0
1
0
0
0
1
1
0
0
1
1
0
16. Импликация («если …, то …»)
Логические основы компьютеров16
Импликация («если …, то …»)
Высказывание «A B» истинно, если не
исключено, что из А следует B.
A – «Работник хорошо работает».
B – «У работника хорошая зарплата».
A
0
0
1
1
B
0
1
0
1
А B
1
1
0
1
A B A B
17. Импликация («если …, то …»)
Логические основы компьютеров17
Импликация («если …, то …»)
«Если Вася идет гулять, то Маша сидит дома».
A – «Вася идет гулять».
A
B
А
B
B – «Маша сидит дома».
A B 1
? А если Вася не идет
гулять?
Маша может пойти гулять
(B=0), а может и не пойти (B=1)!
0
0
1
1
0
1
0
1
1
1
0
1
18. Эквивалентность («тогда и только тогда, …»)
Логические основы компьютеров18
Эквивалентность («тогда и только тогда, …»)
Высказывание «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
19. Базовый набор операций
Логические основы компьютеров19
Базовый набор операций
С помощью операций И, ИЛИ и НЕ можно
реализовать любую логическую операцию.
И
ИЛИ
НЕ
базовый набор операций
? Сколько всего существует логических операции
с двумя переменными?
20. Штрих Шеффера, «И-НЕ»
Логические основы компьютеров20
Штрих Шеффера, «И-НЕ»
A | B A B
A
0
0
1
1
B
0
1
0
1
А|B
1
1
1
0
Базовые операции через «И-НЕ»:
A A|A
A B A | B (A | B) | (A | B)
A B A | B (A | A) | (B | B)
21. Стрелка Пирса, «ИЛИ-НЕ»
Логические основы компьютеров21
Стрелка Пирса, «ИЛИ-НЕ»
A B A B
A
0
0
1
1
B
0
1
0
1
Базовые операции через «ИЛИ-НЕ»:
! Самостоятельно…
А↓B
1
0
0
0
22. Формализация
Логические основы компьютеров22
Формализация
Прибор имеет три датчика и может работать, если два из
них исправны. Записать в виде формулы ситуацию
«авария».
A – «Датчик № 1 неисправен».
B – «Датчик № 2 неисправен».
Формализация – это
переход к записи на
C – «Датчик № 3 неисправен».
формальном языке!
Аварийный сигнал:
X – «Неисправны два датчика».
X – «Неисправны датчики № 1 и № 2» или
«Неисправны датчики № 1 и № 3» или
«Неисправны датчики № 2 и № 3».
логическая
формула
X A B A C B C
!
23. Вычисление логических выражений
Логические основы компьютеров23
Вычисление логических выражений
1
4
2
5
3
X A B A C B C
+
Порядок вычислений:
•скобки
•НЕ
•И
•ИЛИ, исключающее ИЛИ
•импликация
•эквивалентность
+
A
B
A
B
С
C
24. Составление таблиц истинности
Логические основы компьютеров24
Составление таблиц истинности
X A B A B B
0
1
2
3
A
B
A·B
A B
B
X
0
0
1
1
0
1
0
1
0
0
0
1
0
1
0
0
1
0
1
0
1
1
1
1
Логические выражения могут быть:
• тождественно истинными (всегда 1, тавтология)
• тождественно ложными (всегда 0, противоречие)
• вычислимыми (зависят от исходных данных)
25. Составление таблиц истинности
Логические основы компьютеров25
Составление таблиц истинности
X A B A C B C
0
1
2
3
4
5
6
7
A
B
C
A∙B
A∙C
B∙C
X
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
0
0
0
0
0
1
1
0
0
0
0
0
1
0
1
0
0
0
1
0
0
0
1
0
0
0
1
0
1
1
1
26. Задачи (таблица истинности)
Логические основы компьютеров26
Задачи (таблица истинности)
Символом F обозначено одно из
указанных ниже логических выражений
от трех аргументов: X, Y, Z. Дан
фрагмент таблицы истинности
выражения F. Какое выражение
соответствует F?
1) X Y Z
1) ¬X ¬Y ¬Z
2) X Y Z
2) X Y Z
3) X Y Z
3) X Y Z
4) X Y Z
4) ¬X ¬Y ¬Z
X
1
0
1
Y
0
0
1
Z
0
0
1
F
1
1
0
27. Логические основы компьютеров
27Логические
основы
компьютеров
3.3 Диаграммы
28. Диаграммы Венна (круги Эйлера)
Логические основы компьютеров28
Диаграммы Венна (круги Эйлера)
A
A
A
B
B
A·B
A
A+B
A
A
A
B
B
A B
A B
B
A B
29. Диаграмма с тремя переменными
Логические основы компьютеров29
Диаграмма с тремя переменными
Хочу
Могу
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
! Логические выражения можно упрощать!
30. Задачи
Логические основы компьютеров30
Задачи
Известно количество сайтов, которых находит
поисковый сервер по следующим запросам :
Запрос
огурцы
помидоры
огурцы & помидоры
Количество сайтов
100
200
50
Сколько сайтов будет найдено по запросу
огурцы | помидоры
31. Задачи
Логические основы компьютеров31
Задачи
A
B
NA|B = NA+ NB
50
огурцы & помидоры
A
B
NA|B = NA+ NB – NA&B
огурцы | помидоры
огурцы
помидоры
250
100
200
32. Задачи
Логические основы компьютеров32
Задачи
Известно количество сайтов, которых находит
поисковый сервер по следующим запросам :
Запрос
Динамо & Рубин
Спартак & Рубин
(Динамо | Спартак) & Рубин
Количество
сайтов
320
280
430
Сколько сайтов будет найдено по запросу
Динамо & Спартак & Рубин
33. Задачи
Логические основы компьютеров33
Задачи
Спартак
Динамо
Спартак & Рубин
= 2 + 3 = 280
2
Динамо & Рубин
= 1 + 2 = 320
1
3
Рубин
(Динамо | Спартак) & Рубин
= 1 + 2 + 3 = 430
Динамо & Спартак & Рубин
= 2
= (320 + 280) – 430 = 170
34. Задачи
Логические основы компьютеров34
Задачи
Некоторый сегмент сети Интернет состоит из 1000
сайтов. Поисковый сервер в автоматическом режиме
составил таблицу ключевых слов для сайтов этого
сегмента. Вот ее фрагмент:
Ключевое слово
сканер
принтер
монитор
Количество сайтов, для которых
данное слово является ключевым
200
250
450
Сколько сайтов будет найдено по запросу
(принтер | сканер) & монитор
если по трем следующим запросам найдено:
принтер | сканер
– 450 сайтов,
принтер & монитор
– 40 сайтов
сканер & монитор
– 50 сайтов.
35. Задачи
Логические основы компьютеров35
Задачи
(принтер | сканер) & монитор = ?
А (сканер)
B (принтер)
450
принтер | сканер
0
NA|B = NA+ NB – NA&B
сканер
200
принтер
250
принтер
сканер
принтер & монитор = 40
50
40
сканер & монитор = 50
монитор
40 + 50 = 90
36. Сложная задача
Логические основы компьютеровСложная задача
Ниже приведены запросы и количество страниц, которые нашел
поисковый сервер по этим запросам в некотором сегменте
Интернета:
мезозой
500
кроманьонец
600
неандерталец
700
мезозой | кроманьонец
800
мезозой | неандерталец
1000
неандерталец & (мезозой | кроманьонец) 200
Сколько страниц будет найдено по запросу
кроманьонец & (мезозой | неандерталец)
36
37. Логические основы компьютеров
37Логические
основы
компьютеров
3.4 Упрощение логических
выражений
38. Законы алгебры логики
Логические основы компьютеров38
Законы алгебры логики
название
для И
для ИЛИ
A A
двойного отрицания
A A 0
A A 1
операции с
константами
A 0 0, A 1 A
A 0 A, A 1 1
повторения
A A A
A A A
поглощения
A ( A B) A
A A B A
переместительный
A B B A
A B B A
исключения третьего
сочетательный
A (B C) ( A B) C A (B C) ( A B) C
распределительный
A B C ( A B) ( A C)
A (B C) A B A C
законы де Моргана
A B A B
A B A B
39. Упрощение логических выражений
Логические основы компьютеров39
Упрощение логических выражений
Шаг 1. Заменить операции на их выражения
через И, ИЛИ и НЕ:
A B A B A B
A B A B
A B A B A B
Шаг 2. Раскрыть инверсию сложных выражений по
формулам де Моргана:
A B A B,
A B A B
Шаг 3. Используя законы логики, упрощать выражение,
стараясь применять закон исключения третьего.
40. Упрощение логических выражений
Логические основы компьютеров40
Упрощение логических выражений
Q M X H M X H (M M ) X H X H
X (B A) (A B) (A C)
( B A) (A B) (A C)
формула де Моргана
( B A) A B (A C)
( B A A A ) B (A C)
B A B (A C)
B A (A C)
B A
раскрыли
распределительный
исключения третьего
повторения
поглощения
41. Задачи (упрощение)
Логические основы компьютеровЗадачи (упрощение)
Какое логическое выражение равносильно выражению
A ¬(¬B C)?
1) ¬A ¬B ¬C
1)A B C
2) A ¬B ¬C
2) A B C
3) A B ¬C
3) A B C
4) A ¬B C
4) A B C
A ( B C) A B C A B C
41
42. Логические уравнения
Логические основы компьютеров42
Логические уравнения
A B A B C 1
A B 1
A=1, B=0, C=1
или
A=0, B=1, C – любое
2 решения: (0, 1, 0), (0, 1, 1)
A B C 1
! Всего 3 решения!
K L M L N K L M 1
K=1, L=1,
M и N – любые
4 решения
M=1, L=1, N=1,
K – любое
2 решения
L (K M N) 1
K=1, L=1, M=0,
N – любое
2 решения
! Всего 5 решений!
43. Логические основы компьютеров
43Логические
основы
компьютеров
3.5 Синтез логических
выражений
44. Синтез логических выражений
Логические основы компьютеров44
Синтез логических выражений
A B
X
0
0
1
1
1
1
0
1
0
1
0
1
A B
A B
A B
Шаг 1. Отметить строки в
таблице, где X = 1.
Шаг 2. Для каждой из них
записать логическое
выражение, которое истинно
только для этой строки.
Шаг 3. Сложить эти выражения и
упростить результат.
распределительный
X A B A B A B A (B B) A B
A A B ( A A) ( A B) A B
исключения
третьего
распределительный
исключения
третьего
45. Синтез логических выражений (2 способ)
Логические основы компьютеров45
Синтез логических выражений (2 способ)
A B
X
0
0
1
1
1
1
0
1
0
1
0
1
A B
Шаг 1. Отметить строки в
таблице, где X = 0.
Шаг 2. Для каждой из них
записать логическое
выражение, которое истинно
только для этой строки.
Шаг 3. Сложить эти выражения и
упростить результат, который
равен X .
Шаг 4. Сделать инверсию.
X A B X A B A B
? Когда удобнее применять 2-ой способ?
46. Синтез логических выражений (3 способ)
Логические основы компьютеров46
Синтез логических выражений (3 способ)
A B
X
0
0
1
1
0
1
0
1
0
1
0
1
A B
A B
Шаг 1. Отметить строки в
таблице, где X = 0.
Шаг 2. Для каждой из них
записать логическое
выражение, которое ложно
только для этой строки.
Шаг 3. Перемножить эти
выражения и упростить
результат.
X (A B) ( A B) A A B A A B B B
B (A A) B B
47. Синтез логических выражений
Логические основы компьютеров47
Синтез логических выражений
A
B C
X
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
1
1
1
1
0
1
0
1
0
1
0
1
0
1
0
1
X A B C A B C
A B C
A B C
A B C
A B C
A B C
A B C
A B C A B C
A B C A B C
A B ( C C)
A B ( C C)
A C ( B B)
A B A B A C
A (B B) A C
A A C
(A A) ( A C) A C
48. Синтез логических выражений (2 способ)
Логические основы компьютеров48
Синтез логических выражений (2 способ)
A
B C
X
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
1
1
1
1
0
1
0
1
0
1
0
1
0
1
0
1
X A B C A B C
A C ( B B)
A C
X A C A C
A B C
A B C
! 3-й способ –
самостоятельно.
49. Логические основы компьютеров
49Логические
основы
компьютеров
3.6 Предикаты и кванторы
50. Предикаты
Логические основы компьютеровПредикаты
Предикат (логическая функция) – это утверждение,
содержащее переменные.
Предикат-свойство – от одной переменной:
P(N) = «В городе N живут более 2 млн человек»
P(Москва) = 1
P(Якутск) = 0
Простое(x) = «x – простое число»
Спит(x) = «x всегда спит на уроке»
Предикат-отношение – от нескольких переменных:
Больше(x, y) = «x > y»
Живет(x, y) = «x живет в городе y»
Любит(x, y) = «x любит y»
50
51. Предикаты и кванторы
Логические основы компьютеров51
Предикаты и кванторы
Предикаты задают множества:
P( x ) ( x 0)
P( x, y ) ( x y 1)
Предикаты, которые всегда истинны:
2
P( x) ( x 0) для всех вещественных чисел
«Для любого допустимого x утверждение P(x)
истинно»:
квантор
x P(x )
высказывание
Квантор – знак, обозначающий количество.
А (all – все) E (exists – существует)
52. Кванторы
Логические основы компьютеровКванторы
Какой квантор использовать?
моря соленые».
« …
кошки серые».
« …
числа чётные».
« …
« …
окуни – рыбы».
прямоугольники – квадраты».
« …
квадраты – прямоугольники».
« …
Истинно ли высказывание?
x P(x ) при P( x ) ( x 0)
x P(x ) при P( x ) ( x 0)
x P(x ) при P( x) ( x 2 0)
x P(x ) при P( x) ( x 2 0)
52
53. Кванторы
Логические основы компьютеров53
Кванторы
Дано:
A = «Все люди смертны» = 1.
B = «Сократ – человек» = 1.
Доказать:
C = «Сократ смертен» = 1.
Доказательство:
A
0
0
B
0
1
А B
1
1
1
1
0
1
0
1
P(x) = «x – человек»
Q(x) = «x – смертен»
x (P( x ) Q( x))
A = 1:
P( Сократ ) Q( Сократ) 1
при «x =Сократ»
P( Сократ ) 1
B = 1:
по свойствам импликации Q( Сократ ) 1
54. Несколько кванторов
Логические основы компьютеров54
Несколько кванторов
Квантор связывает одну переменную:
x P( x, y ) – предикат от переменной y
y P( x, y ) – предикат от переменной x
Два квантора связывают две переменных:
x y P( x, y ) – высказывание «для любого x
существует y, при котором P(x,y)=1»
x y P( x, y ) – высказывание «существует x, такой
что при любом y верно P(x,y)=1»
Сравните два последних высказывания при:
P( x, y ) ( x y 0)
P( x, y ) ( x y 0)
55. Отрицание
Логические основы компьютеров55
Отрицание
НЕ «для любого x выполняется P(x)»
«существует x, при котором не выполняется P(x)»
x P(x) x P(x)
НЕ «существует x, при котором выполняется P(x)»
«для любого x не выполняется P(x)»
x P(x) x P(x)
56. Логические основы компьютеров
56Логические
основы
компьютеров
3.7 Логические элементы
компьютера
57. Логические основы компьютеров
57Логические основы компьютеров
Логический элемент компьютера – это
часть электронной логической схемы,
которая
реализует
элементарную
логическую функцию.
Логическими элементами компьютера
являются логические схемы И, ИЛИ,
НЕ, И-НЕ, ИЛИ-НЕ и др.,а также
триггер.
58. Логические элементы компьютера
Логические основы компьютеров58
Логические элементы компьютера
значок инверсии
A
A
A
&
A
A B
B
НЕ
B
И
A
&
B
A B
ИЛИ
A
1
B
И-НЕ
1
ИЛИ-НЕ
A B
A B
59. Логические элементы компьютера
Логические основы компьютеров59
Логические элементы компьютера
Любое логическое выражение можно реализовать на
элементах И-НЕ или ИЛИ-НЕ.
И: 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
60. Составление схем
Логические основы компьютеров60
Составление схем
последняя операция - ИЛИ
X A B A B C
И
A
B
C
A
B
&
A
B
& A B
A B
A B C
C
&
1
X
61. Триггер (англ. trigger – защёлка)
Логические основы компьютеров61
Триггер (англ. 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
основной
выход
запрещен
62. Триггер – таблица истинности
Логические основы компьютеров62
Триггер – таблица истинности
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
запрещен
63. Полусумматор
Логические основы компьютеров63
Полусумматор
Полусумматор – это логическая схема, способная
складывать два одноразрядных двоичных числа.
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-х
? Схема
элементах?
64. Сумматор
Логические основы компьютеров64
Сумматор
Сумматор – это логическая схема, способная
складывать два одноразрядных двоичных числа с
переносом из предыдущего разряда.
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
65. Многоразрядный сумматор
Логические основы компьютеров65
Многоразрядный сумматор
это логическая схема, способная складывать два
n-разрядных двоичных числа.
A
an an-1 a1
B
bn bn-1 b1
C p cn cn-1 c1
перенос
a1
b1
0
c1
Σ
p2
a2
b2
Σ
c2
p3
an
bn
pn
cn
Σ
p
перенос
66. Логические основы компьютеров
66Логические
основы
компьютеров
3.8 Логические задачи
67. Метод рассуждений
Логические основы компьютеров67
Метод рассуждений
Задача 1. Министры иностранных дел России, США и Китая обсудили за
закрытыми дверями проекты договора, представленные каждой из стран.
Отвечая затем на вопрос журналистов: «Чей именно проект был
принят?», министры дали такие ответы:
Россия — «Проект не наш (1), проект не США (2)»;
США
— «Проект не России (1), проект Китая (2)»;
Китай — «Проект не наш (1), проект России (2)».
Один из них оба раза говорил правду; второй – оба раза говорил
неправду, третий один раз сказал правду, а другой раз — неправду. Кто
что сказал?
проект США (?)
проект Китая (?)
(1) (2)
проект России (?)
(1) (2)
(1) (2)
Россия
+
–
Россия
+
+
Россия
–
+
США
+
–
США
+
+
США
–
Китай
+
–
+
Китай
Китай
68. Табличный метод
Логические основы компьютеров68
Табличный метод
Задача 2. Дочерей Василия Лоханкина зовут Даша, Анфиса и Лариса. У
них разные профессии и они живут в разных городах: одна в Ростове,
вторая – в Париже и третья – в Москве. Известно, что
• Даша живет не в Париже, а Лариса – не в Ростове,
• парижанка – не актриса,
• Много вариантов.
• в Ростове живет певица,
• Есть точные данные.
• Лариса – не балерина.
Париж
Ростов
Москва
0
1
0
1
0
0
0
0
1
Певица
Балерина
Актриса
1
0
0
0
1
0
0
0
1
Даша
Анфиса
Лариса
! В каждой строке и в каждом столбце может
быть только одна единица!
69. Использование алгебры логики
Логические основы компьютеров69
Использование алгебры логики
Задача 3. Следующие два высказывания истинны:
1. Неверно, что если корабль A вышел в море, то корабль C – нет.
2. В море вышел корабль B или корабль C, но не оба вместе.
Определить, какие корабли вышли в море.
Решение:
… если корабль A вышел в море, то корабль C – нет.
1. Неверно, что если корабль A вышел в
море, то корабль C – нет.
A C 0
2. В море вышел корабль B или корабль C, но не оба
вместе.
A C (B C) 1
A C 1
A C 1
B C 1
A C (B C B C) 1
A C (B C B C) 1
A C B 1
A 1, B 0, C 1
70. Использование алгебры логики
Логические основы компьютеров70
Использование алгебры логики
Задача 4. Когда сломался компьютер, его хозяин сказал «Память не могла
выйти из строя». Его сын предположил, что сгорел процессор, а винчестер
исправен. Мастер по ремонту сказал, что с процессором все в порядке, а
память неисправна. В результате оказалось, что двое из них сказали все
верно, а третий – все неверно. Что же сломалось?
Решение:
A – неисправен процессор, B – память, C – винчестер
хозяин:
B 0, B 1
сын: A C 1
Если ошибся хозяин:
X1 B A C A B 1
Если ошибся сын:
X2 B A C A B 1
Если ошибся мастер:
X3 B A C A B 1
мастер: A B 1
X3 B A C (A B ) 1
X3 B A C 1
A 1
B 0
C 0
71. Использование алгебры логики
Логические основы компьютеров71
Использование алгебры логики
Задача 5. На вопрос «Кто из твоих учеников изучал логику?»
учитель ответил: «Если логику изучал Андрей, то изучал и Борис.
Однако неверно, что если изучал Семен, то изучал и Борис». Кто же
изучал логику?
Решение: A – логику изучал Андрей, B – Борис, C – Семен
«Если логику изучал Андрей,
то изучал и Борис».
A B 1
«Неверно, что если изучал
Семен, то изучал и Борис».
C B 0
1 способ:
(A B) (C B) 1
( A B) (C B) 1
( A B) C B 1
A C B 1
C B 1
A 0
B 0
C 1
72. Использование алгебры логики
Логические основы компьютеров72
Использование алгебры логики
Задача 5. На вопрос «Кто из твоих учеников изучал логику?»
учитель ответил: «Если логику изучал Андрей, то изучал и Борис.
Однако неверно, что если изучал Семен, то изучал и Борис». Кто же
изучал логику?
Решение: A – логику изучал Андрей, B – Борис, C – Семен
«Неверно, что если изучал
Семен, то изучал и Борис».
2 способ:
B 0
C 1
«Если логику изучал Андрей,
то изучал и Борис».
C B 0
A B 1
С
B
С B
A
B
A B
0
0
1
0
0
1
0
1
1
0
1
1
1
0
0
1
0
0
1
1
1
1
1
1
A 0
B 0
C 1
73. Использование алгебры логики
Логические основы компьютеров73
Использование алгебры логики
Задача 6. Суд присяжных пришел к таким выводам:
• если Аськин не виновен или Баськин виновен, то виновен
Сенькин
• если Аськин не виновен, то Сенькин не виновен
Виновен ли Аськин?
Решение: A – виновен Аськин, B – Баськин, C – Сенькин
«Если Аськин не виновен или Баськин
виновен, то виновен Сенькин».
«Если Аськин не виновен, то
Сенькин не виновен».
(A B) C 1
A C 1
((A B) C) (A C ) 1
(( A B) C) (A C) 1
(A B C) (A C ) 1
A 0
C C 1
Аськин
виновен
74. Использование алгебры логики
Логические основы компьютеров74
Использование алгебры логики
Задача 6б. Суд присяжных пришел к таким выводам:
• если Аськин не виновен или Баськин виновен, то виновен
Сенькин
• если Аськин не виновен, то Сенькин не виновен
Виновен ли Баськин?
Решение: A – виновен Аськин, B – Баськин, C – Сенькин
(A B C) (A C ) 1
B 0
A 1
(A B C) (A C ) 1
B 1
C A 1
Не получили
противоречия:
возможно, что и
виновен
75. Использование алгебры логики
Логические основы компьютеров75
Использование алгебры логики
Задача 6в. Суд присяжных пришел к таким выводам:
• если Аськин не виновен или Баськин виновен, то виновен
Сенькин
• если Аськин не виновен, то Сенькин не виновен
Виновен ли Сенькин?
Решение: A – виновен Аськин, B – Баськин, C – Сенькин
(A B C) (A C ) 1
C 0
A B 1
(A B C) (A C ) 1
C 1
A 1
Не получили
противоречия:
возможно, что и
виновен
76. Логические основы компьютеров
76Логические
основы
компьютеров
Задачи ЕГЭ
77. Задачи ЕГЭ
Логические основы компьютеров77
Задачи ЕГЭ
Для какого из указанных значений X истинно
высказывание ¬((X > 2)→(X > 3))?
(X 2) (X 3)
1) 1
2) 2
3) 3
4) 4
(X 2) (X 3) 1
A B 0
X 2
X 3
(X 2) (X 3) 0
A 1, B 0
X 3
Укажите, какое логическое выражение равносильно
выражению A ¬(¬B C).
1) A B C
1) ¬A ¬B ¬C
2) A B C
2) A ¬B ¬C
A ( B C)
3) A B C
3) A B ¬C
4) A B C
4) A ¬B C
78. Задачи ЕГЭ (2)
Логические основы компьютеров78
Задачи ЕГЭ (2)
Каково наибольшее целое число X, при котором
истинно высказывание
(50 < X·X) → (50 > (X+1)·(X+1))
В целых числах:
A
B
50 X X 8
50 (X 1)2 X 1 7 - 8 X 6
2
-8 -7 -6
A B 1 A 0, B 0
A 0, B 1
A 1, B 1
6
7
8
Xmax 7
79. Задачи ЕГЭ (6)
Логические основы компьютеров79
Задачи ЕГЭ (6)
Перед началом Турнира Четырех болельщики
высказали следующие предположения по поводу своих
кумиров:
А) Макс победит, Билл – второй;
В) Билл – третий, Ник – первый;
С) Макс – последний, а первый – Джон.
Когда соревнования закончились, оказалось, что
каждый из болельщиков был прав только в одном из
своих прогнозов. Какое место на турнире заняли Джон,
Ник, Билл, Макс? (В ответе перечислите
A подряд
B безC
пробелов места участников в указанном порядке имен.)
Джон
1
Ник
1
Билл
2
3
Ответ: 3124
Макс
1
4
80. Задачи ЕГЭ (7)
Логические основы компьютеровЗадачи ЕГЭ (7)
На одной улице стоят в ряд 4 дома, в каждом из них живет
по одному человеку. Их зовут Василий, Семен, Геннадий и
Иван. Известно, что все они имеют разные профессии:
скрипач, столяр, охотник и врач. Известно, что
(1) Столяр живет правее охотника.
(2) Врач живет левее охотника.
(3) Скрипач живет с краю.
(4) Скрипач живет рядом с врачом.
(5) Семен не скрипач и не живет рядом со скрипачом.
(6) Иван живет рядом с охотником.
(7) Василий живет правее врача.
(8) Василий живет через дом от Ивана.
Определите, кто где живет, и запишите начальные буквы
имен жильцов всех домов слева направо. Например, если бы
в домах жили (слева направо) Кирилл, Олег, Мефодий и
Пафнутий, ответ был бы КОМП.
80
81. Задача Эйнштейна
Логические основы компьютеровЗадача Эйнштейна
Условие: Есть 5 домов разного цвета, стоящие в ряд. В каждом доме живет по одному
человеку отличной от другого национальности. Каждый жилец пьет только один
определенный напиток, курит определенную марку сигарет и держит животное.
Никто из пяти человек не пьет одинаковые напитки, не курит одинаковые сигареты
и не держит одинаковых животных.
Известно, что:
1. Англичанин живет в красном доме.
2. Швед держит собаку.
3. Датчанин пьет чай.
4. Зеленой дом стоит слева от белого.
5. Жилец зеленого дома пьет кофе.
6. Человек, который курит Pallmall, держит птицу.
7. Жилец среднего дома пьет молоко.
8. Жилец из желтого дома курит Dunhill.
9. Норвежец живет в первом доме.
10. Курильщик Marlboro живет около того, кто держит кошку.
11. Человек, который содержит лошадь, живет около того, кто курит Dunhill.
12. Курильщик Winfield пьет пиво.
13. Норвежец живет около голубого дома.
14. Немец курит Rothmans.
15. Курильщик Marlboro живет по соседству с человеком, который пьет воду.
Вопрос: У кого живет рыба?
81
82. Конец фильма
Логические основы компьютеровКонец фильма
ПОЛЯКОВ Константин Юрьевич
д.т.н., учитель информатики высшей категории,
ГОУ СОШ № 163, г. Санкт-Петербург
[email protected]
82