'

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

Понравилась презентация – покажи это...





Слайд 0

Алгебра Логики Москалева Светлана


Слайд 1

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


Слайд 2

История алгебры логики Понятие логики как науки появилось ещё в XIX в., т.е. задолго до появления науки информатики и компьютеров. Элементы математической логики можно найти уже в работах древнегреческих философов. В XVII в. Г. В. Лейбниц высказал идею о том, что рассуждения могут быть сведены к механическому выполнению определенных действий по установленным правилам. Однако как самостоятельный раздел математики логика начала формироваться только с середины XIX в.. Для того чтобы рассуждать, человеку необходим какой-либо язык. Не удивительно, что математическая логика начиналась с анализа того, как говорят и пишут люди на естественных языках. Этот анализ привёл к тому, что выяснилось существование формулировок, которые невозможно разделить на истинные и ложные, но, тем не менее, выглядят осмысленным образом. Это приводило к возникновению парадоксов, в том числе в одной из фундаментальных наук математики. Тогда было решено создать искусственные формальные языки, лишённого «вольностей» языка естественного.


Слайд 3

НАЧАЛА Логическое высказывание — это любoе повествовательное пpедлoжение, в oтнoшении кoтopoгo мoжно oднoзначнo сказать, истиннo oнo или лoжнo. Разумеется, не всякое предложение является логическим высказыванием. Высказываниями не являются, например, предложения "ученик десятого класса" и "информатика — интересный предмет". Первое предложение ничего не утверждает об ученике, а второе использует слишком неопределённое понятие "интересный предмет". Вопросительные и восклицательные предложения также не являются высказываниями, поскольку говорить об их истинности или ложности не имеет смысла.


Слайд 4

Булевы функции Пусть имеется некоторый набор высказываний, о которых можно говорить определённо, что они истинные или ложные. Обозначим их латинскими буквами A, B, C, D … . Если у нас есть два простых предложения, то из них образовать новое, сложносочинённое предложение с помощью союзов «или» либо «и». В математической логике для этой цели используются специальные символы: знак дизъюнкции v знак конъюнкции & (иногда используется ^) Знак NOT – знак отрицания


Слайд 5

Утверждение A v B считается истинным тогда и только тогда, когда истинно хотя бы одно из исходных утверждений; утверждение A & B – когда истинны оба утверждения.


Слайд 6

Таблицы истинности Конъюнкция (И) Дизъюнкция (ИЛИ)


Слайд 7

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


Слайд 8

Было выяснено, что умножение и логическое «И» обладают сходными свойствами - от перестановки мест аргументов результат не изменяется A & B = B & A - существует следующий закон A & (B & C) = (A & B) & C


Слайд 9

Существуют некоторые тождества, опирающиеся на особые свойства функции, например: A & (~A) = ЛОЖЬ (~A) & (~B) = ~ (A v B)


Слайд 10

Сложение и логическое «ИЛИ»: - от перестановки мест аргументов результат не изменяется A v B = B v A - существует следующий закон (A v B) v С = A v (B v C) - можно выносить общий множитель за скобки (A & B) v (С & B) = B & (A v C)


Слайд 11

Некоторые собственные законы сложения: A v (~A) = ИСТИНА (~A) v (~B) = ~ (A & B)


Слайд 12

Нахождение исходного выражения по его значениям. В отличие от алгебраических выражений, булевы можно восстановить, зная их аргументы и соответственные им значения. Пусть нам дана булева функция от 3 переменных: Составим для неё таблицу и условимся обозначать ИСТИНУ - 1, а ЛОЖЬ – 0.


Слайд 13

Для начала выпишем все аргументы функции, при которых функция равна 1. F (1, 1, 0) = 1 F (1, 0, 1) = 1 F (1, 1, 1) = 1


Слайд 14

Теперь запишем 3 таких выражения (функция принимает значение 1 три раза), что они принимают значение 1 только при вышеуказанных значениях X1 & X2 & (~X3) X1 & (~X2) & X3 X1 & X2 & X3


Слайд 15

И запишем их логическую сумму: (X1 & X2 & (~X3)) v (X1 & (~X2) & X3) v (X1 & X2 & X3) – это выражение принимает значение 1 при тех же значениях, что и исходная функция. Полученное выражение можно упростить.


Слайд 16

Упростим (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)


Слайд 17

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


Слайд 18

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


Слайд 19

Источники дополнительных сведений 1. «Компьютер» Ю. Л. Кетков, изд. «Дрофа» 1997 г. 2. «Математика» Ю. Владимиров, изд. «Аванта+» 1998 г.


×

HTML:





Ссылка: