1 of 42

Логические основы компьютеров

§ 16. Логика и компьютер

1

2 of 42

Что такое логика?

Логика (от греч. logos -- слово, рассуждение, разум) -- наука о законах и операциях правильного мышления. Формальная логика обращает основное внимание на форму в отвлечении от содержания.
Слово "логика" происходит от древнегреческого "логос", имеющего значения: слово, наука, разум. Поэтому оно, во-первых, вошло составной частью в названия многих наук, а во-вторых, выражает смысл логики, как НАУКИ О МЫСЛЯХ.

3 of 42

Клод Шеннон (1916-2001). Его исследования позволили применить алгебру логики в вычислительной технике

Логика

Аристотель (384-322 до н.э.). Основоположник формальной логики (понятие, суждение, умозаключение).

Джордж Буль (1815-1864). Создал новую область науки - Математическую логику (Булеву алгебру или Алгебру высказываний).

4 of 42

Алгебра логики (Булева алгебра)

В XIX веке англичанин Джордж Буль превратил мат. логику в АЛГЕБРУ СУЖДЕНИЙ.
Булева алгебра - наука о действиях над суждениями (высказываниями). Буль произвел революцию в науке, о которой сам не подозревал. То, во что он превратил логику, было в дальнейшем положено в основу построения электронно-вычислительных устройств.

5 of 42

Формы мышления

Понятие – это форма мышления, фиксирующая основные признаки объекта.
Высказывание – это форма мышления, в которой что-либо утверждается или отрицается о свойствах объектов.
Умозаключение – это форма мышления, с помощью которой из нескольких суждений получается новое суждение.

6 of 42

Логическое высказывание

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

«6 — четное число»

«Рим — столица Франции»

«Указанное число кратно 3»

«Число 9 кратно 3»

истинно

ложно

не является высказыванием, так как нельзя однозначно сказать, истинно оно или ложно

является высказыванием и имеет значение истинно

7 of 42

Вспомним известное…

7

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

Алгебра логики (булева алгебра) — это математический аппарат, с помощью которого записывают, вычисляют, упрощают и преобразуют логические высказывания.

Логические основы компьютеров, 10 класс

8 of 42

Вспомним известное…

8

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

Логическая функция — это правило преобразования входных логических значений в выходные. Логическая функция задаётся таблицей истинности.

Выражения:

A	B	F
0	0	0
0	1	0
1	0	1
1	1	1

функция

A

A+A⋅B

A⋅(A+B)

Логические основы компьютеров, 10 класс

9 of 42

Операция НЕ (инверсия)

9

Если высказывание A истинно, то «не А» ложно, и наоборот.

А	не А

1

0

1

таблица истинности операции НЕ

также , , �not A (Питон, Паскаль), �! A (Си)

Таблица истинности логического выражения Х – это таблица, где в левой части записываются все возможные комбинации значений исходных данных, а в правой – значение выражения Х для каждой комбинации.

Логические основы компьютеров, 10 класс

10 of 42

Операция НЕ (инверсия)

10

A

НЕ

значок инверсии

Логические основы компьютеров, 10 класс

11 of 42

Операция И

11

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

220 В

A и B

A

B

Логические основы компьютеров, 10 класс

12 of 42

Операция И (логическое умножение, конъюнкция)

12

A	B	А и B

1

0

также: A·B, A ∧ B,�A and B (Питон, Паскаль), �A && B (Си)

0

1

0

1

0
1
2
3

0

конъюнкция – от лат. conjunctio — соединение

A ∧ B

Логические основы компьютеров, 10 класс

13 of 42

Операция И (логическое умножение, конъюнкция)

13

A

B

A·B

&

И

Логические основы компьютеров, 10 класс

14 of 42

Операция ИЛИ (логическое сложение, дизъюнкция)

14

Высказывание «A или B» истинно тогда, когда истинно А или B, или оба вместе.

220 В

A или B

A

B

Логические основы компьютеров, 10 класс

15 of 42

Операция ИЛИ (логическое сложение, дизъюнкция)

15

A	B	А или B

1

0

также: A+B, A ∨ B,�A or B (Питон, Паскаль), �A || B (Си)

0

1

0

1

дизъюнкция – от лат. disjunctio — разъединение

Логические основы компьютеров, 10 класс

16 of 42

Операция ИЛИ (логическое сложение, дизъюнкция)

16

A

B

A+B

1

ИЛИ

Логические основы компьютеров, 10 класс

17 of 42

Операция «исключающее ИЛИ»

17

Высказывание «A ⊕ B» истинно тогда, когда истинно А или B, но не оба одновременно (то есть A ≠ B).

«Либо пан, либо пропал».

A	B	А ⊕ B

0

также: �A xor B (Паскаль), �A ^ B (Питон, Си)

0

1

0

1

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

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

остаток

Логические основы компьютеров, 10 класс

18 of 42

Операция «исключающее ИЛИ»

18

A⊕B

A

B

=1

Искл. ИЛИ

Логические основы компьютеров, 10 класс

19 of 42

Свойства операции «исключающее ИЛИ»

19

A ⊕ A =

(A ⊕ B) ⊕ B =

A ⊕ 0 =

A ⊕ 1 =

A

0

?

A	B	А ⊕ B
0	0
0	1
1	0
1	1

0

1

0

1

0

1

0

1

0

A

Логические основы компьютеров, 10 класс

20 of 42

Импликация («если …, то …»)

20

Высказывание «A → B» истинно, если не исключено, что из А следует B.

