Доклад алгебра логики информатика 8 класс

Обновлено: 02.07.2024

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

Рубрика	Программирование, компьютеры и кибернетика
Вид	реферат
Язык	русский
Дата добавления	22.02.2013
Размер файла	550,6 K

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

по информатике и ИКТ

Что такое алгебра логики

Алгебра логики - это математический аппарат, с помощью которого записывают, вычисляют, упрощают и преобразовывают логические высказывания.

Создателем алгебры логики является живший в XIX в. английский математик Джордж Буль, в честь которого она названа булевой алгеброй высказываний.

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

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

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

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

Чтобы обращаться к логическим высказываниям, им назначают имена.

Каждая логическая связка рассматривается как операция над логическими высказываниями и имеет свое название и обозначение:

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

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

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

Эквиваленцию можно выразить через отрицание, дизъюнкцию и конъюнкцию:

Таким образом, операций отрицания, дизъюнкции и конъюнкции достаточно что бы описывать и обрабатывать логические высказывания.

Что такое логическая формула

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

Бета А и В - формулы, то А, (А * В), (AvB), (A->B), (А В) - формулы. Никаких других формул в алгебре логики нет.

В пункте 1 определены элементарные формулы, в пункте 2 даны правила образования из любых данных формул новых формул.

Высказывания, которые формализуются тавтологиями, называются логически истинными высказываниями.

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

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

Связь между алгеброй логики и двоичным кодированием

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

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

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

В каком виде записываются в памяти компьютера и в регистрах процессора данные и команды

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

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

0 1 0 0 1 1 0 1 0 0

Что такое логический элемент компьютера

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

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

Элементы алгебры логики

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

Первые элементы алгебры логики были описаны в 19 веке в работах английского математика Джорджа Буля. Он первый высказал мысль о связи логики с математикой.

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

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

Например, не являются высказываниями следующие предложения:

Сколько весит слон?
Летайте самолетами Аэрофлота!
5*х + 8*y = 24
Этот фильм самый лучший.

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

Действия над высказываниями

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

Пересечение.
Объединение.
Инверсия.

Наглядно логические операции поясняют круги Эйлера или диаграммы Венна.

Пересечение

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

Пересечение также называют логическим умножением, конъюнкцией или логическим И.

Обозначают знаками И, & или ∩.

Рис. 1. Диаграмма Венна для операции пересечения

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

Объединение

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

Объединение также называют логическим сложением, дизъюнкцией, логическим ИЛИ.

Для ее обозначения используются знаки: ИЛИ, +, U.

Рис. 2. Диаграмма Венна для операции объединения

На диаграмме Венна операция объединения представляет собой всю область, относящуюся и к первому и ко второму операнду.

Инверсия

Инверсия – унарная логическая операция, заключающаяся в изменении на противоположное значение.

Инверсию обозначают знаками НЕ, ¬, ¯.

Инверсия на диаграмме Венна выглядит как область, не относящаяся к операнду.

Рис. 3. Диаграмма Венна для операции инвертирования

Аксиомы алгебры логики

В математике есть понятие аксиома – постулат, не требующий доказательств.

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

Для объединения справедливы аксиомы:

А + 0 = А
А + 1 = 1
А + А = А
А + НЕ(А) = 1

Для пересечения характерны такие аксиомы:

А & 0 = 0
А & 1 = А
А & А = А
А & НЕ(А) = О

Для операции инверсии применима аксиома двойного отрицания НЕ (НЕ (А)), когда дважды проинвертировав операнд получают в итоге само исходное значение.

Что мы узнали?

Алгебра логики стоит на стыке математики и информатики и составляет теоретическую базу, на основе которой строятся методы работы с информацией. Объектом изучения этого направления является высказывания. Основными логическими операциями являются пересечение, объединение и инверсия. В алгебре логики действуют ряд аксиом.

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

Что такое алгебра и алгебра логики

Алгебра — это раздел математики, который обобщенно можно охарактеризовать, как расширение и обобщение арифметики.

Алгебра логики — это раздел математической логики, который исследует операции над высказываниями.

Законы алгебры логики

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

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

Сочетательный закон - применяется, когда есть или только операция дизъюнкции, или только операция конъюнкции. Тогда можно обходиться без скобок или хаотично ставить скобки.

Распределительный закон - имеется два типа данного правила: дистрибутивность дизъюнкции относительно конъюнкции и дистрибутивность конъюнкции относительно дизъюнкции. Первый тип схож с дистрибутивным законом алгебры, а второй — нет, поэтому его нужно доказывать.

Закон двойственности и инверсии (закон Моргана) - основоположником данного правила стал шотландский математик и логик де Морган. Он разработал правило, которое связывает логические операции конъюкцию (И) и дизъюнкцию (ИЛИ) с помощью отрицания.

