Элементы логики на уроках информатики

Что такое алгебра логики? Что такое алгебра логики? МОУ «Гимназия №5»

ВВЕДЕНИЕ ФОРМЫ МЫШЛЕНИЯ Задачи 1 Задачи 2 Задачи 3 Задачи 4 Задачи 5 АЛГЕБРА ВЫСКАЗЫВАНИЙ Логическое отрицание (инверсия) Задачи №6 Задачи №7 Логическое умножение (конъюнкция) Логическое сложение (дизъюнкция) Импликация Эквивалентность Задачи №8 2

ВВЕДЕНИЕ ВВЕДЕНИЕ Логика (от греческого слова “logos” – слово, мысль, речь, разум)  ЛОГИКА – это наука о формах и способах мышления.      Начало исследований в области формальной логики было положено  работами Аристотеля в IV веке до н.э.  развиваться  применяющая            В  середине  XIX  века  возникла  и  начала  математическая  интенсивно  логика,  для  анализа  рассуждений  математические  средства  м  методы.  Именно  она  заложила  теоретические  основы  последующей  разработки  языков  программирования.     Одним  из  основных  разделов  математической  логики  является  алгебра  логики  высказываний),  основоположником  которой  был  английский  математик  Джордж  Буль  (1815­1864),  положивший  в  основу  своего  логического  учения методы алгебры (алгебра Буля).     (исчисление  3 Джордж Буль

Формы мышления Формы мышления Основными  формами  мышления  являются  понятие,  высказывание  и  умозаключение. ПОНЯТИЕ  –  это  форма  мышления,  фиксирующая  основные,  существенные  признаки  объекта,  которые  отличают  его  от  других  объектов. Понятие имеет две стороны: СОДЕРЖАНИЕ и ОБЪЕМ. Содержание понятия составляет совокупность существенных признаков  объекта, необходимых и достаточных для выделения данного объекта из  множества других объектов Объем понятия определяется совокупностью предметов, на которую оно  распространяется. Например,  Понятие Компьютер Содержание Универсальное электронное  устройство для автоматической  обработки информации Объем Совокупность (сотни миллионов) существующих в настоящее время  в мире компьютеров 4

Даже по этому короткому описанию компьютер трудно спутать с  другими объектами, например, с понятием «автомобиль» Понятие Автомобиль Совокупность (сотни миллионов) существующих в настоящее время  Объем в мире автомобилей Содержание Механизм, служащий для  перемещения по дорогам  и хранящимся в гараже 5

Свое  понимание  окружающего  мира  человек  формулирует  в  форме  высказываний (суждений, утверждений). Высказывание  может  быть  выражено  с  помощью  естественных  языков или формальных, например высказывание: «Два умножить на два  равно четырем» ­ на естественном  языке; «2?2=4» ­ на формальном, математическом языке. Логическое  высказывание  —  это  любoе  повествовательное  пpедлoжение,  в  oтнoшении  кoтopoгo  мoжно  oднoзначнo  сказать, истиннo oнo или лoжнo.  Например, предложение:  “6 — четное число” следует считать высказыванием, так как оно истинное.   “Рим — столица Франции”  тоже высказывание, так как оно ложное. “Ученик десятого класса”  ­ высказываниями не являются, т.к.  предложение ничего не утверждает об ученике  “Информатика — интересный предмет”­  использует слишком  неопределённое понятие “интересный предмет”.  6

Предложения  типа  “в  городе  A  более  миллиона  жителей”,  “у  него  голубые  глаза”  не  являются  высказываниями,  так  как  для  выяснения  их  истинности  или  ложности  нужны  дополнительные  сведения:  о  каком  конкретно  городе  или  человеке  идет  речь.  Такие  предложения называются высказывательными формами.  повествовательное  Высказывательная  форма  —  предложение, которое прямо или косвенно содержит хотя бы  одну  переменную  и  становится  высказыванием,  когда  все  переменные замещаются своими значениями.  это  Вопросительные  и  восклицательные  предложения  также  не  являются  высказываниями,  поскольку  говорить  об  их  истинности или ложности не имеет смысла. Любое высказывание рассматривается только  с одной точки зрения — является ли оно  истинным или ложным. 7

Заметим,  что  зачастую  высказывания.  трудно  установить  истинность  Например,  высказывание  “площадь  поверхности  Индийского  океана  равна  75  млн  кв.  км”  в  одной  ситуации  можно  посчитать  ложным, а в другой — истинным.  Ложным  —  так  как  указанное  значение  неточное  и  вообще  не  является постоянным.  Истинным  —  если  рассматривать  его  как  некоторое  приближение,  приемлемое на практике.  Иногда  истинность  того  или  иного  высказывания  является  относительной.  Истинность  высказываний  может  зависеть  от  взглядов людей, от конкретных обстоятельств и т.д.  Например, сегодня высказывание:«На моем компьютере установлен  современный  процессор  Pentium    ­  истинно,  но  пройдет  некоторое время и данное высказывание станет ложным. IV»  8

№1. Какие из предложений являются высказываниями? Определите их  З а д а ч и. истинность.  Число 6 –четное.  Посмотрите на доску.  Все роботы являются машинами.  У каждой лошади есть хвост.  Внимание!  Кто отсутствует?  Есть кошки, которые дружат с собаками.  Не все то золото, что блестит.  Х2 0 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. Некоторые люди являются художниками. 11. Выразите 1 час 15 минут в минутах. 12. Всякий моряк умеет плавать. 9

ВЫСКАЗЫВНИЕ ВЫСКАЗЫВАНИЕ общее общее частное частное единичное единичное Начинается со слов Начинается со слов (или можно начать): (или можно начать): все, всякий,  все, всякий,  каждый, ни один каждый, ни один Начинается со слов Начинается со слов (или можно начать): (или можно начать): некоторые,  некоторые,  большинство и т.п. большинство и т.п. Во всех других  Во всех других  случаях случаях «Все рыбы умеют плавать» «Некоторые  медведи ­ бурые» «Буква А ­ гласная» Пример2. Определить значения истинности для следующих высказываний: 10

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

№3. Какие из приведенных высказываниями являются общими?  З а д а ч и. Определите их истинность.  Не все книги содержат полезную информацию.  Кошка является домашним животным.  Все солдаты храбрые.  Не один внимательный человек не совершит оплошность.  Некоторые ученики двоечники.  Все ананасы приятны на вкус.  Мой кот страшный забияка.  Любой неразумный человек ходит на руках. 1. 2. 3. 4. 5. 6. 7. 8. Приведите примеры истинных и ложных высказываний (домашнее задание):  а) из арифметики;   в) из биологии;    д) из геометрии;    б) из физики;  г) из информатики;  е) из жизни.  12

