Логические схемы и таблицы истинности

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

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

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

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

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

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

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

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

___

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

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

Ä Операция, выражаемая связкой { ИЛИ } называется дизъюнкцией или логическим сложением и обозначается знаком 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)).

Логические схемы и таблицы истинности

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