Основные законы алгебры логики представлены в таблице:

Логические выражения

В информатике предоставляется два вида высказываний: простое и сложное.

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

Нью-Йорк — столица США (ложное);

в России 1117 городов (верное).

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

Идёт дождь, а у меня нет зонта.

Основные логические операции

Логические процессы подразделяются на несколько классов. Рассмотрим их последовательно.

Логическое отрицание (инверсия) —НЕ

Данная операция используется при обозначении отрицания. Она обозначается знаками — NO, NOT, ! В=2 (истина), а после выполнения операции отрицания, В, к примеру, приобретет значение 1 (ложное).

Таблица истинности инверсии:

Результаты операции НЕ следующие:

если исходное выражение истинно, то результат его отрицания будет ложным;

если исходное выражение ложно, то результат его отрицания будет истинным.

Логическое сложение (дизъюнкция, объединение) — ИЛИ

Таблица истинности операции ИЛИ:

Логическое умножение(конъюнкция) — И

В истории данная операция также обозначается как логическое умножение и конъюнкция. Данная операция обозначается элементами — И, AND, &&, &.

За объект описания возьмём А и В. Оба данных выражения могут иметь или неверное значение, или правдивое значение. Для применения операции логическое умножение, и А, и В должны является истинными (то есть равными единице).

При всех остальных значениях операция будет ложной.

Таблица истинности операции И приведена ниже:

Логическое следование (импликация) — ЕСЛИ ТО

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

Таблица истинности операции ЕСЛИ ТО выглядит так:

Операция эквивалентности (равнозначности) - А ТОГДА И ТОЛЬКО ТОГДА, КОГДА В

Данная операция определяется так: сложное высказывание будет истинно тогда и только тогда, когда и А, и В — истинные.

И наоборот: сложное высказывание будет ложным тогда и только тогда, когда и А, и В — ложные.

Таблица истинности операции эквивалентности:

Логика в информатике – это направления исследований и отрасли знания, где логика применяется в информатике и искусственном интеллекте.

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

Математическая логика нашла широкое применение в языках программирования. Все языки программирования включают в себя базовые логические операции и некоторые логические функции: IMP, EQL, и так далее.

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

В практической части будет построена компьютерная модель решения задачи в среде MS Excel.

1. Теоретическая часть

1.1 Основные понятия и определения

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

При этом под высказыванием (суждением) понимают повествовательное предложение, относительно которого можно сказать, истинно или ложно.

Алгебра логики возникла в середине ХIХ века в трудах английского математика Джорджа Буля. Её создание представляло собой попытку решать традиционные логические задачи алгебраическими методами.

Долгое время алгебра логики была известна достаточно узкому классу специалистов. Прошло почти 100 лет со времени создания алгебры логики Дж. Булем, прежде чем в 1938 Клод Шеннон (1916 - 2001) показал, что алгебра логики применима для описания самых разнообразных процессов, в том числе функционирования релейно-контактных и электронно-ламповых схем.

Алгебра логики явилась математической основой теории электрических и электронных переключателей схем, используемых в ЭВМ. В компьютерных науках её предпочитают называть не алгеброй логики, а Булевой алгеброй - по имени её создателя.

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

операциями арифметики для реализации различных алгоритмов.

Таким образом, алгебра логики - это область математики. Она оперирует величинами, которые могут принимать два значения (булевых значения). Эти два значения могут быть обозначены как угодно, лишь бы по-разному. Самые распространенные варианты:

0, 1 F, T false, true ложь, истина Л, И

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

1.2. Основные логические операции и элементы

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

В данный момент вы не можете посмотреть или раздать видеоурок ученикам

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

Получите невероятные возможности

Конспект урока "Элементы алгебры логики. Логические операции"

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

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

Высказывания бывают простыми и сложными.

Простое высказывание – это высказывание, в котором никакая его часть сама не является высказыванием.

К примерам простых высказываний можно отнести следующие предложения:

Первое простое высказывание истинно, а второе – ложно.

Сложные или же составные высказывания – это высказывания, которые строятся из простых с помощью логических операций.

Примером сложного высказывания будет следующее предложение:

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

В первом столбце у нас указаны названия логических операций, а во втором – логические связки.

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

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

То есть мы можем написать просто словами на русском языке: Истинна или Ложь. Или же сократить их до первых букв. Также можно писать на английском языке: True или False. Или также сократить до первых букв. И последнее обозначение — это 1 и 0, где 1 – это истина, а 0 – ложь. Мы с вами будем использовать числа ноль и один.

А теперь давайте подробнее познакомимся с логическими операциями.

Давайте узнаем, как обозначается знак конъюнкции в различных сферах его применения.

