Введение в компьютерную цифровую логику.

Лекция 6

Алгебра логики — это раздел математической логики, значение всех элементов (функций и аргументов) которой определены в двухэлементном множестве: 0 и 1.

Алгебра логики оперирует с логическими высказываниями.

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

Высказывания:

«Сейчас идет снег» — это утверждение может быть истинным или ложным;

«Вашингтон — столица США» — истинное утверждение;

«Частное от деления 10 на 2 равно 3» — ложное утверждение.

Отрицание высказывания х – это новое высказывание, которое является истинным, если высказывание х ложно, и ложным, если высказывание х истинно.

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

Дизъюнкция (логическое сложение) двух высказываний х и у – это новое высказывание, которое считается истинным, если хотя бы одно из высказываний х и у истинно, и ложными, если они оба ложны.

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

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

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

Компьютеры собирают на интегральных схемах. Каждая интегральная схема в компьютере служит определенной цели. Например, имеется интегральная схема, на которой основан центральный процессор, другая управляет памятью и т.д. Сами интегральные схемы составлены из транзисторов, резисторов, конденсаторов и других электронных компонентов, которые объединены в цепи. Первичный компонент - транзистор. Одна интегральная схема может иметь тысячи или даже миллионы транзисторов на площади в 1 квадратный дюйм. Транзисторы могут действовать как усилители или переключатели. Положения «ВКЛ» и «ВЫКЛ» транзисторных переключателей служат, чтобы представить в цепи знаки двоичного алфавита: 1 и 0. Эти транзисторные переключатели объединены, чтобы сформировать электронные переключатели, которые представляют значения Булевой алгебры. Основы математической логики заложил немец кий ученый и философ Готфрид Вильгельм Лейбниц (1646–1716). Он сделал попытку построить первые логические исчисления, считал, что можно заменить простые рассуждения действиями со знаками и привел соответствующие правила. Но Лейбниц высказал только идею, а развил ее окончательно ирландский математик англичанин Джордж Буль

(1815–1864). Буль разработал логическое исчисление, в котором применяются законы и операции математики. Эта логическая система способствовала возникновению алгебры логики. Алгебра логики явилась первой системой математической логики, в которой алгебраическая символика применялась к логическим выводам. Создатель этой системы ставил перед собой цель решать логические задачи с помощью методов, применяемых в алгебре. Любое суждение он пытался выразить в виде уравнений с символами, в которых действуют логические законы, подобные законам алгебры. Функция Буля (или функция алгебры логики) n переменных –это функция n переменных, в которых и каждая переменная, и сама функция может принимать только одно из двух значений, 0 или 1.

Основными понятиями алгебры логики являются логический аргумент и логическая функция. Логический аргумент (или высказывание) в зависимости от смысла может принимать значение «истина» или «ложь».

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

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

Булевы логические правила могут быть описаны в виде формул

Название	Синонимы названия	Обозначения
“ИЛИ”	дизъюнкция	логическое сложение	+илиV
“И”	конъюнкция	логическое умножение	·или&илиL
“НЕ”	инверсия	отрицание	__ (горизонтальная черта сверху) или знак Ø

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

Логический оператор И трактуется таким образом: результат логической операции И – истина, если и только если оба (или больше, когда используется больше чем два) логических операнда равны истине. Это показано в таблице истинности для булева оператора И.

A	B	C
Л	Л	Л
Л	И	Л
И	Л	Л
И	И	И

Так, логическое выражение C=A & B декларирует, что С возвращает значение ИСТИНА если оба операнда А и В истинны.

Логический оператор ИЛИ трактуется следующим образом: результат логической операции ИЛИ является ИСТИНОЙ, если хотя бы один (или более) операнд является ИСТИНОЙ. Это видно из таблицы истинности для булева оператора ИЛИ.

A	B	C
Л	Л	Л
Л	И	И
И	Л	И
И	И	И

Поэтому, логическое выражение C = А V B декларирует, что C = ИСТИНА, если А или B = ИСТИНА

Логический оператор НЕ декларирует, что результатом логической операции является ИСТИНА, если операнд является ЛОЖЬ ( т.е. ИСТИНА, если операнд (высказывание) ЛОЖЬ и наоборот, ЛОЖЬ, если операнд (высказывание) ИСТИНА. Это видно из таблицы истинности для булева оператора НЕ. Таким образом, результат логического

уравнения C= ¬A будет всегда противоположен вводимому операнду:

A	C
Л	И
И	Л

Рассмотрим следующую таблицу истинности:

№	A	B	A & B	A V B	¬A
	И	И	И	И	Л
	И	Л	Л	И	Л
	Л	И	Л	И	И
	Л	Л	Л	Л	И

Например, если А = ИСТИНА и В = ИСТИНА, то в этом случае

A & B = ИСТИНА, A V B = ИСТИНА, ¬A = ЛОЖЬ (горизонтальная строка № 1)

Таблицы истинности могут быть составлены для различных логических выражений. Например, используем стандартную таблицу истинности для логического выражения (A V B) & C.

В нем: А - «я завтра дочитаю книжку», В – «я завтра пойду на футбол» и С – «я завтра сменю воду в аквариуме»

№	A	B	C	(АvВ) & C
	И	И	И	И
	И	И	Л	Л
	И	Л	И	И
	И	Л	Л	Л
	Л	И	И	И
	Л	И	Л	Л
	Л	Л	И	Л
	Л	Л	Л	Л

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

Рассмотрите логическую схему для Булева оператора И:

А Вывод

Дата добавления: 2014-01-05