No Image

Что изучает алгебра логики

СОДЕРЖАНИЕ
2 просмотров
10 марта 2020

Общие теоретические сведения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 1. Основные логические операции

Конъюнкция (логическое умножение)

Дизъюнкция (логическое сложение)

Тогда и только тогда

Исключающее ИЛИ (сложение по модулю 2)

НЕ Операция, выражаемая словом «не», называется отрицанием и обозначается чертой над высказыванием (или знаком ). Высказывание А истинно, когда A ложно, и ложно, когда A истинно.

Пример. Пусть А=«Сегодня пасмурно», тогда А=«Сегодня не пасмурно».

И Операция, выражаемая связкой «и», называется конъюнкцией (лат. conjunctio – соединение) или логическим умножением и обозначается точкой « • » (может также обозначаться знаками или &). Высказывание А • В истинно тогда и только тогда, когда оба высказывания А и В истинны.

Пример. Высказывание «Число 6 делится на 2, и число 6 делится на 3» — истинно, а высказывание «Число 6 делится на 2, и число 6 больше 10» — ложно.

ИЛИ Операция, выражаемая связкой «или» (в неисключающем смысле этого слова), называется дизъюнкцией (лат. disjunctio – разделение) или логическим сложением.

Пример: Высказывание «Число 6 делится на 2 или число 6 больше 10» — истинно, а высказывание «Число 6 делится на 5 или число 6 больше 10» — ложно.

ЕСЛИ … ТО Операция, выражаемая связками «если …, то», «из … следует», «. влечет …», называется импликацией (лат. implico – тесно связаны) и обозначается знаком → . Высказывание А→В ложно тогда и только тогда, когда А истинно, а В ложно.

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

Читайте также:  Смартфон asus zenfone 2 ze550ml

РАВНОСИЛЬНО Операция, выражаемая связками «тогда и только тогда», «необходимо и достаточно», «. равносильно …», называется эквиваленцией или двойной импликацией и обозначается знаком ↔ или

. Высказывание А↔В истинно тогда и только тогда, когда значения А и В совпадают.

Пример: Высказывание «Число является четным тогда и только тогда, когда оно делится без остатка на 2» является истинным, а высказывание «Число является нечетным тогда и только тогда, когда оно делится без остатка на 2» — ложно.

ЛИБО … ЛИБО Операция, выражаемая связками «Либо … либо», называется исключающее ИЛИ или сложением по модулю 2 и обозначается .

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

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

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

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

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

Логическая функция — это функция логических переменных, которая может принимать только два значения: 0 или 1. В свою очередь, сама логическая переменная (аргумент логической функции) тоже может принимать только два значения: 0 или 1.

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

Алгоритм построения таблиц истинности для сложных выражений:

  1. Определить количество строк:
  • количество строк = 2 n + строка для заголовка,
  • n — количество простых высказываний.
  1. Определить количество столбцов:
  • количество столбцов = количество переменных + количество логических операций;
  • определить количество переменных (простых выражений);
  • определить количество логических операций и последовательность их выполнения.

Примечание: И–НЕ называют также «штрих Шеффера» (обозначают | ) или «антиконъюнкция»; ИЛИ–НЕ называют также «стрелка Пирса» (обозначают ↓) или «антидизъюнкция».

Существует три базовых логических элемента, которые реализуют три основные логические операции:

  • логический элемент «И» – логическое умножение – конъюнктор;
  • логический элемент «ИЛИ» – логическое сложение – дизъюнктор;
  • логический элемент «НЕ» – инверсию – инвертор.

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

Логические элементы компьютера оперируют с сигналами, представляющими собой электрические импульсы. Есть импульс – логический смысл сигнала – 1, нет импульса – 0. На входы логического элемента поступают сигналы-значения аргументов, на выходе появляется сигнал-значение функции.

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

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

Читайте также:  Программа для обрезки фото кругом

Содержание

Определение [ править | править код ]

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

Высказывания строятся над множеством , ∧ <displaystyle land > , ∨ <displaystyle lor > , 0, 1>, где B — непустое множество, над элементами которого определены три операции:

а логический ноль и логическая единица 1 — константы.

Так же используются названия

  • Дизъю́нкт — пропозициональная формула, являющаяся дизъюнкцией одного или более литералов (например x 1 ∨ ¬ x 2 ∨ x 4 <displaystyle x_<1>lor
    eg x_<2>lor x_<4>>).
  • Конъюнкт — пропозициональная формула, являющаяся конъюнкцией одного или более литералов (например x 1 ∧ ¬ x 2 ∧ x 4 <displaystyle x_<1>land
    eg x_<2>land x_<4>>).

