ОСНОВЫ ЛОГИКИ (Алгебра логики или алгебра высказываний Угринович 10-11 Стр.123 Практические задания Семакин 7-9 стр.45. - презентация

1 ОСНОВЫ ЛОГИКИ (Алгебра логики или алгебра высказываний Угринович Стр.123 Практические задания Семакин 7-9 стр.45

2 ЛОГИКА НАУКА О ФОРМАХ И СПОСОБАХ МЫШЛЕНИЯ Угринович Стр.123

3 1 этап – формальная логика Основатель – Аристотель ( гг. до н.э. ) Ввёл основные формулы абстрактного мышления

4 2 этап – математическая логика Н емецкий ученый и философ Лейбниц( ), предпринял попытку логических вычислений.

5 Джордж Буль – создатель алгебры логики Джордж Буль – английский математик-самоучка ( г) Джордж Буль по праву считается отцом математической логики. Его именем назван раздел математической логики – булева алгебра.

6 Джордж Буль – создатель алгебры логики Буль изобрел своеобразную алгебру - систему обозначений и правил, применимую ко всевозможным объектам, от чисел до предложений. Пользуясь этой системой, он мог закодировать высказывания (утверждения, истинность или ложность которых требовалось доказать) с помощью символов своего языка, а затем манипулировать ими, подобно тому как в математике манипулируют числами. Основными операциями булевой алгебры являются конъюнкция (И), дизъюнкция (ИЛИ), отрицание (НЕ).

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

8 Клод Шеннон связал алгебру логики с работой компьютера Клод Шеннон ( г) – американский математик В 1936 году выпускник Мичиганского университета Клод Шеннон, которому был тогда 21 год, сумел ликвидировать разрыв между алгебраической теорией логики и ее практическим приложением

9 Клод Шеннон связал алгебру логики с работой компьютера Шеннон, имея два диплома бакалавра - по электротехнике и по математике, выполнял обязанности оператора на неуклюжем механическом вычислительном устройстве под названием "дифференциальный анализатор" Постепенно у Шеннона стали вырисовываться контуры устройства компьютера. Если построить электрические цепи в соответствии с принципами булевой алгебры, то они могли бы выражать логические отношения, определять истинность утверждений, а также выполнять сложные вычисления.

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

11 Джон фон Нейман – создатель первой ЭВМ Джон фон Нейман – американский математик

12 Удивительные способности Неймана Джон фон Нейман родился в 1903 году в семье будапештского банкира и уже в восьмилетнем возрасте владел не только несколькими иностранными языками, но также знал основы высшей математики. Он обладал феноменальной памятью и помнил все, что когда-либо слышал, видел или читал, мог дословно цитировать по памяти большие фрагменты книг, которые читал несколько лет назад.

13 Появление первых ЭВМ В 1944 году фон Нейман был направлен в качестве консультанта по математическим вопросам в группу разработчиков первой ЭВМ ENIAC. После окончания строительства ENIAC фон Нейман опубликовал отчет "Предварительное обсуждение логической конструкции электронной вычислительной машины". Этот отчет стал исходным пунктом в конструировании новых машин. Сам Нейман занялся разработкой собственной версии вычислительной машины, которую назвал машиной с памятью с прямой адресацией - IAS (Immediate Address Storage).

14 Открытие фон Неймана Уже во время работ над ENIAC фон Нейман понял, что создание компьютеров с большим количеством переключателей и проводов, которые реализуют тот или иной алгоритм, очень долго и утомительно. И он понял: в памяти машины должны быть не только данные, которые обрабатываются в ходе работы, но также и сама программа. Таким образом, его фундаментальным открытием в области вычислительной техники стала мысль, которая сегодня кажется нам такой естественной: в ходе работы компьютера и программа и обрабатываемые ею данные должны находиться в одном пространстве оперативной памяти.

15 Применение принципов алгебры логики для создания новой ЭВМ В ходе строительства ENIAC Нейман пришел к выводу, что десятичная арифметика, реализуемая в ENIAC, очень неэффективна. Для каждого десятичного разряда были отведены 10 ламп, и в любой момент времени горела только одна (скажем, если горит седьмая лампа, то в разряде стоит 7, если девятая - 9 и т. д.). В своей машине десятичную арифметику Нейман заменил двоичной.

16 «Фон-неймановская » машина Все современные компьютеры в главных чертах повторяют архитектуру IAS (вычислительной машины, сконструированной фон Нейманом), которая в специальной литературе сегодня так и именуется - "архитектура фон Неймана", или "фон-неймановская машина". Машина фон Неймана состояла из пяти основных узлов: памяти, арифметико-логического устройства (АЛУ), устройства управления и устройств ввода-вывода (в современных микропроцессорах АЛУ и устройство управления объединены в одном корпусе).

17 ВЫСКАЗЫВАНИЕ (суждение, утверждение) повествовательное предложение, о котором можно однозначно сказать, что оно истинно или ложно (Пример: Париж – столица Франции) Угринович Стр.123

18 АЛГЕБРА ЛОГИКИ (высказываний) наука об операциях над высказываниями

19

20 Понятия алгебры логики: Логическая переменная Логическая переменная – это простое высказывание, содержащее только одну мысль – Обозначение: латинская буква (А, В, Х …) – Значение: ИСТИНА (1) или ЛОЖЬ (0) Логическая функция Логическая функция (или формула или логическое выражение) – это составное высказывание, которое содержит несколько простых высказываний, соединенных между собой с помощью логических операций – Обозначение: F Логические операции Логические операции – логическое действие (логическое умножение – коньюнкция, логическое сложение – дизъюнкция, отрицание – инверсия, следование – импликация, равенство – эквивалентность) Угринович Стр.125

21 1.Объясните, почему следующие предложения не являются высказываниями: а)Уходя гасите свет. б)Какого цвета этот дом? в)Посмотрите в окно. 2. Придумай 2 высказывания 3. Придумай сложное высказывание с союзом И

