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

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

Логические операции

Логика

• Слово «логика» происходит от древнегреческого «λόγος», имеющего значения: рассуждение, мысль, разум.
• Логика — наука о том, как правильно рассуждать, делать выводы, доказывать утверждения.

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

• Высказывание — это повествовательное предложение, о котором всегда можно сказать, истинно оно или ложно.
• Пример:
• «6 — четное число» — это истинное высказывание.
• «Рим — столица Франции» — ложное высказывание.

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

• Побудительные и вопросительные предложения не являются высказываниями.
• Пример:
• Приходи на день рождения;
• Кто стучится в дверь ко мне?
• Информатика — интересный предмет;
• Х > 0.

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

• Алгебра логики определяет правила записи и вычисления значений высказываний.
• В алгебре логики высказывания обозначают прописными латинскими буквами.
• Для истинного высказывания значение равно единице (А = 1), для ложного — нулю (В = 0).

​

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

• Создателем алгебры�логики является�живший в ХIХ веке�английский математик�Джордж Буль, в честь которого эта алгебра названа булевой алгеброй высказываний.

Виды высказываний

• Высказывание может быть простым или сложным (составным).
• Высказывание «идет дождь» — простое, а истинное оно или ложное зависит от того, какая погода сейчас за окном.

​

Виды высказываний

• Сложные (составные) высказывания строятся из простых с помощью логических связок: не, и, или.
• Составные высказывания:
• «идет снег» И «2 * 2 = 4»;
• «идет дождь» ИЛИ «2 * 2 = 5».

​

Логические операции

• Логическая операция — операция над высказываниями, позволяющая составлять новые высказывания путём соединения простых высказываний с помощью логических связок.

Инверсия

• Инверсия или логическое отрицание образуется присоединением к высказыванию частицы «не».
• Инверсия обозначается: НЕ, чертой над высказыванием или знаком ¬.
• Логическое отрицание преобра-зует истинное высказывание в ложное и, наоборот, ложное — в истинное.

Ā

¬А

Пример:

• Ввысказывание А: «Основоположником алгебры логики является Джорж Буль» — истинно,�а высказывание ¬А:�«неверно, что основоположником алгебры логики является Джорж Буль» — ложно.

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

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

Таблица истинности инверсии

1

0

• Задача 1. Иван-царевич пришел в замок Змея Горыныча вызволять Василису Прекрасную. Видит три двери, на которых нанесены надписи: «Здесь сидит Василиса», «Эта комната пуста», «Здесь нет Змея Горыныча». Баба Яга сказала Ивану, что в замке Змея на дверях все надписи неверные. Как Ивану-царевичу не попасть в лапы Змея Горыныча и спасти Василису?

Конъюнкция

• Конъюнкция (лат. conjunctio — соединение) или логическое умножение — это операция, объединяющая простые высказывания с помощью логической связки «и».
• Обозначение конъюнкции:� И, точка (⋅), &, /\, and.

Пример:

• высказывание�«2 * 2 = 4 И 5 > 3»

истинно;

• высказывания
• «2 * 2 = 4 И 5 < 3»,
• «2 * 2 ≠ 4 И 5 > 3»,
• «2 * 2 ≠ 4 И 5 < 3»

ложны.

Таблица истинности конъюнкции

0

0

0

1

Дизъюнкция

• Дизъюнкция (лат. disjunctio — разделение) или логическое сложение — это операция, выражаемая связкой «или».
• Обозначение дизъюнкции:� ИЛИ, +, \/, |, or.

Пример:

• Высказывание
• «2 * 2 ≠ 4 ИЛИ 5 < 3»

ложно;

• Высказывания
• «2 * 2 = 4 ИЛИ 5 > 3»,
• «2 * 2 = 4 ИЛИ 5 < 3»,
• «2 * 2 ≠ 4 ИЛИ 5 > 3»

истинны.

Таблица истинности дизъюнкции

0

1

1

1

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

• Инверсия (не)
• Конъюнкция (и)
• Дизъюнкция (или)
• Для изменения порядка выполнения логических операций используются круглые скобки.

• Задача 2. На острове живут лжецы и людоеды. Каждый житель либо лжец, который всегда говорит неправду, либо — людоед. Вы встретили туземца и спросили у него, кем он является. Туземец ответил: «Я — лжец». Опасна ли для вас встреча с туземцем?

• Задача 3. Найдите значение выражений:

а) (0 \/ 1) \/ (1 \/ 0);

б) ¬(1\/ 1);

в) 1 & (1 & 0);

г) (1 & 1) & 1.

​

• Задача 4. Для какого целого числа x верно только одно утверждение из двух: 1). x > –21; 2). x > –22.
• Задача 5. Кролик утверждает, что Винни-Пух съел не более 19 баночек мёда, Пятачок — что не более 18 баночек, ослик Иа — что не более 17. Сколько баночек мёда съел Винни-Пух, если из трех этих утверждений истинно только одно?