Презентация по информатике на тему: "Основы математической логики" (9 класс, информатика)

Основные понятия  математической логики Киркина Юлия Владимировна, Киркина Юлия Владимировна, учитель информатики и ИКТ ГБОУ СО «Школа­интернат АОП № 3 г.Энгельса», учитель информатики и ИКТ ГБОУ СО «Школа­интернат АОП № 3 г.Энгельса», старший преподаватель ГАУ ДПО «СОИРО» старший преподаватель ГАУ ДПО «СОИРО»

Понятие об алгебре высказываний Алгебра логики – это математический аппарат, с помощью которого  записывают, вычисляют, упрощают и  преобразовывают логические высказывания.   Создателем алгебры логики является живший в ХIХ веке  английский математик Джордж Буль, в честь которого  эта алгебра названа булевой алгеброй высказываний.  Логическое высказывание – это любое повествовательное  предложение, в отношении которого можно однозначно  сказать, истинно оно или ложно. Пример: «6 – четное число»                 «Рим – столица Франции»   «Красота!»

Логические высказывания.  Обозначения высказываний. простые высказывания  (элементарные) А — “Тимур поедет летом на море”  В — “Тимур летом отправится в горы” Составные высказывания строятся из простых с помощью логических  связок (операций) "и", "или", "не", "если … то", "тогда и только тогда" и др. “Тимур летом побывает и на море, и в горах” A и B  A или не B если A, то B не A и B A тогда и только тогда, когда B простые высказывания (элементарные)

Основные логические операции: «НЕ» (NOT) «И» (AND) Инверсия «ИЛИ» (OR) Дизъюнкция Логическое сложение Логическое отрицание F = A F = ¬ A AA 00 11 FF 11 00 Конъюнкция  Логическое умножение   F = A  B  F = A & B F = A ∙ B F = A  B F = A + B AA 00 00 11 11 BB 00 11 00 11 FF 00 00 00 11 AA 00 00 11 11 BB 00 11 00 11 FF 00 11 11 11

Логические операции: Импликация Эквивалентность A  , AB  B A  , AB    BAB A BABA AA 00 00 11 11  FF 11 11 00 11 BB 00 11 00 11 AA 00 00 11 11 BB 00 11 00 11   B AB   FF 11 00 00 11

«Исключающее ИЛИ» (XOR) F = AF = A    BB AA    BB  BABABA BB 00 11 00 11 00 11 11 00 арифметическое  сложение, 1+1=2 остаток AA 00 00 11 11 Сложение по модулю 2:  A  B = (A + B) mod 2

Штрих Шеффера Стрелка Пирса  (штрих Лукасевича) “НЕ И” (отрицанию конъюнкции) “НЕ ИЛИ” (отрицанию дизъюнкции) | BAF | BABA AA FF 11 00 00 11 11 11 00 11 BB 00 11 00 11  BAF  BABA AA FF 00 11 00 00 11 00 11 00 BB 00 11 00 11

Логические операции: Приоритеты при выполнении логических операций: ­ отрицания (“не”),  ­ конъюнкция (“и”), ­ дизъюнкция (“или”), ­ импликация и эквивалентность  , 2 1 Пример: F = не а и b или с или d F = не а и b или (с или d) 1 2 4 3 3 4

A A A Диаграммы Вена (круги Эйлера) B A+B B A∙B A A B A A B AB AB AB B 99