22 Базовые логические операции НазваниеОбозначениеСоюз в естественном языке Пример А – «Число 10 – четное» В – «Число 10 – отрицательное» Конъюнкция (сonjuncti соединение) (логическое умножение) А ^ B A & B И«Число 10 четное и отрицательное» - ЛОЖЬ Дизъюнкция (disjunctio разделение) (логическое сложение) A v BИЛИ«Число 10 четное или отрицательно» - ИСТИНА Инверсия (inversio – переворачиваю) отрицание) ¬ A Ā НЕ НЕВЕРНО, ЧТО «Число 10 нечетное» – ЛОЖЬ «Число 10 – не отрицательное» - ИСТИНА Импликация (implico тесно связаны) ( логическое следование) А ВЕСЛИ … ТО …; КОГДА …. ТОГДА …. «Если число 10 – четное, то оно отрицательное» - ЛОЖЬ Эквивалентность (логическое равенство) А В … ТОГДА И ТОЛЬКО ТОГДА, КОГДА … «Число 10 – четное тогда и только тогда, когда оно отрицательное» - ЛОЖЬ Угринович Стр

23 Таблица истинности таблица определяющая значение сложного высказывания при всех возможных значениях простых высказываний

24 Таблица истинности для конъюнкции (умножение) АВА^ВиА^Ви Вывод: Вывод: Результат будет истинным тогда и только тогда, когда оба исходных высказывания истинны

25 Таблицаистинностидля дизъюнкции (сложение) Таблица истинности для дизъюнкции (сложение) АВА v В или Вывод Вывод : Результат будет ложным тогда и только тогда, когда оба исходных высказывания ложны, и истинным во всех остальных случаях

26 Таблицаистинностидляинверсии (отрицание) Таблица истинности для инверсии (отрицание) А Ā Вывод Вывод : Результат будет ложным, если исходное высказывание истинно, и наоборот.

27 Таблицаистинностидля импликации (следование) Таблица истинности для импликации (следование) АВА В Вывод Вывод : Результат будет ложным тогда и только тогда, когда из истинного основания (А) следует ложное следствие (В)

28 Таблицаистинностидля эквивалентности (равенство) Таблица истинности для эквивалентности (равенство) АВА В Вывод Вывод : Результат будет истинным тогда и только тогда, когда оба высказывания одновременно либо ложны, либо истинны

29 Если составное высказывание (логическую функцию) выразить в виде формулы, в которую войдут логические переменные и знаки логических операций, то получится ЛОГИЧЕСКОЕ ВЫРАЖЕНИЕ истина ложь

30 Порядок выполнения логических операций: Действия в скобках Инверсия (отрицание ) Конъюнкция (умножение И ) Дизъюнкция (сложение ИЛИ ) Импликация (следование ) Эквивалентность (равенство )

31 Решение задач Семакин ч.2,стр Мая Повторяем

