При математическом описании различных процессов вводится понятие переменной. Это некоторая независимая, величина, которая может принимать ряд значений в определенном диапазоне.

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

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

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

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

В обычной алгебре для двух переменных А и В существует три возможных отношения между их значениями. А может быть равно, больше или меньше В. В алгебре логики определено лишь отношение эквивалентности, то есть переменные здесь могут быть либо равны, либо не равны. Вопрос, какая из них больше, а какая меньше не имеет смысла.

Кроме того, для таких переменных определены три операции или действия: конъюнкция, дизъюнкция и инверсия.

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

Х1	Х2	Х1·Х2
0	0	0
0	1	0
1	0	0
1	1	1

Правило выполнения операции конъюнкции для двух логических переменных Х1 и Х2 может быть описано словесно, а также представлено в виде такой таблицы. Результат логического умножения равен единице, только, если обе переменные одновременно принимают единичные значения. Данная таблица полностью совпадает с таблицей умножения чисел 0 и 1.

---

Х1	Х2	Х1+Х2
0	0	0
0	1	1
1	0	1
1	1	1

Операция дизъюнкции называемая иначе операцией логического сложения, либо операцией «ИЛИ», обозначается как значком V, так и «+». Данная операция над двумя переменными определяется таблицей.

Х
0	1
1	0

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

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

Х+0=Х	Х·0=0
Х+1=1	Х·1=Х
Х+Х=Х	Х·Х=Х

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

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

Первый, иначе называемый переместительным, записывается следующим образом Х1+Х2=Х2+Х1, и Х1·Х2=Х2·Х1. Из него вытекает, что при сложении и умножении логических переменных их можно менять местами. Второй, ассоциативный закон иначе называется сочетательным. Для трех переменных его можно представить как Х1+Х2+Х3=(Х1+Х2)+Х3=Х1+(Х2+Х3) Х1·Х2·Х3=(Х1·Х2)·Х3=Х1·(Х2·Х3),

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

Дистрибутивный, или распределительный закон, устанавливает правила выполнения скобочных действий

Х1·(Х2+Х3)=Х1·Х2+Х1·Х3, или Х1·Х2+Х1·Х3=Х1·(Х2+Х3).

Данные выражения представляют собой тождества, то есть они справедливы при любых значениях переменных.

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

и наоборот

то есть инверсия суммы логических переменных равна логическому произведению их инверсий, а инверсия произведения – сумме инверсий.

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

.

Как и в алгебре непрерывных переменных, в алгебре логики под функцией понимается некий закон, или правило по которому переменным из одного набора (множества) ставятся в соответствие переменные из другого набора (множества).

---

В обычной алгебре аргумент и функция могут принимать, целые и дробные, положительные, отрицательные значения, и количество функций от одного аргумента не ограничено. Например, Y=X, Y=X², Y=X³, Y=sinX, Y=logX и т.п. В алгебре логики из-за того, что, как у переменной, так и у функции может быть только два значения, число последних конечно.

Х	F1	F2	F3	F4
0	0	0	1	1
1	0	1	0	1

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

Функция F2 называется функцией тождества, так как ее значения совпадают со значениями аргумента. Значения функции F3 противоположны, или инверсны по отношению к значениям аргумента. Последняя функция F4 обоим значениям аргумента Х ставит в соответствие единицы, и называется тождественная единица. Других видов функций от одной переменной нет.

Как и в обычной алгебре, в алгебре логики существуют функции от нескольких аргументов или переменных, причем количество функций N связано с числом переменных n соотношением . Если переменных две Х1 и Х2, то их наборов будет четыре, а количество вариантов задания значений функций на этих наборах и, соответственно число самих несовпадающих функций 16. Они представлены в таблице.

Х1	Х2	F 0	F1	F2	F3	F4	F5	F6	F7	F8	F9	F 10	F 11	F 12	F 13	F 14	F 15
0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

