Алгебра Логики Москалева Светлана. История предмета Алгебра логики возникла в середине ХIХ века в трудах английского математика Джорджа Буля. Ее создание. - презентация

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

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

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

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

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

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

7 Таблицы истинности AB A v B ИСТИНАИСТИНАЛОЖЬЛОЖЬИСТИНАЛОЖЬИСТИНАЛОЖЬИСТИНАИСТИНАИСТИНАЛОЖЬAB A & B ИСТИНАИСТИНАЛОЖЬЛОЖЬИСТИНАЛОЖЬИСТИНАЛОЖЬИСТИНАЛОЖЬЛОЖЬЛОЖЬ Конъюнкция (И) Дизъюнкция (ИЛИ)

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

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

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

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

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

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

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

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

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

17 Упростим (X1 & X2 & (~X3)) v (X1 & (~X2) & X3) v (X1 & X2 & X3) = (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)

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

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

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