Унарная операция отрицания в тексте формул оформляется либо в виде значка перед операндом ( ¬ x <displaystyle lnot x> ) либо в виде черты над операндом ( x ¯ <displaystyle <ar >> ), что компактнее, но в целом менее заметно.

Аксиомы [ править | править код ]

  1. x ¯ ¯ = x <displaystyle <ar <ar >>=x>, инволютивность отрицания, закон снятия двойного отрицания
  2. x ∨ x ¯ = 1 <displaystyle xlor <ar >=1>
  3. x ∨ 1 = 1 <displaystyle xlor 1=1>
  4. x ∨ x = x <displaystyle xlor x=x>
  5. x ∨ 0 = x <displaystyle xlor 0=x>
  6. x ∧ x ¯ = 0 <displaystyle xland <ar >=0>
  7. x ∧ x = x <displaystyle xland x=x>
  8. x ∧ 0 = 0 <displaystyle xland 0=0>
  9. x ∧ 1 = x <displaystyle xland 1=x>

Логические операции [ править | править код ]

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

Как правило, в математических выражениях Ложь отождествляется с логическим нулём, а Истина — с логической единицей, а операции отрицания (НЕ), конъюнкции (И) и дизъюнкции (ИЛИ) определяются в привычном нам понимании. Легко показать, что на данном множестве B можно задать четыре унарные и шестнадцать бинарных отношений и все они могут быть получены через суперпозицию трёх выбранных операций.

Опираясь на этот математический инструментарий, логика высказываний изучает высказывания и предикаты. Также вводятся дополнительные операции, такие как эквиваленция ↔ <displaystyle leftrightarrow > («тогда и только тогда, когда»), импликация → <displaystyle
ightarrow > («следовательно»), сложение по модулю два ⊕ <displaystyle oplus > («исключающее или»), штрих Шеффера ∣ <displaystyle mid > , стрелка Пирса ↓ <displaystyle downarrow > и другие.

