Свойства n-местных булевых функций

Понятия о булевых функциях

Математическая логика

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

не четкие компьютеры.

Истина это 1

Ложь это 0

Мы будем рассматривать булевы функции от любого конечного числа аргументов. Если число аргументов равно n, то такую булеву функцию называют n-местной.

Имеем некоторую n-местную булеву функцию.

Свойство 1: рассматриваем функцию f(x1,x2,xn)(вид 1). Любая местная булева функция вида (1) определена не более чем 2 в степени n наборов ее аргументов. (это было заложено в основу компьютерной техники (Буль и фон Нейман) Таким образом имеем, булев кортеж

Каждому набору аргументов можно поставить соответствие (кортежу) можно поставить в соответствие вершину n-мерного куба.

x₂

01 11

00 10 x₁

Существуют так же булевы функции, которые не определены на одном из наборов своих аргументов, будем называть их частичными булевыми функциями. Набор аргументов Alpha1, Alpha2 Alpha-n можно записать в виде см в тетрадь

001, 010, 011, 100, 101, 111…

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

X1 0 0 0 0 1 1 1 1

X2 0 0 1 1 0 0 1 1

X3 0 1 0 1 0 1 0 1

F(x1,x2,x3)

0 0 0 1 0 1 0 1

Если имеется m-наборов аргументов, то всего можно задать 2 в степени m булевых функций.

Свойство номер 2:

Общее число n-местных булевых функций равно B(n) = 2 в степени 2 в степени n.

B(n+1) = (B(n)) *(B(n))

B(1) = 4;

B(2) = 16;

B(3) = 256

B(4) = 65536;

n-местную булеву функцию можно представить с помощью булевых функций от одного и 2х аргументов. Такие булевы функции (1 и 2х местные) принято называть элементарными.

Пример

Одноместная функция B(1)=4;

Рассмотрим двухместную функцию

B(2)=16

Fi(x,y)

Оставшиеся 10 наборов можно разбить на пары. (Fi1(x,y) и fi2(x,y)) где fi2(x,y) = !fi1(x,y)

Если F(x) = !x то f(xi1(x,y))=fi2(x,y)

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

Конъюнкция (соединение) называют логическое произведение или логическое И.

X ^ Y;

X & Y

Конъюнкция функция равная единице, в том и только в том случае, когда оба ее аргумента равны 1;

X, Y – аргументы. Конъюнктивные члены

Для того что бы она была равна нулю необходимо и достаточно что бы один из аргументов был равен нулю.

Справедлива следующая таблица умножения:

0x0 = 0

0x1 = 0

1x0 = 0

1x1 = 1

Конъюнкция коммутативна и ассоциативна так как и умножение она подчиняется переместительному и сочетательному закону.

1 -> Пустое множество

1 -> I

^ ->

Конъюнкция обладает свойством идемпотентностью

Как и в случае отрицания конъюнкцию можно рассматривать как некоторую операцию на множестве булевых функций.

Fi(x1…xn) ^ fi(x1…xn)

Дизъюнкция – сложение.

1+1 = 1 и 1+1 =0

0 или 0 = 0

0 или 1 = 1

1 или 0 = 1

1 или 1 = 0

Это логическое сложение или операция логического или или операция неразделительного ИЛИ

Дизъюнкция функция равная нулю только тогда когда оба аргумента = 0;

Дизъюнкция напоминает операцию объединения множеств.

Дизъюнкция коммутативна и ассоциативна, а так же идемпотентна.

xUx = x

xVx = x

Аналогии этих функций неформальны, а носят глубокий смысл. Если множество x1 и x2 поставим с соответствие с множеством обладающими свойствами p1 и p2 то получим x= x1 U x2 при p1 U p2;

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

x (+) y – логическая сумма

Логическая сумма отлична от обычного суммирования x + y.

X и y – логические слагаемые или дизъюнктивными членами.

0+0 = 0

0+1 = 1

1+0 = 1

1+1 = 0

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

Последняя операция похожа на симметрическую разность множеств.

X(+)y = x\y U y\x

Разделительное ИЛИ происходит от четвертой операции – симметрической разности

Импликация

X => Y; Влечет

0 => 0; true

0 => 1; true

1 => 0 false

1 => 1 true

импликацию можно опередить как функцию равную нулю тогда и только тогда когда первый элемент равен единице, а второй равен нулю. Операция импликации не коммутативна и она определяет 2 функции. Свойства:

X => Y = XVY

Y => X = XV!Y

Функция Шеффера (|)

Стрелка пирса (стрелка вниз)

Ну или штрих шеффера

X | Y = !(X^Y)

0001 => 1110

Функция пирса

X (стрелка вниз)Y = !(XVY)

0111 => 1000

Равнозначность или логическая эквивалентность

X~Y = !(X(+)Y)

0 ||0 = 1001

Эти три операции коммутативны так же как и операции, из которых они произошли. То есть (X|Y)|Z = X|(Y|Z) and (XстрелкаY)стрелка Z = X стрелка ()

Равнозначность – ассоциативна.

Функция запрета.

X Y = X => Y; запрет по Y

Y X = Y => X Запрет по X

Можно показать что запрет по У равен запрету по Х

X delta Y = X^ !Y

Y delta X = !X ^ Y