1 Логика в информатике Обучение школьников основам информатики, изучение ими такого важного понятия как «алгоритм», невозможно без развития у них логического. - презентация

1

2 1 Логика в информатике Обучение школьников основам информатики, изучение ими такого важного понятия как «алгоритм», невозможно без развития у них логического мышления, умения оперировать понятиями и символикой математической логики. Гаврюкова Г.А. Школа 68 г.Рязань

3 2 Цель курса сформировать умение: выделять существенные высказывания в тексте задачи и формализовывать их; представлять условия и решение задачи в различных видах; преобразовывать логические выражения для обоснования функционирования устройств, являющихся основой компьютера.

4 3 Темы для обсуждения I. Формальная логика (Понятие. Высказывание Умозаключение.) II. Математическая логика (логические операции, построение таблиц истинности и упрощение сложных высказываний) III. Логические основы компьютера (логические элементы, переключательные схемы ) IV. Применение электронных таблиц Excel для построения таблиц истинности и использования условной функции.

5 4 Формальная логика Формальная логика Формальная логика.Формальная логика Понятие Содержание (Совокупность существенных свойств, которые мыслятся в данном понятии) Объем (Совокупность предметов, которые мыслятся в данном понятии) Виды понятий Единичные Общие Пустые

6 5 Отношения между понятиями. Отношения между понятиями. Тестовые задания Тестовые задания 1) Равнозначности ( мыслится один и тот же предмет ) 2) Пересечения ( понятия имеют некоторые общие признаки ) 3) Подчинение ( понятие с большим объемом – подчиняющее, с меньшим – подчиненное. Род – Вид.) 4) Соподчинение ( два понятия находятся в соподчинении к третьему, если они не имеют общих элементов объема и это третье понятие является подчиняющим для каждого из них) 5) Исключения ( объемы полностью исключают друг друга )

7 6 Логические операции над понятиями Обобщение Образование из понятия некоторого нового с более широким объемом Ограничение Переход от понятия с большим объемом к понятию с меньшим объемом Определение Раскрытие содержания понятия Деление Распределение объема понятия на классы с точки зрения некоторого признака Классификация Многоступенчатое, разветвленное деление. Обобщить «ОЗУ» Ограничить «Электронное устройство» Определить «информатика» Разделить «треугольник» Расклассифицировать «память компьютера»

8 7 Высказывание (суждение, утверждение) Классификация высказываний: 1. Общеутвердительные Все S суть Р 2. Общеотрицательные Ни одно S не суть Р 3. Частноутвердительные Некоторые S суть Р 4. Частноотрицательны Некоторые S не суть Р Форма мысли, содержащая описание некоторой ситуации и утверждение или отрицание наличия этой ситуации в действительности В высказывании осуществляется приписывание свойств предмету

9 8 Умозаключение форма мышления, посредством которой из одного или нескольких истинных суждений, называемых посылками, по определенным правилам получают суждение-заключение. А В; В А В; А - А В

10 9 Математическая логика Алгебра логики (алгебра высказываний) - раздел математической логики, изучающий строение (форму, структуру) сложных логических высказываний и способы установления их истинности с помощью алгебраических методов. A & B A & B = = А & ( В B ) = = А & 1 = А

11 10 Логическое высказывание это любoе повествовательное пpедлoжение, в oтнoшении кoтopoгo мoжно oднoзначнo сказать, истиннo oнo или лoжнo. Все рыбы дышат жабрами Волга впадает в Каспийское море

12 11 Обозначение высказываний: Х = Число кратно 3 Р = Чтобы подключиться к Интернету с домашнего компьютера, необходим модем. Если высказывание А истинное, то будем писать «А = 1» и говорить «А – истинно». Если высказывание А ложное, то будем писать«А = 0» и говорить «А – ложно». Джордж Буль

13 12 Логическая операция Тестовые задания Логическая операция Тестовые задания способ построения сложного высказывания из данных высказываний, при котором значение истинности сложного высказывания полностью определяется значениями истинности исходных высказываний. Инверсия Конъюнкция Дизъюнкция Импликация Эквиваленция

14 13 Импликацию можно выразить через дизъюнкцию и отрицание: А В = А v В. Эквиваленцию можно выразить через отрицание, дизъюнкцию и конъюнкцию: А В = ( А v В). ( В v А).

15 14 Логическая формула: Всякая логическая переменная и символы "истина" ("1") и "ложь" ("0") формулы. Если А и В формулы, то, А & В, А v В, А B, А В формулы. Никаких других формул в алгебре логики нет.

16 15 Построение Построение таблиц истинности сложных высказываний КС К C С( К C ) & С( К C ) & С К В классе оказалось разбито стекло. Учитель объясняет директору: это сделал Коля или Саша. Но Саша этого на делал, т.к. в это время сдавал мне зачет. Следовательно, это сделал Коля. Прав ли учитель? Формализуем данное сложное высказывание. К – это сделал Коля С – это сделал Саша Количество простых высказываний n = 2. Форма высказывания: ( К C ) & С К