Некоторые из функций, приведенных в таблице имеют собственные названия. F1 называется функцией логического умножения, конъюнкцией, функцией И, а F7 – функцией логического сложения, дизъюнкцией, либо функцией ИЛИ. Это объясняется тем, что значения данных функций эквивалентны результатам выполнения соответствующих логических операций.

С учетом количества обрабатываемых переменных F1 часто называют функцией 2И, а F7 - 2ИЛИ. Алгебраическая (символьная) запись этих функций выглядит следующим образом F1=Х1·Х2 и F7=Х1+Х2.

Функции F8 отличается от F7 тем, что нули заменены единицами и наоборот. То есть, каждое значение F7 проинвертировано. Поэтому функция F8 называется функцией ИЛИ-НЕ (2ИЛИ-НЕ) и ее связь с F7 можно отобразить таким образом .

---

Х1	Х2	F1	F7	F8	F14	F6	F9
0	0	0	0	1	1	0	1
0	1	0	1	0	1	1	0
1	0	0	1	0	1	1	0
1	1	1	1	0	0	0	1

Аналогичная связь наблюдается и между функциями F14 и F1, вследствие чего F14 носит название функции И-НЕ (2И-НЕ) и соответственно . Отсюда следует, что количество логических функций не только ограничено, но они еще и определенным образом взаимосвязаны между собой.

Функция F6 называется функцией логической неравнозначности, а F9 – функцией логической равнозначности. Первая из них принимает единичное значение в случаях, когда аргументы Х1 и Х2 не равны, а вторая в противоположной ситуации.

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

Вследствие наличия определенной связи между операциями конъюнкции и дизъюнкции, которая описывается законами де-Моргана, одна и та же функция аналитически может быть представлена по-разному. Например f(X1,X2)=X1·X2 можно представить и как . Функция f(X1,X2,Х3)=Х1+Х2·Х3 после тождественных преобразований может выглядеть следующим образом , или , либо как . Возможен также вариант .

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

Примером ДНФ является запись

, а КНФ может выглядеть следующим образом

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

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

Полученное выражение по определению не является КНФ. Однако, если проинвертировать обе части равенства, то КНФ получится для функции .

После замены в КНФ логического умножения на сложение, запись примет вид, , при котором функция оказывается представленной с использованием лишь двух операций – логического сложения (ИЛИ) и инверсии (НЕ). При замене сложения на умножение, получится соотношение, в которое войдут лишь операции логического умножения (И) и инверсии (НЕ).

---

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

Следуя правилам алгебры логики, функцию как НЕ, так и ИЛИ можно представить, используя лишь одну операцию ИЛИ-НЕ. Действительно, ,

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

Аналогичные рассуждения можно провести и по поводу функции И-НЕ. Действительно , , а следовательно и эта функция также может служить в качестве минимального базиса. Отсюда следует, что любую сколь угодно сложную функцию от произвольного количества логических переменных можно представить используя только одну, причем любую из рассмотренных функций. Это обстоятельство в ряде случаев существенно облегчает построение устройств для обработки цифровых сигналов.

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

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

Любая функция, представленная в несовершенной форме, всегда может быть приведена к совершенной, причем единственным образом. В частности для функции F1(X1,X2) это делается умножением первого слагаемого на выражение вида . Так как оно равно единице, то умножение на нее ничего не изменит, но в итоге окажется представленной в виде СДНФ

.

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

Х1	Х2	Х3	Y
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	1

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

Те из них, которые принимают единичные значения, вводятся в соответствующее произведение без инверсии, а равные нулю - с инверсией. Получившаяся при этом компонента называются конституентой единицы.

---

Смотрите также файлы

• ВолковЭТНОПЕДАГОГИКА.doc

• В47 Мировое образовательное пространство.docx

• синтаксис.pdf

• Основные направления деятельности психолога и виды психологической помощи.docx

• 2012_MATEMATIKA-2_GiMU Tovarovedenie NULEVOJ.doc