uzluga.ru
добавить свой файл





  • Алгебра логики — это математический аппарат, с помо-

  • щью которого записывают, вычисляют, упрощают и пре-

  • образовывают логические высказывания.

  • Создателем алгебры логики является живший в ХIХ веке английс-

  • кий математик Джордж Буль, в честь которого эта алгебра названа

  • булевой алгеброй высказываний.



Логическое высказывание — это любoе повествователь-

  • Логическое высказывание — это любoе повествователь-

  • ное пpедлoжение, в oтнoшении кoтopoгo мoжно oднoзначнo

  • сказать, истиннo oнo или лoжнo.

  • Так, например, предложение “8 — четное число” следует считать

  • высказыванием, так как оно истинное.

  • Предложение “Два умножить на два равно пяти” тоже высказыва-

  • ние, так как оно ложное.

  • Разумеется, не всякое предложение является логическим высказы-

  • ванием. Высказываниями не являются, например, предложения

  • “ученик десятого класса” и “информатика — интересный пред-

  • мет”. Первое предложение ничего не утверждает об ученике, а второе

  • использует слишком неопределённое понятие “интересный предмет”.

  • Вопросительные и восклицательные предложения также не являются

  • высказываниями, поскольку говорить об их истинности или ложности

  • не имеет смысла.

  • Высказывания бывают общими, частными и единичными.

  • Общее высказывание начинается со слов: все, каждый, ни один.

  • Частное высказывание начинается со слов: некоторые, большинство.

  • Во всех других случаях высказывание является единичным.





Так, например, из элементарных высказываний “Петров — врач”,

  • Так, например, из элементарных высказываний “Петров — врач”,

  • “Петров — шахматист” при помощи связки “и” можно получить сос-

  • тавное высказывание “Петров — врач и шахматист”, понимаемое

  • как “Петров — врач, хорошо играющий в шахматы”.

  • При помощи связки “или” из этих же высказываний можно получить

  • составное высказывание “Петров — врач или шахматист”, понимае-

  • мое в алгебре логики как “Петров или врач, или шахматист, или и врач

  • и шахматист одновременно”.

  • Истинность или ложность получаемых таким образом составных

  • высказываний зависит от истинности или ложности элементарных

  • высказываний.

  • Чтобы обращаться к логическим высказываниям, им назначают име-

  • на.

  • А — “Тимур поедет летом на море”

  • В — “Тимур летом отправится в горы”.

  • Тогда составное высказывание “Тимур летом побывает и на море, и

  • в горах” можно кратко записать как А и В.

  • Здесь “и” — логическая связка, А, В — логические переменные, которые

  • могут принимать только два значения — “истина” или “ложь”, обозна-

  • чаемые, соответственно, “1” и “0” .

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

  • ческими высказываниями и имеет свое название и обозначение.



Операция, выражаемая словом “не”, называется отрицанием и

  • Операция, выражаемая словом “не”, называется отрицанием и

  • обозначается чертой над высказыванием (или знаком ).

  • Высказывание Ā истинно, когда A ложно, и ложно, когда A истинно.

  • Пример: “Луна — спутник Земли” (А); “Луна — не спутник Земли” (Ā).

  • Операция, выражаемая связкой “и”, называется конъюнкцией

  • или логическим умножением и обозначается точкой “ ” (может также

  • обозначаться знаками или &).

  • Высказывание А В истинно тогда и только тогда, когда оба высказы-

  • вания А и В истинны.

  • “10 делится на 2 и 5 больше 3” - истинно

  • “10 делится на 2 и 5 не больше 3” - ложно

  • “10 не делится на 2 и 5 больше 3” - ложно

  • Операция, выражаемая связкой “или” (в неразделительном, неис-

  • ключающем смысле этого слова), называется дизъюнкцией или логи-

  • ческим сложением и обозначается знаком (или плюсом).

  • Высказывание А В ложно тогда и только тогда, когда оба высказы-

  • вания А и В ложны.

  • “10 не делится на 2 или 5 не больше 3” - ложно

  • “10 делится на 2 или 5 больше 3” - истинно

  • “10 делится на 2 или 5 не больше 3” - истинно

  • “10 не делится на 2 или 5 больше 3” - истинно