32 Таблица истинности для конъюнкции (умножение) АВА^ВиА^Ви Вывод: Вывод: Результат будет истинным тогда и только тогда, когда оба исходных высказывания истинны

33 Таблицаистинностидля дизъюнкции (сложение) Таблица истинности для дизъюнкции (сложение) АВА v В или Вывод Вывод : Результат будет ложным тогда и только тогда, когда оба исходных высказывания ложны, и истинным во всех остальных случаях

34 Таблицаистинностидляинверсии (отрицание) Таблица истинности для инверсии (отрицание) АĀ Вывод Вывод : Результат будет ложным, если исходное высказывание истинно, и наоборот.

35 Таблицаистинностидля импликации (следование) Таблица истинности для импликации (следование) АВА В Вывод Вывод : Результат будет ложным тогда и только тогда, когда из истинного основания (А) следует ложное следствие (В)

36 Таблицаистинностидля эквивалентности (равенство) Таблица истинности для эквивалентности (равенство) АВА В Вывод Вывод : Результат будет истинным тогда и только тогда, когда оба высказывания одновременно либо ложны, либо истинны

37 Импликация (Следование) АВА В когда из истины следует ложь Вывод Вывод: Результат будет ложным тогда и только тогда, Пример

38 Логическая операция ИМЛИКАЦИЯ 4. Операция, выражаемая связками ЕСЛИ..., ТО, ИЗ... СЛЕДУЕТ,... ВЛЕЧЕТ..., называется импликацией (лат. implico тесно связаны) и обозначается знаком ®. Высказывание А ® В ложно тогда и только тогда, когда А истинно, а В ложно. Каким же образом импликация связывает два элементарных высказывания? Покажем это на примере высказываний: данный четырёхугольник квадрат (А) иоколо данного четырёхугольника можно описать окружность (В). Рассмотрим составное высказывание А ® В, понимаемое как если данный четырёхугольник квадрат, то около него можно описать окружность. Есть три варианта, когда высказывание А ®В истинно: 1.А истинно и В истинно, то есть данный четырёхугольник квадрат, и около него можно описать окружность; 1.А ложно и В истинно, то есть данный четырёхугольник не является квадратом, но около него можно описать окружность (разумеется, это справедливо не для всякого четырёхугольника); 1.A ложно и B ложно, то есть данный четырёхугольник не является квадратом, и около него нельзя описать окружность. Ложен только один вариант: А истинно и В ложно, то есть данный четырёхугольник является квадратом, но около него нельзя описать окружность.

39 Вопрос 1 1)Операция, соответствующая связке ИЛИ называется………….. 2)Обозначается…… 3)Истинна тогда……

40 Вопрос 2 1)Операция, соответствующая союзу И называется………….. 2)Обозначается…… 3)Истинна тогда……

41 Вопрос 3 1)Операция, соответствующая связкамЕСЛИ..., ТО, ИЗ... СЛЕДУЕТ,... ВЛЕЧЕТ..., называется………….. 2)Обозначается…… 3)Ложь тогда……

42 Вопрос 4 1)Операция, соответствующая связкамтогда и только тогда, "необходимо и достаточно,... равносильно..., называется………….. 2)Обозначается…… 3)Истинна тогда……

43 6_1 Обозначьте простые высказывания логическими переменными А и В и запишите логическую операцию 1.Марина старше Светы. И Оля старше Светы А= Марина старше Светы; В= Оля старше Светы А И В А^B – это конъюнкция

44 2. Половина класса изучает английский язык или немецкий А= Одна половина класса изучает английский язык В= Вторая половина – немецкий А ИЛИ В А+B – это дизъюнкция 6_2 Обозначьте простые высказывания логическими переменными А и В и запишите логическую операцию

45 6_3 Обозначьте простые высказывания логическими переменными А и В и запишите логическую операцию 3. В кабинете есть учебники. В кабинете есть справочники. А= В кабинете есть учебники В= В кабинете есть справочники А И В А*B – это конъюнкция

46 6_4 Обозначьте простые высказывания логическими переменными А и В и запишите логическую операцию 4. Слова в этом предложении начинаются на букву Ч. Слова в этом предложении начинаются на букву А. А= Слова в этом предложении начинаются на букву Ч В= Слова в этом предложении начинаются на букву А А ИЛИ В А+B – это дизъюнкция