№4. Установите, какие из следующих предложений являются логическими  высказываниями, а какие — нет (объясните почему):  а) “Солнце есть спутник Земли”;  б) “2+3х4”;  в) “сегодня отличная погода”;  г) “в романе Л.Н. Толстого “Война и мир” 3 432 536 слов”;  д) “Санкт­Петербург расположен на Неве”;  е) “музыка Баха слишком сложна”;  ж) “первая космическая скорость равна 7.8 км/сек”;  з) “железо — металл”;  и) “если один угол в треугольнике прямой, то треугольник будет  к) “если сумма квадратов двух сторон треугольника равна квадрату третьей,  тупоугольным”;  то он прямоугольный”.  ОТВЕТ: Являются высказываниями: а), г), д), ж), з), и), к); Не являются высказываниями: б); в);  е).  №5. Укажите, какие из высказываний предыдущего упражнения истинны, какие  —  ложны,  а  какие  относятся  к  числу  тех,  истинность  которых  трудно  или  невозможно установить.  ОТВЕТ: Истинные: д), з), к);  Можно рассматривать и как истинное, и как ложное в зависимости от требуемой  Истинность трудно установить: г);  ложные: а), и);  13 точности представления: ж).

Bысказывания, образованные из других высказываний с помощью логических  связок, называются составными.  Высказывания, не являющиеся составными, называются элементарными.  Употребляемые в обычной речи слова и словосочетания "не”, “и”, “или”,  “если... , то”, “тогда и только тогда” и другие позволяют из уже заданных  высказываний строить новые высказывания. Такие слова и словосочетания  называются логическими связками.  Так, например, из элементарных высказываний  “Петров — врач”, “Петров — шахматист”  при помощи связки  “и”  можно получить составное высказывание  “Петров — врач и шахматист”,  понимаемое как “Петров — врач, хорошо играющий в шахматы”.  При помощи связки “или” из этих же высказываний можно получить  составное высказывание “Петров — врач или шахматист”,  понимаемое в алгебре логики как “Петров или врач, или шахматист, или и врач  и шахматист одновременно”.  !    Истинность  или  ложность  получаемых  таким  образом  составных  высказываний  зависит  от  истинности  или  ложности  элементарных  высказываний.  14

№5. Определите значения истинности высказываний:  а) “наличия аттестата о среднем образовании достаточно для  поступления в институт”;  З а д а ч и. б) “наличие аттестата о среднем образовании необходимо для  поступления в институт”;  в) “если целое число делится на 6, то оно делится на 3”;  г) “подобие треугольников является необходимым условием их  равенства”;  д) “подобие треугольников является необходимым и достаточным  условием их равенства”;  е) “треугольники подобны только в случае их равенства”;  ж) “треугольники равны только в случае их подобия”;  з) “равенство треугольников является достаточным условием их  подобия”;  и) “для того, чтобы треугольники были неравны, достаточно, чтобы они  были неподобны”;  к) “для того, чтобы четырёхугольник был квадратом, достаточно, чтобы  его диагонали были равны и перпендикулярны”.  ОТВЕТ: Истинны: б), в), г), з), к), и);  ложны: а), д), е), ж).  15

Умозаключения позволяют на основе известных фактов, выраженных в  форме  высказываний,  получать  заключение,  т.е.  новое  знание.  Примером умозаключений могут быть геометрические доказательства. Например, если мы имеем суждение «Все углы треугольника равны»,  то  мы  можем  путем  умозаключения  доказать,  что  в  этом  случае  справедливо высказывание «Этот треугольник равносторонний». УМОЗАКЛЮЧЕНИЕ – это форма мышления, с помощью которой из  одного  или  нескольких  суждений  (высказываний)  может  быть  получено новое суждение (высказывание). Например,  из  двух  суждений  :  «Все  металлы  электропроводны»  и  Например, «Ртуть  является  металлом»  путем  умозаключения  делается  вывод,  что «Ртуть электропроводна». Приведите примеры умозаключений (домашнее задание). 16

АЛГЕБРА ВЫСКАЗЫВАНИЙ В  алгебре  высказываний  суждениям  (простым  высказываниям)  ставятся  в  соответствие  логические  переменные,  обозначаемые  прописными  буквами  латинского  алфавита,  которые  могут  принимать  лишь  два  значения:  «истина» (1) и «ложь» (0). Пусть через А обозначено высказывание “Тимур поедет летом на море”,  а через В — высказывание “Тимур летом отправится в горы”.  Тогда  составное  высказывание  “Тимур  летом  побывает  и  на  море,  и  в  горах”  можно  кратко записать как А и В.  Здесь “и” — логическая связка, А, В — логические переменные, которые могут принимать  только два значения — “истина” или “ложь”, обозначаемые, соответственно, “1” и “0”  А В “Тимур поедет летом на море”, “Тимур летом отправится в горы” И А и В 17 “Тимур летом побывает  на море и в горах

Каждая логическая связка рассматривается как  операция  над  логическими  высказываниями  и  имеет свое название и обозначение:  18

ЛОГИЧЕСКОЕ ОТРИЦАНИЕ (ИНВЕРСИЯ) Операция,  выражаемая  словом  “не”,  называется  операцией  логического  отрицания  и  обозначается  чертой  над  высказыванием  (или  знаком      ).  Высказывание    истинно,  когда  A  ложно,  и  ложно,  когда  A  истинно.  Пример.  “Луна — спутник Земли” (А); “Луна — не спутник Земли” (А).  ИНВЕРСИЯ  высказывание ложным и наоборот. (логическое  отрицание)  делает  истинное  Таблица истинности функции логического ОТРИЦАНИЯ x 0 1      1 0 19

