Сообщение на тему булева алгебра

Обновлено: 17.05.2024

sanit 27.03.2006 19:30 Ответить

Да уж! В 1949 г. журнал популярная механика опубликовал прогноз:
В будующем компьютеры могут весить не более полутора тонн.
:)))

WaLLik sanit 30.07.2007 21:45 Ответить

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

Anastasija 18.04.2009 09:46 Ответить

Отличная статья. Можно я помещу её на своём сайте http://fizikadetiam.ucoz.com/index/ ? У меня там есть глава "Для умников и умниц". Есть ведь ещё пока интересующиеся дети. Спасибо. Анастасия

samara 28.12.2010 17:32 Ответить

под квантовыми компьютерами понимают совсем не счёт на основе целых молекул, а счёт на основе квантовой неопределённости кубитов и "запутаности" обьектов-ячеек.
имхо: а будуещее за системами с недвоичным счётом (4/8/10/16 градаций сигнала например)

vp_lisin 13.02.2011 19:49 Ответить

Замечание на фразу:
"Качественное изменение ЭВМ произошло после еще одного эпохального открытия физики — изобретения в 1947 году Джоном Бардином, Уолтером Браттейном и Уильямом Шокли полевого транзистора."
-- Они изготовили не полевой, а биполярный транзистор. Первый полевой
был изготовлен в 1960 г., хотя запатентован лет на 25-30 раньше.

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

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

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

МИНИСТЕРСТВО ЗДРАВООХРАНЕНИЯ РЕСПУБЛИКИ КАЗАХСТАН

ЮЖНО-КАЗАХСТАНСКАЯ ГОСУДАРСТВЕННАЯ ФАРМАЦВТИЧЕСКАЯ АКАДЕМИЯ

Кафедра медицинской биофизики, информатики и математики

Тема: Булева алгебра

История Булева алгебра

Понятие Булева алгебра

Дизъюнктивная нормальная форма и совершенная дизъюнктивная нормальная форма

Конъюнктивная нормальная форма и совершенная конъюнктивная нормальная форма

Введение

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

История Булева алгебра

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

Формулы векторной алгебры во многом отличны от формул элементарной алгебры. Например, и в элементарной алгебре и в векторной имеется операция сложения. Но выполняется она совершенно по-разному. Сложение чисел выполняется совсем не так, как сложение векторов.

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

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

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

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

Понятие Булева алгебра

Дизъюнктивная нормальная форма и совершенная дизъюнктивная нормальная форма

Элементарной конъюнкцией n переменных называется конъюнкция переменных или их отрицаний.

Дизъюнктивной нормальной формой (ДНФ) формулы А называется равносильная ей формула, представляющая собой дизъюнкцию элементарных конъюнкций.

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

Например, для формулы А = х (х y) имеем:

А = х ( х y) = (х х) (х y) = х y, то есть

ДНФ А = (х х) (х y) и

Среди многочисленных ДНФ А существует единственная ДНФ А, для которой выполняются перечисленные выше четыре свойства совершенства. Такая ДНФ А называется совершенной дизъюнктивной нормальной формой формулы А (СДНФ А).

Как уже указывалось, СДНФ А может быть получена с помощью таблицы истинности.

Другой способ получения СДНФ формулы А основан на равносильных преобразованиях формулы и состоит в следующем:

путем равносильных преобразований формулы А получают одну из ДНФ А.

если в полученной ДНФ А входящая в нее элементарная конъюнкция В не содержит переменную xi, то, используя закон B (xi xi) = B, элементарную конъюнкцию B заменяют на две элементарных конъюнкции (B xi) и (B xi), каждая из которых содержит переменную xi.

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

если некоторая элементарная конъюнкция В, входящая в ДНФ А, содержит переменную xi и ее отрицание xi, то, на основании закона xi xi = 0, В = 0 и В, таким образом, можно исключить из ДНФ А, как нулевой член дизъюнкции.