Операция, выражаемая связками “если ..., то”, “из ... следует”,

  • Операция, выражаемая связками “если ..., то”, “из ... следует”,

  • “... влечет ...”, называется импликацией и обозначается знаком “ ”.

  • Высказывание А В ложно тогда и только тогда, когда А истинно, а

  • В — ложно.

  • Каким же образом импликация связывает два элементарных выска-

  • зывания? Покажем это на примере высказываний:

  • А - “данный четырёхугольник — квадрат”

  • В - “около данного четырёхугольника можно описать окружность”

  • А В - “если данный четырёхугольник квадрат, то около него

  • можно описать окружность”.

  • Есть три варианта, когда высказывание А В истинно:

  • 1. А истинно и В истинно, то есть данный четырёхугольник квад-

  • рат, и около него можно описать окружность;

  • 2. А ложно и В истинно, то есть данный четырёхугольник не явля-

  • ется квадратом, но около него можно описать окружность (разуме-

  • ется, это справедливо не для всякого четырёхугольника);



  • 3. A ложно и B ложно, то есть данный четырёхугольник не являет-

  • ся квадратом, и около него нельзя описать окружность.

  • Ложен только один вариант:

  • А истинно и В ложно, то есть данный четырёхугольник является

  • квадратом, но около него нельзя описать окружность.

  • В обычной речи связка “если ..., то” описывает причинно-следствен-

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

  • сказываний не учитывается. Рассматривается только их истинность

  • или ложность. Поэтому не надо смущаться “бессмысленностью” имп-

  • ликаций, образованных высказываниями, совершенно не связанными по

  • содержанию.

  • Например, такими:

  • “если президент США — демократ, то в Африке водятся жирафы”,

  • “если арбуз – ягода, то в бензоколонке есть бензин”,

  • “если Волга впадает в Каспийское море, то катет короче гипотенузы”,

  • “если Москва – столица России, то гепард – самое быстрое животное”.



Операция, выражаемая связками “тогда и только тогда”,



Итак, нами рассмотрены пять логических операций: отрицание,

  • Итак, нами рассмотрены пять логических операций: отрицание,

  • конъюнкция, дизъюнкция, импликация и эквиваленция.

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

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

  • Таким образом, операций отрицания, дизъюнкции и конъюнкции достаточ-

  • но, чтобы описывать и обрабатывать логические высказывания.

  • Порядок выполнения логических операций задается круглыми скобка-

  • ми. Но для уменьшения числа скобок договорились считать, что

  • сначала выполняется операция отрицания (“не”),

  • затем конъюнкция (“и”),

  • после конъюнкции — дизъюнкция (“или”)

  • и в последнюю очередь — импликация.



Таблица истинности основных операций алгебры логики



Логический элемент компьютера

  • Логический элемент компьютера

  • Логический элемент компьютера — это часть электронной ло-

  • гической схемы, которая реализует элементарную логическую

  • функцию.

  • Логические элементы компьютеров:

  • электронные схемы И, ИЛИ, НЕ, И-НЕ, ИЛИ-НЕ и другие (называемые

  • также вентилями),

  • триггер.

  • С помощью этих схем можно реализовать любую логическую функ-

  • цию, описывающую работу устройств компьютера. Обычно у вентилей

  • бывает от двух до восьми входов и один или два выхода.

  • Чтобы представить два логических состояния — “1” и “0” в венти-

  • лях, соответствующие им входные и выходные сигналы имеют один из

  • двух установленных уровней напряжения. Например, +5 В и 0 В.

  • Высокий уровень обычно соответствует значению “истина” (“1”), а

  • низкий — значению “ложь” (“0”).

  • Каждый логический элемент имеет свое условное обозначение, ко-

  • торое выражает его логическую функцию, но не указывает на то, какая

  • именно электронная схема в нем реализована. Это упрощает запись и

  • понимание сложных логических схем.

  • Работу логических элементов описывают с помощью таблиц ис-

  • тинности.



Схема И

  • Схема И

  • Схема И реализует конъюнкцию двух или более логических значений.

  • Условное обозначение на структурных схемах схемы И с двумя вхо-

  • дами представлено на рисунке. Таблица истинности — в таблице.

  • Единица на выходе схемы И будет тогда и только тогда, когда на

  • всех входах будут единицы. Когда хотя бы на одном входе будет ноль,

  • на выходе также будет ноль.

  • Связь между выходом z этой схемы и входами x и y описывается со-

  • отношением:

  • Операция конъюнкции на функциональных схемах обозначается зна-

  • ком “&” (читается как "амперсэнд").



Схема ИЛИ



Схема НЕ

  • Схема НЕ

  • Схема НЕ (инвертор) реализует операцию отрицания.

  • Связь между входом x этой схемы и выходом z можно записать со-

  • отношением , где - инверсия х.

  • Если на входе схемы 0, то на выходе 1. Когда на входе 1, на выходе 0.

  • Условное обозначение инвертора — на рисунке, а таблица истинности

  • — в таблице.