Презентация ориентирована на использование интерактивной доски в ходе урока Презентацию разработала Воеводина Н.Д. - презентация

1 Презентация ориентирована на использование интерактивной доски в ходе урока Презентацию разработала Воеводина Н.Д.

2 Алгебра логики (булева алгебра) - это раздел математики, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности или ложности) и логических операций над ними.

3 Джордж Буль

4 Логическое высказывание (суждение ) это любое повествовательное предложение, в отношении которого можно однозначно сказать, истинно оно или ложно.

5 Так, например, предложение " Трава зеленая" следует считать высказыванием, так как оно истинное. Предложение " Лев - птица" тоже высказывание, так как оно ложное.

6 Не всякое предложение является логическим высказыванием. Высказываниями не являются, например, предложения «ученик десятого класса»- ничего не утверждает об ученике и "информатика интересный предмет". (интересный - неопределенное понятие)

7 Употребляемые в обычной речи слова и словосочетания "не", "и", "или", "если..., то", "тогда и только тогда" и другие позволяют из уже заданных высказываний строить новые высказывания. Такие слова и словосочетания называются логическими связками.

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

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

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

11 Упражнение 3 Из двух простых суждений постройте сложное суждение. 1. Марина старше Светы. Оля старше Светы. 2. Иван – сын Петра. Иван – внук Петра. 3. Одна половина класса изучает английский язык. Вторая половина класса изучает немецкий язык. 4. В кабинете есть учебники. В кабинете есть справочники. 5. Слова в этом предложении начинаются на букву Ч. Слова в этом предложении начинаются на букву А. 6. Часть туристов любит чай. Остальные туристы любят молоко. 7. Синий кубик меньше красного. Синий кубик меньше зеленого. 8. Х Летом я поеду в деревню. Летом я поеду в туристическую поездку.

12 Чтобы обращаться к логическим высказываниям, им назначают имена. Пусть через А обозначено высказывание "Тимур поедет летом на море", а через В высказывание "Тимур летом отправится в горы".

13 Тогда составное высказывание "Тимур летом побывает и на море, и в горах" можно кратко записать как А и В. Здесь "и" логическая связка, А, В логические переменные, которые могут принимать только два значения - "истина" или "ложь", обозначаемые, соответственно, "1" и "0".

14 Упражнение 1 Определите истинность суждений: 1.Наполеон был французским императором. 2.Чему равно расстояние от Земли до Марса ? 3.Киев – столица Украины. 4.Некоторые рыбы – хищники. 5.Внимание! Посмотрите направо. 6.Электрон – элементарная частица. 7.Не нарушайте правила дорожная движения! 8.Полярная Звезда находится в созвездии Малой Медведицы. 9.Все ребята умеют плавать

15 Типы суждений (высказываний) Общие Начинается со слов: все, всякий, каждый, ни один. Частные Начинается со слов некоторые, большинство, не все и т.п. Единичные Все остальные

16 Упражнение 2 Определить тип суждения: Все рыбы умеют плавать. Некоторые медведи – бурые. Буква А – гласная. Не все книги содержат полезную информацию. Кошка является домашним животным. Все лекарства приятны на вкус. Некоторые лекарства приятны на вкус. Не всё то золото, что блестит. Все хорошо, что хорошо кончается. Часть народов России принадлежит к монгольской расе. Ни один внимательный человек не совершит оплошность. Некоторые ученики – двоечники. Мой кот страшный забияка. Отдельные животные не имеют легких. Любой неразумный человек ходит на руках. У некоторых змей нет ядовитых зубов. Многие растения обладают целебными свойствами. Все металлы проводят тепло. Рыбы дышат жабрами. Многие из почтенных людей несчастны. Только один металл жидкий. Автор Гулливера жил в Англии. Не все званные избраны. Ни один из римских рабов не обладал гражданским правом.

17

18 Высказывание А истинно, когда A ложно, и ложно, когда A истинно. Пример. "Луна спутник Земли" (А); "Луна не спутник Земли" (А).

19 НЕ Операция, выражаемая словом "не", называется инверсией или отрицанием и обозначается чертой над высказыванием.

20 И Операция, выражаемая связкой "и", называется конъюнкцией (лат. conjunctio соединение) или логическим умножением и обозначается точкой ". " (может также обозначаться знаками /\ или &).

21 Высказывание А · В истинно тогда и только тогда, когда оба высказывания А и В истинны. Например, высказывание "10 делится на 2 и 5 больше 3" истинно, а высказывания "10 делится на 2 и 5 не больше 3", "10 не делится на 2 и 5 больше 3", "10 не делится на 2 и 5 не больше 3" - ложны.

22 ИЛИ Операция, выражаемая связкой "или" (в неисключающем смысле этого слова), называется дизъюнкцией (лат. disjunctio разделение) или логическим сложением и обозначается знаком v (или плюсом).

23 Высказывание А v В ложно тогда и только тогда, когда оба высказывания А и В ложны. Например, высказывание "10 не делится на 2 или 5 не больше 3" ложно, а высказывания "10 делится на 2 или 5 больше 3", "10 делится на 2 или 5 не больше 3", "10 не делится на 2 или 5 больше 3" истинны.

