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

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

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

Операция НЕ (инверсия)
Если высказывание A истинно, то «не А» ложно, и наоборот.
1
0
0
1
таблица истинности операции НЕ
также , ,
not 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,
1
1
дизъюнкция – от лат. disjunctio — разъединение

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

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

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

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

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

Вычисление логических выражений
Порядок вычислений:
скобки
НЕ
И
ИЛИ
импликация
эквиваленция
1 4 2 5 3

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

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

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