Булево выражение – Булево выражение — это… Что такое Булево выражение?

Булево выражение — это… Что такое Булево выражение?



Булево выражение

Логическое выражение в программировании — конструкция языка программирования, результатом вычисления которой является «истина» или «ложь».

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

Операция	Си	Паскаль
Равно	==	=
Не равно	!=	<>
Больше	>	>
Меньше	<	<
Больше или равно	>=	>=
Меньше или равно	<=	<=

Например, логическое выражение «5 > 3» истинно, а «6 != 6» ложно.

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

Примеры сложных логических выражений:

Язык	Выражение
си	!A && (B || C)
паскаль	not A and (B or C)
си	A > 3 && B < 6
паскаль	(A > 3) and (B < 6)

См. также

Wikimedia Foundation. 2010.

• Булдакова, Людмила Степановна
• Булева сигма-алгебра

Смотреть что такое «Булево выражение» в других словарях:

• булево выражение — — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Булево выражение Математическое выражение, в котором все переменные имеют значения либо 0 либо 1. [http://www.rfcmd.ru/glossword/1.8/index.php?a=index …   Справочник технического переводчика

• булево выражение — — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Булево выражение Математическое выражение, в котором все переменные имеют значения либо 0 либо 1. [http://www.rfcmd.ru/glossword/1.8/index.php?a=index …   Справочник технического переводчика

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

dic.academic.ru

Булевы выражения — это… Что такое Булевы выражения?

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

Основные сведения

Каждая булева функция арности n полностью определяется заданием своих значений на своей области определения, то есть на всех булевых векторах длины n. Число таких векторов равно 2ⁿ. Поскольку на каждом векторе функция может принимать значение либо 0, либо 1, количество всех n-арных булевых функций равно . То, что каждая булева функция задаётся конечным массивом данных, позволяет представлять их в виде таблиц. Такие таблицы носят название таблиц истинности и в общем случае имеют вид:

x1	x2	…	xn	f(x1,x2,…,xn)
0	0	…	0	f(0,0,…,0)
1	0	…	0	f(1,0,…,0)
0	1	…	0	f(0,1,…,0)
1	1	…	0	f(1,1,…,0)
0	1	…	1	f(0,1,…,1)
1	1	…	1	f(1,1,…,1)

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

Нульарные функции

При n = 0 количество булевых функций сводится к двум, первая из них тождественно равна 0, а вторая 1. Их называют булевыми константами — тоджественный нуль и тоджественная единица.

Унарные функции

При n = 1 число булевых функций равно . Им соответствуют следующие таблицы истинности.

x	g1 ()	g2 (=)	g3 (1)	g4 (0)
0	1	0	1	0
1	0	1	1	0

Здесь:

• g₁(x) — отрицание (обозначения: ),
• g₂(x) — тождественная функция,
• g₃(x) и g₄(x) — соответственно, тождественная истина и тождественная ложь.

Бинарные функции

При n = 2 число булевых функций равно . Им соответствуют следующие таблицы истинности.

Здесь:

• f₁(x, y) — конъюнкция (обозначения: x&y, ),
• f₂(x, y) — дизъюнкция (обозначение: ),
• f₃(x, y) — эквивалентность (обозначения: ),
• f₄(x, y) — исключающее «или» (сложение по модулю 2; обозначения: ),
• f₅(x, y) — импликация от y к x (обозначения: ),
• f₆(x, y) — импликация от x к y (обозначения: ),
• f₇(x, y) — стрелка Пи́рса (функция Да́ггера, функция Ве́бба, антидизъюнкция; обозначение: ),
• f₈(x, y) — штрих Ше́ффера (антиконъюнкция; обозначение: ),
• f₉(x, y) — отрицание импликации f₆(x, y),
• f₁₀(x, y) — отрицание импликации f₅(x, y),
• f₁₁(x, y) = g₁(x),
• f₁₂(x, y) = g₁(y),
• f₁₃(x, y) = g₂(x),
• f₁₄(x, y) = g₂(y),
• f₁₅(x, y), f₁₆(x, y) — тождественная истина и тождественная ложь.

Полные системы булевых функций

Суперпозиция и замкнутые классы функций

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

x	y	z		f(x,y,z)
0	0	0		1
0	0	1		1
0	1	0		1
0	1	1		1
1	0	0		0
1	0	1		0
1	1	0		1
1	1	1		0

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

В качестве простейших примеров замкнутых классов булевых функций можно назвать множество {x}, состоящее из одной тождественной функции, или множество {0}, все функции из которого тождественно равны нулю вне зависимости от своих аргументов. Замкнуты также множество функций и множество всех унарных функций. А вот объединение замкнутых классов может таковым уже не являться. Например, объединив классы {0} и , мы с помощью суперпозиции сможем получить константу 1, которая в исходных классах отсутствовала.

Разумеется, множество P₂ всех возможных булевых функций тоже является замкнутым.

Тождественность и двойственность

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

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

А проверка таблиц, построенных для некоторых суперпозиций, даст следующие результаты:

(дистрибутивность конъюнкции и дизъюнкции)

Функция называется двойственной функции , если . Легко показать, что в этом равенстве f и g можно поменять местами, то есть функции f и g двойственны друг другу. Из простейших функций двойственны друг другу константы 0 и 1, а из законов де Моргана следует двойственность конъюнкции и дизъюнкции. Тождественная функция, как и функция отрицания, двойственна сама себе.

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

Полнота системы, критерий Поста

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

P₂.

Американский математик Эмиль Пост ввёл в рассмотрение следующие замкнутые классы булевых функций:

• Функции, сохраняющие константу T₀ и T₁;
• Самодвойственные функции S;
• Монотонные функции M;
• Линейные функции L.

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

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

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

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

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

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

Дизъюнктивная нормальная форма (ДНФ)

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

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

Легко убедиться, что каждой булевой функции соответствует некоторая ДНФ, и даже СДНФ. Для этого достаточно взять таблицу истинности этой функции и найти все булевы векторы, на которых её значение равно 1. Для каждого такого вектора строится конъюнкция , где . Если взять дизъюнкцию этих конъюнкций, то результатом очевидно будет СДНФ. Поскольку на всех булевых векторах её значения совпадают со значениями исходной функции, она будет СДНФ этой функции. Например, для импликации , результатом будет , что можно упростить до .

Конъюнктивная нормальная форма (КНФ)

Конъюнктивная нормальная форма (КНФ) определяется двойственно к ДНФ. Простой дизъюнкцией или дизъюнктом называется дизъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная входит в неё не более одного раза. КНФ — это конъюнкция простых дизъюнкций.

Совершенной конъюнктивной нормальной формой (СКНФ), относительно некоторого заданного конечного набора переменных, называется такая КНФ, у которой в каждую дизъюнкцию входят все переменные данного набора, причём в одном и том же порядке. Поскольку (С)КНФ и (С)ДНФ взаимодвойственны, свойства (С)КНФ повторяют все свойства (С)ДНФ, грубо говоря, «с точностью до наоборот».

КНФ может быть преобразована к эквивалентной ей ДНФ, путём раскрытия скобок по правилу:

которое выражает дистрибутивность конъюнкции относительно дизъюнкции. После этого, необходимо в каждой конъюнкции удалить повторяющиеся переменные или их отрицания, а также выбросить из дизъюнкции все конъюнкции, в которых встречается переменная вместе со своим отрицанием. При этом, результатом не обязательно будет СДНФ, даже если исходная КНФ была СКНФ. Точно также, можно всегда перейти от ДНФ к КНФ. Для этого следует использовать правило

выражающее дистрибутивность дизъюнкции относительно конъюнкции. Результат нужно преобразовать способом, описанным выше, заменив слово «конъюнкция» на «дизъюнкция» и наоборот.

Полиномы Жегалкина

Полином Жегалкина это форма представления логической функции с помощью Функции Жегалкина (Исключающее ИЛИ). Для получения полинома Жегалкина следует выполнить следуюющие действия:

1. Получить ДНФ функции
2. Все ИЛИ заменить на Исключающее ИЛИ
3. Во всех термах заменить элементы с отрицанием на конструкцию: («элемент» «исключающее ИЛИ» 1)
4. Раскрыть скобки по правилам алгебры Жегалкина и привести попарно одинаковые термы

BDD

См. также

Литература

Ссылки

Wikimedia Foundation. 2010.

dic.academic.ru

булево выражение — это… Что такое булево выражение?



булево выражение

 

булево выражение
—
[Л.Г.Суменко. Англо-русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.]

Булево выражение
Математическое выражение, в котором все переменные имеют значения либо 0 либо 1.
[http://www.rfcmd.ru/glossword/1.8/index.php?a=index&d=23]

Параллельные тексты EN-RU

The output signal of an equation can be fed into a further, higher order equation as an input signal thus creating a sequence of interlinked Boolean equations.
[Schneider Electric]

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

The Boolean equations need to be defined without the use of brackets.
[Schneider Electric]

Булевы выражения должны определяться без скобок.
[Перевод Интент]

Тематики

• Булева алгебра, элементы цифровой техники

Синонимы

• булева функция

EN

• Boolean
• Boolean equation
• Boolean expression

Справочник технического переводчика. – Интент. 2009-2013.

• видеокоммутатор
• коэффициент искажения синусоидальности кривой напряжения (тока)

Смотреть что такое «булево выражение» в других словарях:

• булево выражение — — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Булево выражение Математическое выражение, в котором все переменные имеют значения либо 0 либо 1. [http://www.rfcmd.ru/glossword/1.8/index.php?a=index …   Справочник технического переводчика

• Булево выражение — Логическое выражение в программировании конструкция языка программирования, результатом вычисления которой является «истина» или «ложь». В большинстве языков программирования среднего и высокого уровня определён набор встроенных операций… …   Википедия

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

technical_translator_dictionary.academic.ru

булево выражение — это… Что такое булево выражение?



булево выражение

 

булево выражение
—
[Л.Г.Суменко. Англо-русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.]

Булево выражение
Математическое выражение, в котором все переменные имеют значения либо 0 либо 1.
[http://www.rfcmd.ru/glossword/1.8/index.php?a=index&d=23]

Параллельные тексты EN-RU

The output signal of an equation can be fed into a further, higher order equation as an input signal thus creating a sequence of interlinked Boolean equations.
[Schneider Electric]

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

The Boolean equations need to be defined without the use of brackets.
[Schneider Electric]

Булевы выражения должны определяться без скобок.
[Перевод Интент]

Тематики

• Булева алгебра, элементы цифровой техники

Синонимы

• булева функция

EN

• Boolean
• Boolean equation
• Boolean expression

Справочник технического переводчика. – Интент. 2009-2013.

• булева алгебра элементарных логических операции
• булево линейное программирование

Смотреть что такое «булево выражение» в других словарях:

• булево выражение — — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Булево выражение Математическое выражение, в котором все переменные имеют значения либо 0 либо 1. [http://www.rfcmd.ru/glossword/1.8/index.php?a=index …   Справочник технического переводчика

• Булево выражение — Логическое выражение в программировании конструкция языка программирования, результатом вычисления которой является «истина» или «ложь». В большинстве языков программирования среднего и высокого уровня определён набор встроенных операций… …   Википедия

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

technical_translator_dictionary.academic.ru

булево выражение — это… Что такое булево выражение?



булево выражение

1. Boolean expression
2. Boolean equation
3. Boolean

 

булево выражение
—
[Л.Г.Суменко. Англо-русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.]

Булево выражение
Математическое выражение, в котором все переменные имеют значения либо 0 либо 1.
[http://www.rfcmd.ru/glossword/1.8/index.php?a=index&d=23]

Параллельные тексты EN-RU

The output signal of an equation can be fed into a further, higher order equation as an input signal thus creating a sequence of interlinked Boolean equations.
[Schneider Electric]

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

The Boolean equations need to be defined without the use of brackets.
[Schneider Electric]

Булевы выражения должны определяться без скобок.
[Перевод Интент]

Тематики

• Булева алгебра, элементы цифровой техники

Синонимы

• булева функция

EN

• Boolean
• Boolean equation
• Boolean expression

Русско-английский словарь нормативно-технической терминологии. academic.ru. 2015.

• булева алгебра элементарных логических операции
• булево линейное программирование

Смотреть что такое «булево выражение» в других словарях:

• булево выражение — — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Булево выражение Математическое выражение, в котором все переменные имеют значения либо 0 либо 1. [http://www.rfcmd.ru/glossword/1.8/index.php?a=index …   Справочник технического переводчика

• булево выражение — — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Булево выражение Математическое выражение, в котором все переменные имеют значения либо 0 либо 1. [http://www.rfcmd.ru/glossword/1.8/index.php?a=index …   Справочник технического переводчика

• Булево выражение — Логическое выражение в программировании конструкция языка программирования, результатом вычисления которой является «истина» или «ложь». В большинстве языков программирования среднего и высокого уровня определён набор встроенных операций… …   Википедия

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

normative_ru_en.academic.ru

Булевское выражение — Большая Энциклопедия Нефти и Газа, статья, страница 1

Булевское выражение

Cтраница 1

Булевское выражение — это выражение, которое принимает значение True или False, Оно состоит из выражений отношений, булевских операторов, булевских переменных и / или других булевских выражений.  [1]

Булевское выражение служит для задания правил вычисления некоторого логического значения — подобно тому, как арифметическое выражение служит для задания правил вычисления некоторого числового значения.  [2]

Условные арифметические и булевские выражения также могут использоваться в операторах присваивания в качестве их правых частей.  [3]

Первичными булевскими выражениями являются логические значения true и false, отношения, логические переменные, указатели логических функций и булевские выражения ( безусловные или условные), заключенные в круглые скобки.  [4]

Если булевское выражение Е в (7.16) в свою очередь является условным, то для вычисления его значения снова применяем то же самое правило, так что вычисление значения условного выражения носит рекурсивный характер, Например, в качестве значения условного выражения вида (7.14) принимается значение выражения В2, если В1 принимает значение истина, значение выражения В4, если В1 принимает значение ложь, но ВЗ принимает значение истина, и значение выражения В5, если и В1, и ВЗ принимают значение ложь.  [5]

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

Имеются дополнительные булевские выражения для сравнения элементных выражений и множеств. Например, множество А меньше множества В, если оно является соответствующим подмножеством В.  [7]

А — арифметические и булевские выражения, но и идентификаторы, описанные в программе в качестве массивов.  [8]

Порядок вычисления булевских выражений важен и в случае сравнения указателей.  [9]

В определении первичного булевского выражения фигурируют также указатели логических функций.  [10]

Правила являются булевскими выражениями.  [12]

THEN; рассматривается булевское выражение. Если его значение ненулевое ( истина), то выполняется следующий оператор после THEN.  [13]

Отметим еще некоторые простейшие булевские выражения, которые остаются истинными, независимо от истинности или ложности входящих в них высказываний.  [14]

Как видно, условное булевское выражение определяется рекурсивно: в его образовании участвует само определяемое понятие ( условное булевское выражение как частный случай булевского выражения) как в условии, так и справа от символа иначе.  [15]

Страницы:      1    2    3    4

www.ngpedia.ru

Построение таблицы истинности по булеву выражению

Построим таблицу истинности для следующей функции:

F(Xl,X2,XЗ) = (X1 V Х2) • (X1 v not ХЗ) v not (X2 • ХЗ)

Так как n=3, то всего может быть 8 различных комбинаций значений аргументов. (Для записи комбинаций следует пользоваться двоичной системой счисления.)

X1 X2 X3 F

X1	X2	X3	F
0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	1

Вычислим значение F для каждого набора (х1,x2,х3).

F(0,0,0) = (0 or not 0) • (0 or 0) or not ( 0 • 0) = (0 v 1) •0 or not ( 0 ) = 0 •1 or 1=1

F(0,0,1) = (0 or not 0) • (0 or 1) or not (o •1) = (0 or 1) •1 or 1 = 1 и так далее.

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

Получение булевых выражений по таблицам истинности

Правила построения булева выражения:

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

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

Пример. Дана таблица истинности [2]:

X1	X2	X3	F
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	0

Построим булево выражение для F. Найдем строки, в которых F=1.Это вторая, третья и шестая.

Для второй строки X1=0, Х2=0, X3=1. Эту строку описывает минтерм not x1•not x2•X3

Для третьей строки X1=0, Х2=1, X3=0. Эту строку описывает минтерм not x1•X2•not x3

Для шестой строки X1=1, X2=0, X3=1. Эту строку описывает минтерм X1•not x2•X3

Объединяя термы, получим булево выражение для F:=not x1•not x2•X3 or not x1•X2•not x3 or X1•not x2•X3

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

studfiles.net