47 6_5 Обозначьте простые высказывания логическими переменными А и В и запишите логическую операцию 3. Часть туристов любит чай. Остальные туристы любят молоко А= Часть туристов любит чай В= Остальные туристы любят молоко А И В А*B – это конъюнкция

48 6_6 Обозначьте простые высказывания логическими переменными А и В и запишите логическую операцию 3. Синий кубик меньше красного. Синий кубик меньше зеленого А= Синий кубик меньше красного В= Синий кубик меньше зеленого А И В А*B – это конъюнкция

49 6_7 Обозначьте простые высказывания логическими переменными А и В и запишите логическую операцию 3. Х=3, Х>2 А= Х=3. В= Х>2 А И В А*B – это конъюнкция

50 Построение таблиц истинности Для решения логического выражения необходимо построить таблицу истинности. Это таблица, в которой по действиям показано, какие значения принимает логическое выражение при всех возможных наборах значений логических переменных.

51 Порядок выполнения логических операций: Действия в скобках Инверсия (отрицание ) Конъюнкция (умножение И ) Дизъюнкция (сложение ИЛИ ) Импликация (следование ) Эквивалентность (равенство )

52 Правила построения таблиц истинности Установить последовательность выполнения логических операций Найти количество строк в таблице (по формуле 2^n, где n – количество переменных Найти количество столбцов = кол-во переменных + количество операций (действий) Построить таблицу, указывая названия столбцов и возможные наборы значений исходных логических переменных Заполнить таблицу по столбцам

53

54 Доказать истинность высказывания

55 Построение таблицы истинности с помощью логических функций в Excel Используются логические функции И ИЛИ НЕ и ЕСЛИ ЗАДАНИЕ 1. Постройте таблицы истинности для дизъюнкции, отрицания. 2. Постройте таблицу истинности для функции

56 Решение задач Задача 1 Это составное высказывание состоит из простых высказываний: А = «Петя поедет в деревню» В = «Будет хорошая погода» С = «Он пойдет на рыбалку» Записываем высказывание в виде логического выражения, учитывая порядок действий F = A ^ (B C) Записать в виде логического выражения следующее высказывание: «Летом Петя поедет в деревню и, если будет хорошая погода, то он пойдет на рыбалку»

57 Задача 2 Записать логическое выражение, которое принимает значение true при выполнении указанных условий и значение false в противном случае: каждое из чисел А и В больше 500; хотя бы одно из трех целых чисел делится на 5; каждое из трех заданных целых чисел делится на 3 и оканчивается нулем. A>500 и B>500 АvBvC A&B&CA&B&C

58 Задача 3 Записать логическое выражение для фразы: Если для солнечной погоды необходимо отсутствие дождя, то для того, чтобы пошел дождь, достаточно, чтобы погода была пасмурной и безветренной. (С Д) (П& В Д)

59 Задача 4 Вычислить значения логического выражения, если х и у натуральные числа: (1/х>х) and not(1+x 2 >0) or (132

60 Задача 5 Доказать истинность высказывания Высказывание истинно, так как истинно исходное выражения при любых значениях логических переменных X и Y

61 Задача 6 Докажите равносильность логических выражений (Отрицание дизъюнкции = конъюнкции отрицаний – правило Моргана) XYX+YNOT(X+Y)NOT(X)NOT(Y)NOT(X) & NOT(Y) Логические выражения равносильны, так как в таблице истинности значения в последних столбцах совпадают

62 Задания из ЕГЭ Ответы A9 ->2; A10->1; A11->4

63 Задания из ЕГЭ Ответы 2) Для какого слова истинно высказывание ¬ (Первая буква слова согласная –> (Вторая буква слова гласная \/ Последняя буква слова гласная)) 1) ГОРЕ 2) ПРИВЕТ 3) КРЕСЛО 4) ЗАКОН

64 Задания из ЕГЭ Ответы 3) Укажите, какое логическое выражение равносильно выражению ¬ (¬A /\ B) \/ ¬C. 1) ¬A \/ B \/ ¬C 2) ¬A \/ ¬B \/ ¬C 3) A \/ ¬B \/ ¬C 4) A \/ B \/ ¬C

65 Задания из ЕГЭ Ответы Решение: Используя правило де Моргана единственный ответ 4). Укажите, какое логическое выражение равносильно выражению ¬(A \/ ¬ B \/ C) 1)¬A \/ B \/ ¬C2)A /\ ¬B /\ C 3)¬A \/ ¬B \/ ¬C4)¬A /\ B /\ ¬C