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

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

Аристотель
Древнегреческий философ
Основоположник логики
Исследовал различные формы рассуждений , ввел понятие силлогизма
384 — 322 до н. э.

Рене Декарт
1596 − 1650
Французский
философ,
математик, механик, физик и физиолог
Рекомендовал в логике использовать математические методы

Готфрид Вильгельм Лейбниц
1646 − 1716
Немецкий философ,
логик, математик,
механик, физик, юрист, историк, дипломат, языковед и изобретатель
Предложил в логике использовать двоичную систему счисления и математическую символику

Джордж Буль
1815 − 1864
Английский математик и логик
Основоположник математической логики
«Математический анализ логики»
1847

Алгебра логики
раздел математической логики, в котором изучаются логические операции над высказываниями
Алгебра логики = Булева алгебра
НЕ учитываем смысл высказываний

Высказывание
Предложение, относительно которого имеет смысл утверждать, истинно оно или ложно
Истинностные значения:
- Ложь или Истина
- 0 или 1

Высказывания
Простые
Сложные
выделить некоторую часть, которая сама является высказыванием и не совпадает по смыслу со всем высказыванием
НЕЛЬЗЯ
МОЖНО

Пример
Простое высказывание
«Ивдель − это город»
Сложное высказывание
«Ивдель − это красивый и культурный город»

Обозначения
Большие буквы латинского алфавита
А – высказывание
А = 1 – высказывание истинно
А = 0 – высказывание ложно

Высказывательные переменные
Всякая большая буква латинского алфавита как некоторое переменное высказывание, которое может принимать значения 0 или 1, если не сказано, что данная буква обозначает конкретное высказывание

Логические связки
Инверсия (отрицание)
Конъюнкция (и)
Дизъюнкция (или)
Импликация (следование)
Эквиваленция

Инверсия (отрицание)
Нет; не; неверно, что…
¬, ′ , 

Пример
А = «Ивдель − культурный город!»
Инверсия
¬ А = «Неверно, что Ивдель − культурный город!»

Конъюнкция
И; а; но...
&, ∧, ⋅
Логическое умножение

Пример
А = «В Ивделе светит солнце»
В = «В Ивделе идёт дождь»
Конъюнкция
А & В = «В Ивделе светит солнце и идёт дождь»

Задания
Известно, что высказывание А&В истинно.
Что можно сказать об истинности высказываний А и В?
Известно, что высказывание А&В ложно.
Что можно сказать об истинности высказываний А и В?

Дизъюнкция
Или; либо…
∨
Логическое сложение

Пример
А = «В Ивделе светит солнце»
В = «В Ивделе идёт дождь»
Дизъюнкция
А ∨ В = «В Ивделе светит солнце или идёт дождь»

Задания
Известно, что высказывание А∨В истинно.
Что можно сказать об истинности высказывания А ∧В?
Известно, что высказывание А∨В ложно.
Что можно сказать об истинности высказывания А ∧В?

Импликация
Следует; влечет; если.. то..; тогда; вытекает..
⇒, →

Пример
А = «В Ивделе идёт дождь»
В = «В Ивделе мокрые улицы»
Импликация
А ⇒ В = «В Ивделе идёт дождь, следовательно, в Ивделе мокрые улицы»

Задания
Известно, что высказывание А⇒В истинно.
Что можно сказать об истинности высказываний А и В?
Известно, что высказывание А⇒В ложно.
Что можно сказать об истинности высказываний А ∧В и А∨В?

Эквиваленция
Эквивалентно; равносильно; если и только если; тогда и только тогда; в том, и только в том случае…
⇔, ~

Пример
А = «В Ивделе идёт дождь»
В = «В Ивделе мокрые улицы»
Эквиваленция
А ⇔ В = «В Ивделе идёт дождь тогда и только тогда, когда в Ивделе мокрые улицы»

Задание
Известно, что высказывание А~В истинно.
Что можно сказать об истинности высказываний ¬А ~В и А→В?

Формулы
1) большие буквы латинского алфавита, снабжённые, быть может, штрихами или индексами и обозначающие высказывания или высказывательные переменные

Формулы
2) Если a и b – формулы, то выражения
¬a, a & b, a ∨ b, a → b, a~ b
тоже являются формулами
3) Других формул нет

