Реферат: Алгебра логики
Реферат выполнили ученики 10 класса «В»Криницин Валерий, Урбанович Дмитрий
Министерство науки УР
Средняя школа № 12
Сарапул, 2004 г.
1. Введение
Целью данной работы было выяснение сути алгебры логики,основных методов работы с логическими операторами, роли логики в вычислительнойтехнике и информатике. Для выполнения этой работы потребовалось найтиметодические материалы по теме, решить некоторые опытные задачи и сделатьвыводы. Предмет исследования — операции над логическими функциями.
В реферате будут рассмотрены следующие вопросы:
1) Возникновение логики.
Здесь приводится краткая историческая справка возникновениялогики как науки.
2) Булевы функции.
Здесь будут рассмотрены особые математические функции отлогических аргументов.
3) Преобразование выражений, состоящих из булевых функций.
Особое значение имеет упрощение логических выражений, т.к.это соответствует сути экономики – хозяйственной деятельности человека.
4) Нахождение исходного выражения по его значениям.
Благодаря особым свойствам логических функций, возможно ихвосстановление, зная только значения функции при определённых аргументах.
5) Применение в вычислительной технике и информатике.
2. Алгебра логики.
Возникновение логики.
Понятие логики как науки появилось ещё в XIX в., т.е.задолго до появления науки информатики и компьютеров. Элементы математическойлогики можно найти уже в работах древнегреческих философов. В XVII в. Г. В.Лейбниц высказал идею о том, что рассуждения могут быть сведены к механическомувыполнению определенных действий по установленным правилам. Однако каксамостоятельный раздел математики логика начала формироваться только с серединыXIX в..
Для того чтобы рассуждать, человеку необходим какой-либоязык. Не удивительно, что математическая логика начиналась с анализа того, какговорят и пишут люди на естественных языках. Этот анализ привёл к тому, что выяснилосьсуществование формулировок, которые невозможно разделить на истинные и ложные,но, тем не менее, выглядят осмысленным образом. Это приводило к возникновениюпарадоксов, в том числе в одной из фундаментальных наук математики. Тогда былорешено создать искусственные формальные языки, лишённого «вольностей» языкаестественного.
Булевы функции.
Пусть имеется некоторый набор высказываний, о которых можноговорить определённо, что они истинные или ложные. Обозначим их латинскимибуквами A, B, C, D … .
Если у нас есть два простых предложения, то из нихобразовать новое, сложносочинённое предложение с помощью союзов «или» либо «и».В математической логике для этой цели используются специальные символы:
— знак дизъюнкции v
— знак конъюнкции & (иногда используется ^)
Таким образом, из утверждений A, B с помощью знаковдизъюнкции и конъюнкции получим новые утверждения:
— A v B («A или B»)
— A & B («A и B»)
Утверждение A v B считается истинным тогда и только тогда, когда истиннохотя бы одно из исходных утверждений; утверждение A & B – когда истинны обаутверждения.
Дизъюнкцию и конъюнкцию можно рассматривать как особыеоперации, определённые не на числах, а на логических значениях ИСТИНА и ЛОЖЬ.Для этих операций существуют таблицы, подобные таблице умножения.
A B A v BИСТИНА
ИСТИНА
ЛОЖЬ
ЛОЖЬ
ИСТИНА
ЛОЖЬ
ИСТИНА
ЛОЖЬ
ИСТИНА
ИСТИНА
ИСТИНА
ЛОЖЬ
A B A & BИСТИНА
ИСТИНА
ЛОЖЬ
ЛОЖЬ
ИСТИНА
ЛОЖЬ
ИСТИНА
ЛОЖЬ
ИСТИНА
ЛОЖЬ
ЛОЖЬ
ЛОЖЬ
Логические значения ИСТИНА и ЛОЖЬ называют также булевымизначениями – в честь английского математика Джорджа Буля, который в XIX в.заложил основы современной математической логики. Функции с булевымиаргументами называют булевыми функциями. Всего булевых функций от 2 переменных– 16. Для всех булевых функций от двух переменных имеются соответствующиеконструкции на русском языке. В информатике в основном используются следующиебулевы функции:
— логическое ИЛИ (дизъюнкция)
— логическое И (конъюнкция)
— логическое отрицание («НЕ», обозначается ~ ипротивоположно своему аргументу)
— исключающее ИЛИ
Из этих основных складываются комбинированные функции:ИЛИ-НЕ, И-НЕ. Именно они получили наибольшее распространение в логическойэлектронике, в компьютерах.
Преобразование выражений, состоящих избулевых функций.
В математической логике преобразование выше указанныхвыражений проводится для различных целей – от упрощения исходного додоказательства утверждений. В информатике же оно используется в основном дляупрощения, ведь при производстве цифровой электроники, как и любого другоготовара, требуются наименьшие затраты. Для упрощения булевых выраженийиспользуются те же методы, что и при упрощении алгебраических. Для начала былапроведена аналогия между алгебраическими операторами от двух аргументов(сложение, вычитание, умножение и т.д.) и булевыми. Было выяснено, чтоумножение и логическое «И» обладают сходными свойствами:
— от перестановки мест аргументов результат не изменяется
A & B = B & A
— существует следующий закон
A & (B & C) = (A & B) & C
Также существуют некоторые тождества, опирающиеся на особыесвойства функции, например:
1) A & (~A) = ЛОЖЬ
2) (~A) & (~B) = ~ (A v B)
Аналогично, сложение и логическое «ИЛИ»:
— от перестановки мест аргументов результат не изменяется
A v B = B v A
— существует следующий закон
(A v B) v С = A v (B v C)
— можно выносить общий множитель за скобки
(A & B) v (С & B) = B & (A v C)
И также некоторые собственные законы:
1) A v (~A) = ИСТИНА
2) (~A) v (~B) = ~ (A & B)
Когда вычисляется значение булевого выражения, товыполняется определённая очерёдность действий: на очерёдность влияют скобки,сначала считаются «И», затем «ИЛИ». Благодаря этой очерёдности возможносоздание электронных цифровых схем.
Нахождение исходного выражения по егозначениям.
В отличие от алгебраических выражений, булевы можновосстановить, зная их аргументы и соответственные им значения. Пусть нам данабулева функция от 3 переменных:
X1 X2 X3 F1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
Составим для неё таблицу и условимся обозначать ИСТИНУ — 1,а ЛОЖЬ – 0.
Для начала выпишем все аргументы функции, при которыхфункция равна 1.
Это:
F (1, 1, 0) = 1
F (1, 0, 1) = 1
F (1, 1, 1) = 1
Теперь запишем 3 таких выражения (функция принимаетзначение 1 три раза), что они принимают значение 1 только при вышеуказанныхзначениях.
X1 & X2 & (~X3)
X1 & (~X2) & X3
X1 & X2 & X3
И запишем их логическую сумму:
(X1 & X2 & (~X3)) v (X1 & (~X2) & X3) v (X1 & X2 & X3) – это выражение принимает значение 1 при тех жезначениях, что и исходная функция. Полученное выражение можно упростить.
(X1 & X2 & (~X3)) v (X1 & (~X2)& X3) v (X1 & X2 & X3) =
= X1 & ((X2 & (~X3)) v ((~X2) & X3)v (X2 & X3)) =
= X1 & ((X2 & (~X3)) v X3 & ((~X2) vX2)) =
= X1 & ((X2 & (~X3)) v X3) – эта формула несколько длиннее исходной, но намногопроще полученной в первый раз. Дальнейшие пути упрощения более сложны ипредставляют большой интерес для проектировщиков интегральных микросхем, т.к.меньшее число операций требует меньшее число элементов, их которых состоит ИС.
Применение в вычислительной технике иинформатике.
После изготовления первого компьютера стало ясно, что приего производстве возможно использование только цифровых технологий –ограничение сигналов связи единицей и нулём для большей надёжности и простотыархитектуры ПК. Благодаря своей бинарной природе, математическая логикаполучила широкое распространение в ВТ и информатике. Были созданы электронныеэквиваленты логических функций, что позволило применять методы упрощениябулевых выражений к упрощению электрической схемы. Кроме того, благодаря возможностинахождения исходной функции по таблице позволило сократить время поисканеобходимой логической схемы.
В программировании логика незаменима как строгий язык ислужит для описания сложных утверждений, значение которых может определитькомпьютер.
3. Заключение.
Итак, логика возникла задолго до появления компьютеров ивозникла она в результате необходимости в строгом формальном языке. Былипостроены функции – удобное средство для построения сложных утверждений ипроверки их истинности. Оказалось, что такие функции обладают аналогичнымисвойствами с алгебраическими операторами. Это дало возможность упрощатьисходные выражения. Особое свойство логических выражений – возможность ихнахождения по значениям. Это получило широкое распространение в цифровой электронике,где используются логические элементы, и программировании.
Список литературы
1. «Компьютер» Ю. Л. Кетков, изд. «Дрофа» 1997 г.
2. «Математика» Ю. Владимиров, изд. «Аванта+» 1998 г.