Материал: 5469

6

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

Логической основой компьютера является алгебра логики, которая рассматривает логические операции над высказываниями.

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

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

Пример. «3 – простое число» является высказыванием, поскольку оно истинно.

Не всякое предложение является логическим высказыванием.

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

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

Пример. «x+2>5» – высказывательная форма, которая при x>3 является истинной, иначе ложной.

Алгебра логики рассматривает любое высказывание только с одной точки зрения – является ли оно истинным или ложным. Слова и словосочетания «не», «и», «или», «если..., то», «тогда и только тогда» и другие позволяют из уже заданных высказываний строить новые высказывания. Такие слова и словосочетания называются логическими связками.

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

Пример. Высказывание «Число 6 делится на 2» – простое высказывание. Высказывание «Число 6 делится на 2, и число 6 делится на 3» – составное высказывание, образованное из двух простых с помощью логической связки «и».

Истинность или ложность составных высказываний зависит от истинности или ложности элементарных высказываний, из которых они состоят.

Чтобы обращаться к логическим высказываниям, им назначают имена. Пример. Обозначим через А простое высказывание «число 6 делится на 2», а

через В простое высказывание «число 6 делится на 3». Тогда составное высказывание «Число 6 делится на 2, и число 6 делится на 3» можно записать как «А и В». Здесь «и» – логическая связка, А, В – логические переменные, которые могут

7

принимать только два значения – «истина» или «ложь», обозначаемые, соответственно, «1» и «0».

2.1.Логическое умножение (конъюнкция)

Объединение двух (или нескольких) высказывании в одно с помощью союза «и» называется операцией логического умножения или конъюнкцией,

логическим И.

Для обозначения операции логического умножения, или конъюнкции, ис-

пользуют символы Ʌ , &, . (точку, которую можно опускать), AND.

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

Следовательно, составное высказывание принимает значение “ложь”, когда ложно хотя бы одно из этих высказываний.

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

Перейдём теперь от записи высказываний на естественном языке к их записи на формальном языке алгебры высказываний (алгебры логики). Образуем составное высказывание F, которое получится в результате конъюнкции двух простых высказываний:

F = А & В либо (F = А Ʌ В)

С точки зрения алгебры высказываний мы записали формулу функции логического умножения, аргументами которой являются логические переменные А и В, которые могут принимать значения «истина» (1) и «ложь» (0).

Сама функция логического умножения F также может принимать лишь два значения «истина» (1) и «ложь» (0). Значение логической функции можно определить с помощью таблицы истинности данной функции, которая показывает, какие значения принимает логическая функция при всех возможных наборах её аргументов (таблица 1).

8

Таблица 1 – Таблица истинности функции логического умножения (конъюнкции)

По таблице истинности легко определить истинность составного высказывания, образованного с помощью операции логического умножения. Рассмотрим, например, составное высказывание «2 • 2 = 4 и З • 3 = 10».

Первое простое высказывание истинно (А = 1), а второе высказывание ложно (В = 0); по таблице определяем, что логическая функция принимает значение “ложь” (F = 0), то есть данное составное высказывание ложно.

2.2.Логическое сложение (дизъюнкция)

Объединение двух (или нескольких) высказываний с помощью союза «или» называется операцией логического сложения или дизъюнкцией.

Операцию логического сложения (дизъюнкцию, логическое ИЛИ) принято обозначать символами «V», «+», OR.

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

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

Запишем теперь операцию логического сложения на формальном языке алгебры логики.

Образуем составное высказывание F, которое получится в результате дизъюнкции двух простых высказываний:

F = A v В

С точки зрения алгебры высказываний мы записали формулу функции логи-

9

ческого сложения, аргументами которой являются логические переменные А и В. Значение логической функции можно определить с помощью таблицы истинности данной функции, которая показывает, какие значения принимает логическая функция при всех возможных наборах ее аргументов (таблица 2).

Таблица 2 – Таблица истинности функции логического сложения (дизъюнкция)

По таблице истинности легко определить истинность составного высказывания, образованного с помощью операции логического сложения. Рассмотрим, например, составное высказывание «2 • 2 = 4 или 3 • 3 = 10».

Первое простое высказывание истинно (А = 1), а второе высказывание ложно (В = 0); по таблице определяем, что логическая функция принимает значение истина (F = 1), то есть данное составное высказывание истинно.

2.3.Логическое отрицание (инверсия)

Присоединение частицы «не» к высказыванию называется операцией логиче-

ского отрицания.

Операция логического отрицания является унарной, так как имеет один аргу-

мент. Иначе её называют инверсией, дополнением, НЕ и обозначают Ā или ¬А,

NOT A.

Логическое отрицание (инверсия) делает истинное высказывание ложным и, наоборот, ложное — истинным.

Пусть А = «Два умножить на два равно четырём» — истинное высказывание, тогда высказывание F = «Два умножить на два не равно четырём», образованное с помощью операции логического отрицания, — ложно.

Образуем высказывание F, являющееся логическим отрицанием А:

F = Ā

Истинность такого высказывания задаётся таблицей истинности функции логического отрицания (таблица 3).

Таблица 3 – Таблица истинности функции логического отрицания (инверсия)

10

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

Например, высказывание:

«Два умножить на два не равно четырём» ложно (А = 0), а полученное из него в результате логического отрицания высказывание

«Два умножить на два равно четырём» истинно (F = 1).

2.4.Логическое следование (импликация)

Операцию логического следования иначе называют импликацией и для обозначения используют символ → "следовательно" и выражается словами ЕСЛИ … , ТО ….

Логическое следование: ИМПЛИКАЦИЯ – связывает два простых логических выражения, из которых первое является условием (А), а второе (В) – следствием из этого условия. Результатом ИМПЛИКАЦИИ является ЛОЖЬ только тогда, когда условие А истинно, а следствие В ложно (таблица 4).

Импликацией А→В называется высказывание, которое ложно тогда и только тогда, когда А истинно и В ложно.

Таблица 4 – Таблица истинности функции логического следования (импликация)

2.5.Логическое тождество (эквиваленция)

Операцию логического тождества обозначают символами =, ↔, ~. Интуитивно можно догадаться, что высказывания эквивалентны (равносиль-

ны), когда их значения истинности одинаковы.

Например, эквивалентны высказывания: "железо тяжёлое" и "пух лёгкий", так же как и высказывания: "железо лёгкое" и "пух тяжёлый". Обозначим эквиваленцию символом ↔ и запись "А ↔ В" будем читать "А эквивалентно В", или "А равносильно В", или "А, если и только если В".

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

Высказывание типа "А, если и только если В" можно заменить высказыванием "Если А, то В и, если В, то А".