Алгебра логики

Возникновение логики. Элементы математической логики. Операции над логическими функциями. Булевы функции. Преобразование выражений булевых функций. Нахождение исходного выражения по его значениям. Применение в вычислительной технике и информатике.

Рубрика Математика
Вид реферат
Язык русский
Дата добавления 14.07.2008
Размер файла 16,8 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Министерство науки УР

Средняя школа № 12

Реферат

Тема: Алгебра логики

Выполнили:

Ученики 10 класса «В»

Криницин Валерий

Урбанович Дмитрий

Проверил:

Р. Ф. Набиев

Сарапул, 2008 г.

Содержание

1. Введение

2. Алгебра логики

2.1. Возникновение логики

2.2. Булевы функции

2.3. Преобразование выражений, состоящих из булевых функций

2.4. Нахождение исходного выражения по его значениям

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

3. Заключение

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

F

0

1

0

1

0

1

0

1

0

0

1

1

0

0

1

1

0

0

0

0

1

1

1

1

0

0

0

1

0

1

0

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) v X2)) =

= X1 & ((X2 & (~X3)) v X3) - эта формула несколько длиннее исходной, но намного проще полученной в первый раз. Дальнейшие пути упрощения более сложны и представляют большой интерес для проектировщиков интегральных микросхем, т.к. меньшее число операций требует меньшее число элементов, их которых состоит ИС.

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

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

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

3. Заключение.

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

Список используемой литературы.

1. «Компьютер» Ю. Л. Кетков, изд. «Дрофа» 1997 г.

2. «Математика» Ю. Владимиров, изд. «Аванта+» 1998 г.


Подобные документы

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

    контрольная работа [83,3 K], добавлен 26.04.2011

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

    реферат [63,3 K], добавлен 06.12.2010

  • Булевы алгебры – решетки особого типа, применяемые при исследовании логики (как логики человеческого мышления, так и цифровой компьютерной логики), а также переключательных схем. Минимальные формы булевых многочленов. Теоремы абстрактной булевой алгебры.

    курсовая работа [64,7 K], добавлен 12.05.2009

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

    контрольная работа [50,4 K], добавлен 10.10.2014

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

    презентация [67,8 K], добавлен 23.12.2012

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

    контрольная работа [345,3 K], добавлен 29.11.2010

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

    учебное пособие [702,6 K], добавлен 29.04.2009

  • Логика - наука о законах и формах мышления, а основное понятие алгебры логики - высказывание. Основные понятия и тождества булевой алгебры. Изучение методов минимизации булевых функций. Метод Квайна, основанный на применении двух основных соотношений.

    контрольная работа [178,2 K], добавлен 20.01.2011

  • Основные определения математической логики, булевы и эквивалентные функции. Общие понятия булевой алгебры. Алгебра Жегалкина: высказывания и предикаты. Определение формальной теории. Элементы теории алгоритмов, рекурсивные функции, машина Тьюринга.

    курс лекций [651,0 K], добавлен 08.08.2011

  • Алгебра логики, булева алгебра. Алгебра Жегалкина, педикаты и логические операции над ними. Термины и понятия формальных теорий, теорема о дедукции, автоматическое доказательство теорем. Элементы теории алгоритмов, алгоритмически неразрешимые задачи.

    курс лекций [652,4 K], добавлен 29.11.2009

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.