Описание презентации по отдельным слайдам:

• 

  1 слайд

  Основы логики
  и
  Логические основы компьютера
  МБОУ «Средняя общеобразовательная школа №25»
  Учитель информатики и ИКТ
  Смирнова Елена Александровна
  
  

• 

  2 слайд

  Содержание
  Введение
  Этапы развития логики
  Алгебра логики
  Основные понятия логики
  Основные логические операции
  Логическая формула
  Как упростить логическую формулу?
  Таблицы истинности
  Способы решения логических задач
  Переключательные схемы
  

• 

  3 слайд

  Введение
  Термин «логика» происходит от древнегреческого logos – «слово, мысль, понятие, рассуждение, закон».
  Логика является одной из дисциплин, образующих математический фундамент информатики.
  В вычислительной технике и автоматике используются логические схемы – устройства, которые преобразуют двоичные сигналы.
  Анализ и проектирование логических схем опираются на законы алгебры логики.
  Любой язык программирования содержит логические переменные и средства для описания и вычисления логических выражений.
  Логические методы применяются и при работе с базами данных.
  

• 

  4 слайд

  Логика – это наука о законах и формах мышления. Она изучает абстрактное мышление как средство познания объективного мира.
  

• 

  5 слайд

  Этапы развития логики
  Первые учения о формах и способах рассуждений возникли в странах Дальнего Востока (Китай, Индия), но в основе современной логики лежат учения, созданные древнегреческими мыслителями. Основы формальной логики заложил Аристотель (384–322 гг. до н.э.), который впервые отделил логические формы речи от ее содержания.
  

• 

  6 слайд

  В XVII веке немецкий ученый и философ Готфрид Вильгельм Лейбниц (1646 – 1716) попытался построить первые логические исчисления, усовершенствовал и уточнил логические символы.
  Многие философы и математики развивали отдельные положения логики и иногда даже намечали контуры современного исчисления высказываний, но ближе всех к созданию математической логики подошел именно Лейбниц, указавший пути для перевода логики “из словесного царства, полного неопределенностей, в царство математики, где отношения между объектами или высказываниями определяются совершенно точно”. Лейбниц надеялся даже, что в будущем философы, вместо того чтобы бесплодно спорить, станут брать бумагу и вычислять, кто из них прав. При этом в своих работах Лейбниц затрагивал и двоичную систему счисления.
  

• 

  7 слайд

  На фундаменте, заложенном Лейбницем, другой великий математик, англичанин Джордж Буль (1815-1864) воздвиг здание новой области науки – математической логики.
  Начальный раздел математической логики называют алгеброй логики или Булевой алгеброй.
  Спустя 100 лет алгебра логики стала основой теории цифровых вычислительных машин, ее используют в компьютерной логике, электронике, в основе всех микропроцессорных операций.
  

• 

  8 слайд

  Алгебра логики
  С точки зрения устройства ЭВМ нас интересует алгебра логики, в которой не рассматривается конкретное содержание основного понятия логики – высказывания, а важно только истинно оно или ложно.
  Основным объектом в логике является высказывание.
  
  Высказывание – это повествовательное предложение,
  о котором можно сказать истинно оно или ложно.
  Высказывание называется простым,
  если никакая его часть сама
  не является высказыванием.
  Высказывание называется составным,
  если оно состоит из простых высказываний,
  соединенных логическими связками:
  И, ИЛИ, частицей НЕ, ЕСЛИ…, ТО
  «Петров – врач»,
  «Петров – шахматист».
  «Петров – врач и шахматист».
  

• 

  9 слайд

  Не всякое высказывание является логическим высказыванием!
  Высказываниями не являются:
  
  Например:
  
  «Ученик десятого класса»
  
  «Информатика – интересный предмет»
  
  Первое предложение ничего не утверждает об ученике, а второе использует слишком неопределённое понятие «интересный предмет».
  
  Вопросительные и восклицательные предложения также не являются высказываниями, т.к. говорить об их истинности или ложности не имеет смысла.
  
  
  
  

