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

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

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

Содержание

Определение

Базовыми элементами, которыми оперирует алгебра логики, являются высказывания. Высказывания строятся над множеством {B, \lnot, \land, \lor, 0, 1}, где B — непустое множество, над элементами которого определены три операции:

\lnot отрицание (унарная операция),
\land конъюнкция (бинарная),
\lor дизъюнкция (бинарная),

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

Дизъю́нкт — пропозициональная формула, являющаяся дизъюнкцией одного или более литералов (например x_1 \lor \neg x_2 \lor x_4). Конъюнкт — пропозициональная формула, являющаяся конъюнкцией одного или более литералов (например x_1 \land \neg x_2 \land x_4).

Аксиомы

  1. \bar {\bar x}=x, инволютивность отрицания, закон снятия двойного отрицания
  2. x\lor\bar x=1
  3. \ x\lor1=1
  4. \ x\lor x=x
  5. \ x\lor0=x
  6. \ x\land\bar x=0
  7. \ x\land x=x
  8. \ x\land0=0
  9. \ x\land1=x

Логические операции

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

B = { Ложь, Истина }

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

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

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

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

Свойства логических операций

  1. Коммутативность: x\circy = y\circx, \circ\in{&, \lor, \oplus, \sim, \mid, \downarrow}.
  2. Идемпотентность: x\circx = x, \circ\in{&, \lor}.
  3. Ассоциативность: (x\circy)\circz = x\circ(y\circz), \circ\in{&, \lor, \oplus, \sim}.
  4. Дистрибутивность конъюнкций и дизъюнкции относительно дизъюнкции, конъюнкции и суммы по модулю два соответственно:
    • x\land  (y\lor z) = x\land y\lor x\land z,
    • x\lor y\land  z = (x\lor y)\land (x\lor z),
    • x\land (y\oplus z) = x\land y\oplus x\land z.
  5. Законы де Мо́ргана:
    • \overline{x\land y} = \bar x \lor  \bar y,
    • \overline{x\lor y} = \bar x\land \bar y.
  6. Законы поглощения:
    • x\land (x\lor y) = x,
    • x\lor x\land y = x.
  7. Другие (1):
  8. Другие (2):
    • x\oplus y = x\land \bar y \lor  \bar x\land y = (x\lor y)\land (\bar x\lor \bar y).
    • x\sim y = \overline{x\oplus y} = 1\oplus x\oplus y = x\land y\lor \bar x \land  \bar y = (x\lor \bar y)\land (\bar x\lor y).
    • x\rightarrow y = \bar x \lor  y = x\land y\oplus x\oplus 1.
    • x \lor  y = x \oplus y \oplus x\land y.
  9. Другие (3) (Дополнение законов де Мо́ргана):
    • x\mid y = \overline {x\land y} = \bar x \lor  \bar y.
    • x\downarrow y = \overline {x\lor y}= \bar x\land \bar y.

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

История

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

См. также

Примечания



Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Полезное


Смотреть что такое "Алгебра логики" в других словарях:

  • АЛГЕБРА ЛОГИКИ —         система алгебраич. методов решения логич. задач, а также совокупность задач, решаемых такими методами. А. л. в узком смысле слова алгебраич. (табличное, матричное) построение классич. логики высказываний, в котором рассматриваются… …   Философская энциклопедия

  • алгебра логики —         АЛГЕБРА ЛОГИКИ исторически первая форма математической (символической) логики, сложившаяся к последней трети 19 в. К ее созданию привела аналогия между решением алгебраических уравнений и выводом следствий из посылок, а также то, что… …   Энциклопедия эпистемологии и философии науки

  • алгебра логики — булева алгебра — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом Синонимы булева алгебра EN logical algebra …   Справочник технического переводчика

  • АЛГЕБРА ЛОГИКИ — система алгебраических методов решения логических задач и совокупность таких задач; в узком смысле табличное, матричное построение логики высказываний, определяющее логические операции над ними …   Большой Энциклопедический словарь

  • АЛГЕБРА ЛОГИКИ — раздел математической логики, изучающий строение сложных логических высказываний и способы установления их истинности с помощью алгебраических методов. В формулах А. л. переменные являются логическими или двоичными, т. е. принимающими только два… …   Большая политехническая энциклопедия

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

  • алгебра логики — система алгебраических методов решения логических задач и совокупность таких задач. * * * АЛГЕБРА ЛОГИКИ АЛГЕБРА ЛОГИКИ, система алгебраических методов решения логических задач и совокупность таких задач; в узком смысле табличное, матричное… …   Энциклопедический словарь

  • алгебра логики — logikos algebra statusas T sritis automatika atitikmenys: angl. algebra of logic vok. Algebra der Logik, f; logische Algebra, f rus. алгебра логики, f pranc. algèbre logique, f …   Automatikos terminų žodynas

  • АЛГЕБРА ЛОГИКИ — раздел математической логики, изучающий высказывания, рассматриваемые со стороны их логич. значений (истинности пли ложности), и логич. операций над ними. А. л. возникла в сер. 19 в. в трудах Дж. Буля (см. [1], [2]) и развилась затем в работах Ч …   Математическая энциклопедия

  • АЛГЕБРА ЛОГИКИ — раздел матем. логики, изучающий высказывания, рассматриваемые со стороны их логич. значений (истинности или ложности), и логич. операции над ними. В А. л. принято отождествлять истинность высказывания с числом 1, а ложность с числом О (А = 1 и С …   Большой энциклопедический политехнический словарь


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»