8-01-06-Математическая логика

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

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

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

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

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

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

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

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

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

Упрощение логических выражений
A и 0 = A ∙ 0 =
A и 1 = A ∙ 1 =
A
0
A или 0 = A + 0 =
A или 1 = A + 1 =
1
A
A и не A = A ∙ A =
A или (не A) = A + A =
0
1

Логические выражения
Логическое выражение — это выражение, результат вычисления которого — логическое значение (истина или ложь).
Авария = вышли из строя 2 из 3-х двигателей.
A – «Двигатель № 1 неисправен».
B – «Двигатель № 2 неисправен».
C – «Двигатель № 3 неисправен».
Аварийный сигнал:
X = «Неисправны два двигателя»
= (A и B) или (A и C) или (B и C)
логическое выражение

Порядок вычисления
скобки
НЕ
И
ИЛИ
1
2
3
4
5
6

Таблицы истинности