• 

  10 слайд

  Примеры:
  Москва – столица России
  Студент математического факультета педагогического университета
  Треугольник АВС подобен треугольнику А’В’С’
  Луна есть спутник Марса
  Кислород – газ
  Каша – вкусное блюдо
  Математика – интересный предмет
  Железо тяжелее свинца
  Треугольник называется равносторонним, если все его стороны равны
  Сегодня плохая погода
  Река Ангара впадает в озеро Байкал
  
  Какие из этих предложений являются высказываниями?
  Ответ: 1, 4, 5, 8, 9, 11
  

• 

  11 слайд

  Основные понятия логики:
  Утверждение – высказывание, которое требуется доказать или опровергнуть.
  Например: «Сумма внутренних углов треугольника равна 1800»
  Рассуждение – цепочка высказываний или утверждений, определенным образом связанных друг с другом.
  Например: «Если хотите начать работать на компьютере, то необходимо сначала включить электропитание»
  Умозаключение – логическая операция, в результате которой из одного или нескольких данных высказываний получается (выводится) новое высказывание.
  Например: «Все металлы электропроводны». «Ртуть является металлом». Путем умозаключения можно сделать вывод, что «Ртуть электропроводна».
  Логическое выражение – запись или устное утверждение, в которое, наряду с постоянными, обязательно входят переменные величины (объекты).
  Например: (А ۸ (В ۷ С))
  

• 

  12 слайд

  Простые высказывания обозначают
  заглавными латинскими буквами
  A, B, C…X, Y, Z и называют
  логическими переменными
  Значения высказываний
  ИСТИНА или ЛОЖЬ обозначают
  соответственно цифрами 1 и 0
  и называют логическими величинами
  Составные высказывания называются
  логическими выражениями и включают
  в себя логические переменные,
  операции логики и скобки для изменения
  порядка действий операций
  

• 

  13 слайд

  Рассмотрим следующие высказывания:
  
  A = (7 > 3)
  B = (7 = 3)
  C = (7 ≠ 3)
  На языке алгебры логики эти высказывания можно записать так:
  A = ИСТИНА = 1
  B = ЛОЖЬ = 0
  C = ИСТИНА = 1
  Примеры:
  

• 

  14 слайд

  Основные логические операции
  КОНЪЮНКЦИЯ (логическое умножение)
  Конъюнкцией высказывание А и В называется высказывание, обозначаемое А&В, которое истинно тогда и только тогда, когда истинны одновременно оба высказывания А и В.
  Соответствует союзу И
  Обозначается & или ۸
  

• 

  15 слайд

  Соответствует союзу ИЛИ
  Обозначается ۷
  ДИЗЪЮНКЦИЯ (логическое сложение)
  Дизъюнкцией высказываний А и В называется высказывание, обозначаемое АvВ, которое истинно тогда и только тогда, когда истинно хотя бы одно из высказываний А и В.
  Основные логические операции
  

• 

  16 слайд

  Число 2 четное или Это простое число
  2 * 2 = 4 или Белые медведи живут в Африке
  Каша – вкусное блюдо или Математика – интересный предмет
  Луна – спутник Марса или Луна – спутник Земли
  Сегодня плохая погода или Кислород – вода
  Microsoft Word – текстовый редактор или Paint – графический редактор
  Определить значения истинности следующих высказываний:
  Примеры:
  Ответ: истинными высказываниями являются: 1, 2, 4, 6
  

• 

  17 слайд

  ИНВЕРСИЯ (отрицание)
  Соответствует частице НЕ
  Обозначается
  Отрицанием высказывания А называется высказывание, обозначаемое , которое истинно тогда и только тогда, когда высказывание А ложно.
  Основные логические операции
  

