Что такое булева логика

2. Логика буля

Аппарат логики Буля, или иначе алгебры логики, оперирует с логическими переменными, которые могут принимать только два значения: 0 и 1. Логические переменные определяют некую логическую зависимость, которую принято называть булевой функцией. Множество всех булевых функций и операций над ними образует булеву алгебру или алгебру логики. Булевы функции, или иначе функции алгебры логики (ФАЛ), могут принимать тоже только два взаимно исключающих значения 0 и 1. При формальном рассмотрении законов булевой алгебры логические переменные обычно обозначают строчными буквами латинского алфавита или присваивают им идентификаторы.

Логические величины 0 и 1 нельзя трактовать как числа, над ними нельзя производить арифметические действия, поскольку алгебра логики – это не алгебра чисел, а алгебра состояний. Тем не менее в булевой алгебре производятся логические действия над переменными, которые и определяют характер логических функций. Основные логические действия соответствуют простейшим операциям над множествами: инверсия, или отрицание, дизъюнкция, или логическое сложение, и конъюнкция, или логическое умножение. На основании этих трех логических действий строятся все сколь угодно сложные логические функции. При этом следует особо выделить функции одной и двух переменных, которые играют в алгебре Буля весьма важную роль. При помощи этих функций, используя принцип суперпозиции, можно описать любую логическую функцию любой сложности любого числа переменных.

Принцип суперпозиции заключается в том, что каждый аргумент логической функции может являться функцией других логических переменных, а именно: если есть функция fx₁;x₂;x₃>, то возможно, что x₁ =  (x₄,x₅).

Булевых функций одной переменной всего четыре.

Нулевая (const”0”) Ф = Х =0 – значение функции равно нулю, каким бы ни было значение входной переменной.
Инверсия(не) Ф =– значение функции инверсно значению входной переменной.
Повторение(да) Ф = Х – значение функции повторяет значение входной переменной.
Единичная (const”1”) Ф = Х = 1 – значение функции равно единице при любом значении входной переменной.

Из всех функций двух переменных десять являются самостоятельными и зависят как от переменной а, так и от переменной b. Притом функции Y₅ ,Y₆ отличаются от соответствующих им Y₇ ,Y₈ лишь порядком расположения аргументов. Таким образом, лишь восемь из 16-ти булевых функций двух переменных являются оригинальными. 1. Y₁ = a  b–конъюнкция, логическое «и»; 2. Y₂ = a  b –дизъюнкция, логическое «или»; 3. Y₃ = a / b –штрих Шеффера, логическое «и-не»; 4. Y₄ = a  b –стрелка Пирса (функция Вебба), «или — не»; 5. Y₅ = a b –запрет b, «а, но не b» ; 6. Y₆ = a b –импликация b, «если а, то b» ; 7. Y₇ = b a –запрет а, «b, но не а» ; 8. Y₈ = b a –импликация а, «если b, то а» ; 9. Y₉ = a  b –эквивалентность, равнозначность; 10. Y₁₀ = a  b –неравнозначность, «сумма по модулю 2».

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

Алгебра Буля, как любая математическая наука, базируется на нескольких аксиомах, или постулатах.

Если x ≠ 1, то = 0; если x ≠ 0, то = 1 (аксиома взаимоисключения).
0  0 = 0; 0  0 = 0.
0  1 = 0; 0  1 = 1; (1  0 = 0; 1  0 = 1).
1  1 = 1; 1  1 = 1.
; (инверсии).
; (двойной инверсии).

В качестве основных законов алгебры Буля чаще других используют следующие (законы и теоремы приведены без доказательств). 1. Нулевого множества:0  a = 0; 0  a  b  …  x = 0; 0  a = a 2. Универсального множества: 1  a = a; 1  a = 1; 1  a  b  c … x = 1; 3. Идемпотентности (повторения): a  a  a  …  a = a; a  a  a  … a = a; 4. Дополнительности (противоречия): a  = 0;a  = 1; 5. Двойной инверсии: =a ; 6. Коммутативности (переместительный): a  b = b  a; a  b = b  a; 7. Ассоциативности (сочетательный): a  (b  c) = (a  b)  c; a  (b  c) = (a  b)  c; 8. Дистрибутивности (распределительный): a  (b  c) = (a  b)  (a c); a  (b  c) = (a  b)  (a c); 9. Поглощения: a  (a  b) = a; a  (a  b) = a; 10. Склеивания: (a  b)  (a  ) = a ; (a  b)  (a  ) = a ; a  ( b) = a  b ; a  ( b) = a  b ; 11. Инверсии (теорема де Моргáнa): ; ; 12. Теорема Шеннона: для того, чтобы получить инверсию некоторой ФАЛ, необходимо взять инверсии переменных и заменить операции дизъюнкции на конъюнкции и наоборот: если существует Y = f (a,b,c. x, , ), то =f(,,…,_,__,__).. 13. Разложения: f (a,b,c. x) = [a  f (1,b,c. x)] [ f (0,b,c. x)]; f (a,b,c. x) = [a  f (0,b,c. x)] [ f (1,b,c. x)]. Законы и теоремы булевой алгебры необходимы для преобразования и упрощения логических функций, для доказательства тождественности и равносильности функций, а также для представления булевых функций в различных формах.

5.1. Что такое алгебра логики?

Алгебра логики — это математический аппарат, с помощью которого записывают, вычисляют, упрощают и преобразовывают логические высказывания. Создателем алгебры логики является живший в ХIХ веке английский математик Джордж Буль, в честь которого эта алгебра названа булевой алгеброй высказываний.

Что же такое логическое высказывание?

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

Так, например, предложение “6 — четное число” следует считать высказыванием, так как оно истинное. Предложение “Рим — столица Франции” тоже высказывание, так как оно ложное.

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

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

Высказывательная форма — это повествовательное предложение, которое прямо или косвенно содержит хотя бы одну переменную и становится высказыванием, когда все переменные замещаются своими значениями. Алгебра логики рассматривает любое высказывание только с одной точки зрения — является ли оно истинным или ложным. Заметим, что зачастую трудно установить истинность высказывания. Так, например, высказывание “площадь поверхности Индийского океана равна 75 млн кв. км” в одной ситуации можно посчитать ложным, а в другой — истинным. Ложным — так как указанное значение неточное и вообще не является постоянным. Истинным — если рассматривать его как некоторое приближение, приемлемое на практике.

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

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

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

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

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

Чтобы обращаться к логическим высказываниям, им назначают имена. Пусть через А обозначено высказывание “Тимур поедет летом на море”, а через В — высказывание “Тимур летом отправится в горы”. Тогда составное высказывание “Тимур летом побывает и на море, и в горах” можно кратко записать как А и В. Здесь “и” — логическая связка, А, В — логические переменные, которые мoгут принимать только два значения — “истина” или “ложь”, обозначаемые, соответственно, “1” и “0”

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

(1) Операция, выражаемая словом “не”, называется отрицанием и обозначается чертой над высказыванием (или знаком щ ). Высказывание истинно, когда A ложно, и ложно, когда A истинно. Пример. “Луна — спутник Земли” (А); “Луна — не спутник Земли” ().

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

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

истинно, а высказывания

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

(3) Операция, выражаемая связкой “или” (в неразделительном, неисключающем смысле этого слова), называется дизъюнкцией (лат. disjunctio — разделение) или логическим сложением и обозначается знаком v (или плюсом). Высказывание А v В ложно тогда и только тогда, когда оба высказывания А и В ложны. Например, высказывание

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

ложно, а высказывания

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

(4) Операция, выражаемая связками “если . то”, “из . следует”, “. влечет . ”, называется импликацией (лат. implico — тесно связаны) и обозначается знаком ®. Высказывание А ® В ложно тогда и только тогда, когда А истинно, а В — ложно.

Каким же образом импликация связывает два элементарных высказывания? Покажем это на примере высказываний: “данный четырёхугольник — квадрат” (А) и “около данного четырёхугольника можно описать окружность” (В). Рассмотрим составное высказывание А ® В, понимаемое как “если данный четырёхугольник квадрат, то около него можно описать окружность”. Есть три варианта, когда высказывание А ®В истинно:

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

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

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

Ложен только один вариант: А истинно и В ложно, то есть данный четырёхугольник является квадратом, но около него нельзя описать окружность.

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

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

(5) Операция, выражаемая связками “тогда и только тогда”, «необходимо и достаточно”, “. равносильно . ”, называется эквиваленцией или двойной импликацией и обозначается знаком « или ~ . Высказывание А « В истинно тогда и только тогда, когда значения А и В совпадают.

“24 делится на 6 тогда и только тогда, когда 24 делится на 3”, “23 делится на 6 тогда и только тогда, когда 23 делится на 3”

истинны, а высказывания

“24 делится на 6 тогда и только тогда, когда 24 делится на 5”, “21 делится на 6 тогда и только тогда, когда 21 делится на 3”

Высказывания А и В, образующие составное высказывание А « В, могут быть совершенно не связаны по содержанию, например: “три больше двух” (А), “пингвины живут в Антарктиде” (В). Отрицаниями этих высказываний являются высказывания “три не больше двух” (), “пингвины не живут в Антарктиде” (). Образованные из высказываний А, В составные высказывания A«B и « истинны, а высказывания A«и «B — ложны.

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

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

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

А « В = (v В) • (v А).Таким образом, операций отрицания, дизъюнкции и конъюнкции достаточно, чтобы описывать и обрабатывать логические высказывания.

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

Булевский тип

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

Реализация

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

Доступные операции

К этому типу данных применимы следующие операции:

И (логическое умножение) ( AND , & , * ),
ИЛИ (логическое сложение) ( OR , | , + ),
исключающее ИЛИ (умножение с переносом) ( xor , NEQV , ^ ),
эквивалентность (равенство) ( EQV , = , == )
инверсия ( NOT , ~ , ! )
сравнение ( > , < , = )

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

Применение

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

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

Реализация в различных языках программирования

Ada

Язык программирования Ada определяет Boolean в пакете Standard как нумерованный тип со значениями False и True в котором False < True .

type Boolean is (False, True);

p : Boolean := True; . if p then . end if;

Родственные операторы ( = , /= , < , , >= ) применяются ко всем нумерованым типам, включая Boolean . Булевые операторы and , or , xor и not применимы к типу Boolean и любым объявленным подтипам. Булевые операторы также применимы к массивам, содержащим значения Boolean .

Algol

Algol 60 имеет тип данных boolean и соответствующие операторы, установленные в спецификации Algol 60. Тип данных был сокращён до bool в ALGOL 68.

C

В языке программирования C, который не предоставлял булевых значений в C89 (но вводит в C99) вместо значений true/false было установлено сравнение значения с нулём. Для примера, код на C

if (my_variable) < printf("True!\n"); >else
if (my_variable != 0) < printf("True!\n"); >else

Это было честно для типа данных целочисленное (integer); тем не менее бинарные значения чисел с плавающей запятой (floating-point) были приближёнными к выводимым на экран десятичным значениям и это давало ошибки при сравнении. Традиционно, целое содержало одну (или более) булевую переменную (одну на каждый разряд целого).

Python

строки: пустая строка — ложь, непустая строка истина.
числа: нулевое число — ложь, ненулевое число (в том числе и меньшее единицы) — истина.
списки и кортежи: пустой список (кортеж) — ложь, непустой (даже содержащий один элемент, например пустой кортеж) — истина.
функции — всегда истина.

Для других объектов результат рассчитывается через метод __nonzero__, который в идеале должен возвращать значения True/False.

Булевый тип приводится к следующим типам данных:

строковый: ‘True’ для истины, ‘False’ для лжи.
числовой (встроеные типы int, long, float): 1 для истины, 0 для лжи.

К другим типам данных булевый тип не приводится.

Pascal

Описание переменных

Операции

Арифметических нет. Операций отношений нет. Допустимы следующие логические операции: Not, And, Or, Xor Допустимые функции: Ord,Pred,Succ

Руби

В Руби булевский тип представлен двумя предопределенными переменными: true и false . Появляется логический тип в результате логических операций или вызова логических методов. По традиции, имя логических методов (то есть методов, которые возвращают значение true или false) заканчивается на «?».

В качестве false может выступать nil , а в качестве true — любой объект, в том числе переменная со значением «0» или пустая строка, что часто является неожиданностью для новичков.

Wikimedia Foundation . 2010 .

Булева алгебра

Булевой алгеброй [1] [2] [3] называется непустое множество A с двумя бинарными операциями $\land$ (аналог конъюнкции), $\lor$ (аналог дизъюнкции), унарной операцией $\lnot$ (аналог отрицания) и двумя выделенными элементами: 0 (или Ложь) и 1 (или Истина) такими, что для всех a, b и c из множества A верны следующие аксиомы:

$a \lor (b \lor c) = (a \lor b) \lor c$	$a \land (b \land c) = (a \land b) \land c$	ассоциативность
$a \lor b = b \lor a$	$a \land b = b \land a$	коммутативность
$a \lor (a \land b) = a$	$a \land (a \lor b) = a$	законы поглощения
$a \lor (b \land c) = (a \lor b) \land (a \lor c)$	$a \land (b \lor c) = (a \land b) \lor (a \land c)$	дистрибутивность
$a \lor \lnot a = 1$	$a \land \lnot a = 0$	дополнительность

$\begin & a+(b+c)=(a+b)+c & a(bc)=(ab)c \\ & a+b=b+a & ab=ba \\ & a+ab=a & a(a+b)=a \\ & a+bc=(a+b)(a+c) & a(b+c)=ab+ac \\ & a+\bar=1 & a\bar = 0 \end» width=»» height=»» /> Первые три аксиомы означают, что (A, <img decoding=$ , $\lor$ ) является решёткой. Таким образом, булева алгебра может быть определена как дистрибутивная решётка, в которой выполнены две последние аксиомы. Структура, в которой выполняются все аксиомы, кроме предпоследней, называется псевдобулевой алгеброй.

Некоторые свойства

Из аксиом видно, что наименьшим элементом является 0, наибольшим является 1, а дополнение ¬a любого элемента a однозначно определено. Для всех a и b из A верны также следующие равенства:

$a \lor a = a$	$a \land a = a$
$a \lor 0 = a$	$a \land 1 = a$
$a \lor 1 = 1$	$a \land 0 = 0$
$\lnot 0 = 1$	$\lnot 1 = 0$	дополнение 0 есть 1 и наоборот
$\lnot (a \lor b) = \lnot a \land \lnot b$	$\lnot (a \land b) = \lnot a \lor \lnot b$	законы де Моргана
$\lnot \lnot a = a$ .	инволютивность отрицания, закон снятия двойного отрицания.

Основные тождества

В данном разделе повторяются свойства и аксиомы, описанные выше с добавлением ещё нескольких.

Сводная таблица свойств и аксиом, описанных выше:

$a \lor b = b \lor a$	$a \land b = b \land a$	1 коммутативность, переместительность
$a \lor (b \lor c) = (a \lor b) \lor c$	$a \land (b \land c) = (a \land b) \land c$	2 ассоциативность, сочетательность
3.1 конъюнкция относительно дизъюнкции $a \lor (b \land c) = (a \lor b) \land (a \lor c)$	3.2 дизъюнкция относительно конъюнкции $a \land (b \lor c) = (a \land b) \lor (a \land c)$	3 дистрибутивность, распределительность
$a \lor \lnot a = 1$	$a \land \lnot a = 0$	4 комплементность, дополнительность (свойства отрицаний)
$\lnot (a \lor b) = \lnot a \land \lnot b$	$\lnot (a \land b) = \lnot a \lor \lnot b$	5 законы де Моргана
$a \lor (a \land b) = a$	$a \land (a \lor b) = a$	6 законы поглощения
$a \lor(\lnot a \land b) = a \lor b$	$a \land(\lnot a \lor b) = a \land b$	7 Блейка-Порецкого
$a \lor a = a$	$a \land a = a$	8 Идемпотентность
$\lnot \lnot a = a$	9 инволютивность отрицания, закон снятия двойного отрицания
$a \lor 0 = a$	$a \land 1 = a$	10 свойства констант
$a \lor 1 = 1$	$a \land 0 = 0$
дополнение 0 есть 1 $\lnot 0 = 1$	дополнение 1 есть 0 $\lnot 1 = 0$
$(a \lor b)\land(\lnot a \lor b)=b$	$(a \land b) \lor (\lnot a \land b)=b$	11 Склеивание

Примеры

Самая простая нетривиальная булева алгебра содержит всего два элемента, 0 и 1, а действия в ней определяются следующей таблицей:

∧	0	1
0	0	0
1	0	1

∨	0	1
0	0	1
1	1	1

a	0	1
¬a	1	0

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

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

Множество всех подмножеств данного множества S образует булеву алгебру относительно операций ∨ := ∪ (объединение), ∧ := ∩ (пересечение) и унарной операции дополнения. Наименьший элемент здесь — пустое множество, а наибольший — всё S.

Если R — произвольное кольцо, то на нём можно определить множество центральных идемпотентов так:
A = < e ∈ R : e² = e, ex = xe, ∀x ∈ R >,
тогда множество A будет булевой алгеброй с операциями e ∨ f := e + f − ef и e ∧ f := ef.

Принцип двойственности

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

Представления булевых алгебр

Можно доказать, что любая конечная булева алгебра изоморфна булевой алгебре всех подмножеств какого-то множества. Отсюда следует, что количество элементов в любой конечной булевой алгебре будет степенью двойки.

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

Аксиоматизация

В 1933 г. американский математик Хантингтон предложил следующую аксиоматизацию для булевых алгебр:

Здесь использованы обозначения Хантингтона: + означает дизъюнкцию, n — отрицание.

Герберт Роббинс поставил следующий вопрос: можно ли сократить последнюю аксиому так, как написано ниже, то есть будет ли определённая выписанными ниже аксиомами структура булевой алгеброй?

Аксиоматизация алгебры Роббинса:

Этот вопрос оставался открытым с 30-х годов и был любимым вопросом Тарского и его учеников.

В 1996 г. Вильям МакКьюн, используя некоторые полученные до него результаты, дал утвердительный ответ на этот вопрос. Таким образом, любая алгебра Роббинса является булевой алгеброй.

См. также

Алгебра логики
Булева функция
Битовые операции

Примечания

↑D. A. VladimirovSpringer Online Reference Works — Boolean algebra (англ.) . Springer-Verlag (2002). Архивировано из первоисточника 9 февраля 2012.Проверено 4 августа 2010.
↑Владимиров Д. А.Булевы алгебры. — М .: «Наука», 1969. — С. 19.
↑Кузнецов О. П., Адельсон-Вельский Г. М. Дискретная математика для инженера. — М .: Энергоатомиздат, 1988. — С. 58.

Литература

Владимиров Д. А.Булевы алгебры. — М .: «Наука», 1969. — 320 с.
Иванов Б. Н.Дискретная математика. Алгоритмы и программы. Расширенный курс. — М .: «Известия», 2011. — 512 с. — ISBN 978-5-206-00824-1
Кузнецов О. П., Адельсон-Вельский Г. М. Дискретная математика для инженера. — М .: Энергоатомиздат, 1988. — 480 с.

Проставив сноски, внести более точные указания на источники.