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

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

Дата добавления: 2015-07-23 ; просмотров: 5017 ; Нарушение авторских прав

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

Обозначим через B двухэлементное множество <0,1>. Тогда

это множество всех двоичных последовательностей (наборов, векторов) длины n. Булевой функцией от n переменных (аргументов) называется любая функция f(x1, xn): B n -> B . Каждый из ее аргументов xi, 1 k . В нашем случае B=<0, 1>, а A = B n . Тогда m=2 и k= |B n | = 2 n . Отсюда следует утверждение теоремы.

Суперпозицией булевых функций f0 и f1. fn называется функция f(x1. xm) = f0(g1(x1. xm). gk(x1. xm)), где каждая из функций gi(x1,. xm) либо совпадает с одной из переменных (тождественная функция), либо – с одной из функций f1. fn.

19. Число булевых функций от n аргументов. Выражение булевых функций через конъюнкцию, дизъюнкцию и отрицание (теорема о разложении функции по переменной и теорема о представлении булевых функций через конъюнкцию, дизъюнкцию и отрицание).

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

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

§ правильная, если в неё каждая переменная входит не более одного раза (включая отрицание);

§ полная, если в неё каждая переменная (или её отрицание) входит ровно 1 раз;

§ монотонная, если она не содержит отрицаний переменных.

Например — является ДНФ.

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

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

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

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

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

Читайте также:  Самая быстрая виртуальная машина

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

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

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

Булевы функции от $n$ переменных
  1. Услуги проектирования
  2. Алгебра логики [Ф.Г. Кораблёв]
  3. Булевы функции от $n$ переменных

Дадим два эквивалентных определения булевой функции.

Определение 1. Функцию $f (x_1, x_2, … , x_n)$ назовем булевой, если она сама и ее аргументы принимают значения 0 и 1.

Определение 2. Булевой функцией $f(x_1, x_2, … , x_n)$ назовем однозначное отображение булева пространства $B^n$ в булево множество $B$, то есть $f : B^n
ightarrow B$.

Пример. Булева функция двух аргументов, принимающая на наборах $01$ и $11$ значение $0$, а на наборах $00$ и $10$ значение $1$:

Определение. Булевы функции равны, $f_1(x_1, …, x_n) = f_2(x_1, …, x_n)$, если на одинаковых наборах они принимают одинаковые значения.

Число булевых функций от $n$ переменных равно $2^ < 2^ < n >> $

Пример 1. Число булевых функций от $n = 1$ переменной равно $2^ < 2^ < n >> = 2^ < 2^ < 1 >> = 2^ < 2 >= 4$. Это $0, 1, x$ и $ar < x >$

Пример 2. Число булевых функций от $n = 2$ переменных равно $2^ < 2^ < n >> = 2^ < 2^ < 2 >> = 2^ < 4 >= 16$. Они все указаны в таблице

$x_1$ $x_2$ $f_1$ $f_2$ $f_3$ $f_4$ $f_5$ $f_6$ $f_7$ $f_8$ $f_9$ $f_ < 10 >$ $f_ < 11 >$ $f_ < 12 >$ $f_ < 13 >$ $f_ < 14 >$ $f_ < 15 >$ $f_ < 16 >$
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1

У некоторых функций есть специальные названия.

$f_1(x_1, x_2) = 0$ — тождественный нуль;

$f_2(x_1, x_2) = x_1And x_2$ — конъюнкция. Очень часто знак $And $ опускают и пишут просто $x_1x_2$;

$f_7(x_1, x_2) = x_1oplus x_2$ — сложение по модулю 2;

$f_8(x_1, x_2) = x_1vee x_2$ — дезъюнкция;

$f_9(x_1, x_2) = x_1downarrow x_2$ — стрелка Пирса;

$f_ < 10 >(x_1, x_2) = x_1equiv x_2$ — эквиваленция;

$f_ < 14 >(x_1, x_2) = x_1
ightarrow x_2$ — импликация;

$f_ < 15 >(x_1, x_2) = x_1|x_2$ — штрих Шеффера;

$f_ < 16 >(x_1, x_2) = 1$ — тождественная единица.

Далее:

Линейный интеграл и циркуляция векторного поля

Логические следствия

Инвариантное определение дивергенции

Теорема Остроградского

Выражение площади плоской области через криволинейный интеграл

Соленоидальное векторное поле

Вычисление криволинейного интеграла второго рода. Примеры.

Функции k-значной логики. Элементарные функции. Лемма об аналоге правила де Моргана

Поверхностный интеграл первого рода и его свойства

Полином Жегалкина. Пример.

Переход от двойного интеграла к повторному. Изменение порядка интегрирования. Переход к полярным координатам

Читайте также:  Мультиварка скороварка oursson mp5010psd рецепты

Свойства двойного интеграла

Нормальные формы

СДНФ. Теорема о представлении в виде СДНФ. Построение СДНФ по таблице

Механические приложения двойного интеграла

Огравление $Rightarrow $

Булевы функции от одной переменной – это отображения множества <0,1>в себя. Булевы функции от одной переменной можно рассматривать как унарные операции на множестве

<0,1>. В следующей таблице приведены все четыре булевы функции от одной переменной.

x g 0 ( x ) g 1 ( x ) g 2 ( x ) g 3 ( x )

