Глава 8. Алгебра логики. Алгебра логики схемы

Глава 8. Алгебра логики

8.1. Возникновение логики как самостоятельной науки

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

Логику, основанную Аристотелем (384–322 до н. э. - крупнейший древнегреческий мыслитель), принято называть формальной. Это название закрепилось за ней потому, что она возникла и развилась как наука о формах мышления.

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

Для того чтобы рассуждать, человеку необходим какой-либо язык. Не удивительно, что математическая логика начиналась с анализа того, как говорят и пишут люди на естественных языках. Этот анализ привёл к тому, что выяснилось существование формулировок, которые невозможно разделить на истинные и ложные, но, тем не менее, выглядят осмысленным образом. Это приводило к возникновению парадоксов, в том числе в одной из фундаментальных наук математики. Тогда было решено создать искусственные формальные языки, лишённого «вольностей» языка естественного.

Рис. 8. 1. Джордж Буль – английский математик-самоучка

Джордж Буль (1815-1864г) по праву считается отцом математической логики (рис. 8.1). Его именем назван раздел математической логики – булева алгебра.

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

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

А еще несколько десятилетий спустя, уже в ХХ столетии, ученые объединили созданный Джорджем Булем математический аппарат с двоичной системой счисления, заложив тем самым основы для разработки цифрового электронного компьютера.

Рис. 8. 2. Клод Шеннон – американский математик

В 1936 году выпускник Мичиганского университета Клод Шеннон (1916-2001г), которому был тогда 21 год, сумел ликвидировать разрыв между алгебраической теорией логики и ее практическим приложением (рис. 8.2).

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

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

Применение в вычислительной технике и информатике алгебры логики

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

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

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

Из этого следует два вывода:

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

Логический элемент компьютера — это часть электронной логичеcкой схемы, которая реализует элементарную логическую функцию.

Логическими элементами компьютеров являются электронные схемы И, ИЛИ, НЕ, И—НЕ, ИЛИ—НЕ и другие (называемые также вентилями), а также триггер. Триггер имеет два устойчивых состояния, одно из которых соответствует двоичной единице, а другое — двоичному нулю.

Термин триггер происходит от английского слова trigger — защёлка, спусковой крючок. Для обозначения этой схемы в английском языке чаще употребляется термин flip-flop, что в переводе означает “хлопанье”. Это звукоподражательное название электронной схемы указывает на её способность почти мгновенно переходить (“перебрасываться”) из одного электрического состояния в другое и наоборот. Поскольку один триггер может запомнить только один разряд двоичного кода, то для запоминания байта нужно 8 триггеров, для запоминания килобайта, соответственно, 8 х 210 = 8192 триггеров. Современные микросхемы памяти содержат миллиарды триггеров.

studfiles.net

Алгебра логики. Функциональные схемы.

Алгебра логики — раздел математической логики, в котором изучаются логические операции над высказываниями. Высказывания могут быть истинными, ложными или содержащими истину и ложь в разных соотношениях. Функциональная схема – это логическая диаграмма, графический (геометрический, точнее — топологический) аппарат математической логики, показывающий её работу.

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

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

Закон де Моргана (Если существует операция логического умножения двух и более элементов, операция «и» — (A&B), то для того, чтобы найти обратное от всего суждения~(A&B), необходимо найти обратное от каждого элемента и объединить их операцией логического сложения, операцией «или» — (~A+~B). Закон работает аналогично в обратном направлении: ~(A+B) = (~A&~B)) . Докажем его с помощью диаграммы эйлера-венна.

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

Для визуального представления правой части равенства выполним последовательно: заштрихуем область для отображения инверсии (А) серым цветом и аналогично область В также серым цветом; затем для отображения конъюнкции нужно взять пересечение этих серых областей (результат наложения представлен черным цветом): Видим, что области для отображения левой и правой части равны. Что и требовалось доказать.

pdnr.ru

Логические схемы

Логические основы устройства компьютера.

Математический аппарат алгебры логики очень удобен для описания того, как функционируют аппаратные средства компьютера, поскольку основной системой счисления в компьютере является двоичная

ЛОГИЧЕСКИЕ СХЕМЫ

КОНЪЮНКЦИЯ (ЛОГИЧЕСКОЕ УМНОЖЕНИЕ)

ДИЗЪЮНКЦИЯ (ЛОГИЧЕСКОЕ СЛОЖЕНИЕ)

ЛОГИЧЕСКИЕ СХЕМЫ

ИНВЕРСИЯ (ЛОГИЧЕСКОЕ ОТРИЦАНИЕ)

ЛОГИЧЕСКИЕ СХЕМЫ

Пример: Составить логические схемы по следующим функциям.

ЛОГИЧЕСКИЕ СХЕМЫ

Пример: Составить логическую функцию по логической схеме

Составить логическую схему по логической функции.

Самостоятельно

Пример: Составить логические схемы по следующим функциям.

САМОСТОЯТЕЛЬНО: Составить логическую функцию по логической схеме.

ЗАКОНЫ АЛГЕБРЫ ЛОГИКИ

ПРИМЕРЫ

Упростить выражение

ПРИМЕРЫ Упростить выражение

