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

Другие логические операции
§ 11. Логические выражения
§ 12. Множества и логика

правильно рассуждать, делать выводы, доказывать утверждения.
Формальная логика отвлекается от конкретного

Логическое высказывание – это повествовательное предложение, относительно которого можно однозначно сказать, истинно оно или ложно.

предмет.
У квадрата – 10 сторон и все разные.
Красиво!
В городе N

логики — это математический аппарат, с помощью которого записывают, упрощают

Алгебра высказываний,
булева алгебра

двоичная логика

открыта.
простые высказывания (элементарные)
Составные высказывания строятся из простых с помощью логических

A и B
A или не B
если A, то B
A тогда и только
тогда, когда B

Сейчас идет дождь и открыта форточка.
Сейчас идет дождь или форточка закрыта.
Если сейчас идет дождь, то форточка открыта.
Дождь идет тогда и только тогда, когда открыта форточка.

и наоборот.
1
0
0
1
таблица истинности операции НЕ
Таблица истинности логического выражения Х –

когда А и B истинны одновременно.
A и B
A
B

от лат. conjunctio — соединение
A и B = min(A,

когда истинно А или B, или оба вместе.
A или B
A
B

от лат. disjunctio — разъединение
A и B = max(A,

и 1 = A ∙ 1 =
A
0
A или 0 =

1

A

A и не A = A ∙ A =
A или (не A) = A + A =

0

1

и B)
не (A или B)
«И»
«ИЛИ»

Лена раскрывает зонтик.
X = A

Импликация A → B истинна, если не исключено, что из A следует B.

1

1

0

1

Идёт дождь, но Лена не раскрыла зонтик.

B  A

А и B равны.

или B, но не оба одновременно (A  B).
«Либо пан,

0

0

1

1

сложение по модулю 2: А  B = (A + B) mod 2

арифметическое сложение, 1+1=2

остаток

A =
(A  B)  B =
A
0
A
операция обратима

0 0 1
B = 0 1 0 1
(A 

B = 0 1 0 1

1 0 0 1

= A

логическое значение (истина или ложь).
Авария = вышли из строя 2

= (A и B) или (A и C) или (B и C)

логическое выражение

(всегда 1, тавтология)
тождественно ложными (всегда 0, противоречие)

переменных, они называются равносильными (определяют одну и ту же логическую

2-й строке
25 = 32

1 единица,
все строки разные!

и (x  6)
(1  x) и (x  3)

граница:
y  – x
(x  – 1)
и (y  –

и (y  – x)

 1)
левая
нижняя
и (y  – x)
верхняя

и (x  0) и (y  – x))

высказывание:
(X

X = 2:

( 1 ) И НЕ ( 0 )

X = 4:

( 1 ) И НЕ ( 0 )

X = 8:

( 0 ) И НЕ ( 0 )

( 0 И 1)

= 0

( 1 И 1 )

= 1

( 1 И 1 )

= 1

можно не вычислять!

R =

≥ 3) И НЕ (X = 8)) ИЛИ (X ≤

X = 4:

(НЕ (1) И НЕ (0)) ИЛИ (1)

= 1

X = 1:

(НЕ (0) И НЕ (0)) ИЛИ (1)

= 1

X = 8:

(НЕ (1) И НЕ (1)) ИЛИ (0)

( 0 И 0 ) ИЛИ (0)

= 0

? + 1

НЕ (X < 1) ?
(X < 5) И (X

1, 2, 3, 4

(Последняя буква гласная) ?
(Первая буква согласная)

(Последняя буква гласная) ?
(Первая буква согласная) ИЛИ
(Последняя буква гласная)

Никита
Антон
Даниил
Инна

Кирилл
Егор
Мефодий
Игнат

ЛОЖНО

A + B = 0

ИЛИ  И,
обратные условия

(Последняя буква гласная) ?
(Первая буква согласная) И
(Последняя буква гласная)

Никита
Антон
Даниил
Инна

Кирилл
Егор
Мефодий
Игнат

ЛОЖНО

A · B = 0

И  ИЛИ,
обратные условия

И НЕ (X = 8)) ИЛИ (X ≤ 5) ?

ЛОЖНО ( (X < 3) И (X <> 8)) ИЛИ (X ≤ 5)

6, 7, 8, …

ИСТИННО ( (X ≥ 3) ИЛИ (X = 8)) И (X > 5)

И  ИЛИ,
обратные условия

отличается от остальных.
пустое множество: 
конечное число элементов: буквы русского алфавита
бесконечное

Как задать множество?
перечислением элементов
{Вася, Петя, Коля}
логическим выражением:
{x: x > 0}

и (не B)
не A
(не A) и (не B)

(and) | = или (or)
NA –

NA NA & B



?

NA NA | B



?

в порядке возрастания количества страниц, которые найдет поисковый сервер по

АВБГ

в порядке убывания количества страниц, которые найдет поисковый сервер по

ГБВА

следующим запросам :





Сколько сайтов будет найдено по запросу

NA

NB

NA&B

NA|B

NA + NB
A
B
NA | B =

NA + NB =

NA&B =

NA | B = NA + NB – NA & B

Формула включений
и исключений

+ = NA | B +

A | B

по следующим запросам:






Сколько сайтов будет найдено по запросу

NB – NA|B
A = собаки & лемуры

по следующим запросам:






Сколько сайтов будет найдено по запросу

A

B

A | B

A & B

сайтов будет найдено по запросу
(принтер | сканер)

Задачи с тремя областями

NA&B
принтер | сканер
450
сканер
принтер
200
250
0
сканер
принтер
монитор
90
40 + 50 =
принтер & монитор =

сканер & монитор = 50

50

40

(принтер | сканер) & монитор

Санкт-Петербург
kpolyakov@mail.ru
ЕРЕМИН Евгений Александрович
к.ф.-м.н., доцент кафедры мультимедийной дидактики и ИТО