• 

  18 слайд

  Волга впадает в Каспийское море.
  Число 28 не делится на число 7.
  6 > 3.
  Ответ: истинными высказываниями являются: 2
  Сформулируйте отрицания следующих высказываний и укажите значения истинности полученных отрицаний:
  Примеры:
  

• 

  19 слайд

  Основные логические операции
  ИМПЛИКАЦИЯ (логическое следование)
  Соответствует обороту ЕСЛИ…, ТО…
  Обозначается →
  Импликацией высказываний А и В называется высказывание, обозначаемое
  А → В, которое ложно тогда и только тогда, когда А – истинно, а В – ложно.
  

• 

  20 слайд

  Определить значения истинности следующих высказываний:
  Примеры:
  
  Если 12 делится на 6, то 12 делится на 3.
  Если 11 делится на 6, то 11 делится на 3.
  Если 15 делится на 6, то 15 делится на 3.
  Если 15 делится на 3, то 15 делится на 6.
  Если Саратов расположен на Неве, то белые медведи обитают в Африке.
  Ответ: истинными высказываниями являются: 1, 2, 3, 5
  

• 

  21 слайд

  ЭКВИВАЛЕНЦИЯ (равнозначность)
  Эквиваленцией высказываний А и В называется высказывание, обозначаемое А ↔ В, которое истинно тогда и только тогда, когда А и В одновременно истинны или ложны.
  
  Соответствует оборотам:
  ТОГДА И ТОЛЬКО ТОГДА;
  В ТОМ И ТОЛЬКО В ТОМ СЛУЧАЕ Обозначается ↔; ~
  Основные логические операции
  

• 

  22 слайд

  Примеры:
  
  12 делится на 6 тогда и только тогда, когда 12 делится на 3.
  11 делится на 6 тогда и только тогда, когда 11 делится на 3.
  15 делится на 6 тогда и только тогда, когда 15 делится на 3.
  15 делится на 5 тогда и только тогда, когда 15 делится на 4.
  Определить значения истинности следующих высказываний:
  Ответ: истинными высказываниями являются: 1, 2
  

• 

  23 слайд

  Логическая формула
  С помощью логических переменных и символов логических операций любое высказывание можно формализовать, т.е. заменить логической формулой.
  Логическая формула:
  
  Всякая логическая переменная и символы «истина» («1») и «ложь» («0») – формулы.
  
  Если А и В – формулы, то , А&В, АvВ, А → В, А ↔ В – формулы.
  
  Никаких других формул в алгебре логики нет.
  Логическая формула – формула, содержащая лишь логические величины и знаки логических операций.
  
  Результатом логической формулы является «истина» или «ложь».
  

• 

  24 слайд

  Формула называется выполнимой, если она хотя бы при одном наборе значений переменных принимает значение «истина».
  
  Например:
  
  Вычислить значение логической формулы х & y v x & z, если х=0, у=1, z=1.
  
  Порядок выполнения логических операций.
  
  Действие в скобках
  Операция отрицания
  Операция конъюнкция
  Операция дизъюнкция
  Операция импликация
  Операция эквиваленция
  Логическая формула
  

• 

  25 слайд

  Формула называется тавтологией или тождественно-истинной формулой, ели она при каждом наборе значений переменных принимает значение «истина».
  
  Например:
  
  Формула Аv , соответствует высказыванию
  «Этот треугольник прямоугольный или косоугольный».
  
  Эта формула истинна и тогда, когда треугольник прямоугольный, и тогда, когда треугольник не прямоугольный.
  
  Формула называется противоречием или тождественно-ложной формулой, если она при каждом наборе значений переменных принимает значение «ложь».
  
  Например:
  
  Формула А& , соответствует высказыванию
  «Катя самая высокая девочка в классе, и в классе есть девочки выше Кати».
  
  Эта формула ложна, т.к. либо А, либо обязательно ложно.
  
  
  
  
  
  
  
  
  Логическая формула
  