Решение логических задач средствами алгебры логики

Пример: Трое друзей, болельщиков автогонок "Формула-1", спорили о результатах предстоящего этапа гонок.

Пример: Трое друзей, болельщиков автогонок "Формула-1", спорили о результатах предстоящего этапа гонок.
— Вот увидишь, Шумахер не придет первым, — сказал Джон. Первым будет Хилл.

— Да нет же, победителем будет, как всегда, Шумахер, — воскликнул Ник. — А об Алези и говорить нечего, ему не быть первым.

— Да нет же, победителем будет, как всегда, Шумахер, — воскликнул Ник. — А об Алези и говорить нечего, ему не быть первым.
Питер, к которому обратился Ник, возмутился:
— Хиллу не видать первого места, а вот Алези пилотирует самую мощную машину.

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

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

Решение. Введем обозначения для логических высказываний:

Решение. Введем обозначения для логических высказываний:
Ш — победит Шумахер; Х — победит Хилл; А — победит Алези.

Зафиксируем высказывания каждого из друзей:

Зафиксируем высказывания каждого из друзей:

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

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

ЗАКОНЫ АЛГЕБРЫ ЛОГИКИ

ЗАДАНИЕ

Упростить логические выражения:

ЗАДАНИЕ Упростить логические выражения

_____________
_____
F = Х & Y v X &Y
_ _____
F = A v A v B
__ _____
F = A v B v A & B v C

ДОМАШНЕЕ ЗАДАНИЕ

dok.opredelim.com

"Основы логики" - 11 класс

Над возможностью применения логики в технике ученые и инженеры задумывались уже давно. Например, голландский физик Пауаль Эренфест (1880-1933), кстати несколько лет работавший в России, писал еще в 1910 году: "...Пусть имеется проект схемы проводов автоматической телефонной станции. Надо определить: 1) будет ли она правильно функционировать при любой комбинации, могущей встретиться в ходе деятельности станции; 2) не содержит ли она излишних усложнений. Каждая такая комбинация является посылкой, каждый маленький коммутатор есть логическое "или-или", воплощенное в эбоните и латуни; все вместе- система чисто качественных... "посылок", ничего не оставляющая желать в отношении сложности и запутанности...правда ли, что, несмотря на существование алгебры логики, своего рода "алгебра распределительных схем" должна считаться утопией?". Созданная позднее М.А.Гавриловым (1903-1979) теория релейно- контактных схем показала, что это вовсе не утопия.

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

На рисунках контакты обозначены латинскими буквами А и В. Введем обозначения:1- контакт замкнут, 0- контакт разомкнут. Цепь на схеме 1 с последовательным соединением контактов соответствует логической операции "ИЛИ". Цепь на схеме 3 (электромагнитное реле) соответствует логической операции "НЕ".

А	В	Результат	А	В	Результат	А	B
1	1	1	1	1	1	1	0
1	0	0	1	0	1	0	1
0	1	0	0	1	1
0	0	0	0	0	0
Конъюнктор			Дизъюнктор			Инвертор

Схема №1 1) Оба контакта в положении "включено". Тогда ток через лампочку идет и она горит. 2) Первый контакт в положении "вкл", второй- в положении "выкл". Ток не идет, лампочка не горит. 3) Обратная ситуация. Лампочка не горит. 4) Оба контакта в положении "выкл". Тока нет. Лампочка не горит.

Вывод: первая схема действительно реализует логическую операцию "И".

Схема № 2 1) Оба контакта в положении "включено". Ток через лампочку идет и она горит. 2) Первый контакт в положении "вкл", второй- в положении "выкл". Ток идет, лампочка горит. 3)Обратная ситуация. Лампочка горит. 4) Оба контакта в положении "выкл". Тока нет. Лампочка не горит.

Вывод: вторая схема действительно реализует логическую операцию "ИЛИ".

Схема №3

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

Вывод: схема №3 действительно реализует логическую операцию "НЕ".

Почему необходимо уметь строить логические схемы?

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

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

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

Построение логических схем

Правило построения логических схем: 1) Определить число логических переменных. 2) Определить количество базовых логических операций и их порядок. 3) Изобразить для каждой логической операции соответствующий ей вентиль (базовый логический элемент). 4) Соединить вентили в порядке выполнения логических операций.

Пример №1

Пусть Х=истина, Y=ложь. Составить логическую схему для следующего логического выражения: F=XvY&X. 1) Две переменные- Х и Y. 2) Две логические операции: 21 XvY&X 3) Строим логические операции: 4) Ответ: 1v0&1=1.

Пример №2

Постройте логическую схему, соответствующую логическому выражению F=X&Y v!(YvX).Выяснить значения выражения для Х=1,Y=0. 1) Переменные две. 2)Логических операций три: конъюнкция и две дизъюнкции: 1 4 3 2 X&Yv!(YvX). 3) Схему строим слева направо в соответствии с порядком логических операций: 4) Вычислим значение выражения: F=1&0 v!(0v1)=0.

<<	<	Ноябрь 2013			>	>>
Пн	Вт	Ср	Чт	Пт	Сб	Вс
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30

Глава 8. Алгебра логики. Алгебра логики схемы