Законы алгебры логики название для И для ИЛИ двойного отрицания AA  исключения  третьего операции с  константами повторения поглощения переместительный сочетательный распределительный правила де Моргана 0AA   A1A0, 0A   1AA  11AA, 0A  AAA  ( AA B)  ABBA A C)BA ACBA (  CB)A ( (   AB) C) ( BABA   AAA  ABAA  ABBA   BA C) A CB) ( ( BA CABAC)  BABA  (

Упрощение логических выражений 1. Заменить операции  на их выражения через  И, ИЛИ и НЕ:  BABABA  BAB A  BABAB A 2. Раскрыть инверсию сложных выражений по  формулам де Моргана:  BABA,BABA  3. Используя законы логики, упрощать выражение,  стараясь применять закон исключения третьего.

Упрощение логических выражений (BF  (AA) B)  B( (AA)  B)  B(  BAA)  B)AAAB(  BAB BB A BA  раскрыли  формула де Моргана исключения третьего переместительны й повторения раскрыли формула де Морганаисключения третьегоповторенияпереместительный

ДНФ, СДНФ ДНФ, СДНФ Простая конъюнкция – конъюнкция одной или нескольких переменных,  при  этом  каждая  переменная  встречается  не  более  одного  раза  (либо  сама, либо ее отрицание).  cba  bcacab  Дизъюнктивная нормальная форма (ДНФ) – дизъюнкция простых  конъюнкций. ba  Совершенная дизъюнктивная нормальная форма (СДНФ) – ДНФ, у  которой в каждую конъюнкцию входят все переменные данного списка  (либо сами, либо их отрицания), причем в одном и том же порядке. cba  bc  a

КНФ, СКНФ КНФ, СКНФ Простая дизъюнкция – дизъюнкция одной или нескольких переменных,  при  этом  каждая  переменная  встречается  не  более  одного  раза  (либо  сама, либо ее отрицание).   cba Конъюнктивная нормальная форма (КНФ) – конъюнкция простых  дизъюнкций.  baba    Совершенная  конъюнктивная  нормальная  форма  (СКНФ)  –  КНФ,  у  которой в каждую дизъюнкцию входят все переменные данного списка  (либо сами, либо их отрицания), причем в одном и том же порядке.   acbcba   

Алгоритм построения СДНФ  Алгоритм построения СДНФ  по таблице истинности по таблице истинности 1. Выбрать все строки таблицы, в которых функция  принимает значение 1. 2. Каждой такой строке поставить в соответствие  конъюнкцию всех аргументов или их инверсий. При  этом аргумент, принимающий значение 0, входит в  функцию с отрицанием, а значение 1 – без отрицания. 3. Наконец, образуем дизъюнкцию всех полученных  конъюнкций.

Алгоритм построения СКНФ  Алгоритм построения СКНФ  по таблице истинности по таблице истинности 1. Выбрать все строки таблицы, в которых функция  принимает значение 0. 2. Каждой такой строке поставить в соответствие  дизъюнкцию всех аргументов или их инверсий. При  этом аргумент, принимающий значение 0, входит в  функцию с отрицанием, а значение 1 – без отрицания. 3. Наконец, образуем конъюнкцию всех полученных  дизъюнкций.

Логические схемы: Логический  элемент  компьютера  —  это  часть  электронной  логической  схемы,  которая  реализует  элементарную  логическую  функцию. ! Логическими  элементами  компьютеров  являются  электронные  схемы  И,  ИЛИ, НЕ, И­НЕ, ИЛИ­НЕ и другие (называемые также вентилями).  Чтобы представить два логических состояния — “1” и “0” в  вентилях, соответствующие им входные и выходные сигналы имеют  один из двух установленных уровней напряжения. Например, +5  вольт и 0 вольт.

Переключательные схемы: х y х y

Логические элементы:

Составление схем  CBABAF A B A B & & BA   CBA 1 F BA  C & A B C

Триггер (англ. trigger – защёлка) ­ это логическая схема, способная хранить 1 бит  информации (1 или 0).  Строится на 2­х элементах ИЛИ­НЕ или на 2­х элементах  И­НЕ. set, установка S 1 вспомогательный  выход Q S R Q Q 00 00 00 11 0 1 11 00 11 11 0 Q Q 1 0 0 режим хранение хранение сброс установка запрещен обратные связи Q основной  выход 1 R reset, сброс

Полусумматор Полусумматор – это логическая схема, способная  складывать два одноразрядных двоичных числа. ΣA B S P сумма перенос  BAP  BABABAS A B B A BA  BA  BA  AA BB 00 00 00 11 00 11 11 11 SS PP 0         0 0         1 0         1 1         0  BABAS P

Сумматор Сумматор – это логическая схема, способная  складывать два одноразрядных двоичных числа с  переносом из предыдущего разряда. ΣA B C перенос S P сумма перенос AA 00 00 00 00 11 11 11 11 BB CC 00 00 00 11 00 11 11 11 00 00 11 00 00 11 11 11 PP 00 00 00 11 00 11 11 11 SS 00 11 11 00 11 00 00 11

Постройте таблицу истинности для  данного логического выражения  yx y x x

Алгоритм построения таблицы  истинности логической функции 1. Вычислить количество строк и столбцов  (n­ количество логических переменных) Кол­во строк: Str = 2n + заголовок Кол­во столбцов: Stb = кол­во переменных +кол­во операций 3 2 4 x x y 5 1  yx 2 n = 5 Str = 2+5=7 Stb =

2. Начертить таблицу и заполнить заголовок: имена переменных по алфавиту, промежуточные формулы в  соответствии с приоритетом y xy x+y ┐(x+y) xy + ┐(x+y) xy + ┐(x+y) + x

3. Заполнить первые столбцы значениями переменных: xy x+y ┐(x+y) xy + ┐(x+y) xy + ┐(x+y) + x x 0 0 1 1 y 0 1 0 1

4. Заполнить остальные столбцы в соответствии с таблицами  истинности логических операций x 0 0 1 1 y 0 1 0 1 xy 0 0 0 1 x+y 0 1 1 1 ┐(x+y) xy + ┐(x+y) xy + ┐(x+y) + x 1 0 0 0 1 0 0 1 1 0 1 1

Минимизируйте логическую схему 1x 1x 2x 2x 3x 3x

Алгоритм решения данных упражнений 1. Записать данную схему с помощью логических переменных  и операций  x 1  x 2    x 1 x 3    x 2 3 x

2. Упростить данное логическое выражение    x x 2 3     xx xx x x 21 3 32    xxx xx xxx 21 31 32 2  xxx ( )1 31 2 2 2 2     x x x x 1 3 1     xx xx 31 11    xxx xx 321 21    1( x ) xx 3 21    xx xx 31 21   x ) ( xx 3 1 2  xxx 31 3  xxx 21 3  xxx 32 3  

3. Представить полученное логическое выражение в виде  физической схемы: 1x 2х 3х

Требуется найти все решения  уравнения:    ACB    0 DCA  

Вариант I:  Импликация равна нулю только тогда, когда первое выражение  равно 1, а второе — 0. ACB 1     ACBACB 1   0 DСA формула де  Моргана СA  ,0  0 D A A  1 C ,1 ,1 B  ,1 В ,0 С  0 Ответ  0,0,0,1: формула де Моргана

Вариант  II — упростить выражение.   ACB  DCA ACB          DCA        ACB      DCAACBDCA   0 DACB Ответ 0,0,0,1: 

Вариант III — построить таблицу истинности логического  выражения в левой части и найти все варианты, при которых оно  равно 0.  Однако таблица истинности логического выражения с четырьмя  переменными содержит 24 = 16 строк, поэтому такой подход  достаточно трудоемок. Ответ  0,0,0,1:

Решение логических  содержательных задач  различными методами

Как решать логические задачи? Разнообразие логических задач очень велико.  Способов их решения тоже немало. Но наибольшее  распространение получили следующие три способа  решения логических задач:   средствами алгебры логики;   табличный;   с помощью рассуждений.

I. Решение логических задач средствами алгебры логики Обычно используется следующая схема решения:   изучается условие задачи;   вводится система обозначений для логических  высказываний;   конструируется логическая формула, описывающая  логические связи между всеми высказываниями условия  задачи;  определяются значения истинности этой логической  формулы;  из полученных значений истинности формулы определяются  значения истинности введённых логических высказываний, на  основании которых делается заключение о решении.

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

Решение логических задач  средствами алгебры логики На олимпиаде по информатике студенты  A, B, C и D заняли первые четыре места.  Когда их спросили о распределении  мест, они дали три ответа: D – первый  или B – второй; C – первый или A –  четвертый; D – второй или B – третий.  Как распределились места, если в  каждом ответе только одно утверждение  истинно?

 D – первый или B – второй: D1B2=1  C – первый или A – четвертый: C1A4=1  D – второй или B – третий: D2B3=1 (D1B2)(C1A4)(D2B3)=1 (D1C1B2C1D1A4B2A4)(D2B3)=1 B2C1D2D1A4D2B2A4D2B2C1B3D1A4B3B2A4B3=1 D1A4B3=1 Следовательно, D – первый, С – второй,  B – третий, A – четвертый.

Решение логических задач  табличным способом В симфонический оркестр приняли на работу трёх музыкантов:  Брауна, Смита и Вессона, умеющих играть на скрипке, флейте,  альте, кларнете, гобое и трубе.  Известно, что:  Смит самый высокий;  играющий на скрипке меньше ростом играющего на флейте;  играющие на скрипке и флейте и Браун любят пиццу;  когда между альтистом и трубачом возникает ссора, Смит  мирит их;  Браун не умеет играть ни на трубе, ни на гобое.  На каких инструментах играет каждый из музыкантов, если  каждый владеет двумя инструментами?

скрипка флейта альт кларнет гобой труба Браун Смит ­ ­ Вессон + + ­ ­ ­ + ­ ­ + ­ + ­ ­ ­ ­ +

Решение логических задач  с помощью рассуждений Антон, Борис, Вадим, Дима и Гриша познакомились с  девушкой. Они предложили ей отгадать их фамилии,  причем каждый высказал одно истинное и одно ложное  утверждение. Дима: «Моя фамилия  ­ Мишин, а Бориса ­ Хохлов». Антон: «Мишин – это моя фамилия, а Вадима ­ Белкин». Борис: «Фамилия Вадима – Тихонов, а моя ­ Мишин». Вадим: «Моя фамилия – Белкин, а Гриши ­ Чехов». Гриша: «Моя фамилия – Чехов, а Антона ­ Тихонов». У кого какая фамилия?

Пусть Дима Мишин – истинно, тогда Антон Мишин,  Борис Мишин – ложно.  Если Антон Мишин, Борис Мишин – ложно, то  Вадим Белкин, Вадим Тихонов должны быть  истинны, но они не могут быть одновременно  истинными. Значит, Борис Хохлов – истинно.  Борис Хохлов = 1, Борис Мишин = 0, Вадим  Тихонов = 1, Антон Тихонов = 0, Гриша Чехов = 1,  Вадим Белкин = 0, Антон Мишин = 1. Ответ:  Борис Хохлов, Вадим Тихонов, Гриша  Чехов, Антон Мишин, Дима Белкин.

Алгоритм решения задач на приведение  множеств во взаимно­однозначное  соответствие 1. 2. 3. 4. 5. 6. Строится пространственная система координат XYZ, на осях  проставляются названия множеств и элементы этих множеств. Читается условие задачи. Если пара элементов в двух  множествах находится в соответствии, то точка, лежащая на  пересечении соответствующих прямых становится центром  темного кружка, в противном случае – белого кружка. Применяется правило экстраполяции. Применяется правило проектирования. Повторять шаги 3)­4) пока это возможно. Если в сложившейся ситуации возможности экстраполяции и  проектирования исчерпаны, а задача не решена, то делается  допущение о цвете фигуры в какой­либо свободной вершине  сетки. В случае противоречия допущение отклоняется цвет  фигуры в данной точке меняется на противоположный.

