Математическая логика. Логические выражения

1. Математическая логика

1
Математическая
логика
§ 8. Логические выражения
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

2. Логические выражения

Математическая логика, 9 класс
2
Логические выражения
Логическое выражение — это выражение,
результат вычисления которого — логическое
значение (истина или ложь).
Авария = вышли из строя 2 из 3-х двигателей.
A – «Двигатель № 1 неисправен».
логическое
B – «Двигатель № 2 неисправен».
выражение
C – «Двигатель № 3 неисправен».
Аварийный сигнал: X ( A B) ( A C) (B C)
X = «Неисправны два двигателя»
= (A и B) или (A и C) или (B и C)
!
Формализация – это переход к записи на
формальном языке!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

3. Порядок вычисления

Математическая логика, 9 класс
3
Порядок вычисления
• скобки
• НЕ
•И
• ИЛИ , исключающее ИЛИ
• импликация
• эквиваленция
5
6
1 3
4 2
X A B (A B B )
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Математическая логика, 9 класс
4
Таблицы истинности
X A B A B
0
1
2
3
A
B
A B
A B
X
0
0
1
1
0
1
0
1
0
0
1
0
0
1
0
0
0
1
1
0
Логические выражения могут быть:
• вычислимыми (зависят от исходных данных)
• тождественно истинными (всегда 1, тавтология)
• тождественно ложными (всегда 0, противоречие)
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Математическая логика, 9 класс
5
Таблицы истинности
X ( A B) ( A B )
0
1
2
3
A
B
0
0
1
1
0
1
0
1
A B A B
0
1
1
1
1
1
1
0
равносильны
X
A B A B
0
1
1
0
0
1
1
0
Если два выражения принимают одинаковые
значения при всех значениях переменных, они
называются равносильными (определяют
одну и ту же логическую функцию).
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

6. Неполные таблицы истинности

Математическая логика, 9 класс
6
Неполные таблицы истинности
A
B
C
F
0
0
1
0
1
1
1
1
1
1
0
0
?
?
Сколько строк в полной
таблице?
3
2 =8
Сколько подходящих
функций?
25 = 32
а) F A B C
один ноль в таблице
F A C B
в) F A B C
по 1-й строке
б)
г)
по 2-й строке
F A B C
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

7. Сколько нулей и единиц?

Математическая логика, 9 класс
7
Сколько нулей и единиц?
в таблице истинности функции от 3-х переменных:
A B C
A B C
A B C
A B C
A ( B C)
К.Ю. Поляков, Е.А. Ерёмин, 2018
нулей
единиц
1
7
7
1
5
7
1
1
7
3
http://kpolyakov.spb.ru

8. Неполные таблицы истинности

Математическая логика, 9 класс
8
Неполные таблицы истинности
A
0
1
B
C
F
1
0
1
1
0
1
один ноль,
две единицы
а)
F A B C
по 1-й строке
1 B 0 0
б)
F A B C
по 2-й строке
0 0 C 1
в)
F A B C
г)
F A B C
К.Ю. Поляков, Е.А. Ерёмин, 2018
только 1 единица,
все строки разные!
http://kpolyakov.spb.ru

9. Составление условий

Математическая логика, 9 класс
9
Составление условий
0
1
2
3
4
5
(x 3) и (x 6)
0
1
2
3
6
7
x
8
(3 x) и (x 6)
4
5
6
7
x
8
(1 x) и (x 3) или (5 x) и (x 8)
0
1
2
К.Ю. Поляков, Е.А. Ерёмин, 2018
3
4
5
6
7
8
x
http://kpolyakov.spb.ru

10. Составление условий

Математическая логика, 9 класс
10
Составление условий
x 1 y
x –1
нижняя граница: y – 1
верхняя граница: y – x
левая граница:
-1
y 1 - 1
1 x
y x
!
Всё одновременно!
(x – 1) и (y – 1) и (y – x)
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

11. Составление условий

Математическая логика, 9 класс
11
Составление условий
y
x2 y 2 1
1 x
-1
y
-1
(x2+y2 1) и (x 0)
x y 1
2
2
1 x
(x 0) и (x2+y2 1)
и (y – x)
y x
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

12. Составление условий

Математическая логика, 9 класс
12
Составление условий
y
x2 y 2 1
y
-1
1 x
=
-1
y
x2 y 2 1
1 x
+
x2 y 2 1
1 x
-1
y x
(…) или (…)
y x
((x2+y2 1) и (x 0)) или
? Как упростить?
((x2+y2 1) и (x 0) и (y – x))
А ещё?
?
(x2+y2 1) и ((x 0) или ((x 0) и (y – x)))
(x2+y2 1) и ((x 0) или (y – x))
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru