Опубликовано

Законы булевой алгебры

Понятие алгебры логики

На этом уроке знакомимся с алгеброй логики, одним из основателей которой стал английский математик Джордж Буль (1815-1864), который был из довольно бедной семьи, а в юности зарабатывал переводами сочинений древнегреческих философов. За этим занятием его и посетила мысль о том, что высказываниям можно присваивать значения 1 («истина») и 0 «ложь».

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

Создание алгебры логики в середине ХIХ века в трудах Джорджа Буля представляло собой попытку решать традиционные логические задачи алгебраическими методами.

Функция от n переменных называется логической или булевой или переключательной или функцией алгебры логики, если сама функция и любой из ее аргументов могут принимать значения только из множества {0, 1}. Описанную функцию часто называют также булевым вектором. Количество функций от n переменных равно 2 в степени n. То же самое можно сказать и иначе: число различных n-мерных булевых векторов равно 2 в степени n. А число различных функций алгебры логики от этих векторов равно уже .

Значениям переменной в булевой алгебре соответствуют состояниям элементов микросхем компьютера или любого другого электронного устройства: сигнал присутствует (логическая «1») или сигнал отсутствует (логический «0»).

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

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

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

Логические функции

Логические функции одной переменной

Функция Название Обозначение
Константа нуля
Повторение x
Логическое отрицание, инверсия, «НЕ»
Константа единицы
Переменная Логические функции
x
0 0 0 1 1
1 0 1 0 1

Логические функции двух переменных

Функция Название Обозначение
Константа нуля или False
Логическое умножение, конъюнкция, «И» или или или
Запрет по или
Переменная
Запрет по или
Переменная
Сложение по модулю 2, отрицание эквивалентности, исключающее «ИЛИ» или или
Логическое сложение, дизъюнкция, «ИЛИ» или или или
Функция Пирса (Вебба), «ИЛИ-НЕ» или или
Логическая равнозначность, эквиваленция или или или
Отрицание
Правая импликация или
Отрицание
Левая импликация или
Функция Шеффера, «И-НЕ» или или
Константа единицы или True
X1 0 0 1 1
X2 0 1 0 1
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1

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

Ответить на контрольные вопросы, а затем посмотреть ответы

Контрольный вопрос 1. Даны две переменные x1 и x2. Число различных булевых векторов и различных ФАЛ от полученных векторов равны соответственно:

  • 8 и 16
  • 8 и 32
  • 4 и 8
  • 4 и 16

Контрольный вопрос 2. Какие из функций не являются ФАЛ одной переменной (и одна, и вторая в варианте ответа):

  • отрицание и сложение по модулю два
  • эквивалентность и повторение x
  • отрицание и импликация
  • функция Шеффера и эквивалентность
  • запрет по x2 и отрицание

Правильные ответы на вопрос 1 и вопрос 2.

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

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

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

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

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

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

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

Ссылки

Логика

Формальная

Логические операции с понятиями

Изменение содержания понятия: отрицание • ограничение • обобщение • деление
Изменение объёма понятия: сложение • умножение • вычитание

Типы: Многозначная логика

Математическая
(теоретическая, символическая)

Логические связки (операции) над высказываниями

Высказывание — построение над множеством {B, , , , 0, 1}
В — непустое множество, над элементами которого определены три операции: конъюнкция ( или &,бинарная) • дизъюнкция (,бинарная) • отрицание (,унарная)

2 константы: 0 • 1

Прочее

импликация ()

Не следует путать с булевой алгеброй. Запрос «Двоичная логика» перенаправляется сюда. На эту тему нужна отдельная статья.

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

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

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

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

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

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

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

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

> Аксиомы

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

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

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

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

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

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

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

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

> См. также

  • Булева алгебра
  • Булева функция
  • Битовые операции
  • Логика высказываний
  • Функциональная полнота

Булевы типы

Результатом логического выражения всегда является булево (логическое) значение. Булев тип данных (boolean) может принимать только два значения (true или false). Эти величины упорядочены следующим образом: false < true. Это значит, что данные булевого типа являются не только результатом операций отношения, но и могут выступать в роли операндов операции отношения. Также к ним можно применять функции ord, succ, pred, процедуры inc и dec.