g 0 ( x )=0 – функция, тождественно равная 0 (тождественный ноль);

g 1 ( x )= x – тождественная функция;

g 2 ( x )=1– x – эта функция соответствует отрицанию и носит то же название; в теории булевых функций отрицание принято обозначать через x ’, поэтому мы будем писать g 2 ( x )= x ’;

g 3 ( x )=1 – функция, тождественно равная 1 (тождественная единица).

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

0 – тождественный ноль

– сложение по модулю 2

1 – тождественная единица

перечисленные функции (с помощью

суперпозиций), можно строить более сложные булевы функции,

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

( xy )’= x ’ y ’; ( x y )’= x ’ y ’.

Кроме того, имеем:

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

x ’ = x → 0 = x | x = x ↓ x = 1 x ;

xy = ( x ’ y ’)’ = x ’ ↓ y ’ = ( x ↓ x ) ↓ ( y ↓ y );

x y = ( x ’ y ’)’ = x ’ → y = =( x → y ) → y = x ’| y ’ = ( x | x )|( y | y ); x → y = x ’ y ;

x ↔ y = ( x → y ) ( y → x ) = xy x ’ y ’; x y = xy ’ x ’ y .

Все эти равенства легко проверяются с помощью таблиц.

Принцип двойственности естественным образом переносится на булевы функции. Приведем необходимые формулировки. Двойственной к булевой функции f ( x , y ,…, z ) называется функция

f * ( x , y ,…, z )= f ’( x ’, y ’,…, z ’).

Если f ( x , y ,…, z ) представлена формулой, содержащей только конъюнкции, дизъюнкции и отрицания, то двойственная функция получается заменой в этой формуле конъюнкций на дизъюнкции, а дизъюнкций на конъюнкции.

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

x y z f ( x , y , z )

f ( x , y , z ) = x ’ y ’ z ’ xy ’ z ’ xyz .

Каждый из трех дизъюнктивных членов (слагаемых) записанной формулы соответствует набору значений аргументов, для которого функция принимает значение 1. Каждое слагаемое содержит все три аргумента функции; отрицанием снабжены те из них, которые имеют значение 0 в соответствующем наборе. Так, набору (0,0,0) соответствует слагаемое x ’ y ’ z ’, набору (1,0,0) – слагаемое xy ’ z ’, набору (1,1,1)

– слагаемое xyz . Каждый из дизъюнктивных членов принимает значение 1 на своем наборе значений переменных и значение 0

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

Читайте также:  Где находится видеокарта в ноутбуке lenovo

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

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

f ( x , y , z ) = ( x y z ’)( x y ’ z )( x y ’ z ’)( x ’ y z ’)( x ’ y ’ z ).

Каждый из пяти конъюнктивных членов (множителей) соответствует набору значений аргументов, для которого функция принимает значение 0. Каждый множитель содержит все три аргумента функции; отрицанием снабжены те из них, которые имеют значение 1 в соответствующем наборе. Так, набору (0,0,1) соответствует множитель xyz ’, набору (0,1,0) –

множитель xy ’ z , и т. д. Каждый из конъюнктивных членов принимает значение 0 на своем наборе значений переменных и значение 1 – на всех остальных. Конъюнкция этих трех множителей принимает значение 0 лишь тогда, когда значение 0 принимает хотя бы один из множителей. Таким образом, функция в правой части записанного равенства принимает значение 0 на тех же трех наборах значений аргументов, что и функция f .

Описанный выше способ построения СДНФ и СКНФ опирается на следующую теорему о разложении функции по переменной.

Теорема. Пусть f ( x 1 , x 2 ,…, x n ) – произвольная булева функция. Тогда

f ( x 1 , x 2 ,…, x n ) = x 1 f (1, x 2 ,…, x n ) x 1 ’ f (0, x 2 ,…, x n );

f ( x 1 , x 2 ,…, x n ) = ( x 1 f (0, x 2 ,…, x n ))( x 1 ’ f (1, x 2 ,…, x n )).

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

f ( x , y ) = x f (1, y ) x ’ f (0, y ).

При любом y подстановка в правую часть x =1 и x =0 дает соответственно

1 f (1, y ) 1’ f (0, y ) = f (1, y ) 0 f (0, y ) = f (1, y ) 0 = f (1, y );

0 f (1, y ) 0’ f (0, y ) = 0 1 f (0, y ) = 1 f (0, y ) = f (0, y ).

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

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

f ( x , y ) = x f (1, y ) x ’ f (0, y ) =

= x ( y f (1,1) y ’ f (1,0)) x ’ ( y f (1,1) y ’ f (1,0)) =

= x y f (1,1) x y ’ f (1,0) x ’ y f (1,1) x ’ y ’ f (1,0).

Функция f ( x , y ) представлена в виде дизъюнкции четырех

дизъюнктивных членов. Те из них, для которых коэффициент f ( α , β ) равен нулю, можно отбросить. В результате получится СДНФ. Например, для функции f ( x , y )= x y имеем f (0,0)= f (1,1)=0

и f (0,1)= f (1,0)=1, поэтому

Элементарной конъюнкцией ( конъюнктом ) называют конъюнкцию переменных и/или их отрицаний, в которой каждая переменная встречается не более одного раза.

Ссылка на основную публикацию
Adblock detector