17 16 Под упрощением формулы, не содержащей операций импликации и эквиваленции, понимают равносильное преобразование, приводящее к формуле, которая либо содержит по сравнению с исходной меньшее число операций конъюнкции и дизъюнкции и не содержит отрицаний неэлементарных формул, либо содержит меньшее число вхождений переменных. УпрощениеУпрощение сложных высказываний Пример 1 Упростить: A & B A & B. Применим закон исключенного третьего A & B A & B = А & ( В B ) = = А & 1 = А

18 17 Пример 2.Упростить: (A B) & (A B).Упростить: Способ 1. Применим законы дистрибутивности и непротиворечия: (A B) & (A B) = A (В & B ) = A 0 = А Способ 2. Перемножим скобки (как в алгебре чисел) (A B) & (A B) = A & А A & B В & А В & B = = A А & ( B В ) 0 = A А & 1 = A А = А.

19 18 Пример 3. Упростить: ( Х У). Применим законы де Моргана и двойного отрицания: ( Х У) = Х & У = Х & У. Пример 4.

20 19 Перед сдачей вступительных экзаменов в институт абитуриент предположил, что: 1) если он сдаст математику, то не получит двойку по диктанту только при условии, что он сдаст информатику; 2) не м.б., чтобы он одновременно получил двойки и по диктанту и по математике; 3) достаточное условие несдачи экзамена по информатике – двойка по диктанту. После сдачи экзаменов оказалось, что из трех предположений только одно было ложным. Как сдал экзамены? M ( I D) D I M D

21 20 MID M ( I D) M D D I

22 21 Решение логических содержательных задач Процесс решения: Алгебраический, табличный, графический… Условия задачи о двух утверждениях: Либо одновременно И, либо одновременно Л A & B v A & B = 1 Одно И, другое Л A & B v A & B = 1

23 22 Логические основы компьютера Цифровой сигнал - это сигнал, который может принимать только одно из двух установленных значений. Примеры таких состояний: Напряжения +5 В и 0,4 В Сила тока 20 мА и 1 мА Лампа горит или нет Кнопка нажата или нет.

24 23 Логический элемент преобразователь, который получая сигналы об истинности отдельных высказываний, обрабатывает их и в результате выдает значение логического отрицания, логической суммы или логического произведения этих высказываний.

25 24 Логические элементы «Не» Инвертор «И» Конъюнктор «Или» Дизъюнктор Выдает на выходе сигнал, противоположный сигналу на входе, т.е. На его выходе будет 1, если на вход поступит 0 и наоборот Выдает на выходе значение логического произведения входных сигналов. Выдает на выходе значение логической суммы входных сигналов. Физически можно реализовать при помощи реле с нормально замкнутыми контактами. последовательным соединением переключателей параллельным соединением переключателей

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

27 26 Функциональные схемы и структурные формулы логических устройств. Логическое устройство - цепочка из логических элементов, в которой выходы одних элементов являются входами других. Функциональная схема – схема соединения логических элементов, реализующая логическую функцию.логическую функцию Формой описания функции, реализуемой логическим устройством, является структурная формула. F(X,Y) = X V Y

28 27 Установите соответствие между логической функцией и таблицей истинности: А) F(Х,У) = Х & Y Х & Y Б) F(Х,У) = Х & Y В) F(Х,У) = Х & Y 1 2 XYF XYF

29 28 Научимся строить функциональные схемы по структурным формулам и наоборот. 1 ) Определите структурную формулу по заданной функциональной схеме: х у 1 Ответ: F(X,Y) = ( X Y ) 2) Постройте функциональную схему, отвечающую структурной формуле F(X,Y) = X & Y & XYXY F(X,Y)

30 29 Применение математической логики в технике. 1) Изобразите переключательные схемы, отвечающие следующим сложным высказываниям: А) ( А B ) & (C D) Б ) A & B & C A & B C 2) Можно ли изображенную на рисунке электрическую цепь заменить более простой схемой, соответствующей формуле F(X, Y, Z) = X Y&Z приложение X Y Z Y X

31 30 Типовые логические устройства компьютера ( сумматоры, полусумматоры, триггеры, счетчики, регистры, шифраторы, дешифраторы) Сумматор является основным узлом АЛУ и служит для суммирования чисел посредством поразрядного сложения. Одноразрядный двоичный сумматор: на два входа и два выхода – одноразрядный полусумматор на три входа и два выхода – одноразрядный сумматор на три входа. X Y X Y P Q P S S Сумма Перенос в старший разряд Перенос из младшего разряда

32 31 Хранение двоичных кодов. Триггер – устройство, запоминающее один бит информации (сигналы 0 и 1). Для запоминания и демонстрации n-разрядного двоичного числа необходимо n параллельно соединенных триггеров, совокупность которых называется n-разрядным регистром. Для запоминания одного байта потребуется 8 триггеров. Оперативная память компьютера часто конструируется в виде набора регистров. Как правило, один регистр образует одну ячейку памяти, каждая ячейка имеет свой номер. Условное обозначение Реализация с помощью вентилей ИЛИ- НЕ

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

34 33 Литература Контрольная работа Применение электронных таблиц Excel

35 34 Спасибо за внимание!