Значение типа boolean занимает в памяти 1 байт.

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

Кроме типа boolean в Pascal введены еще три булевых типа — bytebool (занимает 1 байт), wordbool (занимает 2 байта) и longbool (занимает 4 байта).
Для всех булевых типов значению false соответствует 0, а значению true — любое ненулевое значение. Логические переменные, принадлежащие разным булевым типам, ведут себя по-разному при выполнении над ними операций. Ниже приводится пример, реализованный на языке FreePascal (в комментариях отображается результат).

var b:boolean; wb:wordbool; begin b:= false; b:= pred(b); writeln(b,’ ‘,ord(b)); // TRUE 255 writeln(b=true); // TRUE wb:= false; wb:= pred(wb); writeln(wb,’ ‘,ord(wb)); // TRUE -1 b:= true; b:= succ(b); writeln(b,’ ‘,ord(b)); // TRUE 2 wb:= true; wb:= succ(wb); writeln(wb,’ ‘,ord(wb)); // FALSE 0 end.

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

С помощью логических операторов можно формировать сложные логические выражения. Логические операторы часто применяются по отношению к простым логическим выражениям.

В языке программирования Pascal предусмотрены следующие логические операции:

true xor true = false
true xor false = true
false xor true = true
false xor false = false

  • Конъюнкция (логическое умножение, пересечение) — and. Выражение a and b дает значение true только в том случае, если a и b имеют значение true. Во всех остальных случаях значения выражения a and b дает false. true and true = true true and false = false false and true = false false and false = false
  • Дизъюнкция (логическое сложение, объединение) – or. Выражение a or b дает значение false только в том случае, если a и b имеют значение false. Во всех остальных случаях результат – true. true or true = true true or false = true false or true = true false or false = false
  • Отрицание (инверсия) – not. Выражение not a имеет значение, противоположное значению a. not true = false not false = true
  • Исключающее ИЛИ – xor. Выражение a xor b дает значение true только в том случае, когда только один из операндов имеет значение true.

Последовательность выполнения логических операторов: not, and, or.

В языке Паскаль сначала выполняются логические операторы (and, or, xor, not), а уже потом операторы отношений (>, >=, <, <=, <>, =), поэтому не нужно забывать расставлять скобки в сложных логических выражениях.

Сложные булевы выражения могут не обрабатываться до конца, если продолжение вычислений не изменит результат. Если булево выражение в обязательном порядке нужно обрабатывать до конца, то это обеспечивается включением директивы компиляции {B+}.

Стандартные булевские функции

  • odd(x) = true, если x нечетный (x целый тип);
  • eoln(x) = true, если встретился конец строки текстового файла x;
  • eof(x) = true, если встретился конец файла x.

В остальных случаях эти функции принимают значение false.

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

Пример 1.

Составить таблицу истинности функции трех переменных, заданной формулой:

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

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

Примеры функционально полных систем логических функций:

и другие.

Основополагающим и наиболее хорошо изученным является базис {&, v, -}.

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

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

Следовательно система булевых функций (операций) {&, v, -} функционально полна.

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

Система операций булевой алгебры { &, v, — } функционально полна. Это означает, что переход от табличного задания любой логической функции к формуле булевой алгебры, или булевой формуле, всегда возможен.

Переход от табличного задания логической функции к булевой формуле осуществляется в 3 этапа:

1. для каждого набора значений переменных х1, х2, …, хn на котором функция f(х1, х2, …, хn) равна 1, выписываются конъюнкции всех переменных;

2. над теми переменными, которые на этом наборе равны 0, ставятся отрицания;

3. все такие конъюнкции соединяются знаками дизъюнкции.

Полученная таким образом формула называется совершенной дизъюнктивной нормальной формой (СДНФ) логической функции f(х1, х2, …, хn).

Для каждой функции СДНФ единственна (с точностью до перестановок переменных или конъюнкций).

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *