Алгебра логики. Вильгельм Лейбниц (1646-1716)

Логика – это наука о формах и законах человеческого мышления.

Логика
Джордж Буль (1815-1864). Создал новую область науки - Алгебру логики (Булеву алгебру или Алгебру высказываний).
Вильгельм Лейбниц (1646-1716). Основоположник математической логики (пытался построить первые логические исчисления: арифметические и буквенно-алгебраические).

Алгебра логики (булева алгебра) - это раздел математики, изучающий высказывания, и логические операции над ними.
Цель алгебры логики - описание поведения и структуры логических схем.
Объекты алгебры логики – высказывания.

высказывания

Логическое высказывание – это повествовательное предложение, относительно которого можно однозначно сказать, истинно оно или ложно.
Высказывание или нет?
Сейчас идет дождь.
Жирафы летят на север.
История – интересный предмет.
У квадрата – 10 сторон и все разные.
Красиво!
В городе N живут 2 миллиона человек.
Который час?

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

Высказывание называется простым, если никакая его часть сама не является высказыванием.
Сложные (составные) высказывания строятся из простых с помощью логических связок (и; или; не; если, то; и др).

Так, например, из элементарных высказываний "Петров — врач", "Петров — шахматист"
при помощи связки "и" можно получить составное высказывание
"Петров — врач и шахматист", понимаемое как "Петров — врач, хорошо играющий в шахматы".

При помощи связки "или" из этих же высказываний можно получить составное высказывание
"Петров — врач или шахматист",
понимаемое в алгебре логики как
"Петров или врач, или шахматист, или и врач и шахматист одновременно".

В алгебре логики высказывания обозначают ЗАГЛАВНЫМИ буквами латинского алфавита и называют логическими переменными.
Если высказывание истинно, то значение соответствующей ему логической переменной обозначают единицей (А = 1), а если ложно - нулём (В = 0).
0 и 1 называются логическими значениями.

Так, например, предложение
" Трава зеленая" следует считать высказыванием, так как оно истинное.
Записывается: А=1
Предложение " Лев - птица" тоже высказывание, так как оно ложное.
Записывается: В=0

Пусть через А обозначено высказывание "Тимур поедет летом на море", а через В — высказывание "Тимур летом отправится в горы".

Тогда составное высказывание "Тимур летом побывает и на море, и в горах" можно кратко записать как
А и В
Здесь "и" — логическая связка, А, В — логические переменные, которые могут принимать только два значения - "истина" или "ложь", обозначаемые, соответственно, "1" и "0".

A – Сейчас идет дождь.
B – Форточка открыта.
A и B
A или не B
если A, то B
не A и B
A тогда и только
тогда, когда B
Сейчас идет дождь и открыта форточка.
Сейчас идет дождь или форточка закрыта.
Если сейчас идет дождь, то форточка открыта.
Сейчас нет дождя и форточка открыта.
Дождь идет тогда и только тогда, когда открыта форточка.
Составьте из простых высказываний составные при помощи связок:

Операции над логическими
высказываниями

Операция НЕ
Операция, выражаемая словом "не", называется инверсией или отрицанием и обозначается чертой над высказыванием.
Если высказывание A истинно,
то "не А" ложно, и наоборот.

Высказывание А истинно, когда A ложно, и ложно, когда A истинно.
Пример. "Луна — спутник Земли" (А);
"Луна — не спутник Земли" (А).

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

Операция И
Операция, выражаемая связкой "и", называется конъюнкцией
(лат. conjunctio — соединение)
или логическим умножением
и обозначается точкой " . "
(может также обозначаться знаками ^ или &).

Высказывание А · В истинно тогда и только тогда, когда оба высказывания А и В истинны.
Например, высказывание
"10 делится на 2 и 5 больше 3" истинно, а высказывания:
"10 делится на 2 и 5 не больше 3",
"10 не делится на 2 и 5 больше 3",
"10 не делится на 2 и 5 не больше 3" — ложны.

1
0
также: A·B, A ∧ B,
A & B
0
0
A ∧ B
Таблица истинности конъюнкции

Операция ИЛИ
Операция, выражаемая связкой "или" называется дизъюнкцией
(лат. disjunctio — разделение)
или логическим сложением и обозначается знаком v (или + «плюсом»).

Высказывание А v В ложно тогда и только тогда, когда оба высказывания А и В ложны.
Например, высказывание
"10 не делится на 2 или 5 не больше 3" ложно, а высказывания
"10 делится на 2 или 5 больше 3",
"10 делится на 2 или 5 не больше 3",
"10 не делится на 2 или 5 больше 3"— истинны.

1
0
также: A+B, A ∨ B
1
1
Таблица истинности дизъюнкции

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

Операция ЕСЛИ-ТО
Операция, выражаемая связками "если ..., то", "из ... следует", "... влечет ...",
называется импликацией
(лат. implico — тесно связаны) и обозначается знаком . Высказывание А В ложно тогда и только тогда, когда А истинно, а В ложно.

A – "Работник хорошо работает".
B – "У работника хорошая зарплата".
1
1
1
0
Таблица истинности импликации

