Ћекции.ќрг


ѕоиск:




 атегории:

јстрономи€
Ѕиологи€
√еографи€
ƒругие €зыки
»нтернет
»нформатика
»стори€
 ультура
Ћитература
Ћогика
ћатематика
ћедицина
ћеханика
ќхрана труда
ѕедагогика
ѕолитика
ѕраво
ѕсихологи€
–елиги€
–иторика
—оциологи€
—порт
—троительство
“ехнологи€
“ранспорт
‘изика
‘илософи€
‘инансы
’ими€
Ёкологи€
Ёкономика
Ёлектроника

 

 

 

 


Ѕулева функци€ (логическа€ функци€, функци€ алгебры




^логики) - это функци€ одной или нескольких переменных

I , где Z - логические переменные,

' т.е. и значени€ аргументов, и значение функции - ноль или единица. “ем самым, булева функци€ п переменных есть функци€ на Хг множестве п -мерных векторов , компоненты которых

'равны 0 или 1: . ћожно примен€ть векторные обозначени€

|дл€ сокращени€ записи. ѕользу€сь другими терминами, можно

f

[считать областью определени€ булевой функции множество вершин

i п -мерного единичного куба

.Ќа рис.19 изображена

√функци€ 3 переменных

f

fпринимающа€ значение 1 на

t1наборах (001), (011), (100)

[ќбратите внимание на допустимую

форму записи: можно не раздел€ть зап€тыми значени€ аргументов -все они однозначные числа.

;≈сли число переменных равно

п и люба€ из них может независимо от других принимать 2:значени€, то число различных п -

векторов равно . ќтносительно

t

каждой функции все множество разбиваетс€

на два класса // -векторов прообраз значени€ 0 и прообраз значени€

1 функции Z ћы будем рассматривать только всюду определенные функции

≈сли считать, что переменные обозначают истинность

(значение 1) или ложность (значение 0) высказываний-аргументов, то

функци€ Z выражает истинность или ложность определенного сложного высказывани€ при различных сочетани€х значений аргументов Ќапример, конъюнкци€ двух высказываний - это сложное высказывание, истинное тогда и только тогда, когда истинны оба составл€ющих простых высказывайс€. — функциональной точки зрени€ конъюнкцию можно рассматривать как булеву функцию двух логических переменных, принимающую значение 1 тогда и только тогда, когда оба аргумента равны 1.

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

- таблица из строк - п -мерных булевых векторов в алфавитном пор€дке, каждому из которых сопоставлено значение функции Z, равное 0 или 1. «аметим, что булева функци€ Z €вл€етс€ на характеристической функцией того множества точек

, дл€ которых Z = 1. ¬ таблице 5 представлены все функции одной переменной - их 4

¬ 1 -м столбце - значени€ переменной X; в каждом из последующих -значени€ соответствующей функции, обозначение функции - в 1-й

строке ¬о 2-м столбце - функци€-константа , в 5-м - функци€-

константа . ¬ 3-м столбце тождественна€ функци€ Z = X, в 4-м -

функци€ , которую обозначают также и называют

отрицанием. ¬торой способ обозначени€ подчеркивает, что отрицание

- одноместна€ функци€ аргумента X.

јналогично могут быть заданы функции нескольких переменных Ќекоторые из них - дл€ двух переменных - в табл.6 —равните их (столбцы 3-5) с таблицами истинности основных логических операций конъюнкции, дизъюнкции, импликации, эквивалентности,'дл€ которых значени€ аргументов и результатов операций обозначались буквами », Ћ ќтметим также, что с арифметической точки зрени€, т.е. если рассматривать 0 и 1 как натуральные числа с обычными операци€ми

арифметики, выполнены равенства:

ѕоэтому конъюнкцию называют умножением и записывают

со знаком произведени€: или вообще - как в алгебре - без

знака: XY. ƒизъюнкцию иногда удобно называть логическим сложением, а св€зываемые ею члены - логическими, или дизъюнктивными слагаемыми. ќднако следует иметь в виду, что, во-первых, на наборе (1, 1) значение дизъюнкции не совпадает с арифметической суммой, а, во-вторых, термин "сумма" дл€ логических переменных употребл€етс€ и в другом значении, представленном в той же табл.6. ¬ двух последних столбцах табл.6 представлены функции, которые не встречались раньше, а именно:

—умма по модулю 2 - функци€ двух переменных, равна€ 0, если значени€ аргументов совпадают, и 1 в противном случае; ее обозначение

- . јрифметическое значение -остаток от делени€ числа

(X + Y) на 2, - отсюда название. ƒругое название - неэквивалентность,

поскольку выполнено тождество:

—умма по модулю 2 как бинарна€ операци€ обладает свойствами

коммутативности и ассоциативности , и поэтому

ее можно записывать без скобок и переставл€ть слагаемые.

Ўтрих Ўеффера - функци€ двух переменных, равна€ 0 тогда и

только тогда, когда оба аргумента равны 1. ќбозначение: , условное

название " X несовместно с Y". ¬ыполнены тождества:

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

значений длины 4. “ак же, булевым вектором длины задаетс€ логическа€ функци€ п переменных. ƒл€ удобства записи можно транспонировать столбец значений в строку и таким сокращенным

способом задавать булевы функции. Ќапример, представл€ет

конъюнкцию, - дизъюнкцию, - импликацию;

представл€ет функцию трех переменных , заданную в

последнем столбце табл.7. ƒл€ получени€ таблицы нужно приписать слева к столбцу значений стандартный (дл€ каждого п) перечень всех /; -наборов, расположенных в алфавитном пор€дке, т.е. описанную

в І4 гл 2 таблицу

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

Ќапример, функцию из табл.7 можно задать кортежем: [3,5,6,7], а

функцию из той же таблицы - [0, 1, 4, 5]. Ёто особенно удобно, если

функци€ принимает значение №на небольшом числе наборов, по сравнению с их общим количеством.

”пражнение. ќб€зательно ли при таком задании функции указывать число переменных?

¬ажный пример применени€ булевых функций дают арифметические действи€ над двоичными числами: поскольку возможные знаки в двоичной системе суть 0 и 1, то зависимости знаков результата от знаков слагаемых/сомножителей выражаютс€ булевыми

функци€ми. ѕри сложении двух однозначных двоичных чисел ј и ¬ знак суммы в младшем разр€де равен , а знак переноса

возникает только если оба слагаемых равны 1, т.е. ”множение однозначных двоичных чисел тождественно конъюнкции, что фактически отмечено выше.

¬ табл.7 представлены 3 функции трех переменных. ѕервую из них

называют иногда функцией большинства - ее значение

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

единиц равно 2 или 3, т.е. он равн€етс€ значению функции большинства от тех же d переменных.

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

от аргумента Y, а функци€ от аргументов X, Z. ƒействительно, если, например, X = 0,7 = 1, то и при Y = ќ (набор 001), и при Y = \ (набор 011) выполнено равенство . “аким же образом провер€ютс€

остальные 3 сочетани€ переменных X и Z. ¬ведем определение Ќесущественные (фиктивные) переменные: дл€ функции

переменна€ называетс€

несущественной, если выполнено

при всех значени€х

“аким образом, дл€ функции несущественной переменной €вл€етс€ Y, а дл€ функции - несущественные переменные X и Z. ≈сли относить к функци€м п переменных и функции, существенно

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

булевых векторов длины , т.е. . ƒл€ одной переменной это число равно 4 (см.

табл.5); дл€ двух переменных - 24 =16; сщ€ трех переменных - 28 = 256; дл€

нетырех переменных -2|6 = 65536и т.д. “аблица всех 16 функций 2 переменных содержитс€ в файле материалов. ћножество всех логических функций, от любого конечного числа

переменных обозначаетс€

≈сли - фиктивна€ переменна€ функции

то перва€ половина задающего ее столбца значений совпадает со второй, и если отбросить вторую половину таблицы этой функции и затем удалить 1-й столбец (состо€щий из нулей), то останетс€ таблица

некоторой функции (п -1) переменных . јналогично, если

- фиктивна€ переменна€ функции и вычеркнуть

из таблицы столбец переменной и все строки с единичным

значением (т е строки, в которых ), то останетс€ таблица

функции . Ѕудем говорить, что g

получаетс€ из удалением, а - введением фиктивной

переменной

‘ункции, которые могут быть получены друг из друга удалением и введением фиктивных переменных, считаютс€ равными. ќчевидно,

равенство функций есть отношение эквивалентности на , поэтому множество всех булевых функций разбиваетс€ на классы равных

функций. ¬ этом смысле, использованные выше записи

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

функции одной переменной Y, имеющей столбец значений

ѕон€тно, что удаление фиктивных переменных делает задание функции таблицей более компактным. ќднако и введение фиктивных переменных может быть полезным: некоторую совокупность функций от разных множеств переменных можно рассматривать как завис€щую от одного и того же множества переменных - объединени€ множеств переменных всех функций совокупности, если это объединение конечно.





ѕоделитьс€ с друзь€ми:


ƒата добавлени€: 2015-10-01; ћы поможем в написании ваших работ!; просмотров: 609 | Ќарушение авторских прав


ѕоиск на сайте:

Ћучшие изречени€:

Ќадо любить жизнь больше, чем смысл жизни. © ‘едор ƒостоевский
==> читать все изречени€...

1411 - | 1174 -


© 2015-2024 lektsii.org -  онтакты - ѕоследнее добавление

√ен: 0.024 с.