Элементы комбинаторики, теории множеств и математической логики

1.

Элементы комбинаторики,
теории множеств и
математической логики
Жук И.А.
1

2.

Принципы обработки информации
компьютером
Между алгеброй логики и двоичным
кодированием существует следующая связь :
математический аппарат алгебры
логики очень удобен для описания того как
функционируют
аппаратные
средства
компьютера, поскольку основной системой
счисления в компьютере является двоичная, в
которой используются цифры 1 и 0, а значений
логических переменных
тоже два : “1” и “0”.

3.

Выводы:
одни и те же устройства компьютера могут
применяться для обработки и хранения как
числовой информации, представленной в
двоичной системе счисления, так и логических
переменных;
на этапе конструирования аппаратных средств
алгебра логики позволяет значительно упростить
логические функции, описывающие
функционирование схем компьютера, и ,
следовательно, уменьшить число основных узлов
компьютера.
3

4.

Логические операции
Логическое умножение (конъюнкция) «И»
A И B или A&B или A ∧ B
A И B истинно тогда и только тогда,
когда оба высказывания A и B истинны.
Примеры:
0 И 0=0 0 И 1=0 1 И 0=0 1 И 1=1
Техническая реализация И два последовательно соединенных
ключа:
4

5.

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

6.

Логическое сложение «ИЛИ»
A ИЛИ B или A ∨ B или A+B
A или B ложно тогда и только тогда, когда оба
высказывания A и B ложны.
Примеры:
0 ИЛИ 1=1 1 ИЛИ 0=1 0 ИЛИ 0=0 1 ИЛИ 1=1
Техническая реализация ИЛИ - два параллельно
соединенных ключа:
6

7.

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

8.

Логическое отрицание (инверсия)
Логическое отрицание (инверсия ) «НЕ»
НЕ А или ¬A
делает истинное выражение ложным и,
наоборот, ложное –истинным.
8

9.

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

10.

Техническая реализация НЕ –
при отсутствии электрического тока
через обмотку реле контакты реле
замкнуты,
при протекании достаточного тока через
обмотку реле контакты реле
разомкнуты:
10

11.

Логические операции
Логическое следование
(импликация) A→B
A→B ложно только тогда,
когда А истинно, а В ложно.
Импликация выражается через
дизъюнкцию и отрицание:
A→B = НЕ A ИЛИ B
11

12.

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

13.

Логические операции
Эквивалентность
A↔B или A≡B
Истинно если А и В имеют
одинаковые значения
А
0
0
1
1
В
0
1
0
1
A≡B
1
0
0
1
13

14.

Приоритет логических операций
1) Инверсия НЕ
2) Конъюнкция И
3) Дизъюнкция ИЛИ
4) Импликация →
5) Эквивалентность ↔
14

15.

Законы алгебры логики
15

16.

Законы алгебры логики
16

17.

Законы алгебры логики
17

18.

Задачи
1.Для какого значения числа Х, изменяющегося
от 2 до 5, истинно высказывание:
НЕ ((X>3)→ (X>4))?
Решение (способ 1)
18

19.

По таблице истинности импликации видим,
что она будет ложной в одном единственном
случае: когда первое высказывание истинно,
а второе ложно.
Первое высказывание (X>3) может быть
истинно только при X=4 или X=5.
Второе высказывание принимает значение
ЛОЖЬ только при X=4.
Ответ: 4
19

20.

Решение (способ 2)
Метод последовательной подстановки
1)Х=2 НЕ((2>3)→(2>4))= ¬(0→0)=¬(1)=0
2) X=3 НЕ((3>3)→(3>4))= ¬(0→0)=¬(1)=0
3) X=4 НЕ((4>3)→(4>4))= ¬(1→0)=¬(0)=1
4) X=5 НЕ((5>3)→(5>4))= ¬(1→1)=¬(1)=0
Ответ: 3) 4
20

21.

Логическая функция F задаётся выражением
(¬x ∧ ¬y) ∨ (y ≡ z) ∨ ¬w.
x
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
y
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
z
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
w
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
¬x
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
¬y
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
(¬x ∧ ¬y) y ≡ z
1
1
1
1
1
0
1
0
0
0
0
0
0
1
0
1
0
1
0
1
0
0
0
0
0
0
0
0
0
1
0
1
(¬x ∧ ¬y) ∨ (y ≡ z)
1
1
1
1
0
0
1
1
1
1
0
0
0
0
1
1
¬w
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
(¬x ∧ ¬y) ∨ (y ≡ z) ∨ ¬w
1
1
1
1
1
0
1
1
1
1
1
0
1
0
1
1
21

22.

1. ¬ X v Y &¬ Z
2. ¬ X & ¬ Y v Z
3. X → (Y & ¬ Z)
4. X v ¬ Y ↔ Z
22