зачем нужна алгебра логики
Алгебра логики
Законы алгебры логики
Алгебра логики это раздел математической логики, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности или ложности), и логические операции над ними.
В алгебре логики принято отождествлять истинность высказывания с числом 1, а ложность — с числом 0 (А = 1 и С = 0 означает, что А истинно и что С ложно).
Что изучает алгебра логики?
Предметом изучения алгебры логики являются функции которые принимают лишь два значения: 0 или 1. Объединение простых высказываний в сложные в алгебре логики производится без учёта внутреннего содержания (смысла) этих высказываний.
К основным логическим операциям относятся операции: отрицания, логического умножения, или конъюнкции, логического сложения, или дизъюнкции, эквивалентности, импликации.
Любое сложное выражение, полученное из простых высказываний посредством основных логических операции, называется формулой алгебры логики.
Где используется алгебра логики?
Использование аппарата алгебры логики в теории устройств дискретного действия основано на том, что элементы этих устройств являются двух позиционными приборами, т. е. приборами, которые по условиям работы могут находиться лишь в одном из двух различных устойчивых состояний, например «контакт замкнут», «транзистор открыт».
Конъюнкция такого рода высказываний будет тогда средством выражения последовательного соединения элементов, а дизъюнкция — их параллельного соединения. На этом основана возможность применять средства алгебры логики к задачам анализа и синтеза переключателей схем. Алгебра логики используется в теории релейных схем, теории ЭВМ и в теории дискретных автоматов.
Информатика не может существовать без такого важного раздела математики, который называется алгеброй логики. В данной статье будет рассказана основополагающая информация по данной теме, обозначены её главные правила и законы.
Что такое алгебра и алгебра логики
Алгебра — это раздел математики, который обобщенно можно охарактеризовать, как расширение и обобщение арифметики.
Алгебра логики — это раздел математической логики, который исследует операции над высказываниями.
Законы алгебры логики
Имеется большое количество правил в данной сфере деятельности, но сегодня будет рассмотрено несколько основных.
Основные законы алгебры логики представлены в таблице:
Логические выражения
В информатике предоставляется два вида высказываний: простое и сложное.
Простое — это утверждение, которое обычно обозначается в виде предложения и про него можно сказать — ложное оно или истинное.
Нью-Йорк — столица США (ложное);
в России 1117 городов (верное).
Сложное высказывание обозначает некий набор простых утверждений, которые связаны логическими процессами.
Идёт дождь, а у меня нет зонта.
Основные логические операции
Логические процессы подразделяются на несколько классов. Рассмотрим их последовательно.
Логическое отрицание (инверсия) —НЕ
Таблица истинности инверсии:
Результаты операции НЕ следующие:
если исходное выражение истинно, то результат его отрицания будет ложным;
если исходное выражение ложно, то результат его отрицания будет истинным.
Логическое сложение (дизъюнкция, объединение) — ИЛИ
Понятие «Логическое ИЛИ» также можно заменить понятием «Дизъюнкция». Данная операция обозначается знаками — ИЛИ, OR, ||, |.
Но есть небольшое отличие: в «Логическом И» результат отрицания равен единице, если оба обозначения равны единице, а в «Логическом ИЛИ» итог равен единице, если одно из обозначений равно единице.
Таблица истинности операции ИЛИ:
Логическое умножение(конъюнкция) — И
В истории данная операция также обозначается как логическое умножение и конъюнкция. Данная операция обозначается элементами — И, AND, &&, &.
За объект описания возьмём А и В. Оба данных выражения могут иметь или неверное значение, или правдивое значение. Для применения операции логическое умножение, и А, и В должны является истинными (то есть равными единице).
При всех остальных значениях операция будет ложной.
Таблица истинности операции И приведена ниже:
Логическое следование (импликация) — ЕСЛИ ТО
Данная программа имеет также название «Импликация». Она образуется из двух высказываний, которые соединяет: «если. то».
Необходимо запомнить, что данная операция ложна только тогда, когда из первого ложного утверждения следует ложный итог. На компьютерном языке данный процесс обозначается формулой: if. then.
Таблица истинности операции ЕСЛИ ТО выглядит так:
Данная операция определяется так: сложное высказывание будет истинно тогда и только тогда, когда и А, и В — истинные.
И наоборот: сложное высказывание будет ложным тогда и только тогда, когда и А, и В — ложные.
Таблица истинности операции эквивалентности:
Зачем нужна алгебра логики
ну а теперь немного о жизни.
В математической логике было дано точное определение алгоритма и вычислимости. Вопрос о существовании алгоритмов имеет для математики первостепенное значение (например, алгоритм существования решений для системы уравнений). Были получены разрешающие алгоритмы для ряда теорий, например, элементарной геометрии, упорядоченного поля действительных чисел, атомной булевой алгебры и т.д. Неразрешимы теории (т.е. не существует единого алгоритма для решения всех задач) элементарной арифметики, анализа, класса всех конечных симметрических групп (т.е.групп перестановок), аксиоматических систем теории множеств.
В последние годы большое внимание уделяется теории сложности алгоритмов и вычислений. Выяснилось, что одного только существования алгоритма, решающего ту или иную массовую проблему, далеко не достаточно для практики. После уточнения понятия сложности вычисления стали исследовать вопросы такого рода, как внутренняя сложность вычислимой функции, ее криптографическая стойкость, приобретающие особую актуальность с развитием сетей связи, вычислительной техники и автоматизированных систем управления.
а историю с философией вы зачем учите. чтобы мозг ваш начал учиться анализировать ситуацию вокруг вас.
а зачем вы учили матанализ и геометрию. наверное, чтобы потом написать какие-то полезные программы для решения конкретных практических задач!
метод резолюций, например, является основой логического программирования (а это, в свою очередь, база в разработке систем искусственного интеллекта и экспертных систем)
формулы алгебры логики используюстя в РКС, на которых построена любая ЭВМ.
с их же (формул) помощью решаются довольно легко различные логические задачи, где есть куча условий и их все нужно проанализировать, свести во едино и сделать верное умозаключение.
спросите, зачем вам нужна эта наука? так вы же пришли учиться в вуз! если вам нужны знания только для выполнения механической работы, связанной с компами, сетями и прочим, тогда надо было идти в техникум, там не углубляются в теоретическую науку настолько!
Зачем нужна алгебра логики
Основные понятия алгебры логики, её применение в информатике. Решение задачи с расчетом стоимости стеклопакетов. Информационная и аналитическая модель задачи, технология решения задачи в MS Excel. Результаты компьютерного эксперимента и их анализ.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 22.01.2015 |
| Размер файла | 44,7 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФГБОУ ВПО
«Финансовый университет при правительстве российской федерации»
Кафедра Экономической теории
по дисциплине «Информатика»
на тему «Применение алгебры логики в информатике»
алгебра логика задача компьютерный
1. Теоретическая часть
1.1 Наука алгебра логики
1.2 Основные понятия алгебры логики
1.3 Применение алгебры логики в информатике
2. Практическая часть
2.1 Постановка задачи
2.1.1 Цель решения задачи
2.1.2 Условие задачи
2.2 Компьютерная модель решения задачи
2.2.1 Информационная модель решения задачи
2.2.2 Аналитическая модель решения задачи
2.2.3 Технология решения задачи
2.3 Результаты компьютерного эксперимента и их анализ
2.3.1 Результаты компьютерного эксперимента
2.3.2 Анализ полученных результатов
Список использованной литературы
Тема теоретической части курсовой работы: Применение алгебры логики в информатике. Алгебра логики является составной частью одного из современных быстро развивающихся разделов математики — математической логики. Математическая логика применяется в информатике, позволяет моделировать простейшие мыслительные процессы. Одним из занимательных приложений алгебры высказываний — решение логических задач.
В логических задачах исходными данными являются не только и не столько числа, а сложные логические суждения, подчас весьма запутанные. Эти суждения и связи между ними бывают иногда столь противоречивы, что для их разрешения привлекают вычислительные машины.
Цель данной курсовой работы состоит в изучении применения алгебры логики в информатике.
Для достижения цели необходимо ответить на следующие вопросы:
— наука алгебра логики
— основные понятия алгебры логики
— применение алгебры логики в информатике (к построению схем, обработке знаний и т.д.)
Практическая часть выполнена с использование MS Excel и MS Word.
Алгебра логики возникла в середине ХIХ века в трудах английского математика Джорджа Буля. Её создание представляло собой попытку решать традиционные логические задачи алгебраическими методами.
Отцом алгебры логики по праву считается английский математик 19-го столетия Джорж Буль (1815-1864). Именно он построил один из разделов формальной логики в виде некоторой «алгебры», аналогичной алгебре чисел, но не сводящейся к ней. Алгебра в широком смысле слова — наука об общих операциях, аналогичных сложению и умножению, которые могут выполняться не только с числами, но и над другими математическими объектами. Существуют алгебры натуральных чисел, многочленов, векторов, матриц, множеств и т.д.
Большой вклад в становление и развитие алгебры логики внесли Августус де Морган (1806-1871), Уильям Стенли Джевонс (1835-1882), П.С. Порецкий(1846 — 1907), Чарлз Сандерс Пирс (1839-1914), А.А. Марков (1903-1979), А.Н. Колмогоров (1903-1987) и др.
Долгое время алгебра логики была известна достаточно узкому классу специалистов. Прошло почти 100 лет со времени создания алгебры логики Дж. Булем, прежде чем в 1938 Клод Шеннон (1916-2001) показал, что алгебра логики применима для описания самых разнообразных процессов, в том числе функционирования релейно-контактных и электронно-ламповых схем.
Алгебра логики явилась математической основой теории электрических и электронных переключателей схем, используемых в ЭВМ. В компьютерных науках её предпочитают называть не алгеброй логики, а Булевой алгеброй — по имени её создателя.
Алгебра логики изучает свойства функций, у которых и аргументы, и значения принадлежат заданному двухэлементному множеству (например, ).Иногда вместо термина «алгебра логики» употребляют термин «двузначная логика».
Алгебра логики — предельно важная для цифровых компьютеров тема. И с точки зрения их устройства, схем техники, и с точки зрения их функционирования и программирования поведения.
Действительно, мало-мальски сложное действие невозможно без обратной связи, без анализа условий выполнения. Например, «ЕСЛИ нам хочется пить, ТО мы пьём, ИНАЧЕ мы даже не думаем об этом». «ЕСЛИ компьютер не работает И питание включено, ТО компьютер сгорел». «ЕСЛИ точка левее левой стороны квадрата ИЛИ правее правой, ТО точка расположена не в квадрате». «Ревёт ли зверь в лесу глухом, трубит ли рог, гремит ли гром. ». «Кошелёк или жизнь». Помимо манипуляций константами «да» и «нет» логические переменные могут являться результатом применения к числам операторов отношения (меньше, больше, равно и т.п.). В компьютерах булевы переменные представляются (кодируются) битами (разрядами двоичной системы счисления), где 1 означает истину, а 0 — ложь. Манипуляции высказываниями и их комбинациями используются для получения некоего единственного результата, который можно использовать, например, для выбора той или иной последовательности действий. Поскольку логические переменные кодируются по тем же принципам, что и числа, символы и прочая информация, то можно комбинировать операции логики с операциями арифметики для реализации различных алгоритмов.
Таким образом, алгебра логики (другое название — Булева алгебра) — это область математики. Она оперирует величинами, которые могут принимать два значения (булевых значения). Эти два значения могут быть обозначены как угодно, лишь бы по-разному. Самые распространенные варианты:
При применении булевой алгебры в вычислительной технике, булевы значения — это 0 и 1. Они представляют собой состояние ячейки памяти объёмом в 1 бит или наличие/отсутствие напряжения в электрической схеме. Алгебра логики позволяет строить сложные электронные узлы, элементы которых работают согласно этой математической теории. При применении булевой алгебры в логических построениях в математике, булевы значения — это «ложь» и «истина». Они определяют истинность или ложность некоторого высказывания. Под высказываниями понимаются математические формулы. При применении булевой алгебры в повседневных рассуждениях, булевы значения — это также «ложь» и «истина». Они представляют собой оценку истинности или ложности некоторого высказывания. Под высказываниями понимаются фразы, которые удовлетворяют строго определенному списку свойств.
Алгебра логики применяется:
1) для упрощения сложных логических формул и доказательств тождеств;
2) при решении логических задач;
3) в контактных схемах;
4) при доказательствах теорем;
5) в базах данных при составлении запросов.
1.2 Основные понятия алгебры логики
Объектом логики как науки выступает абстрактное мышление. Логика изучает абстрактное мышление как средство познания объективного мира, исследует формы и законы, в которых происходит отражение мира в процессе мышления. Основными формами абстрактного мышления являются:
Понятие — форма мышления, в которой отражаются существенные признаки отдельного предмета или класса однородных предметов: портфель трапеция ураганный ветер, (например, «дерево», «самолет») или группой слов, т.е. словосочетаниями, например, «студент гуманитарного института», «создатель художественных картин», «река Дон», «космический корабль» и др.
Суждение — мысль, в которой что-либо утверждается или отрицается о предметах. Суждения являются повествовательными предложениями, истинными или ложными. Они могут быть простыми и сложными: Весна наступила, и грачи прилетели.
Пример сложного суждения: «Наступила осень, и лебеди улетают». Оно состоит из двух простых суждений.
Умозаключение — прием мышления, посредством которого из исходного знания получается новое знание; из одного или нескольких истинных суждений, называемых посылками, мы по определенным правилам вывода получаем заключение. Есть несколько видов умозаключений. Все металлы — простые вещества. Литий — металл. Литий — простое вещество.
Все металлы — вещества. Железо — металл. Железо — вещество
Чтобы достичь истины при помощи умозаключений, надо соблюдать законы логики.
Формальная логика — наука о законах и формах правильного мышления.
Математическая логика изучает логические связи и отношения, лежащие в основе дедуктивного (логического) вывода.
Законы алгебры логики
Алгебра логики это раздел математической логики, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности или ложности), и логические операции над ними.
В алгебре логики принято отождествлять истинность высказывания с числом 1, а ложность — с числом 0 (А = 1 и С = 0 означает, что А истинно и что С ложно).
Что изучает алгебра логики?
Предметом изучения алгебры логики являются функции которые принимают лишь два значения: 0 или 1. Объединение простых высказываний в сложные в алгебре логики производится без учёта внутреннего содержания (смысла) этих высказываний.
К основным логическим операциям относятся операции: отрицания, логического умножения, или конъюнкции, логического сложения, или дизъюнкции, эквивалентности, импликации.
Любое сложное выражение, полученное из простых высказываний посредством основных логических операции, называется формулой алгебры логики.
Где используется алгебра логики?
Использование аппарата алгебры логики в теории устройств дискретного действия основано на том, что элементы этих устройств являются двух позиционными приборами, т. е. приборами, которые по условиям работы могут находиться лишь в одном из двух различных устойчивых состояний, например «контакт замкнут», «транзистор открыт».
Конъюнкция такого рода высказываний будет тогда средством выражения последовательного соединения элементов, а дизъюнкция — их параллельного соединения. На этом основана возможность применять средства алгебры логики к задачам анализа и синтеза переключателей схем. Алгебра логики используется в теории релейных схем, теории ЭВМ и в теории дискретных автоматов.
Что такое алгебра логики?
Алгебра логики (булева алгебра) – это раздел математики, возникший в XIX веке благодаря усилиям английского математика Дж. Буля. Поначалу булева алгебра не имела никакого практического значения. Однако уже в XX веке ее положения нашли применение в описании функционирования и разработке различных электронных схем. Законы и аппарат алгебры логики стал использоваться при проектировании различных частей компьютеров (память, процессор). Хотя это не единственная сфера применения данной науки.
Что же собой представляет алгебра логики?
Во-первых, она изучает методы установления истинности или ложности сложных логических высказываний с помощью алгебраических методов. Во-вторых, булева алгебра делает это таким образом, что сложное логическое высказывание описывается функцией, результатом вычисления которой может быть
либо истина, либо ложь (1, либо 0). При этом аргументы функции (простые высказывания) также могут иметь только два
логическое высказывание? Это фразы типа «два больше одного», «5.8 является целым числом». В первом случае мы имеем истину, а во втором ложь. Алгебра логики не касается сути этих высказываний. Если кто-то решит, что высказывание «Земля квадратная» истинно, то алгебра логики это примет как факт. Дело в том, что булева алгебра занимается вычислениями результата сложных логических высказываний на основе заранее известных значений простых высказываний.
Логические операции. Дизъюнкция, конъюнкция и отрицание
Так как же связываются между собой простые логические высказывания, образуя сложные? В естественном языке мы используем различные союзы и другие части речи. Например, «и», «или», «либо», «не», «если», «то», «тогда». Пример сложных высказываний: «у него есть знания
и навыки», «она приедет во вторник,
либо в среду», «я буду играть
тогда, когда сделаю уроки», «5
не равно 6». Как мы решаем, что нам сказали правду или нет? Как-то логически, даже где-то неосознанно, исходя из предыдущего жизненного опыта, мы понимает, что правда при союзе «и» наступает в случае правдивости обоих простых высказываний. Стоит одному стать ложью и все сложное высказывание будет лживо. А вот, при связке «либо» должно быть правдой только одно простое высказывание, и тогда все выражение станет истинным.
Булева алгебра переложила этот жизненный опыт на аппарат математики, формализовала его, ввела жесткие правила получения однозначного результата. Союзы стали называться здесь логическими операторами.
Алгебра логики предусматривает множество логических операций. Однако три из них заслуживают особого внимания, т.к. с их помощью можно описать все остальные, и, следовательно, использовать меньше разнообразных устройств при конструировании схем. Такими операциями являются
конъюнкция (И),
дизъюнкция (ИЛИ) и
отрицание (НЕ). Часто конъюнкцию обозначают
&, дизъюнкцию —
||, а отрицание — чертой над переменной, обозначающей высказывание.
При конъюнкции истина сложного выражения возникает лишь в случае истинности всех простых выражений, из которых состоит сложное. Во всех остальных случаях сложное выражение будет ложно.
При дизъюнкции истина сложного выражения наступает при истинности хотя бы одного входящего в него простого выражения или двух сразу. Бывает, что сложное выражение состоит более, чем из двух простых. В этом случае достаточно, чтобы одно простое было истинным и тогда все высказывание будет истинным.
Отрицание – это унарная операция, т.к выполняется по отношению к одному простому выражению или по отношению к результату сложного. В результате отрицания получается новое высказывание, противоположное исходному.
Таблицы истинности
Логические операции удобно описывать так называемыми
таблицами истинности, в которых отражают результаты вычислений сложных высказываний при различных значениях исходных простых высказываний. Простые высказывания обозначаются переменными (например, A и B).
Логические основы компьютера
В ЭВМ используются различные устройства, работу которых прекрасно описывает алгебра логики. К таким устройствам относятся группы переключателей, триггеры, сумматоры.
Кроме того, связь между булевой алгеброй и компьютерами лежит и в используемой в ЭВМ системе счисления. Как известно она двоичная. Поэтому в устройствах компьютера можно хранить и преобразовывать как числа, так и значения логических переменных.
Переключательные схемы
В ЭВМ применяются электрические схемы, состоящие из множества переключателей. Переключатель может находиться только в двух состояниях: замкнутом и разомкнутом. В первом случае – ток проходит, во втором – нет. Описывать работу таких схем очень удобно с помощью алгебры логики. В зависимости от положения переключателей можно получить или не получить сигналы на выходах.
Вентили, триггеры и сумматоры
Вентиль представляет собой логический элемент, который принимает одни двоичные значения и выдает другие в зависимости от своей реализации. Так, например, есть вентили, реализующие логическое умножение (конъюнкцию), сложение (дизъюнкцию) и отрицание.
Триггеры и сумматоры – это относительно сложные устройства, состоящие из более простых элементов – вентилей.
Триггер способен хранить один двоичный разряд, за счет того, что может находиться в двух устойчивых состояниях. В основном триггеры используется в регистрах процессора.
Сумматоры широко используются в арифметико-логических устройствах (АЛУ) процессора и выполняют суммирование двоичных разрядов.