Приоритет логических связок
Инверсия
Конъюнкция
Дизъюнкция
Импликация и эквиваленция

Логическая возможность формулы
Формула a(A1, A2, …, An)
Всякий набор конкретных значений истинности для букв A1, A2, …, An

Таблица логических возможностей
Таблица , содержащая перечень всевозможных логических возможностей формулы а

Таблица логических возможностей
Формула a(A1, A2)

Формула a(A1, A2, A3)

Пусть a и b – две формулы, а
A1, A2, …, An – все высказывательные переменные , входящие в запись хотя бы одной из этих формул.
Общей логической возможностью формул называется всякий набор конкретных значений истинности для высказывательных переменных A1, A2, …, An

Пример
Найти общие логические возможности формул

Таблица истинности
Таблица ,в которой приведён перечень всевозможных логических возможностей формулы а вместе с указанием её значений в каждой логической возможности

Формулы a и b называются равносильными, если во всякой общей логической возможности они принимают одинаковые значения
a ≡ b

Формула называется тождественно истинной (тавтологией) , если во всех логических возможностях она принимает одно и то же значение, равное 1
a ≡ 1

Формула называется тождественно ложной (противоречием) , если во всех логических возможностях она принимает одно и то же значение, равное 0
a ≡ 0

Задача
Докажите тождественную истинность формулы
a → (b → a)

a → (b → a)

a → (b → a)

a → (b → a)

Задача
Докажите тождественную истинность формулы
a → (b → a)
Постройте таблицу истинности для формулы
¬((a → b)&(b → a))

f=¬((a → b)&(b → a))

f=¬((a → b)&(b → a))

f=¬((a → b)&(b → a))

f=¬((a → b)&(b → a))

f=¬((a → b)&(b → a))

f=¬((a → b)&(b → a))

ЗАКОНЫ ЛОГИКИ

1. Тождества
a & a ≡ a
a ∨ a ≡ a

2. Переместительный
a & b ≡ b & a
a ∨ b ≡ b ∨ a

3. Сочетательный
a & (b & с) ≡ (a & b) & с
a ∨ (b ∨ с) ≡ (a ∨ b) ∨ с

4. Распределительный
a& (b∨с) ≡ (a&b) ∨ (a&с)
a ∨ (b & с) ≡ (a ∨ b) & (a ∨ с)

5. Закон двойного отрицания
¬(¬a) ≡ a

6. Законы поглощения
a & (a ∨ b) ≡ a
a ∨ (a & b) ≡ a

Огастес де Морган
Шотландский математик и логик
Первый президент Лондонского математического общества
1847 − элементы логики высказываний независимо от Джорджа Буля
1806 — 1871

7. Законы де Моргана
¬(a ∨ b) ≡ ¬a & ¬ b
¬(a & b) ≡ ¬a ∨ ¬ b

8. Закон исключённого третьего
¬a ∨ a ≡ 1

9. Закон противоречия
¬a & a ≡ 0

10. Свойства тавтологии и противоречия
1 & a ≡ a 1 ∨ a ≡ 1
0 & a ≡ 0 0 ∨ a ≡ a
¬ 0 ≡ 1 ¬ 1 ≡ 0

11. Закон контрапозиции (контроппозиции)
a → b ≡ ¬b → ¬ a

12. Правило исключения импликации
a → b ≡ ¬ a ∨ b

13. Правило исключения эквиваленции
a ~ b ≡ (a → b) &(b → a)

Задача
Докажите тождественную истинность формулы c помощью законов логики
a → (b → a)

Задача
Упростите формулу
¬((a → b)&(b → a))

РЕЛЕЙНО-КОНТАКТНЫЕ СХЕМЫ

Двухполюсный переключатель
Два состояния:
«замкнуто» – 1
«разомкнуто» – 0

Инверсия
Разомкнут, когда замкнут А
Замкнут, когда разомкнут А

Последовательное включение
Конъюнкция

Параллельное включение
Дизъюнкция

Множество высказываний и множество переключательных схем одинаково устроены (изоморфны)
Это можно использовать при решении задач

Анализ схем
Для данной схемы строим формулу
Упрощаем её с помощью законов логики
Строим более простую схему, которая обладает теми же электрическими свойствами, что и исходная

Задача
Упростить схему

Упрощённая схема

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