Операция РАВНОСИЛЬНО
Операция, выражаемая связками "тогда и только тогда", "необходимо и достаточно", "... равносильно ...", называется эквиваленцией и обозначается знаком или ~.
Высказывание А В истинно тогда и только тогда, когда значения А и В совпадают.

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

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

Определение логической формулы:
1. Всякая логическая переменная и символы "истина" ("1") и "ложь" ("0") - формулы.
2. Если А и В - формулы, то А , А · В ,
А v В , А B , А В - формулы.
3. Никаких других формул в алгебре логики нет.

Порядок выполнения логических операций в сложном логическом выражении
1.Инверсия;
2. Конъюнкция;
3. Дизъюнкция;
4. Импликация;
5. Эквивалентность.

Определите истинность составного высказывания:
(А&В) & (C\/D), состоящего из простых высказываний:
А = {Принтер – устройство вывода информации},
В = {Процессор – устройство хранения информации},
С = {Монитор – устройство вывода информации},
D = {Клавиатура – устройство обработки информации}.
Сначала на основании знания устройства компьютера устанавливаем истинность простых высказываний:
А = 1, В = 0, С = 1, D = 0.
Определим теперь истинность составного высказывания, используя таблицы истинности логических операций:
( 1 & 0 ) &(1 \/ 0) = (0 & 1) & (1 \/ 0) = 0
Составное высказывание ложно.

Даны простые высказывания:
А = {Принтер – устройство ввода информации},
В = {Процессор – устройство обработки информации},
С = {Монитор – устройство хранения информации},
D = {Клавиатура – устройство ввода информации}.
Определите истинность составных высказываний:
а) (А & В) & (C v D);
б) (А & В) => (C v D);
в) (А v В) ⬄ (C & D);
г) А ⬄ B .

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

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

Построение таблиц истинности для логических выражений
подсчитать n - число переменных в выражении
подсчитать общее число логических операций в выражении
установить последовательность выполнения логических операций
определить число столбцов в таблице
заполнить шапку таблицы, включив в неё переменные и операции
определить число строк в таблице без шапки: m =2n
выписать наборы входных переменных
провести заполнение таблицы по столбцам, выполняя логические
операции в соответствии с установленной последовательностью

А V A & B
n (число переменных) = 2,
m (количество строк без шапки)= 22 = 4.
Операций – 2, значит количество столбцов будет: n+2=4
Приоритет операций: &, V
Пример построения таблицы истинности

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

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

ЗАКОНЫ АЛГЕБРЫ ЛОГИКИ

Закон тождества
A = A
Закон тождества означает, что в процессе рассуждения нельзя подменять одну мысль другой, одно понятие другим. При нарушении этого закона возможны логические ошибки.
Например, рассуждение Правильно говорят, что язык до Киева доведет, а я купил вчера копченый язык, значит, теперь смело могу идти в Киев неверно, так как первое и второе слова «язык» обозначают разные понятия.
Всякое понятие и суждение тождественно самому себе.

Закон непротиворечия
A & notA = 0
Не могут быть одновременно истинны утверждение и его отрицание.
То есть если высказывание А— истинно, то его отрицание не А должно быть ложным (и наоборот). Тогда их произведение будет всегда ложным.
Это равенство часто используется при упрощении сложных логических выражений.
Примеры невыполнения закона непротиворечия:
1. На Марсе есть жизнь и на Марсе жизни нет.
2. Оля окончила среднюю школу и учится в X классе.

Закон исключения третьего
A and not A = 1
В один и тот же момент времени высказывание может быть либо истинным, либо ложным, третьего не дано.
Истинно либо А, либо не А.
Примеры выполнения закона исключенного третьего:
1. Число 12345 либо четное, либо нечетное, третьего не дано.
2. Предприятие работает убыточно или безубыточно.
3. Эта жидкость является или не является кислотой.

Закон двойного отрицания
Not (notA)=1
Если отрицать дважды некоторое высказывание, то в результате получается исходное высказывание.
Например, высказывание
А = Матроскин — кот эквивалентно высказыванию
А = Неверно, что Матроскин не кот.

ЛОГИЧЕСКИЕ ЭЛЕМЕНТЫ
КОМПЬЮТЕРА

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

Логическими элементами компьютеров являются электронные схемы И, ИЛИ, НЕ, И—НЕ, ИЛИ—НЕ и другие.

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

Логические элементы компьютера
НЕ
И
ИЛИ
ИЛИ-НЕ
И-НЕ
значок инверсии

Логические элементы компьютера
Любое логическое выражение можно реализовать на элементах И-НЕ или ИЛИ-НЕ.
И:
НЕ:
ИЛИ:

Составление схем
последняя операция - ИЛИ
&
И

Триггер (англ. trigger – защёлка)
– это логическая схема, способная хранить 1 бит информации (1 или 0). Строится на 2-х элементах ИЛИ-НЕ или на 2-х элементах И-НЕ.
основной
выход
вспомогательный
выход
reset, сброс
set, установка
обратные связи
1
1
0
0
0
0

Полусумматор
– это логическая схема, способная складывать два одноразрядных двоичных числа.
0 0
0 1
0 1
1 0