• 

  26 слайд

  Если две формулы А и В одновременно, т.е. при одинаковых наборах значений входящих в них переменных, принимают одинаковые значения, то они называются равносильными.
  
  Обозначение символом «=» или «»
  Логическая формула
  

• 

  27 слайд

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

• 

  28 слайд

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

• 

  29 слайд

  Алгоритм построения таблиц истинности для сложных выражений:
  
  Определить количество переменных (простых выражений);
  Определить количество логических операций и последовательность их выполнения.
  Определить количество строк:
  количество строк = 2ª + строка для заголовка, где a – количество логических переменных.
  4. Определить количество столбцов: количество столбцов = количество переменных + количество логических операций;
  5. Заполнить столбцы результатами выполнения логических операций в обозначенной последовательности с учетом таблиц истинности основных логических операций.
  
  Алгоритм построения таблицы истинности:
  

• 

  30 слайд

  Рассмотрим пример построения таблицы истинности для следующего сложного (составного) логического выражения:
  
  А & (B V C)
  Сначала определяем количество столбцов в будущей таблице истинности
  1
  2
  3
  4
  5
  6
  Определяем приоритетность выполнения логических операций
  
  1
  2
  3
  

• 

  31 слайд

  Решение:
  Простые выражения (логические переменные): А, В, С; (3)
  Количество логических операций:
  ¬ А - инверсия;
  B  C - операция дизъюнкции;
  ¬ А & (B  C). операция конъюнкции. Всего: 3
  Количество строк: на входе три простых высказывания: А, В, С , поэтому a=3 и количество строк = 2³ +1 = 9.
  Количество столбцов: 3+3=6
  Заполняем столбцы с учетом таблиц истинности логических операций.
  
  

• 

  32 слайд

  0
  0
  0
  0
  1
  1
  1
  1
  0
  0
  1
  1
  0
  0
  1
  1
  0
  1
  0
  1
  0
  1
  0
  1
  0
  0
  1
  1
  1
  1
  1
  0
  0
  0
  0
  0V0
  0
  1
  1
  1
  0
  1
  1
  1
  1&0
  0
  1
  1
  1
  0
  0
  0
  0
  Таблица истинности:
  

• 

  33 слайд

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

• 

  34 слайд

  I. Решение логических задач средствами алгебры логики
  
  

• 

  35 слайд

  Внимание!
  На территории школы обнаружен правонарушитель.
  Просьба ко всем, помогите установить личность нарушителя.
  Имеются свидетельские показания.
  Благодарим за оказанную помощь.
  Администрация
  

• 

  36 слайд

  Показания свидетелей
  Преступник брюнет с усами.
  Преступник блондин без усов.
  Преступник блондин, но без портфеля.
  Преступник шатен с портфелем.
  

• 

  37 слайд

  Каким был
  правонарушитель?
  

• 

  38 слайд

  Решение:
  Выделим простые высказывания и запишем их через переменные:
  1 этап:
  

• 

  39 слайд

  Запишем показания свидетелей, в виде составного логического высказывания:
  2 этап:
  Преступник брюнет с усами.
  1 свидетель
  B & A
  

• 

  40 слайд

  2 этап:
  2 свидетель
  C & Ā
  Преступник блондин без усов.
  Запишем показания свидетелей, в виде составного логического высказывания:
  

• 

  41 слайд

  2 этап:
  3 свидетель
  C & ¬D
  Преступник блондин, но без портфеля.
  Запишем показания свидетелей, в виде составного логического высказывания:
  

• 

  42 слайд

  2 этап:
  4 свидетель
  E & D
  Преступник шатен с портфелем.
  Запишем показания свидетелей, в виде составного логического высказывания:
  

• 

  43 слайд

  Запишем логические функции для каждого из показаний:
  3 этап:
  f1 = ¬B & A ۷ ¬A&B
  f2 = ¬C & ¬A ۷ A&C
  f3 = ¬C & ¬D ۷ D&C
  f4 = ¬D & E ۷ ¬E&D
  f5=B&¬C&¬E۷¬B&C&¬E۷¬B&¬C&E
  B & A
  C & Ā
  C & ¬D
  E & D
  

• 

  44 слайд

  Запишем произведение логических функций:
  4 этап:
  F= (¬B & A ۷ ¬A&B)&(¬C & ¬A ۷ A&C) & (¬C & ¬D ۷ D&C )&(¬D & E ۷ ¬E&D)& (B&¬C&¬E۷¬B&C&¬E۷¬B&¬C&E) =
  
  =A&¬B&C&D&¬Е
  
  

• 

  45 слайд

  F=1, тогда:
  5 этап:
  A&¬B&C&D&¬Е = 1
  

• 

  46 слайд

  Составление таблицы истинности:
  6 этап:
  A&¬B&C&D&¬Е
  Количество строк = 2ⁿ = 32
  Количество столбцов = 5(переменных) + 6(действий) = 11
  

• 

  47 слайд

  Составление таблицы истинности:
  6 этап:
  A&¬B&C&D&¬Е
  Порядок действий (без учета скобок):
  Инверсия;
  Конъюнкция;
  Дизъюнкция.
  

• 

  48 слайд

  Анализ результата:
  7 этап:
  A&¬B&C&D&¬Е =1, при
  А=1; В=0; С=1; D=1; E=0
  

• 

  49 слайд

• 

  50 слайд

  Правонарушитель блондин с усами и с портфелем.
  Вывод:
  

• 

  51 слайд

  II. Решение логических задач табличным способом
  
  Света, Марина, Андрей, Кирилл и Юра держат домашних животных. У каждого либо кошка, либо собака, либо попугай.
  Девочки не держат собак, а мальчики попугаев. У Светы нет кошки. У Светы и Марины разные животные. У Марины и Андрея – одинаковые. У Андрея и Кирилла – разные. У Кирилла и Юры – одинаковые. Какие животные у каждого.
  задача:
  

• 

  52 слайд

  1. Девочки не держат собак
  

• 

  53 слайд

  2. Мальчики не держат попугаев
  

• 

  54 слайд

  3. У Светы нет кошки → у Светы попугай
  

• 

  55 слайд

  4. У Светы и Марины разные животные
  

• 

  56 слайд

  5. У Марины и Андрея - одинаковые
  

• 

  57 слайд

  6. У Андрея и Кирилла – разные
  

• 

  58 слайд

  7. У Кирилла и Юры - одинаковые
  

• 

  59 слайд

  III. Решение логических задач с помощью рассуждений
  В лесу проводили кросс. Обсуждая его итоги, одна Белка сказала:
  «Заяц занял первое место, а лиса-второе».
  Другая Белка возразила:
  «Заяц занял второе место, а лось – первое».
  На что Филин заметил, что в высказываниях каждой Белки одна часть верная, а другая – нет. Кто был первым в этом кроссе?
  задача:
  

• 

  60 слайд

  В лесу проводили кросс. Обсуждая его итоги, одна Белка сказала:
  «Заяц занял первое место, а лиса-второе».
  Другая Белка возразила:
  «Заяц занял второе место, а лось – первое».
  На что Филин заметил, что в высказываниях каждой Белки
  одна часть верная, а другая – нет. Кто был первым в этом кроссе?
  Выделим высказывания
  

• 

  61 слайд

  Предположим, что в первом предложении истинно
  1-я белка:
  
  «Заяц занял первое место, а лиса-второе».
  
  2-я белка:
  «Заяц занял второе место, а лось – первое».
  
  Пусть высказывание истинно
  В результате исходного предположения мы пришли к противоречию. Заяц не может занять второе место – это ложь. Лось не может быть первым - это ложь. В высказываниях каждой Белки одна часть верная, а другая – нет.
  
  

