ћерион Ќетворкс

7 минут

¬се мы любим компьютеры. ќни могут делать столько удивительных вещей. «а пару дес€тилетий компьютеры произвели самую насто€щую революцию почти во всех аспектах человеческой жизни.

ќни могут справл€тьс€ с задачами различной степени сложности, просто переворачива€ нули и единицы. ѕросто удивительно, как такое простое действие может привести к такому уровню сложности.

Ќо € уверен, что вы все знаете, что такой сложности нельз€ добитьс€ (практически нельз€) простым случайным переворачиванием чисел. Ќо за этим стоит определенные логические рассуждени€. ≈сть правила, которые определ€ют, как это все должно происходить. ¬ данной статье мы обсудим эти правила и увидим, как они управл€ют Ђмышлениемї компьютера.


„то такое булева алгебра?

Ёто правила, о которых € упоминал выше, описываютс€ некой областью математики, называемой булевой алгеброй.

¬ своей книге 1854 года британский математик ƒжордж Ѕуль предложил использовать систематический набор правил дл€ работы со значени€ми истинности. Ёти правила положили математическую основу дл€ работы с логическими высказывани€ми. ј эти основы привели к развитию булевой алгебры.

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

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

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

Ѕулева алгебра также имеет дело с символами и правилами, позвол€ющими выполн€ть различные операции над этими символами. –азница заключаетс€ в том, что эти символы что-то значат.

¬ случае обычной алгебры символы обозначают действительные числа. ј в булевой алгебре они обозначают значени€ истинности.

Ќа рисунке ниже представлен весь набор действительных чисел. Ќабор действительных чисел включает натуральные числа (1, 2, 3, 4, Е), положительные целые числа (все натуральные числа и 0), целые числа (Е, -2, -1, 0, 1, 2, 3, Е) и т.д. ќбычна€ алгебра имеет дело со всем этим набором чисел.

„исла

ƒл€ сравнени€, значени€ истинности состо€т из набора, который включает в себ€ только два значени€: True и False. «десь € хотел бы отметить, что мы можем использовать любые другие символы дл€ обозначени€ этих значений.

Ќапример, в информатике, как правило, эти значени€ обозначают через 0 и 1 (0 используетс€ в качестве False, 1 Ц в качестве True).

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

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

“еперь вопрос в том, что если (True и False), (0 и 1) Ц это просто обозначени€, то что же они пытаютс€ обозначить?

—мысл, лежащий в основе значений истинности, исходит из области логики, где значени€ истинности используютс€ дл€ того, чтобы определить, €вл€етс€ ли высказывание Ђ»стиннымї (True) или ЂЋожнымї (False). «десь значени€ истинности обозначают соответствие высказывани€ истине, то есть показывают, €вл€етс€ ли высказывание истинным или ложным.

¬ысказывание Ц это просто некоторое утверждение, что-то вроде Ђ¬се кошки милыеї.

≈сли приведенное выше высказывание верно, то мы присваиваем ему значение истинности Ђ»стинаї (True) или Ђ1ї, в противном случае мы присваиваем ему значение истинности ЂЋожьї (False) или Ђ0ї.

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


Ћогические операции и таблицы истинности

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

¬ булевой алгебре есть три основные операции.

OR: OR или "»Ћ»", также известна€ как дизъюнкци€. Ёта операци€ выполн€етс€ над двум€ логическими переменными. –езультатом операции OR будет 0, если оба операнда равны 0, иначе будет 1.

ƒл€ того, чтобы более нагл€дно продемонстрировать принцип работы этой операции, визуализируем ее с помощью таблицы истинности.

“аблицы истинности дают нам хорошее представление о том, как работают логические операции. “акже это удобный инструмент дл€ выполнени€ логических операций.

ќпераци€ OR:

ѕеременна€ 1 ѕеременна€ 2 –езультат
0 0 0
0 1 1
1 0 1
1 1 1

AND: AND или "»", также известна€ как конъюнкци€. Ёта операци€ выполн€етс€ над двум€ логическими переменными. –езультатом операции AND будет 1, если оба операнда равны 1, иначе будет 0. “аблица истинности выгл€дит следующим образом.

ќпераци€ AND:

ѕеременна€ 1 ѕеременна€ 2 –езультат
0 0 0
0 1 0
1 0 0
1 1 1

NOT: NOT или "Ќ≈", также известное как отрицание. Ёта операци€ выполн€етс€ только над одной переменной. ≈сли значение переменной равно 1, то результатом этой операции будет 0, и наоборот, если значение переменной равно 0, то результатом операции будет 1.

ќпераци€ NOT:

ѕеременна€ 1 –езультат
0 1
1 0

Ѕулева алгебра и цифровые схемы

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

¬ 1930-х годах  лод Ўеннон, американский математик, обнаружил, что булеву алгебру можно использовать в схемах, где двоичные переменные могут обозначать сигналы Ђнизкогої и Ђвысокогої напр€жени€ или состо€ни€ Ђвключеної и Ђвыключеної.

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

÷ифровые схемы реализуют булеву алгебру при помощи логических элементов Ц схем, обозначающих логическую операцию. Ќапример, элемент OR будет обозначать операцию OR. “о же самое относитс€ и к элементам AND и NOT.

Ќар€ду с основными логическими элементами существуют и логические элементы, которые можно создать путем комбинировани€ основных логических элементов.

NAND: элемент NAND, или "»-Ќ≈", образован комбинацией элементов NOT и AND. Ёлемент NAND дает на выходе 0, если на обоих входах 1, в противном случае Ц 1.

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

Ёлемент NAND:

¬ход 1 ¬ход 2 –езультат
0 0 1
0 1 1
1 0 1
1 1 0

NOR: элемент NOR, или "»Ћ»-Ќ≈", образован комбинацией элементов NOT и OR. Ёлемент NOR дает на выходе 1, если на обоих входах 0, в противном случае Ц 0.

Ёлемент NOR, как и элемент NAND, обладает свойством функциональной полноты. Ёто означает, что люба€ логическа€ функци€ может быть реализована только с помощью элементов NOR.

Ёлемент NOR:

¬ход 1 ¬ход 2 –езультат
0 0 1
0 1 0
1 0 0
1 1 0

Ѕольшинство цифровых схем построены с использованием элементов NAND и NOR из-за их функциональной полноты, а также из-за простоты изготовлени€.

ѕомимо элементов, рассмотренных выше, существуют также особые элементы, которые служат дл€ определенных целей. ¬от они:

XOR: элемент XOR, или "исключающее »Ћ»", - это особый тип логических элементов, который дает на выходе 0, если оба входа равны 0 или 1, в противном случае Ц 1.

Ёлемент XOR:

¬ход 1 ¬ход 2 –езультат
0 0 0
0 1 1
1 0 1
1 1 0

XNOR: элемент XNOR, или "исключающее »Ћ»-Ќ≈", - это особый тип логических элементов, который дает на выходе 1, когда оба входа равны 0 или 1, в противном случае Ц 0.

Ёлемент XNOR:

¬ход 1 ¬ход 2 –езультат
0 0 1
0 1 0
1 0 0
1 1 1

«аключение

»так, на этом мы можем закончить обсуждение булевой алгебры. Ќадеюсь, что к текущему моменту у вас сложилась неплоха€ картина того, что же такое булева алгебра. Ёто, конечно, далеко не все, что вам следует знать о булевой алгебре. ¬ ней есть множество пон€тий и деталей, которые мы не обсудили в данной статье.


—кидки 50% в Merion Academy

¬ыбрать курс