если некоторая элементарная конъюнкция, входящая в ДНФ А, содержит переменную xi дважды, то одну переменную можно отбросить, пользуясь законом xi xi = xi.

Ясно, что после выполнения описанной процедуры будет получена СДНФ А. Например, для формулы А = x y (x y) ДНФ А = x (x y) (y y). Так как элементарная конъюнкция В = х, входящая в ДНФ А, не содержит переменной у, то заменим ее на две элементарных конъюнкции (x y) и (x y), В результате получим ДНФ А = x y x y x y y y.

Так как теперь ДНФ А содержит две одинаковых элементарных конъюнкции x y, то отбросим лишнюю. В результате получим ДНФ A = x y x y y y.

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

Таким образом, получаем СДНФ А = x y x y.

Конъюнктивная нормальная форма и совершенная конъюнктивная нормальная форма

Элементарной дизъюнкцией п переменных называется дизъюнкция переменных или их отрицаний.

Конъюнктивной нормальной формой (КНФ) формулы А называется равносильная ей формула, представляющая собой конъюнкцию элементарных дизъюнкций.

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

Например, для формулы А = (х у) х у имеем:

А = ( (х у) х у) (х у (х у)) =

= (х у х у) ( (х у) (х у)) =

= (х х у) (х у у) ( х у х) ( х у у) , то есть

КНФ А = (х х у) (х у у) ( х у х) ( х у у).

Но так как х х = х, у у = у, х х = х, у у = у, то

КНФ A = (х у) (х у) ( х у) ( х у).

А так как (х у) (х у) = х у, ( х у) ( х у) = ( х у), то

КНФ A = (х у) ( х у).

булева алгебра математическая логика

КНФ А называется совершенной конъюнктивной нормальной формой формулы А (СКНФ А), если для нее выполнены условия:

Все элементарные дизъюнкции, входящие в КНФ А , различны.

Все элементарные дизъюнкции, входящие в КНФ А, содержат все переменные.

Каждая элементарная дизъюнкция, входящая в КНФ А, не содержит двух одинаковых переменных.

Каждая элементарная дизъюнкция, входящая в КНФ А, не содержит переменную и ее отрицание.

Можно доказать, что каждая не тождественно истинная формула имеет единственную СКНФ.

Один из способов получения СКНФ состоит в использовании таблицы истинности для формулы А. Действительно, получив с помощью таблицы истинности СДНФ А, мы получим СКНФ А, взяв отрицание (СДНФ А), то есть СКНФ А = (СДНФ А).

Другой способ получения СКНФ, использующий равносильные преобразования, состоит в следующем:

Путем равносильных преобразований формулы А получают одну из КНФ А.

Если в полученной КНФ А входящая в нее элементарная дизъюнкция В не содержит переменную хi, то, используя закон В (xi xi) = В, элементарную дизъюнкцию В заменяют на две элементарные дизъюнкции В xi и В xi, каждая из которых содержит переменную xi.

Если в КНФ А входят две одинаковых элементарных дизъюнкции В, то лишнюю можно отбросить, пользуясь законом В В = В.

Если некоторая элементарная дизъюнкция, входящая в КНФ А, содержит переменную xi дважды, то лишнюю можно отбросить, пользуясь законом xi xi = xi.

Если некоторая элементарная дизъюнкция, входящая в КНФ А, содержит переменную xi, и ее отрицание, то xi xi = 1 и, следовательно, вся элементарная дизъюнкция имеет значение 1, а поэтому ее можно отбросить, как истинный член конъюнкции.

Ясно, что после описанной процедуры будет получена СКНФ А. Например, для формулы А = x y (x y) КНФ А = x (y (x y)) = (x y) (x x y). Так как обе элементарные дизъюнкции содержат все переменные (x и y), то первое и второе условие СКНФ выполнены. Элементарная дизъюнкция x x y содержит переменную х дважды, но x x = x, поэтому КНФ А = (x y) (x y); причем, ни одна из элементарных дизъюнкций не содержит переменную и ее отрицание. Значит, все условия СКНФ выполнены, и, следовательно, СКНФ А = (x y) (x y).

Заключение

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

Список литературы

1. Малая математическая энциклопедия. Э. Фрид., И. Пастор., И. Рейман., П. Ревес., И. Ружа. Издательсво академии наук Венгрии. Будапешт 1976 г.

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

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

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

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

лабораторная работа [83,6 K], добавлен 26.11.2011

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

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

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

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

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

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

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

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

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

Для учеников 1-11 классов и дошкольников
Бесплатные сертификаты учителям и участникам

I . Основные понятия. 4

1.1 Операции над логическими высказываниями. 4

1.2 Выражение одних булевых функций через другие. 12

1.3. Основные законы логики высказываний. 13

II . Разработка факультативного курса по теме "Булева алгебра" для учащихся 9 классов средней школы. 14

2.1 Цели и задачи факультативного курса. 14

2.2 Содержание факультативного курса. 15

2.3 Примерный перечень вопросов к зачёту. 16

Список литературы. 18

Список литературы. 20

Целью данной курсовой работы является изучение булевой алгебры и разработка факультативного курса "Булева алгебра" для учащихся 9-х классов средней школы.

Задачами данной курсовой работы являются:

- изучение основных понятий, связанных с булевой алгеброй;

- разработка факультативного курса по заданной теме;

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

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

Объектом исследования курсовой работы является булева алгебра.

I . Основные понятия

1.1 Операции над логическими высказываниями

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

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

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

1. Закон тождества: каждый из предметов, о которых идет речь, все время должен оставаться самим собой. Это требование совершенно необходимо, так как в противном случае изменчивость предмета привела бы к тому, что уже в ходе самого рассуждения истинные высказывания становились бы ложными, вследствие чего из этих высказываний нельзя было бы извлечь никакой надежной информации.

2. Закон противоречия: одно и то же нельзя одновременно и утверждать, и отрицать. Это требование тоже совершенно необходимо. В самом деле: если в высказывании что-то одновременно и утверждается, и отрицается, то это высказывание по существу никакой информации не несет.

3. Закон исключенного третьего: каждое высказывание непременно должно быть либо истинным, либо ложным. Это требование основано на убеждении, что относительно любого осмысленного высказывания всегда может быть установлено, истинно оно или ложно. А значит, что третьего не дано[2].

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

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

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

Каждая логическая связка рассматривается как операция над логическими высказываниями (булева функция) и имеет свое название и обозначение[8].

Высказывание истинно, когда оба высказывания истинны. Высказывание ложно, когда:

Содержание

Определение

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

Булева алгебра как предметная область определяется следующими критериями:

Непустое множество А.
Бинарные операции Конъюнкция(ʌ) и Дизъюнкция ( v)
Унарная операция отрицания (¬ или не)
Логические константы Истина (1) и Ложь (0)

Происхождение

В этой книге Буль изложил большую часть новой алгебры, особенно пригодную для анализа классов и предложений (высказываний).

Другие математики и логики, в том числе Джон Венн и Эрнст Шрёдер, впоследствии значительно усовершенствовали и расширили алгебру Буля.

Аксиомы

1) Булева переменная всегда равна либо нулю, либо единице

2) Инверсное значение переменной x противоположно ее прямому значению

3) Правила выполнения логического умножения (конъюнкции)

4) Правила выполнения логического сложения (дизъюнкции)

Законы

1) Ассоциативный (сочетательный) закон

Ассоциативность конъюнкции и дизъюнкции выражается следующими формулами:

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

2) Коммутативный (переместительный) закон Правила

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

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

Обозначение на логических схемах

Для обозначения логических элементов используется несколько стандартов. Наиболее распространёнными являются американский (ANSI), европейский (DIN), международный (IEC) и российский (ГОСТ). На рисунке ниже приведены обозначения логических элементов в этих стандартах.

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