Базовые элементы алгебры логики

Базовые элементы алгебры логики

Ключевые слова

• алгебра логики
• высказывание
• логическая операция
• конъюнкция
• дизъюнкция
• инверсия

Л огик а

Аристотель (384-322 до н.э.). Основоположник формальной логики (понятие, суждение, умозаключение).

Джордж Буль (1815-1864). Создал новую область науки - Математическую логику (Булеву алгебру или Алгебру высказываний).

Клод Шеннон (1916-2001). Его исследования позволили применить алгебру логики в вычислительной технике

Алгебра

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

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

Высказывание - это предложение на любом языке, содержание которого можно однозначно определить как истинное или ложное .

В русском языке высказывания выражаются повествовательными предложениями:

Земля вращается вокруг Солнца .

Москва - столица.

Но не всякое повествовательное предложение является высказыванием:

Это высказывание ложное.

Побудительные и вопросительные предложения высказываниями не являются.

Без стука не входить!

Откройте учебники.

Ты выучил стихотворение?

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

Алгебра логики определяет правила записи, вычисления значений, упрощения и преобразования высказываний.

В алгебре логики высказывания обозначают буквами и называют логическими переменными .

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

0 и 1 называются логическими значениями .

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

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

Другое название: логическое умножение.

Обозначения:  ,  , & , И.

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

Графическое представление

А

0

В

А & В

0

0

0

1

1

1

0

0

0

1

1

A

B

А & В

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

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

Другое название: логическое сложение .

Обозначения: V , |, ИЛИ, +.

Графическое представление

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

А

0

В

А V В

0

0

0

1

1

1

0

1

1

1

1

A

B

А V В

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

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

Другое название: логическое отрицание.

Обозначения: НЕ, ¬ , ¯ .

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

Графическое представление

А

0

Ā

1

1

0

A

Ā

Логические операции имеют следующий приоритет:

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

Подведем итоги:

Высказывание – это предложение на любом языке, содержание которого

можно однозначно определить как истинное или ложное.

Основные логические

операции

Дизъюнкция

Конъюнкция

Инверсия

А

A

0

A

Ā

0

0

1

B

1

B

A & B

0

0

0

0

0

A V B

1

0

1

0

1

1

1

1

0

0

1

0

1

0

1

1

1

1

Приоритет выполнения логических операций: ¬, &, V .