Построение таблиц истинности. Логические основы компьютера презентация

Вспомним известное…
Логическое высказывание – это повествовательное предложение, относительно которого можно однозначно сказать, истинно оно (0) или ложно (1).
Алгебра логики (булева алгебра) — это математический аппарат, с помощью которого записывают, вычисляют, упрощают и преобразуют логические высказывания.

Вспомним известное…
Логическое выражение — это символическая запись высказывания, которая может содержать логические переменные и знаки логических операций.
Логическая функция — это правило преобразования входных логических значений в выходные. Логическая функция задаётся таблицей истинности.
Выражения:
функция
A
A+A⋅B
A⋅(A+B)

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

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

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

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

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

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

Свойства операции «исключающее ИЛИ»
A ⊕ A =
(A ⊕ B) ⊕ B =
A ⊕ 0 =
A ⊕ 1 =
A
0
?

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

Импликация («если …, то …»)
«Если Вася идет гулять, то Маша сидит дома».
A – «Вася идет гулять».
B – «Маша сидит дома».
Маша может пойти гулять
(B=0), а может и не пойти (B=1)!

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

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

Штрих Шеффера, «И-НЕ»
Базовые операции через «И-НЕ»:

Стрелка Пирса, «ИЛИ-НЕ»
Базовые операции через «ИЛИ-НЕ»:

Логические выражения
Примеры и решение задач

Формализация
Прибор имеет три датчика и может работать, если два из них исправны. Записать в виде формулы ситуацию «авария».
A – «Датчик № 1 неисправен».
B – «Датчик № 2 неисправен».
C – «Датчик № 3 неисправен».
Аварийный сигнал:
X – «Неисправны два датчика».
X – «Неисправны датчики № 1 и № 2» или
«Неисправны датчики № 1 и № 3» или
«Неисправны датчики № 2 и № 3».
логическая формула

Вычисление логических выражений
Порядок вычислений:
скобки
НЕ
И
ИЛИ, исключающее ИЛИ
импликация
эквиваленция
A
B
+
∙
+
B
C
∙
A
С
∙
1 4 2 5 3

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

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

Задачи
Задача 1. При каких значениях логических переменных истинно выражение:
Решение. Все сомножители равны 1:
Задача 2. При каких значениях логических переменных ложно выражение:
Решение. Все слагаемые равны 0:

Задачи
Задача 3. Запишите любое логические выражение, соответствующее таблице истинности:
в полной
23 = 8 строк
истинно при X = 1, Y = Z = 0

Задачи
Задача 4. Запишите любое логические выражение, соответствующее таблице истинности:
ложно при X = 1, Y = Z = 0

Задачи
Задача 5. Символом F обозначено одно из указанных ниже логических выражений от трёх аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F. Какое выражение соответствует F?
¬X ∧ ¬Y ∧ ¬Z
X ∧ Y ∧ Z
X ∨ Y ∨ Z
¬X ∨ ¬Y ∨ ¬Z
Быстрый способ:

Задачи
Задача 6. Запишите любое логические выражение, соответствующее таблице истинности:
«И»

Задачи
Задача 7. Задана таблица истинности логической функции . Определите, где какой столбец.
1
1
1
X
Y
Z

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

Диаграмма с тремя переменными
Хочу
Могу
Надо
1
2
3
4
5
6
7
8

Диаграмма с тремя переменными
Х
М
Н

Диаграмма с тремя переменными
Х
М
Н

Известно количество сайтов, которых находит поисковый сервер по следующим запросам:
Сколько сайтов будет найдено по запросу
огурцы | помидоры
Задачи

Задачи
NA|B = NA+ NB
A
B
A
B
NA|B = NA+ NB – NA&B
огурцы | помидоры
50
огурцы
помидоры
100
200
огурцы & помидоры
250

Известно количество сайтов, которых находит поисковый сервер по следующим запросам:
Сколько сайтов будет найдено по запросу
Динамо & Спартак & Рубин
Задачи

Задачи
Динамо
Спартак
Рубин
1
2
3
Динамо & Рубин
= 1 + 2 = 320
Спартак & Рубин = 2 + 3 = 280
(Динамо | Спартак) & Рубин
= 1 + 2 + 3 = 430
Динамо & Спартак & Рубин
= 2
= (320 + 280) – 430 =
170
B
A
A & B
A | B
NA&B = NA+ NB – NA|B

Известно количество сайтов, которых находит поисковый сервер по следующим запросам :
Сколько сайтов будет найдено по запросу
Динамо & Спартак
Задачи
Ответ: 320 + 280 – 430 =
170

Задачи
Динамо
Спартак
Рубин
1
2
3
Динамо & Рубин
= 1 + 2 = 320
Спартак & Рубин = 2 + 3 = 280
(Динамо | Спартак) & Рубин
= 1 + 2 + 3 = 430
Динамо & Спартак & Рубин
= 2
= (320 + 280) – 430 =
170

Поисковый сервер в автоматическом режиме составил таблицу ключевых слов для сайтов некоторого сегмента Интернета. Вот ее фрагмент:
Сколько сайтов будет найдено по запросу
(принтер | сканер) & монитор
если по трем следующим запросам найдено:
принтер | сканер – 450 сайтов,
принтер & монитор – 40 сайтов
сканер & монитор – 50 сайтов.
Задачи

Задачи
А (сканер)
B (принтер)
NA|B = NA+ NB – NA&B
принтер | сканер
450
сканер
принтер
200
250
0
сканер
принтер
монитор
90
40 + 50 =
принтер & монитор = 40
сканер & монитор = 50
50
40
(принтер | сканер) & монитор = ?