A – «Работник хорошо работает».

B – «У работника хорошая зарплата».

A	B	А → B
0	0
0	1
1	0
1	1

1

0

Логические основы компьютеров, 10 класс

21 of 42

Импликация («если …, то …»)

21

«Если Вася идет гулять, то Маша сидит дома».

A – «Вася идет гулять».

B – «Маша сидит дома».

Маша может пойти гулять �(B=0), а может и не пойти (B=1)!

A	B	А → B
0	0	1
0	1	1
1	0	0
1	1	1

А если Вася не идет гулять?

?

Логические основы компьютеров, 10 класс

22 of 42

Импликация («если …, то …»)

22

A→B

A

B

Логические основы компьютеров, 10 класс

23 of 42

Эквиваленция («тогда и только тогда, …»)

23

Высказывание «A ↔ B» истинно тогда и только тогда, когда А и B равны.

A	B	А ↔ B
0	0	1
0	1	0
1	0	0
1	1	1

Логические основы компьютеров, 10 класс

24 of 42

Эквиваленция («тогда и только тогда, …»)

24

A

B

A↔B

Логические основы компьютеров, 10 класс

25 of 42

Базовый набор операций

25

С помощью операций И, ИЛИ и НЕ можно реализовать любую логическую операцию.

ИЛИ

И

НЕ

базовый набор операций

Сколько всего существует логических операций с двумя переменными?

?

Логические основы компьютеров, 10 класс

26 of 42

Штрих Шеффера, «И-НЕ»

26

A	B	А \| B
0	0	1
0	1	1
1	0	1
1	1	0

Базовые операции через «И-НЕ»:

&

И-НЕ

Логические основы компьютеров, 10 класс

27 of 42

Стрелка Пирса, «ИЛИ-НЕ»

27

A	B	А ↓ B
0	0	1
0	1	0
1	0	0
1	1	0

1

ИЛИ-НЕ

Логические основы компьютеров, 10 класс

28 of 42

Диаграммы Венна (круги Эйлера)

28

A

B

A

B

A

A·B

A

B

A+B

A⊕B

A→B

A↔B

A

B

A

B

Логические основы компьютеров, 10 класс

29 of 42

Логические элементы компьютера

29

&

1

&

НЕ

И

ИЛИ

ИЛИ-НЕ

И-НЕ

значок инверсии

Логические основы компьютеров, 10 класс

30 of 42

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

30

название	для И	для ИЛИ
двойного отрицания
исключения третьего
операции с константами
повторения
поглощения
переместительный
сочетательный
распределительный
законы де Моргана

Логические основы компьютеров, 10 класс

31 of 42

Логические основы компьютеров

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

31

32 of 42

Формализация

32

Прибор имеет три датчика и может работать, если два из них исправны. Записать в виде формулы ситуацию «авария».

A – «Датчик № 1 неисправен».

B – «Датчик № 2 неисправен».

C – «Датчик № 3 неисправен».

Аварийный сигнал:

X – «Неисправны два датчика».

X – «Неисправны датчики № 1 и № 2» или

«Неисправны датчики № 1 и № 3» или

«Неисправны датчики № 2 и № 3».

логическая формула

Формализация – это переход к записи на формальном языке!

!

Логические основы компьютеров, 10 класс

33 of 42

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

33

Порядок вычислений:

скобки
НЕ
И
ИЛИ, исключающее ИЛИ
импликация
эквиваленция

A

B

+

∙

+

B

C

∙

A

С

∙

1 4 2 5 3

Логические основы компьютеров, 10 класс

34 of 42

Составление таблиц истинности

34

A	B	A·B	X
0	0
0	1
1	0
1	1

0
1
2
3

0

1

0

1

0

1

0

1

Логические выражения могут быть:

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

Логические основы компьютеров, 10 класс

35 of 42

Составление таблиц истинности

35

A	B	C	A∙B	A∙C	B∙C	X
0	0	0
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

0
1
2
3
4
5
6
7

0

1

0

1

0

1

0

1

0

1

0

1

0

1

Логические основы компьютеров, 10 класс

36 of 42

Составление таблиц истинности

36

Х = не (А \/ С) \/ не B /\ A

Х = A /\ С → B ⊕ не С

Х = не (A ↓ B) → (не А | не В)

Упростите выражения 2 и 3

Логические основы компьютеров, 10 класс

37 of 42

Логические основы компьютеров

§ 21. Упрощение логических выражений

37

38 of 42

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

38

Логические основы компьютеров, 10 класс

39 of 42

Упрощение логических выражений

39

Шаг 1. Заменить операции ⊕→↔ на их выражения через И, ИЛИ и НЕ:

Шаг 2. Раскрыть инверсию сложных выражений по формулам де Моргана:

Шаг 3. Используя законы логики, упрощать выражение, стараясь применять закон исключения третьего.

Логические основы компьютеров, 10 класс

40 of 42

Упрощение логических выражений

40

раскрыли →

формула де Моргана

распределительный

исключения третьего

повторения

поглощения

Как сделать проще?

?

Логические основы компьютеров, 10 класс

41 of 42

Примеры:

41

Ответ:

Логические основы компьютеров, 10 класс

42 of 42

Задачи (упрощение)

42

Какое логическое выражение равносильно выражению �A ∧ ¬(¬B ∨ C)?

¬A ∨ ¬B ∨ ¬C
A ∧ ¬B ∧ ¬C
A ∧ B ∧ ¬C
A ∧ ¬B ∧ C

Логические основы компьютеров, 10 класс