А сейчас мы с вами составим таблицу истинности для конъюнкции.

Пусть у нас есть два высказывания А и B. Они будут заголовками первого и второго столбца. А новое выражение, которое образуется с помощью конъюнкции обозначим А и B – и это будет являться заголовком для третьего столбца.

Далее, вспомним, что если высказывание истинно, то ему соответствует число 1, а если ложно – 0.

Допустим, высказывания А и B – оба ложны. Занесём нули в соответствующие ячейки.

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

Далее, пусть А будет ложным, а B – истинным. Новое высказывание будет ложным, так как высказывание А – ложно.

Теперь сделаем наоборот, пусть А – истинно, B – ложно. И снова новое высказывание будет ложным.

А если высказывания А и B будут истинными, то новое высказывание также будет истинно. Так как в определение сказано, что новое высказывание будет истинно тогда и только тогда, когда истинны исходные высказывания.

Мы с вами рассмотрели все возможные значения исходных высказываний А и B.

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

Лампочка загорится только в том случае, если два выключателя будут включены (замкнуты).

То есть тогда новое высказывание будет истинно.

Конъюнкцию также называют логическим умножением. Давайте посмотрим ещё раз на таблицу истинности.

Какие числа мы получим в результате перемножение первого и второго столбцов? В первых трёх строках третьего столбца будут нули, так как любое число при умножении на 0 даёт 0. А вот 1 на 1 равно 1. То есть мы получили такие же данные, как и при первом построении таблицы истинности.

А теперь переходим к дизъюнкции.

В различных сферах применения, дизъюнкция обозначается по-разному.

А теперь давайте составим таблицу истинности для дизъюнкции. Нам даны два высказывания А и B. Их значения мы будем вносить в первых два столбца. А в третий будем вносить обозначения, которые получаются при образовании нового высказывания с использованием дизъюнкции.

Итак, пусть наши два высказывания ложны. В определении сказано, что новое высказывание будет ложно тогда и только тогда, когда ложны два высказывания. Значит в нашем случае новое высказывание будет ложно.

Далее, пусть А будет ложным, а B – истинным. Новое высказывание будет истинным. Так как высказывание B – истинно.

Теперь сделаем наоборот, пусть А – истинно, B – ложно. И снова новое высказывание будет истинным.

А если высказывания А и B будут истинными, то новое высказывание снова будет истинно. Так как в определение сказано, что новое высказывание будет ложно тогда и только тогда, когда ложны исходные высказывания.

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

То есть лампочка загорится в том случае если будет включён (замкнут), хотя бы один выключатель.

Дизъюнкцию ещё называют логическим сложением.

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

И последняя логическая операция, которую мы с вами рассмотрим – это инверсия.

Здесь всё очень просто. Если исходное высказывание было истинно, то после инверсии оно становится ложным, а если исходное высказывание было ложным, то после операции инверсии оно становится истинным.

Давайте посмотрим, как обозначается инверсия в различных сферах её применения.

Нам осталось составить таблицу истинности для инверсии. Нам дано исходно высказывание А. Его значения будем записывать в первый столбик таблицы. А вот значение высказывания, которое получается после инверсии, будем записывать во второй столбик.

Итак, если наше высказывание А ложно, то новое высказывание будет истинно.

А если А – истинно, то новое высказывание после инверсии будет ложно.

Инверсию также называют логическим отрицанием.

Также любое сложное высказывание можно записать в виде логического выражения.

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

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

А сейчас изобразим графически множества точек, для которых истины вышеприведённые выражения. Первое: НЕ А. То есть будет закрашено всё пространство, кроме круга А.

Во втором случае, А V B, будут закрашены два круга А и B.

А в третьем – всё пространство, кроме кругов А и B.

Данные изображения помогут нам решить задачу.

Это все точки, кроме тех, которые входят в круг А.

Второе: А V B. Смотрим на графическое представления для этого выражения.

Это все точки, которые входят в круги А и B. Для того, чтобы найти количество точек, давайте те точки, которые входят только в круг А обозначим буквой x, а которые входят только в B – буквой y. А точки, которые входят и в А и в Бэ обозначим буквой z. В круг А входят 190 точек, но в них есть точки z, которые входят и в А и в B.

Значит то наш x будет вычисляться следующим образом:

x = 190 – 70 = 120.

Аналогично и с кругом B, в который входят 230 точек.

y = 230 – 70 = 160.

Для того, чтобы вычислить точки, которые входят в А или B, нам нужно сделать следующее:

70 + 120 + 160 = 350.

То есть для 350 точек истинно выражения А V B.

Это все точки, которые не входят в круги А и B. Для их нахождения нужно:

Задача решена. И сейчас мы с вами подошли к подведению итогов урока.

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

Читайте также: