Элементарные функции алгебры логики 





Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

Элементарные функции алгебры логики



ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ

 

Пример 2.2

Рассмотрим несколько функций двух переменных (табл.2.7).

 

Таблица 2.7

x1 x2 (x1&x2) f3 f15

 

Покажем, что (х1&x2) существенно зависит от х1. Рассмотрим наборы (0,1) и (1,1), здесь a2=1, f(0,a2)=0 и не равно f(1,a2)=1. Покажем, что х2 – тоже существенная переменная. Рассмотрим наборы (1,0) и (1,1). Здесь a1=1, f(1,0)=0 и не равна f(1,1)=1. Для функции f3(x1,x2) покажем , что х2 – фиктивная переменная, т.е. надо показать, что не существует наборов (a1,0) и (a1,1) таких, что f3(a1,0) f3(a1,1). Пусть a1=0, т.е. рассмотрим наборы (0,0) и (0,1), f(0,0)=f(0,1)=0. Пусть a1=1, но f(1,0)=f(1,1)=1.

Для функции f15 x1 и x2 являются фиктивными переменными. x1–фиктивная переменная, так как существует набор (0,a2) и (1,a2), таких, что f(0,a2f(1,a2). Если a2=0, то f(0,0)=f(1,0)=1, если a2=1, тогда f(0,1)=f(1,1)=1. Аналогично доказывается, что – тоже фиктивная переменная.

Пусть хi является фиктивной переменной для функции f(x1,...,xi,..., xn). Тогда ее можно удалить из таблицы истинности, вычеркнув все строки вида (a1, ...ai–1, 1, ai+1, ...an) или, наоборот, все строки вида (a1, ..., ai–1, 0, ai+1, ...an) и столбец для переменной хi. При этом получим таблицу для некоторой функции g(x1, ..., xi–1, xi+1, ...xn). Будем говорить, что функция g(x1, ...xi–1, xi+1, ...xn) получена из функции f(x1, ..., xi, ...xn) путем удаления фиктивной переменной хi или f получена из g путем введения фиктивной переменной хi (табл.2.8).

Определение 2.4. Функции f1 и f2 называются равными, если f2 можно получить из f1 путем добавления или удаления фиктивной переменной.

 

Пример 2.3

Таблица 2.8

x1 x2 f3

 

Вычеркнули строки типа (a,1), т.е. (0,1) и (1,1) и столбец для х2.

Получили f3(x1 x2) = g(x1) = x1.

Пример 2.4

Пусть функция g(x1 x2) задана табл. 2.9 и существенно зависит от обеих переменных.

Таблица 2.9

x1 x2 g

Построим функцию f(x1,x2,x3), которая получается из g(x1,x2) введением фиктивной переменной х3 (табл. 2.10).

Таблица 2.10

x1 x2 X3 F

 

К наборам (х1,х2) мы добавим х3=0, получим наборы вида (a1,a2,0), на этих наборах функцию f положим равной g(a1,a2), затем добавим наборы вида (a1,a2,1), функцию f(a1,a2,1) положим равной g(a1,a2).

Особую роль играют константы 0 и 1, которые не имеют существенных переменных и которые можно рассматривать как функции от пустого множества переменных.

 

2.2. Формульное задание функции алгебры логики

 

Дадим индуктивное определение формулы над множеством. Это определение несколько сложное по форме, но будет полезно в дальнейшем. С индуктивным определением мы встречались в математическом анализе при определении n-го дифференциала dnf(x) : было введено понятие первого дифференциала df(x), а затем n-й дифференциал определялся как первый дифференциал от d(n–1)f(x).

 

Определение 2.5. Пусть МÌP2, тогда:

1) каждая функция f(x1, ..., xnM называется формулой над M;

2) пусть g(x1, ..., xmM , G1, ..., Gm – либо переменные, либо формулы над M. Тогда выражение g(G1...Gn) – формула над M .

Формулы будем обозначать заглавными буквами: N[f1, ..., fs], имея в виду функции, участвовавшие в построении формулы, или N(х1, ..., xk), имея в виду переменные, вошедшие в формулу. Gi , формулы, участвовавшие в построении g(G1, ..., Gn), называются подформулами.

 

 

Пример 2.5. Пусть N={(x1&x2),(x1Úx2),(`x )}, тогда ((х1&х2х3) – формула над N.

Сопоставим каждой формуле N(x1, ..., xn) функцию f(x1, ..., xnP2. Сопоставление будем производить в соответствии с индуктивным определением формулы.

1) Пусть N(x1, ..., xn)=f(x1, ..., xn), тогда формуле N(x1, ..., xn) сопоставим функцию f(x1, ..., xn).

2) Пусть N(x1, ..., xn)=g(G1, ..., Gm), где каждое Gi – либо формула над M, либо переменная, тогда по индуктивному предположению каждому Gi сопоставлена либо функция fiÎP2 , либо переменная хi , которую можно считать тождественной функцией. Таким образом, каждой формуле Gi сопоставлена функция fi( ), причем { }Í{x1, ..., xn}, так как в формуле N(x1, ..., xn) перечислены все переменные, участвовавшие в построении формулы. Можно считать, что все функции fi зависят от переменных (x1, ..., xn), причем какие-то переменные могут быть фиктивными. Тогда N(x1, ..., xn) = g(G1, ..., Gm) = g( f1(x1, ..., xn), ..., fm(x1,..,xn)). Сопоставим этой формуле функцию h(x1, ..., xn) следующим образом: пусть (a1, ..., an) – произвольный набор переменных (x1, ..., xn). Вычислим значение каждой функции fi на этом наборе, пусть (a1, ..., an)=bi, затем найдем значение функции g(x1, ..., xm) на наборе (b1, ..., bm) и положим h(a1, ..., an) = g(b1, ..., bm) = g(f1(a1, ..., an), ..., fm(a1, ..., an)). Так как каждое fi(x1, ..., xn) есть функция, то на любом наборе (a1, ..., an) она определяется однозначно, g(x1, ..., xm) – тоже функция, следовательно, на наборе (b1, ..., bn) она определяется однозначно , h(x1, ..., xn) есть функция, определенная на любом наборе (a1, ..., an).

Множество всех формул над M обозначим через <M>.

 

Определение 2.6. Две формулы N и D из <M> называются равными N=D или эквивалентными N~D , если функции, реализуемые ими, равны.

 

Упрощение записи формул

1) внешние скобки можно опускать;

2) приоритет применения связок возрастает в следующем порядке: ~, , Ú,&;

3) связка ־ над одной переменной сильнее всех связок;

4) если связка ־ стоит над формулой, то сначала выполняется формула, затем отрицание;

5) если нет скобок, то операции ~ и выполняются в последнюю очередь.

 

Пример 2.6.Доказать эквивалентность формул (табл. 2.11).

( &(х2Åx3))~( ) .

 

Таблица 2.11

x1 x2 x3 x2Åx3 & x2 x3 x3 x2 & Úx1

 

Пример 2.7

Упростим формулы:

1. x2x3Úx1 2x3 = x3(x2Úx1 2) = x3((x2Úx1)&(x2Ú 2)) = (x1Úx2)x3.

2. x1Ú 1x2Ú 1 2x3Ú 1 2x3x4=x1Ú 1(x2Ú 2 3x4)=x1Ú 1

(x2Úx3Ú 2 3x4)=(x1Ú 1)(x1Úx2Úx3Ú 2 3х4)=x1Ú(x2Úx3)Ú( )x4= =x1Ú(x2Úх3Ú( ))(x2Úx3Úx4) = x1Úx2Úx3Úx4.

 

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

 

Определение 2.7. Функция f*(x1, ..., xn) называется двойственной к функции f(x1, ..., xn), если f*(x1, ..., xn) = ( 1, ..., n).

Пример 2.8. Покажем с помощью таблицы истинности

(табл. 2.13) что константа 0 двойственна к 1.

 

Таблица 2.13

x f f*

Функции f(x) = x и g(x) = двойственны сами себе (табл.2.14),

так как f*(0)= (1).

Таблица 2.14

x f f* g g*

Определение 2.8. Если f*(x1, ..., xn) = f(x1, ..., xn), то f(x1, ..., xn) называется самодвойственной.

Если f*– самодвойственна, то ( 1, ..., n) = f(x1, ..., xn), т.е. на противоположных наборах функция принимает противоположные значения.

 

Пример 2.9.Покажем, что f(x1,x2,x3)=x1Åx2Åx3 – самодвойственна (табл. 2.15).

Таблица 2.15

x1 x2 x3 f f*

 

 

Пример 2.10. Покажем, что функция х1Úх2 двойственна к x1&x2, функция х1 х2 двойственна к функции x1|x2 (табл. 2.16).

 

 

Таблица 2.16

x1 x2 f=х1Úх2 f* g=x1|x2 g*=x1 x2
0 0 0 1 1 0 1 1

 

Теорема 2.1. О двойственных функциях

Если f* двойственна к f, то f двойственна к f*.

Доказательство. f*(x1, ..., xn) = ( 1, ..., n). Найдем двойственную функцию к f*, т.е. (f*( x1, ..., xn))* = ( ( 1, ..., n))* = ( 1, ..., n) = f(x1, .., xn).

Предположим, что функция задана формулой. Можно ли найти по этой формуле двойственную функцию? Ответ на этот вопрос дает следующая теорема.

 

 

Теорема 2.2.О принципе двойственности

Пусть функция h(x1, ..., xn) реализована формулой h(x1, ..., xn) = =g(G1, ..., Gm) = g(f1(x1, ..., xn), ..., fm(x1, ..., xn)), где какие-то переменные могут быть фиктивными. Тогда h*( x1, ..., xn) = g*(f1*( x1, ..., xn), ..., fm*(x1, …, xn)), это означает, что если функция задана некоторой формулой, то, чтобы получить двойственную функцию, надо в этой формуле все знаки функций заменить на двойственные: 0 на 1, 1 на 0.

Доказательство. h*(x1, ..., xn) = ( 1, ..., n) = (f1( 1, ..., n), ..., fm( 1, ..., n)) = ( 1( 1, ..., n), ..., ( 1, ..., n)) = = (( ), ..., (( ) = g*(f1*( x1, ..., xn), ..., fm*

( x1, ..., xn)), что и требовалось доказать.

Если функция h(x1, ..., xn) реализуется формулой N[f1, ..., fn], то формулу, полученную из N заменой fi, входящих в нее, на fi* и реализующую функцию h*(x1, ..., xn), будем называть двойственной и обозначать N*(x1, ..., xn).

Пример 2.11. Построить формулу, реализующую f*, если f = =((x y) Ú z) (y (xÅyz)). Покажем, что она эквивалентна формуле N=z(xÅy).

Найдем (xÅy)* и (x y)*.

Таблица 2.17

x y xÅy (xÅy)* x y (x y)*
0 0 0 1 1 0 1 1

Из табл. 2.17 видно, что

(x y)*=x ~ y = = x y 1, x y = y x , (x y)* = y, x y = y.

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

f*= yz ( (x (y z) 1))= yz z(x (y z) 1)= =z( yÚ( xÅ zÅ ))=z( yÚ (xÅzÅ1))=z( yÚ (xÅ ))= =z yÚ(z xÅz ) = z( yÚx ) = z(xÅy).

Тогда f = (f*)* = [z(xÅy)]* = zÚ(x~y).

 

Примеры использования теоремы Поста

1.Покажем, что система функций {f1 =x1x2, f2 =0, f3 =1, f4 = =x1Åx2Åx3} полна в Р2. Составим табл. 2.23, которая называется критериальной

 

Таблица 2.23

  Т0 Т1 L M S
x1x2 + + - + -
+ - + + -
- + + + -
x1Åx2Åx3 + + + - +

 

Таблица 2.24

x1 x2 x3 x1Åx2Åx3
0 0 0 0 1 1 1 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

 

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

Отметим еще одно обстоятельство, касающееся приведенной системы. Какую бы функцию из этой системы мы ни удалили, система станет неполной, действительно, {f2, f3, f4L, {f1, f3, f4T1, {f1, f2, f4T0, {f1, f2, f3M.

2. Мы знаем, что система {x1|x2} полна в Р2. Какова для нее критериальная таблица? x1|x2= = x1x2Å1 (табл.2.25).

 

Таблица 2.25

  Т0 Т1 L M S
x1|x2 - - - - -

3. Составим критериальную таблицу для другой полной системы функций из Р2: {0, 1, x1x2, x1Åx2} (табл.2.26).

 

Таблица 2.26

  Т0 Т1 L M S
+ - + + -
- + + + -
x1x2 + + - + -
x1Åx2 + - + - -

Согласно критериальной таблице, полной является и система {1, x1x2, x1Åx2}. Константа 0 введена в эту систему для удобства, тогда мы можем записать полином Жегалкина в виде, где а равны 0, если члены х х ...х в полиноме отсутствуют.

4. Выясним, полна ли система . Составим критериальную таблицу, очевидно, . Чтобы показать, что , достаточно найти одну функцию и . Возьмем , удовлетворяющую требуемым условиям. Если f S\T0, то f(0, ..., 0) = 1, f(1, ..., 1)=0, следовательно, f M, f T1. Рассмотрим функцию h = x1x2 x2x3 x1x3=1, набор ее значений (11101000), h S\T0, но h L. Следовательно, критериальная таблица имеет вид (табл. 2.27) и А – полная система функций.

Таблица 2.27

  Т0 Т1 L M S
L T1 - + + - -
S\T0 - - - + -

 

Определение 2.15.Система функций {f1, ..., fs, ...} называется базисом в Р2,если она полна в Р2, но любая ее подсистема не будет полной. Например, система функций {x1&x2, 0, 1, x1 x2 x3} – базис.

 

ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ

 

Элементарные функции алгебры логики

 

Обозначения: E2={0,1}; Е = E2´E2´...´E2 – прямое произведение n сомножителей; (x ,..,xn , |E2| – мощность E2, |E2|=2, тогда |Е |=2n.

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

Так как множество Е конечно, то задать отображение Е Þ E2 означает задать множество наборов из Е и для каждого набора указать его образ в Е 2.

 

Пример 2.1. Пусть n=2, тогда Е ={(0 0),(0 1),(1 0),(1 1)}, отображение Е Þ E2 задано, например, так: (0 0) Þ0 ; (0 1) Þ1; (1 0) Þ1 ; (1 1) Þ1.

Тем самым задана функция, для которой мы будем использовать стандартное обозначение f(x1,x2), записывая эту функцию в виде таблицы 2.1.

Таблица 2.1

x1 x2 f(x1,x2)

 

Здесь x1 и x2 обозначают названия столбцов, а f – символ, обозначающий отображение. Следует обратить внимание, что функции f(x1,x2) и f(y1,y2) задают одно и то же отображение и их таблицы отличаются только названиями столбцов.

 

Определение 2.2.Таблица, задающая функцию f(x1,x2,...,xn), называется таблицей истинности для этой функции.

Рассмотрим функции одной переменной. Их будет всего 4, они задаются таблицами истинности 2.2–2.5.

 

Таблица 2.2

x f0(x)
   

Функция называется константой 0, записывается f0(x) 0.

 

Таблица 2.3

x f1(x)

Функция называется тождественной, записывается f1(x)= x.

 

Таблица 2.4

x f2(x)

Функция называется «не x» и записывается f2 (x)= .

 

Таблица 2.5

x f3(x)

 

Функция записывается f3(x) 1 и называется константой 1. Если стандартным расположением переменной x считать 0 в первой строке и 1 во второй, то функции f0, f1, f2, f3 определяются однозначно наборами значений: f0=(0,0), f1=(0,1), f2=(1,0) и f3=(1,1). Наборы значений функций составляют множество E2´Е2, поэтому количество функций одной переменной равно |E2 E2|=4. Для удобства функции пронумерованы так, что двоичный код номера совпадает с набором значений функции.

Рассмотрим функции двух переменных f(x1,x2). Функции двух переменных определены на множестве Е ={(0 0),(0 1),(1 0),(1 1)}, эти наборы переменных из Е можно тоже рассматривать как двоичные коды чисел 0,1,2,3. Именно такой порядок расположения наборов (x1,x2) будем считать стандартным. Тогда функции f(x1,x2) определяются однозначно наборами значений (b1, b2, b3, b4), где каждое biÎE2, поэтому (b1, b2, b3, b4Е . Следовательно, число функций двух переменных равно 24=16, занумеруем их числами от 0 до 15 так, чтобы двоичный код номера совпадал с набором значений функции (табл.2.6).

Таблица 2.6

x1 x2 f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15
0 0 0 1 1 0 1 1

 

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

1) f1(x1,x2) = (x1&x2), читается «конъюнкция х1 и х2», иногда вместо знака & употребляют знак или вообще его опускают, пишут (х1х2). (х1&х2) совпадает с обычным произведением х1х2 и совпадает с min(x1,x2). Эту операцию называют также логическим умножением.

2) f6(x1,x2) = (x1Åx2) – сложение х1 и х2 по модулю два, иногда пишут (х1+х2)mod2.

3) f7(x1,x2) = (x1Úx2), читается «х1 дизъюнкция х2», она совпадает с max(x1,x2), ее называют логическим сложением.

4) f8(x1,x2) = (x1 x2), читается «х1 стрелка Пирса х2» и совпадает с отрицанием дизъюнкции, другие названия: функция Вебба, функция Даггера.

5) f9(x1,x2) = (x1~x2), читается «х1 эквивалентно х2».

6) f13(x1,x2) =( x1 x2), читается «х1 импликация х2», иногда обозначается , т. е. х1 влечет х2 .

7) f14(x1,x2) = (x1|x2), читается «х1 штрих Шеффера х2», она является отрицанием конъюнкции.

Cимволы ,&,Ú, ,~, ,Å,|, участвующие в обозначениях элементарных функций, называются логическими связками или просто связками. Переменные 0 и 1 называются логическими или булевыми переменными, причем 0 соответствует «лжи» , а 1 – «истине», а функции алгебры логики называются еще и булевыми функциями.

Рассмотрим функцию f(x1...xn), где (x1...xnЕ , тогда число наборов (x1...xn), где функция f(x1...xn) должна быть задана, равно |Е |=2n. Обозначим множество всех функций двузначной алгебры логики Р2. Обозначим через Р2(n) число функций, зависящих от n переменных. Очевидно, .

С ростом n число Р2(n) быстро растет: P2(1)=4, P2(2)=16, P2(3)=256, P2(4)=65536 . При больших n табличный способ задания функций становится неприемлемым, используется формульное задание функций. Но прежде чем ввести понятие формулы, дадим определение существенной переменной.

 

Определение 2.3. Функция f(x1,...,xi–1,xi,xi+1,...,xn) существенно зависит от хi, если существуют такие значения a1, ...ai–1, ai+1, ...an переменных x1, ...xi–1, xi+1, ...xn, что

f(a1, ...ai–1, 0, ai+1...anf(a1...ai–1, 1, ai+1...an) . Тогда переменная хi называется существенной переменной. В противном случае хi называется фиктивной переменной.

 

Пример 2.2

Рассмотрим несколько функций двух переменных (табл.2.7).

 

Таблица 2.7

x1 x2 (x1&x2) f3 f15

 

Покажем, что (х1&x2) существенно зависит от х1. Рассмотрим наборы (0,1) и (1,1), здесь a2=1, f(0,a2)=0 и не равно f(1,a2)=1. Покажем, что х2 – тоже существенная переменная. Рассмотрим наборы (1,0) и (1,1). Здесь a1=1, f(1,0)=0 и не равна f(1,1)=1. Для функции f3(x1,x2) покажем , что х2 – фиктивная переменная, т.е. надо показать, что не существует наборов (a1,0) и (a1,1) таких, что f3(a1,0) f3(a1,1). Пусть a1=0, т.е. рассмотрим наборы (0,0) и (0,1), f(0,0)=f(0,1)=0. Пусть a1=1, но f(1,0)=f(1,1)=1.

Для функции f15 x1 и x2 являются фиктивными переменными. x1–фиктивная переменная, так как существует набор (0,a2) и (1,a2), таких, что f(0,a2f(1,a2). Если a2=0, то f(0,0)=f(1,0)=1, если a2=1, тогда f(0,1)=f(1,1)=1. Аналогично доказывается, что – тоже фиктивная переменная.

Пусть хi является фиктивной переменной для функции f(x1,...,xi,..., xn). Тогда ее можно удалить из таблицы истинности, вычеркнув все строки вида (a1, ...ai–1, 1, ai+1, ...an) или, наоборот, все строки вида (a1, ..., ai–1, 0, ai+1, ...an) и столбец для переменной хi. При этом получим таблицу для некоторой функции g(x1, ..., xi–1, xi+1, ...xn). Будем говорить, что функция g(x1, ...xi–1, xi+1, ...xn) получена из функции f(x1, ..., xi, ...xn) путем удаления фиктивной переменной хi или f получена из g путем введения фиктивной переменной хi (табл.2.8).

Определение 2.4. Функции f1 и f2 называются равными, если f2 можно получить из f1 путем добавления или удаления фиктивной переменной.

 

Пример 2.3

Таблица 2.8

x1 x2 f3
<




Последнее изменение этой страницы: 2016-07-14; просмотров: 183; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 35.153.166.111 (0.014 с.)