З а д а ч и. №6. Определите, какие из высказываний (высказывательных форм) в  следующих парах являются отрицаниями друг друга, а какие нет:  а) “5<10”, “5>10”;  б) “10>9”, “10<=9”;  в) “мишень поражена первым выстрелом”, “мишень поражена вторым  выстрелом”;  г) “машина останавливалась у каждого из двух светофоров”, “машина не  останавливалась у каждого из двух светофоров”,  д) “человечеству известны все планеты Солнечной системы”, “в  Солнечной системе есть планеты, неизвестные человечеству”;  е) “существуют белые слоны”, “все слоны серые”;  ж) “кит — млекопитающее”, “кит — рыба”;  з) “неверно, что точка А не лежит на прямой а”, “точка А лежит на прямой  и) “прямая а параллельна прямой b”, “прямая a перпендикулярна прямой  а”;  b”;  к) “этот треугольник равнобедренный и прямоугольный”, “этот  треугольник не равнобедренный или он не прямоугольный”.  ОТВЕТ: Являются отрицаниями друг друга: б), г), д), к);  Не являются отрицаниями друг друга: а), в), е), ж), з), и).  20

№7. Сформулируйте отрицания следующих высказываний или  высказывательных форм:  З а д а ч и. а) “Эльбрус — высочайшая горная вершина Европы”;  б) “2>=5”;  в) “10<7”;  г) “все натуральные числа целые”;  д) “через любые три точки на плоскости можно провести окружность”;  е) “теннисист Кафельников не проиграл финальную игру”;  ж) “мишень поражена первым выстрелом”;  з) “это утро ясное и теплое”;  и) “число n делится на 2 или на 3”;  к) “этот треугольник равнобедренный и прямоугольный”;  л) "на контрольной работе каждый ученик писал своей ручкой".  ОТВЕТ: а) “Эльбрус – не высочайшая горная вершина Европы”;  б) “2<5”; в) “10>=7”;  з) “это утро не ясное или оно не теплое”  л) “не каждый ученик писал контрольную своей ручкой” (вариант: "кто­то  писал контрольную не своей ручкой"). 21

ЛОГИЧЕСКОЕ УМНОЖЕНИЕ (КОНЬЮНКЦИЯ) Операция, выражаемая связкой “и”, называется конъюнкцией (лат. conjunctio  — соединение) или логическим умножением и обозначается точкой "•"  (может также обозначаться знаками         или &).  Высказывание А•В истинно тогда и только тогда, когда оба высказывания А  и В истинны.  Например,  ложны.  Таблица истинности функции логического УМНОЖЕНИЯ высказывание “10 делится на 2 и 5 больше 3” истинно,  а высказывания “10 делится на 2 и 5 не больше 3”, “10 не делится на 2 и 5 больше 3”, “10 не делится на 2 и 5 не больше 3”  22 x 0 0 1 1 y 0 1 0 1 x·у 0 0 0 1

ЛОГИЧЕСКОЕ СЛОЖЕНИЕ (ДИЗЪЮНКЦИЯ) Операция, выражаемая связкой “или” (в неразделительном, неисключающем  смысле этого слова), называется дизъюнкцией (лат. disjunctio — разделение)  или логическим сложением и обозначается знаком v (или плюсом).  Высказывание А v В ложно тогда и только тогда, когда оба высказывания  А и В ложны.  Например, высказывание         “10 не делится на 2 или 5 не больше 3” ложно, а высказывания “10 делится на 2 или 5 больше 3”, “10 делится на 2 или 5 не больше 3”, “10 не делится на 2 или 5 больше 3”  истинны.  Таблица истинности функции логического СЛОЖЕНИЯ x 0 0 1 1 y 0 1 0 1 x v у 0 1 1 1 23

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