После традиционного вечера встречи с выпускниками  школы в стенгазете появилась заметка о трех наших  бывших учениках. В ней было сказано, что Иван, Андрей и  Борис стали учителями. Теперь они преподают разные  дисциплины: один из них – математику, второй – физику, а  третий – химию. Живут они тоже в разных городах: Минске,  Витебске, Харькове. В заметке было также написано, что  их первоначальные планы осуществились не полностью: – Иван живет не в Минске. – Андрей – не в Витебске. – Житель Минска преподает не математику. – Андрей преподает не физику. – Повезло только жителю Витебска: он преподает  любимую им химию. Можно ли по этим данным определить, кто где живет и что  преподает?

Правила экстраполяции в  плоскости • «Темная» экстраполяция. Если на горизонтали  (вертикали) все фигуры, кроме одной, светлы, то  свободная занимается темной фигурой. • «Светлая» экстраполяция. Если на горизонтали  (вертикали) имеется «темная» фигура, то все  фигуры на ней – светлые. • Множественная экстраполяция. Если две (n)  параллели в плоскости одинаково светло  раскрашены везде за исключением двух (n)  неокрашенных вершин, то на двух (n) параллелях  другого направления, проходящих через эти  вершины вне данных прямых вставляются светлые  фигуры.

Правило множественного  проектирования «Темная» фигура в своей плоскости  проектируется на координатные оси.  Прямые, проведенные через проекции в  двух других плоскостях, раскрашиваются  одинаково.

Предмет Ф Х М М В Х Город И А Б Имена

Ответ: • Иван преподает химию и живет в  Витебске. • Андрей преподает математику и живет  в Харькове. • Борис преподает физику и живет в  Минске.

Литература: 1. Журнал «Информатика» // №12 / 2010 Ресурсы сети Интернет: 1. http://window.edu.ru/resource/847/54847/files/log.pdf Е.Е. Лапшева,  «Элементы математической логики». 2. http://www.ido.rudn.ru/nfpk/inf/inf7.html Основы математической  логики. Проект «Информатизация системы образования». 3. http://umk.portal.kemsu.ru/uch­mathematics/papers/posobie/r3­1.htm#t op   Основы математической логики.