Основы математической логики
Математическая логика
– это наука о методах рассуждений, при которых мы отвлекаемся от содержания рассуждений, а используем только их форму и значение.
В математической логике используются только логические переменные, которые принимают только значения 0 (ложь) или 1 (истина)
Функции, которые определены на этих переменных, и принимают значения 0 или 1 тоже называются логическими
Логические функции и таблицы истинности
Логическое сложение a+b, дизъюнкция, a˅b , логическое «или»
a
b
0
a˅b
0
0
1
1
0
1
1
Логическое сложение a+b, дизъюнкция, a˅b , логическое «или»
a
b
0
a˅b
0
0
1
0
1
0
1
1
Логическое сложение a+b, дизъюнкция, a˅b , логическое «или»
a
b
0
a˅b
0
0
1
0
1
1
0
1
1
Логическое сложение a+b, дизъюнкция, a˅b , логическое «или»
a
b
0
a˅b
0
0
1
0
1
1
0
1
1
1
Логическое сложение a+b, дизъюнкция, a˅b , логическое «или»
a
b
0
a˅b
0
0
1
0
1
1
0
1
1
1
1
Вывод:
Дизъюнкция истинна, когда истинно хотя бы одно высказывание
дизъюнкция
Логическое умножение a*b, конъюнкция, a&b, a^b, логическое «и»
a
b
0
a^b
0
0
1
1
0
1
1
Логическое умножение a*b, конъюнкция, a&b, a^b, логическое «и»
a
b
0
a^b
0
0
1
0
1
0
1
1
Логическое умножение a*b, конъюнкция, a&b, a^b, логическое «и»
a
b
0
a^b
0
0
1
0
1
0
0
1
1
Логическое умножение a*b, конъюнкция, a&b, a^b, логическое «и»
a
b
0
a^b
0
0
1
0
1
0
0
1
1
0
Логическое умножение a*b, конъюнкция, a&b, a^b, логическое «и»
a
b
0
a^b
0
0
1
0
1
0
0
1
1
0
1
конъюнкция
Вывод:
Конъюнкция истинна только тогда, когда истинны оба высказывания
Логическое отрицание ā , инверсия, логическое «не»
a
ā
0
a
1
1
0
Логическое отрицание ā , инверсия, логическое «не»
a
ā
0
a
1
1
0
0
Логическое отрицание ā , инверсия, логическое «не»
a
ā
0
a
1
1
0
0
1
Вывод:
Инверсия истинна, когда высказывание ложно, и наоборот
Логические (булевы) выражения – это булевы постоянные и булевы переменные связанные « и », « или », « не » в единую форму.
Приоритет выполнения действий в логических выражениях:
- Инверсия
- Конъюнкция
- Дизъюнкция
для изменения приоритета используют скобки.
Теоремы булевой алгебры
- 1 = 0, 0 = 1
отрицание истины – есть ложь;
отрицание лжи – истина
2. X = X
закон двойного отрицания
3. X V 0 = X,
X * 1 = X
X V 0 = X
при X=0 при X = 1
0 V 0 = 0 1 V 1 = 1
X * 1 = X
при X=0 при X = 1
0 * 0 = 0 1 * 1 = 1
4. X V X = X,
X * X = X
X V X = X
при X=0 при X = 1
0 V 0 = 0 1 V 1 = 1
X * X = X
при X=0 при X = 1
0 * 0 = 0 1 * 1 = 1
5. X V X = 1,
X * X = 0
X V X = 1
при X=0 при X = 1
0 V 0 = 0 V 1 = 1 1 V 1 = 1 V 0 = 1
X * X = 0
при X=0 при X = 1
0 * 0 = 0 * 1 = 0 1 * 1 = 1 * 0 = 0
6. X V Y = Y V X,
X * Y = Y * X
коммутативный закон
7. (X V Y) = X * Y,
(X * Y) = X V Y
закон де-Моргана