Булева логика

Булева логика
Не следует путать с булевой алгеброй.

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

Содержание

Определение

Высказывания строятся над множеством {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. ¬(¬x)=x, x=¬(¬x);
2. x*(¬x)=0;
3. x+1=1;
4. x+x=x, x=x+x+x;
5. x+0=x;
6. x*x=x, x=x*x*x;
7. x*0=0;
8. x*1=x;
9. x+(¬x)=1.

Унарные логические операции
x g1 (\lnot) g2 (=) g3 (1) g4 (0)
0 1 0 1 0
1 0 1 1 0

g1(x) — отрицание/негация (g1(x) = \negx = x')

g2(x) — тождественная функция (g2(x) = x)

Бинарные логические операции
x y f1 (\land) f2 (\lor) f3 (\equiv) f4 (\oplus) f5 (\subset) f6 (\supset) f7 (\downarrow) f8 (\mid)
0 0 0 0 1 0 1 1 1 1
0 1 0 1 0 1 0 1 0 1
1 0 0 1 0 1 1 0 0 1
1 1 1 1 1 0 1 1 0 0
x y f9 f10 f11 f12 f13 f14 f15 f16
0 0 0 0 1 1 0 0 1 0
0 1 0 1 1 0 0 1 1 0
1 0 1 0 0 1 1 0 1 0
1 1 0 0 0 0 1 1 1 0

Здесь 0 и 1 — тождественные нуль и единица соответственно,

f1(x, y) — конъюнкция (f1(x, y) = x&y = x\cdoty = x\landy = min(x, y)),

f2(x, y) — дизъюнкция (f2(x, y) = x\lory = max(x, y)),

f3(x, y) — эквивалентность (f3(x, y) = x\simy = x\equivy = x\leftrightarrowy),

f4(x, y) — сумма по модулю два (f4(x, y) = x\oplusy),

f5(x, y) — импликация от y к x (f5(x, y) = x\leftarrowy = x\subsety),

f6(x, y) — импликация от x к y (f6(x, y) = x\rightarrowy = x\supsety),

f7(x, y) — стрелка Пи́рса = функция Да́ггера = функция Ве́бба
(«антидизъюнкция») (f7(x, y) = x\downarrowy).

f8(x, y) — штрих Ше́ффера («антиконъюнкция») (f8(x, y) = x\midy),

f9(x, y), f10(x, y) — инверсии импликаций f5 и f6,

f11—f14 — функции только одного аргумента,

f15, f16 — тождества.

Все вышеперечисленные функции называются логическими связками.

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

Простейшим и наиболее широко применяемым примером такой алгебраической системы является множество 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\lorz) = (x\landy)\lor(x\landz),
    • x\lor(y\landz) = (x\lory)\land(x\lorz),
    • x\land(y\oplusz) = (x\landy)\oplus(x\landz).
  5. Законы де Мо́ргана:
    • \neg(x\landy) = (\neg x)\lor(\negy),
    • \neg(x\lory) = (\neg x)\land(\negy).
  6. Законы поглощения:
    • x\land(x\lory) = x,
    • x\lor(x\landy) = x.
  7. Другие (1):
    • x\land(\negx) = x\land0 = x\oplusx = 0.
    • x\lor(\negx) = x\lor1 = x\simx = x\rightarrowx = 1.
    • x\lorx = x\landx = x\land1 = x\lor0 = x\oplus0 = x.
    • x\oplus1 = x\rightarrow0 = x\sim0 = x\midx = x\downarrowx = \negx.
    • \bar\bar x = x.
  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} = (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.
  9. Другие (3) (Дополнение законов де Мо́ргана):
    • x\mid y = \neg (x\land y) = \neg x\lor\neg y.
    • x\downarrow y = \neg (x\lor y) = \neg x\land\neg y.

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

История

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

См. также

Ссылки


Wikimedia Foundation. 2010.

Нужно решить контрольную?

Полезное


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

  • булева логика — Boolean logika statusas T sritis automatika atitikmenys: angl. Boolean logic vok. Boolesche Logik, f rus. булева логика, f pranc. logique de Boole, f ryšiai: sinonimas – Bulio logika …   Automatikos terminų žodynas

  • Логика в информатике — Логика в информатике  это направления исследований и отраслей знания, где логика применяется в информатике и искусственном интеллекте. Логика очень эффективна в этих областях[1]. Содержание 1 Область применения …   Википедия

  • Логика в компьютерных науках — Логика в информатике это направления исследований и отрасли знания, где логика применяется в информатике и искусственном интеллекте. Логика оказалась гораздо более эффективной в информатике, чем это было в математике[1]. Включаются следующие… …   Википедия

  • БУЛЕВА АЛГЕБРА — Названная по имени ее создателя, английского математика Джорджа Буля, система операций с символами, которая использует алгебраические процедуры, но независимо от определенных математических интерпретаций. Булева логика, или калькуляция (как она… …   Толковый словарь по психологии

  • ЛОГИКА ВЫСКАЗЫВАНИЙ — раздел логики, в котором изучаются истинностные взаимосвязи между высказываниями. В рамках данного раздела высказывания (пропозиции, предложения) рассматриваются только с т.зр. их истинности или ложности, безотносительно к их внутренней субъектно …   Философская энциклопедия

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

  • логика —         ЛОГИКА (от греч. logik (logos) слово, разум, рассуждение) наука о правильных (корректных) рассуждениях. Традиционно рассуждение состоит из последовательности предложений, названных посылками, из которых следует единственное предложение,… …   Энциклопедия эпистемологии и философии науки

  • Булева формула — (по имени Джорджа Буля) формула логики высказываний. Может содержать логические переменные и пропозициональные связки конъюнкцию ( ), дизъюнкцию ( ), отрицание ( ) и другие. Формула называется тождественно истинной (ложной), если она истинна… …   Википедия

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

  • логика — логические схемы Схемные компоненты, реализующие различные логические операции булевой алгебры. [Л.М. Невдяев. Телекоммуникационные технологии. Англо русский толковый словарь справочник. Под редакцией Ю.М. Горностаева. Москва, 2002] Тематики… …   Справочник технического переводчика

Книги

Другие книги по запросу «Булева логика» >>


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

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