Логика

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

Математические основы ИНФОРМАТИКИ

Алгебра логики (алгебра высказываний) — раздел математической логики, в котором изучаются логические операции над высказываниями.
Многие математические объекты (целые и рациональные числа, многочлены, векторы, множества) вы изучаете в школьном курсе алгебры, где знакомитесь с такими разделами математики, как алгебра чисел, алгебра многочленов, алгебра множеств и т. д. Для информатики важен раздел математики, называемый алгеброй логики; объектами алгебры логики являются высказывания.
Логические операции

КОНЪЮНКЦИЯ

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

Рассмотрим два высказывания:
A = «Основоположником алгебры логики является Джордж Буль»,
B = «Исследования Клода Шеннона позволили применить алгебру логики в вычислительной технике».
Очевидно, новое высказывание «Основоположником алгебры логики является Джордж Буль, и исследования Клода Шеннона позволили применить алгебру логики в вычислительной технике» истинно только в том случае, когда одновременно истинны оба исходных высказывания.
✑ Для записи конъюнкции используются следующие знаки: И, ∧, *, & .
Например: A И B, A ∧ B, A * B, A & B
Конъюнкцию можно описать в виде таблицы, которую называют таблицей истинности. В таблице истинности перечисляются все возможные значения исходных высказываний (столбцы A и B ),

ДИЗЪЮНКЦИЯ

✑ логическая операция, которая каждым двум высказываниям ставит в соответствие новое высказывание, являющееся ложным тогда и только тогда, когда оба исходных высказывания ложны.
⚑ Дизъюнкцию также называют логическим сложением.

Рассмотрим два высказывания:
A = «Идея использования в логике математической символики принадлежит Готфриду Вильгельму Лейбницу»,
B = «Лейбниц является основоположником бинарной арифметики».
Очевидно, новое высказывание «Идея использования в логике математической символики принадлежит Готфриду Вильгельму Лейбницу или Лейбниц является основоположником бинарной арифметики» ложно только в том случае, когда одновременно ложны оба исходных высказывания.
Для записи дизъюнкции используются следующие знаки: ИЛИ; ∨; |; +
Например: A ИЛИ B; A ∨ B; A | B; A + B .
Дизъюнкция определяется следующей таблицей истинности:

ИНВЕРСИЯ

✑ логическая операция, которая каждому высказыванию ставит в соответствие новое высказывание, значение которого противоположно исходному.
⚑ Инверсию также называют логическим отрицанием.

Для записи инверсии используются следующие знаки: НЕ;¬;−
Например: НЕ А; ¬А; А− .
Инверсия определяется следующей таблицей истинности.

ИМПЛИКАЦИЯ

✑ Сложное логическое выражение, которое истинно во всех случаях, кроме как из истины следует ложь. То есть, данная логическая операция связывает два простых логических выражения, из которых первое является условием (A), а второе (A) является следствием условия (A). .
⚑ Импликацию также называют логическим следованием.

Для записи импликации используют следующие знаки: →, ⇒.
Свойства импликации: A → B = ¬ A ∨ B.
Импликация A→B ложна, если A=1 и B=0. Если A=0, то импликация A→B истинна при любом значении B, (из лжи может следовать истинна).

ЭКВИВАЛЕНТНОСТЬ

✑ сложное логическое выражение, которое истинно на равных значениях переменных A и B .
⚑ Эквивалентность также называют логической равнозначностью.

Для записи эквивалентности используют следующие знаки: ↔, ⇔.
Свойства эквивалентности:

  1. Эквивалентность истинна на равных наборах значений переменных A и B.
  2. КНФ
  3. ДНФ
КНФ ДНФ ➤ подробнее ➤

СТРОГАЯ ДИЗЪЮНКЦИЯ/исключающее ИЛИ

✑ Строгая дизъюнкция истинна, если значения аргументов не равны. .
⚑ Сложение по модулю 2 ( в теории множеств это объединение двух множеств без их пересечения)

Для записи используют следующие знаки: ⊕
Свойства строгой дизъюнкции:
КНФ ДНФ ➤ подробнее ➤

СТРЕЛКА ПИРСА

✑ Бинарная логическая операция, булева функция над двумя переменными. .
⚑ Названа в честь Чарльза Пирса и введена в алгебру логики в 1880-1881гг.

Обозначения: ↓ , ИЛИ-НЕ
Стрелка Пирса, как и конъюнкция, дизъюнкция, отрицание, образует базис для булевых функций двух переменных. При помощи стрелки Пирса, можно построить все остальные логические операции, например:

В электронике стрелка Пирса представлена в виде элемента, который носит название «операция 2ИЛИ-НЕ» (2-in NОR)

ШТРИХ ШИФФЕРА

✑ Булева функция двух переменных или бинарная логическая операция. .
⚑ Введена в рассмотрение Генри Шеффером в 1913 г.

Обозначения: |, эквивалентно операции И-НЕ. Свойства: Штрих Шеффера образует базис для всех булевых функций двух переменных. Применяя штрих Шеффера можно построить остальные операции, например:

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

Порядок выполнения логических операций в сложном логическом выражении:
  1. Действие в скобках (если они есть)
  2. Инверсия(отрицание);
  3. Конъюнкция (логическое умножение);
  4. Дизъюнкция и строгая дизъюнкция (логическое сложение);
  5. Импликация (следствие);
  6. Эквивалентность (тождество).
* Для того чтобы изменить указанный порядок выполнения логических операций, необходимо использовать скобки.
Свойства логических операций:
Логические переменные и логические функции:
Студия Компьютерного Мастерства | Работает на WordPress
Тема от Grace Themes