Покажем это на примере высказываний: “данный четырёхугольник — квадрат” (А)   “около данного четырёхугольника можно описать окружность” (В).  Рассмотрим составное высказывание А →В, понимаемое как  “если данный четырёхугольник квадрат, то около него можно описать окружность”.  Есть три варианта, когда высказывание А→В истинно:  и А истинно  В истинно А ложно   и  и  и  В истинно А ложно   В ложно  то есть данный четырёхугольник квадрат,  и около него можно описать окружность то есть данный четырёхугольник не является квадратом, но около него можно описать окружность  (разумеется, это справедливо не для всякого четырёхугольника) то есть данный четырёхугольник не является квадратом,  и около него нельзя описать окружность Ложен только один вариант: А истинно   и  В ложно  25 то есть данный четырёхугольник является квадратом,  но около него нельзя описать окружность

В обычной речи связка “если ..., то” описывает причинно­следственную связь между  высказываниями.  Но в логических операциях смысл высказываний не учитывается.  Рассматривается только их истинность или ложность.  Поэтому не надо смущаться “бессмысленностью” импликаций, образованных  высказываниями, совершенно не связанными по содержанию.  Например, такими: “если президент США — демократ, то в Африке водятся жирафы”, “если арбуз — ягода, то в бензоколонке есть бензин”.  26

ЭКВИВАЛЕНЦИЯ (ДВОЙНАЯ ИМПЛИКАЦИЯ)  Операция, выражаемая связками “тогда и только тогда”, "необходимо и  достаточно”, “... равносильно ...”, называется эквиваленцией или двойной  импликацией и обозначается знаком ↔ или ~ .  Высказывание А  совпадают.  Например,   ↔ В истинно тогда и только тогда, когда значения А и В  высказывания “24 делится на 6 тогда и только тогда, когда 24 делится на 3”, “23 делится на 6 тогда и только тогда, когда 23 делится на 3”  истинны,  ложны.  а высказывания “24 делится на 6 тогда и только тогда, когда 24 делится на 5”, “21 делится на 6 тогда и только тогда, когда 21 делится на 3”  27

Высказывания  А  и  В,  образующие  составное  высказывание  А  ↔  В,  могут  быть  совершенно не связаны по содержанию. Например:  “три больше двух” (А),  “пингвины живут в Антарктиде” (В).  Отрицаниями этих высказываний являются высказывания  “три не больше двух” (А ),  “пингвины не живут в Антарктиде” (В).  Образованные из высказываний А, В составные высказывания  A B↔  и А В↔   истинны,  а высказывания  ложны.  A В↔   и А↔B   28

Итак, нами рассмотрены пять логических операций:  отрицание, конъюнкция, дизъюнкция, импликация и эквиваленция.  Импликацию можно выразить через дизъюнкцию и отрицание:  А→ В = А v В. Эквиваленцию можно выразить через отрицание, дизъюнкцию и конъюнкцию:  А ↔ В = (А v В) • (А v В). Таким образом, операций отрицания,  дизъюнкции и конъюнкции достаточно,  чтобы описывать и обрабатывать логические высказывания.  Порядок выполнения логических операций задается круглыми скобками.  Но для уменьшения числа скобок договорились считать, что  1. операция отрицания (“не”),  2. конъюнкция (“и”),  3. дизъюнкция (“или”)  4. импликация. 29

№7. Определите значения истинности высказываний:  а) “наличия аттестата о среднем образовании достаточно для поступления   в  институт”;  З а д а ч и. б) “наличие аттестата о среднем образовании необходимо для поступления в  институт”;  в) “если целое число делится на 6, то оно делится на 3”;  г) “подобие треугольников является необходимым условием их равенства”;  д) “подобие треугольников является необходимым и достаточным условием  их равенства”;  е) “треугольники подобны только в случае их равенства”;  ж) “треугольники равны только в случае их подобия”;  з) “равенство треугольников является достаточным условием их подобия”;  и) “для того, чтобы треугольники были неравны, достаточно, чтобы они были  неподобны”;  к) “для того, чтобы четырёхугольник был квадратом, достаточно, чтобы его  диагонали были равны и перпендикулярны”.  ОТВЕТ: Истинны: б), в), г), з), к), и);  Ложны: а), д), е), ж).  30