24 ЕСЛИ-ТО Операция, выражаемая связками если..., то", "из... следует", "... влечет...", называется импликацией (лат. implico тесно связаны) и обозначается знаком. Высказывание А В ложно тогда и только тогда, когда А истинно, а В ложно.

25 РАВНОСИЛЬНО Операция, выражаемая связками "тогда и только тогда", "необходимо и достаточно", "... равносильно...", называется эквиваленцией или двойной импликацией и обозначается знаком или ~. Высказывание А В истинно тогда и только тогда, когда значения А и В совпадают.

26 Импликацию можно выразить через дезъюнкцию и отрицание А В = А v В Эквиваленцию можно выразить через Отрицание, дезъюнкцию и конъюнкцию А В = (А v В) ^ (B v A)

27

28 математики в основе число, переменная логики высказывание (логическая переменная)

29 Сколько различных чисел существует? Сколько различных переменных существует? Какие значения могут принимать логические переменные?

30 Над числами и переменными мы производим арифметические действия Над переменными алгебраические преобразования Над высказываниями (логическими переменными) мы можем производить …?

31 …логические операции действия с высказываниями, в результате которых получаются новые высказывания

32 КОНЪЮНКЦИЯ ЛОГИЧЕСКОЕ УМНОЖЕНИЕ ОПРЕДЕЛЯЕТ СОЕДИНЕНИЕ ДВУХ ВЫСКАЗЫВАНИЙ С ПОМОЩЬЮ СОЮЗА В прямоугольнике противоположные стороны равны и параллельны В прямоугольнике противоположные стороны равны и пересекаются

33 ABF = A ^ B КОНЪЮНКЦИЯ ЛОГИЧЕСКОЕ УМНОЖЕНИЕ

34 ДИЗЪЮНКЦИЯ ЛОГИЧЕСКОЕ СЛОЖЕНИЕ ОПРЕДЕЛЯЕТ СОЕДИНЕНИЕ ДВУХ ВЫСКАЗЫВАНИЙ С ПОМОЩЬЮ СОЮЗА Все положительные числа больше отрицательных или больше 0 Все положительные числа больше 1 или больше нуля

35 ABF = A ν B ДИЗЪЮНКЦИЯ ЛОГИЧЕСКОЕ СЛОЖЕНИЕ

36 ОТРИЦАНИЕ (ИНВЕРСИЯ) ОПРЕДЕЛЯЕТ СОЕДИНЕНИЕ ДВУХ ВЫСКАЗЫВАНИЙ С ПОМОЩЬЮ ЧАСТИЦЫ А А - «На улице идет дождь» ¬А Тогда ¬А - А А - «На улице нет дождя»

37 A¬ А¬ А ОТРИЦАНИЕ (ИНВЕРСИЯ)

38 Определите значение логического выражения (0 или 1) : а) ¬А, если А – «число 6 – четное» б) ¬А, если А – «Петр I – не был императором» в) ¬А, если А – «металлы проводят ток» г) ¬А, если А – «Москва – столица России» д) ¬А, если А – «идет второй урок» ОТРИЦАНИЕ (ИНВЕРСИЯ)

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

40 определите, в каком порядке необходимо вычислять значение логического выражения: ¬ А & ¬ B A & (B & C) (A & B) ν (C & ¬ D) A ν ¬ D ν B A ^ B ^ ¬ A РЕШИМ ЗАДАЧИ

41 Алгоритм построения таблицы истинности логической формулы: 1.подсчитать количество переменных в формуле; 2.определить число строк в таблице m = 2n, где n –количество переменных; 3.подсчитать количество логических операций в формуле; 4.установить последовательность выполнения логических операций с учетом скобок и приоритетов; 5.определить количество столбцов в таблице: число переменных + число операций; 6.выписать наборы значений переменных в виде последовательности возрастающих n-разрядных двоичных чисел от 0 до 2n – 1; 7.провести заполнение таблицы истинности по столбцам, выполняя логические операции в соответствии с установленной в п.4 очередностью выполнения

42 АВС ¬B¬B¬С¬С ¬В&¬C¬В&¬CBv( ¬ B& ¬ C)A& (B v ¬ B& ¬ C) Пример: Для формулы А & (B v ¬ B & ¬ C) построить таблицу истинности Построить таблицы истинности для следующих формул: A v (B v ¬ B ) ¬C Дом задание: A & (B & ¬ B ¬C)

43 Пример: Для формулы A v (B v ¬ B ) ¬C построить таблицу истинности

44 С помощью логических переменных и символов логических операций любое высказывание можно формализовать, то есть заменить логической формулой.

45 Определение логической формулы: 1. Всякая логическая переменная и символы "истина" ("1") и "ложь" ("0") - формулы. 2. Если А и В - формулы, то А, А · В, А v В, А B, А В - формулы. 3. Никаких других формул в алгебре логики нет.

46 Логические законы и правила преобразования логических выражений 1.Закон двойного отрицания: А=А 2. Переместительный(коммутативный) закон: -Для логического сложения: A v B = B v A -для логического умножения: A & B = B & A 3. Сочетательный (ассоциативный)закон: -для логического сложения: (A v B) v C =A v ( B v C) -для логического умножения: (A & B) & C = A & (B & C)

47 4. Распределительный (дистрибутивный) закон: -для логического сложения: (A v B)v C=(A & C) v (B & C ) -для логического умножения:(A & B)v C=(A v C) & (B v C) 5.Закон общей инверсии (законы де Моргана) -для логического сложения: (A v B) = ¬ A & ¬B -для логического умножения: (A & B) = ¬ A v ¬ B 6. Закон идемпотентности: -для логического сложения: А v A = A -для логического умножения:A & A = A

48 Логический элемент компьютера это часть электронной логической схемы, которая реализует элементарную логическую функцию.

49 Логическими элементами компьютеров являются электронные схемы И, ИЛИ, НЕ, ИНЕ, ИЛИНЕ и другие.

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

51 Единица на выходе схемы И будет тогда и только тогда, когда на всех входах будут единицы. Когда хотя бы на одном входе будет ноль, на выходе также будет ноль. Таблица истинности схемы И XYX*Y Схема И Схема И реализует конъюнкцию двух или более логических значений. & X Y F=X·Y

52 Таблица истинности схемы ИЛИ xyx v y Когда хотя бы на одном входе схемы ИЛИ бу дет единица, на её выходе также будет единица. Схема ИЛИ реализует дизъюнкцию двух или более логических значений. X Y F=X+Y 1

53 Таблица истинности схемы НЕ xx Если на входе схемы 0, то на выходе 1. Когда на входе 1, на выходе 0. XF=X 1 Схема НЕ (инвертор) реализует операцию отрицания.

54 С х е м а ИНЕ Схема ИНЕ состоит из элемента И и инвертора и осуществляет отрицание результата схемы И. Связь между выходом F и входами x и y схемы записывают следующим образом: F=x·y, где x·y читается как "инверсия x и y". X F=X·Y & Y

55 Таблица истинности схемы ИНЕ xyX*Y X F=X·Y & Y

56 С х е м а ИЛИНЕ Схема ИЛИНЕ состоит из элемента ИЛИ и инвертора и осуществляет отрицание результата схемы ИЛИ. Связь между выходом F и входами x и y схемы записывают следующим образом:F=x+y, где x+y, читается как "инверсия x или y ". X F=X+Y 1 Y

57 Таблица истинности схемы ИЛИ НЕ xyX+Y X F=X+Y 1 Y

58 Элементы схемотехники. Логические схемы конъюнктор Логический элемент (вентиль) И – конъюнктор – реализует операцию логического умножения. дизъюнктор Логический элемент (вентиль) ИЛИ – дизъюнктор – реализует операцию логического сложения. инвентор Логический элемент (вентиль) НЕ – инвентор – реализует операцию отрицания. штрих Шеффера. Логический элемент И – НЕ реализует функцию штрих Шеффера. стрелка Пирса. Логический элемент ИЛИ – НЕ реализует функцию стрелка Пирса. & A B 1 A B A B Из отдельных логических элементов можно составить, например, устройства, производящие арифметические операции над двоичными числами. Электронная логическая схема, выполняющая суммирование двоичных кодов, называется сумматором.

59 Открытые вопросы для самоконтроля 1.Даны два высказывания: А = Число 5 – простое В = Луна – спутник Венеры. Очевидно, что А=1, В=0. Сформулируйте на русском языке высказывания, соответствующие следующим формулам: а) Ā; б) А&B; в) АВ. Какие из них истинны? 2.Найдите значения выражений: а) (1v1) v (1v0);б) ((1&A) v (Ā&0)) v 1; 3.Постройте таблицы истинности для следующих формул: а) A v (B&A);б) A & (B v ¬B &C). 4.В бутылке, стакане, кувшине и банке находятся молоко, лимонад, квас и вода. Известно, что: вода и молоко не в бутылке, сосуд с лимонадом стоит между кувшином и сосудом с квасом,, в банке не лимонад и не вода; стакан стоит между банкой и сосудом с молоком. В каком сосуде находится каждая жидкость? 5.Cоставьте таблицу истинности для следующей логической функции: F = X & ¬Y v ¬X & Y 6.Найдите значение выходного сигнала в приведенной схеме, если: a) А = 0 и В = 0; b) А = 0 и В = 1; c) А = 1 и В = 0; d) А = 1 и В = 1.

60 Ответы на вопросы 1.Истинных высказываний нет. 2.а) 1; б) 1. 3.а) F=( );б) F=( ). 4.Лимонад – в бутылке, вода – в стакане, молоко – в кувшине, квас – в банке. XY¬X¬YX&¬Y¬X&YF ABF ГлавнаяПредыдущий слайд

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

62 Самый распространённый тип триггера так называемый RS- триггер (S и R, соответственно, от английских set установка, и reset сброс) S R Q Q

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

64 Многоразрядный двоичный сумматор