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

Основы алгебры логики

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

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

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

Употребляемые в обычной речи слова и словосочетания {НЕ}, {И}, {ИЛИ}, {ЕСЛИ ..., ТО}, {ТОГДА И ТОЛЬКО ТОГДА} и т.п., позволяют из уже заданных высказываний строить новые высказывания. Такие слова и словосочетания называются логическими связками.

Для обращения к логическим высказываниям, им назначают имена.

Каждая логическая связка рассматривается как операция над логическими высказываниями и имеет свое название и обозначение:

• Операция, выражаемая связкой {НЕ}, называется отрицанием и обозначается чертой над высказыванием или знаком ¬. Высказывание А истинно, когда А ложно, и ложно, когда А истинно, например: {Луна —

___

спутник Земли} (А); {Луна — не спутник Земли} (А).

• Операция, выражаемая связкой {И}, называется конъюнкцией или логическим умножением и обозначается точкой •, или знаками Λ или &. Высказывание А•В истинно тогда и только тогда, когда оба высказывания А и В истинны.

• Операция, выражаемая связкой {ИЛИ} называется дизъюнкцией или логическим сложением и обозначается знаком v или +. Высказывание АvВ ложно тогда и только тогда, когда оба высказывания А и В ложны.

• Операция, выражаемая связками {ЕСЛИ ..., ТО}, {ИЗ ... СЛЕДУЕТ}, {... ВЛЕЧЕТ ...}, называется импликацией и обозначается знаком . Высказывание АВ ложно тогда и только тогда, когда А истинно, а В ложно.

• Операция, выражаемая связками {ТОГДА И ТОЛЬКО ТОГДА}, {НЕОБХОДИМО И ДОСТАТОЧНО}, {... РАВНОСИЛЬНО ...}, называется эквиваленцией или двойной импликацией и обозначается знаком ↔ или ~. Высказывание А↔B истинно тогда и только тогда, когда значения А и В совпа­дают.

__

Импликацию можно выразить через дизъюнкцию и отрицание: А  В = А v В

Эквиваленцию можно выразить через отрицание, дизъюнкцию и конъюнкцию:

___ ___

А ↔ В = (А v В) • (В v А)

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

Порядок выполнения логических операций задается круглы­ми скобками. Но для уменьшения числа скобок счи­тают, что сначала выполняется операция отрицания, затем — конъюнкция, после конъюнкции — дизъюнкция, и в, последнюю очередь, — импликация.

Под логической формулой понимается всякая логическая переменная и

___

символы {1} - истина и {0} - ложь, а также записи: А, А•В, АvВ, АВ, А↔В.

Пример 1: высказывание {ЕСЛИ КУПИТЬ КОМПЬЮТЕР, ТО МОЖНО РАБОТАТЬ В WINDOWS’VISTA} формализуется в виде формулы: АvBC, которая принимает значение истина, а при некоторых других сочетаниях — значение ложь. Такие формулы называются выполнимыми. Некоторые формулы принимают значение истина при лю­бых значениях истинности входящих в них переменных. Такие формулы называются тождественно-истинными формулами или тавтологиями. Высказывания, которые формализуются тавтологиями, назы­ваются логически истинными высказываниями.

Пример 2: высказывание {BIOS — САМАЯ ГЛАВНАЯ МИКРОСХЕМА, И ЕСТЬ

___

МИКРОСХЕМЫ ГЛАВНЕЕ BIOS} формализуется в виде формулы: А•А. Эта

___

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

Если две формулы А и В одновременно, т. е. при одина­ковых наборах значений входящих в них переменных, принимают одинаковые значения, то они называются равносильными. Равносильность двух формул алгебры логики обозначается символами = или ≡ и проверяется таблицами истинности.

Задача 1: Какие из приведённых предложений являются высказываниями? Какие из них высказывания – простые, какие составные?

1. «Число √2 является иррациональным».

2. «Неверно, что число √2 является иррациональным». _

3. «Если число √2 является иррациональным, то число √2+1 также является иррациональным».

4. «Каков объем памяти ПК?»

5. «Идите включать компьютер».

Решение 1: Первые 3 предложения являются высказываниями, последние 2 – нет. Высказывания 1 и 3 истинны, высказывание 2 – ложно. Более точно, значение истинности высказываний 1 и 3 есть истина, а значение истинности высказывания 2 есть ложь.

Анализ высказываний 1 и 3 с точки зрения их «внутреннего строения»: высказывание 1 можно назвать простым. Высказывания 2 и 3 – составными, полученными из простых высказываний 1 и «Число √2+1 является иррациональным».

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

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

 - пустое множество

 - пересечение

 - объединение

 - включение

 - принадлежит

 - не принадлежит

 - всякий

 - некоторый

Решение примера 3:

a M (Ma ( b, c)(Mb  Mc  ab=  ac=  bc))

Задача 2: Запишите на языке логики предикатов следующее высказывание: «Никакая программа Microsoft не является бесплатной программой».

Решение 2: Высказывание можно переписать в виде: «Для всякого Х, если Х — программа Microsoft, Х не является бесплатной», а в символической форме оно запишется так: x(A(x) B(x)).