Алгебра логики (8 класс)

АЛГЕБРА ЛОГИКИ

Основы математической логики

Информатика · 8 класс

0 1

И ИЛИ

НЕ ¬

Что мы узнаем сегодня

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

Логические переменные

1

2

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

значения ИСТИНА (1) и ЛОЖЬ (0)

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

Три операции

3

4

как проверить любое выражение

инверсия, конъюнкция, дизъюнкция

Практика

Законы логики

6

5

и порядок выполнения операций

решаем задачи и строим таблицы

2

Немного истории

IV в. до н. э.

XX век

1847 год

XVII век

Аристотель

Г. Лейбниц

Джордж Буль

К. Шеннон

применил алгебру логики

заложил основы формальной логики:

предложил идею записывать

создал алгебру логики — теперь

к электрическим схемам ЭВМ

рассуждения символами, как в алгебре

она называется булевой алгеброй

учение о суждениях и выводах

Компьютер «понимает» только два состояния: есть сигнал (1) и нет сигнала (0). Поэтому вся его работа описывается алгеброй логики.

3

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

Высказывание — это повествовательное предложение, о котором можно точно сказать,

истинно оно или ложно.

✗ Это не высказывания

✓ Это высказывания

• Который час? (вопрос)

• Москва — столица России. (истина)

• 2 + 2 = 5. (ложь)

• Реши задачу! (побуждение)

• Все квадраты — прямоугольники. (истина)

• Какая красивая песня! (мнение)

• Число 7 делится на 2. (ложь)

• x + 5 = 8 (неизвестен x)

4

Логические переменные и величины

Высказывания обозначают латинскими буквами: A, B, C, X, Y …

1

0

ИСТИНА

ЛОЖЬ

False · высказывание неверно

True · высказывание верно

нет сигнала в цепи

есть сигнал в цепи

Пример записи

• A = «Земля вращается вокруг Солнца» → A = 1

• B = «У треугольника четыре стороны» → B = 0

5

Три основные логические операции

НЕ

ИЛИ

И

Дизъюнкция

Конъюнкция

Инверсия

¬A, A, not A

A ∧ B, A · B

A ∨ B, A + B

логическое умножение:

отрицание:

логическое сложение:

истинно, когда истинно

меняет значение

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

оба истинны

на противоположное

хотя бы одно

2 операнда

1 операнд

2 операнда

Порядок выполнения: 1) скобки 2) НЕ 3) И 4) ИЛИ

6

3» (B = 1) → ¬B = «5 ≤ 3» (¬B = 0) • Двойное отрицание: ¬(¬A) = A В русском языке: «неверно, что …» 7 " width="640"

Инверсия — операция НЕ

Инверсия делает из истинного высказывания ложное, а из ложного — истинное.

Примеры

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

A

1

¬A

0

0

1

• A = «Сегодня идёт дождь»

• ¬A = «Сегодня НЕ идёт дождь»

• B = «5 3» (B = 1) → ¬B = «5 ≤ 3» (¬B = 0)

• Двойное отрицание: ¬(¬A) = A

В русском языке:

«неверно, что …»

7

Конъюнкция — операция И

A ∧ B истинно тогда и только тогда, когда истинны ОБА высказывания.

Пример

«Идёт дождь И светит солнце» — верно только тогда,

когда одновременно и дождь, и солнце.

A

0

B

0

0

A ∧ B

0

1

1

1

0

0

1

0

1

Похоже на умножение чисел 0 и 1:

0·0 = 0 0·1 = 0 1·0 = 0 1·1 = 1

Одна ложь — и всё выражение ложно.

8

Дизъюнкция — операция ИЛИ

A ∨ B ложно только тогда, когда ложны ОБА высказывания.

Пример

«Я поеду на автобусе ИЛИ на метро» — верно,

если хотя бы один вариант выполнен (можно и оба).

A

0

B

0

0

A ∨ B

0

1

1

1

1

0

1

1

1

Похоже на сложение, но 1 + 1 = 1:

0+0 = 0 0+1 = 1 1+0 = 1 1+1 = 1

Одна истина — и всё выражение истинно.

9

Сводная таблица истинности

Все три операции для двух переменных сразу:

A

B

0

¬A

0

0

1

A ∧ B

1

1

A ∨ B

0

0

1

1

1

0

0

0

1

0

0

1

1

1

Как считать число строк: N = 2ⁿ, где n — количество переменных.

2 переменные → 4 строки, 3 переменные → 8 строк, 4 → 16 строк.

10

Строим таблицу истинности: пример

Задача: построить таблицу истинности для F = ¬A ∨ B

Порядок действий

A

0

B

0

¬A

0

1

1

F = ¬A ∨ B

1

1

0

1

1

1

1

0

0

0

1

• Считаем переменные: A и B → 2ⁿ = 4 строки

• Выписываем все наборы значений A и B

• Сначала вычисляем ¬A (операция НЕ)

• Затем ¬A ∨ B (операция ИЛИ)

• Записываем результат в столбец F

Ответ: F ложно только при A = 1, B = 0

11

Основные законы алгебры логики

Законы нуля и единицы

Двойное отрицание

Переместительный

¬(¬A) = A

A ∧ B = B ∧ A

A ∧ 1 = A A ∧ 0 = 0

A ∨ 1 = 1 A ∨ 0 = A

A ∨ B = B ∨ A

Законы де Моргана

Противоречия / исключ. третьего

Идемпотентности

A ∧ ¬A = 0

A ∧ A = A

¬(A ∧ B) = ¬A ∨ ¬B

A ∨ ¬A = 1

A ∨ A = A

¬(A ∨ B) = ¬A ∧ ¬B

Законы помогают упрощать сложные логические выражения

12

Проверь себя

Какие из предложений являются высказываниями?

а) Париж — столица Франции; б) Сколько тебе лет?;

в) 15

1

Определи значение выражения при A = 1, B = 0:

а) A ∧ B; б) A ∨ B; в) ¬A ∨ B; г) ¬(A ∧ B)

2

Построй таблицу истинности для выражения

F = (A ∨ B) ∧ ¬B

3

Запиши на языке логики: «Число делится на 2 и на 3»,

если A = «делится на 2», B = «делится на 3».

4

13

Подсказка: сначала определи порядок операций — скобки, НЕ, И, ИЛИ

Главное на уроке

Высказывание

предложение, которое либо истинно (1), либо ложно (0)

Алгебра логики

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

Три операции

инверсия (НЕ), конъюнкция (И), дизъюнкция (ИЛИ)

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

показывает результат при всех наборах значений, строк 2ⁿ

Порядок операций

скобки → НЕ → И → ИЛИ

Алгебра логики — язык, на котором «думают» компьютеры