• 

  62 слайд

  Предположим, что в первом предложении истинно
  1-я белка:
  
  «Заяц занял первое место, а лиса-второе».
  
  2-я белка:
  
  «Заяц занял второе место, а лось – первое».
  
  Пусть высказывание истинно
  В результате исходного предположения противоречия нет!!!
  Ответ: первым в этом кроссе был лось
  Высказывание истинно
  Высказывание ложно
  

• 

  63 слайд

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

• 

  64 слайд

  Всей переключательной схеме также можно поставить в соответствие логическую переменную, равную единице, если схема проводит ток, и равную нулю — если не проводит.
  Эта переменная является функцией от переменных, соответствующих всем переключателям схемы, и называется функцией проводимости.
  
  
  Каждый переключатель имеет только два состояния:
  замкнутое и разомкнутое.
  
  Переключателю Х поставим в соответствие логическую переменную х, которая принимает значение 1 в том и только в том случае, когда переключатель Х замкнут и схема проводит ток;
  если же переключатель разомкнут, то х равен 0.
  
  Переключательные схемы
  
  

• 

  65 слайд

  Найдем функции проводимости F некоторых переключательных схем:
  
  a)   Схема не содержит переключателей и проводит ток всегда, следовательно F=1
  
  б)   Схема содержит один постоянно разомкнутый контакт, следовательно F=0
  
  
  в)   Схема проводит ток, когда переключатель х замкнут, и не проводит, когда х разомкнут, следовательно, F(x) = x
   
  
  
  Х
  

• 

  66 слайд

  г)   Схема проводит ток, когда переключатель х разомкнут, и не проводит, когда х замкнут, следовательно, F(x) = x;
  
  Х
  д)   Схема проводит ток, когда оба переключателя замкнуты, следовательно,
  F(x,y) = x * y (последовательное соединение)
  
  Х
  У
  е) Схема проводит ток, когда хотя бы один из переключателей замкнут, следовательно, F(x, y)=x v y (параллельное соединение)
  
  Х
  У
  

• 

  67 слайд

  РАВНОСИЛЬНОСТЬ ПЕРЕКЛЮЧАТЕЛЬНЫХ СХЕМ
  Две схемы называются равносильными, если через одну из них проходит ток тогда и только тогда, когда он проходит через другую (при одном и том же входном сигнале).
  
  Из двух равносильных схем более простой считается та схема, функция проводимости которой содержит меньшее число логических операций или переключателей.
  
  

• 

  68 слайд

  ВЫПОЛНИТЬ ЗАДАНИЯ
  
  1. Постройте схему, содержащую 4 переключателя x, y, z и t, такую, чтобы она проводила ток тогда и только тогда, когда замкнут контакт переключателя t и какой-нибудь из остальных трёх контактов.
  
  2. Постройте схему с пятью переключателями, которая проводит ток в том и только в том случае, когда замкнуты ровно четыре из этих переключателей.
  
  3. Найдите функцию проводимости схемы:
  a
  c
  b
  d
  e
  

• 

  69 слайд

  Найдите функции проводимости следующих переключательных схем:
  

• 

  70 слайд

  Проверьте равносильность следующих переключательных схем:
  Не a
  Не a
  a
  b
  b
  c
  И
  a
  b
  c
  b
  c
  b
  Не с
  a
  c
  a
  a
  Не b
  c
  b
  Не с
  c
  Не с
  И
  1.
  2.
  

• 

  71 слайд

  Упростите переключательную схему, постройте ее упрощенный вариант
  1.
  2.
  3.
  4.
  

• 

  72 слайд

  Постройте переключательные схемы с заданными функциями проводимости:
  1. (a v b) * c v a * b
  2. a * (b v c) v b* (a v c)
  3. a v b * c * d v b * c * d v b v b * c * d
  4. a * b * (c * d v b v a) v a * (c v d) *a v b