Логика высказываний послужила основным математическим инструментом при создании компьютеров. Она легко преобразуется в битовую логику: истинность высказывания обозначается одним битом (0 — ЛОЖЬ, 1 — ИСТИНА); тогда операция ¬ <displaystyle
eg > приобретает смысл вычитания из единицы; ∨ <displaystyle lor > — немодульного сложения; & — умножения; ↔ <displaystyle leftrightarrow > — равенства; ⊕ <displaystyle oplus > — в буквальном смысле сложения по модулю 2 (исключающее Или — XOR); ∣ <displaystyle mid > — непревосходства суммы над 1 (то есть A ∣ <displaystyle mid > B = (A + B) Свойства логических операций [ править | править код ]

  1. Коммутативность: x ∘ y = y ∘ x , ∘ ∈ < ∧ , ∨ , ⊕ , ∼ , ∣ , ↓ ><displaystyle xcirc y=ycirc x,circ in <land ,lor ,oplus ,sim ,mid ,downarrow >>.
  2. Идемпотентность: x ∘ x = x , ∘ ∈ < ∧ , ∨ ><displaystyle xcirc x=x,circ in <land ,lor >>.
  3. Ассоциативность: ( x ∘ y ) ∘ z = x ∘ ( y ∘ z ) , ∘ ∈ < ∧ , ∨ , ⊕ , ∼ ><displaystyle (xcirc y)circ z=xcirc (ycirc z),circ in <land ,lor ,oplus ,sim >>.
  4. Дистрибутивность конъюнкций и дизъюнкции относительно дизъюнкции, конъюнкции и суммы по модулю два соответственно:
    • x ∧ ( y ∨ z ) = ( x ∧ y ) ∨ ( x ∧ z ) <displaystyle xland (ylor z)=(xland y)lor (xland z)>,
    • x ∨ ( y ∧ z ) = ( x ∨ y ) ∧ ( x ∨ z ) <displaystyle xlor (yland z)=(xlor y)land (xlor z)>,
    • x ∧ ( y ⊕ z ) = ( x ∧ y ) ⊕ ( x ∧ z ) <displaystyle xland (yoplus z)=(xland y)oplus (xland z)>.
    • Законы де Мо́ргана:
      • x ∧ y ¯ = x ¯ ∨ y ¯ <displaystyle <overline >=<ar >lor <ar >>,
      • x ∨ y ¯ = x ¯ ∧ y ¯ <displaystyle <overline >=<ar >land <ar >>.
      • Законы поглощения:
        • x ∧ ( x ∨ y ) = x <displaystyle xland (xlor y)=x>,
        • x ∨ ( x ∧ y ) = x <displaystyle xlor (xland y)=x>.
        • Другие (1):
          • x ∧ x ¯ = x ∧ 0 = x ⊕ x = 0 <displaystyle xland <ar >=xland 0=xoplus x=0>.
          • x ∨ x ¯ = x ∨ 1 = x ∼ x = x → x = 1 <displaystyle xlor <ar >=xlor 1=xsim x=x
            ightarrow x=1>.
          • x ∨ x = x ∧ x = x ∧ 1 = x ∨ 0 = x ⊕ 0 = x <displaystyle xlor x=xland x=xland 1=xlor 0=xoplus 0=x>.
          • x ⊕ 1 = x → 0 = x ∼ 0 = x ∣ x = x ↓ x = x ¯ <displaystyle xoplus 1=x
            ightarrow 0=xsim 0=xm >.
          • x ¯ ¯ = x <displaystyle <ar <ar >>=x>, инволютивность отрицания, закон снятия двойного отрицания.
          • Другие (2):
            • x ⊕ y = x ∧ y ¯ ∨ x ¯ ∧ y = ( x ∨ y ) ∧ ( x ¯ ∨ y ¯ ) <displaystyle xoplus y=xland <ar >lor <ar >land y=(xlor y)land (<ar >lor <ar >)>.
            • x ∼ y = x ⊕ y ¯ = 1 ⊕ x ⊕ y = x ∧ y ∨ x ¯ ∧ y ¯ = ( x ∨ y ¯ ) ∧ ( x ¯ ∨ y ) <displaystyle xsim y=<overline >=1oplus xoplus y=xland ylor <ar >land <ar >=(xlor <ar >)land (<ar >lor y)>.
            • x → y = x ¯ ∨ y = x ∧ y ⊕ x ⊕ 1 <displaystyle x
              ightarrow y=<ar >lor y=xland yoplus xoplus 1>.
            • x ∨ y = x ⊕ y ⊕ x ∧ y <displaystyle xlor y=xoplus yoplus xland y>.
            • Другие (3) (Дополнение законов де Мо́ргана):
              • x ∣ y = x ∧ y ¯ = x ¯ ∨ y ¯ <displaystyle xm >.
              • x ↓ y = x ∨ y ¯ = x ¯ ∧ y ¯ <displaystyle xdownarrow y=<overline >=<ar >land <ar >>.
              Читайте также:  Что значит борода на сленге

              Существуют методы упрощения логической функции: например, Карта Карно, метод Куайна — Мак-Класки

              История [ править | править код ]

              Своим существованием наука «алгебра логики» обязана английскому математику Джорджу Булю, который исследовал логику высказываний. Первый в России курс по алгебре логики был прочитан П. С. Порецким в Казанском государственном университете.

              См. также [ править | править код ]

              Примечания [ править | править код ]

              1. ↑ Алгебра логики // Большая советская энциклопедия : [в 30 т.] / гл. ред. А. М. Прохоров . — 3-е изд. — М. : Советская энциклопедия, 1969—1978.

              • Найти и оформить в виде сносок ссылки на независимые авторитетные источники, подтверждающие написанное.

              Пожалуйста, после исправления проблемы исключите её из списка параметров. После устранения всех недостатков этот шаблон может быть удалён любым участником.

              Высказывание — построение над множеством < B , ¬ , ∧ , ∨ , 0 , 1 ><displaystyle >
              В — непустое множество, над элементами которого определены три базовые операции: конъюнкция ( ∧ <displaystyle land > или &, бинарная) • дизъюнкция ( ∨ <displaystyle lor > , бинарная) • отрицание ( ¬ <displaystyle
              eg > , унарная)

              Законы алгебры логики

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

              Что изучает алгебра логики?

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

              К основным логическим операциям относятся операции: отрицания, логического умножения, или конъюнкции, логического сложения, или дизъюнкции, эквивалентности, импликации.

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

              Где используется алгебра логики?

              Использование аппарата алгебры логики в теории устройств дискретного действия основано на том, что элементы этих устройств являются двух позиционными приборами, т. е. приборами, которые по условиям работы могут находиться лишь в одном из двух различных устойчивых состояний, например «контакт замкнут», «транзистор открыт».

              Конъюнкция такого рода высказываний будет тогда средством выражения последовательного соединения элементов, а дизъюнкция — их параллельного соединения. На этом основана возможность применять средства алгебры логики к задачам анализа и синтеза переключателей схем. Алгебра логики используется в теории релейных схем, теории ЭВМ и в теории дискретных автоматов.

              Комментировать
              2 просмотров
              Комментариев нет, будьте первым кто его оставит

              Это интересно
              Adblock detector