|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
|
|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Предмет и значение науки логикиСтр 1 из 8Следующая ⇒
Содержание 1. Предмет и значение науки логики......................................................................................................................... 4 2. Логические задачи. Табличный способ решения................................................................................... 4 3. Элементы логики высказываний....................................................................................................................... 9 4. Логические операции.................................................................................................................................................... 10 Упражнения.................................................................................................................................................................................. 13 Самостоятельная работа №1............................................................................................................................................... 14 5. Таблицы истинности.................................................................................................................................................... 14 Упражнения.................................................................................................................................................................................. 15 6. Решение логических задач с помощью таблиц истинности............................................... 15 Самостоятельная работа №2............................................................................................................................................... 17 7. Основные законы логики......................................................................................................................................... 18 Упражнения.................................................................................................................................................................................. 19 8. Решение логических задач..................................................................................................................................... 19 Составление логического уравнения (формулы) и приведение его к нормальной форме. ..... 20 Упражнения.................................................................................................................................................................................. 21 Самостоятельная работа №3............................................................................................................................................... 22 Составление логического уравнения и решение его с помощью ЭВМ................................................ 22 Решение задач с помощью кругов Эйлера и с помощью графов............................................ 24 Решение с помощью кругов Эйлера.. .......................................................................................................................... 24 Решение с помощью графов.. .......................................................................................................................................... 25 Задания для самостоятельного выполнения........................................................................................... 27 Экзаменационные и олимпиадные логические задачи (ДВГУ, 1995 г.).................................. 31 Приложение 1............................................................................................................................................................................ 32 Задания для самостоятельных работ.............................................................................................................................. 32 Самостоятельная работа №1............................................................................................................................................. 32 Самостоятельная работа №2............................................................................................................................................. 33 Самостоятельная работа №3............................................................................................................................................. 34 Некоторые ответы и решения............................................................................................................................................. 35 Приложение 2............................................................................................................................................................................ 37 Логические задачи, составленные учащимися лицея №41.................................................................................. 37 Приложение 3............................................................................................................................................................................ 38 Решение задачи (дистанционная заочная олимпиада по решению логических и математических задач, ДВГУ, 2002 г.)............................................................................................................................................................................................. 38 Приложение 4 (Сценарий проведения игры «Сильное звено».).................................................... 40 Литература.................................................................................................................................................................................. 41 Предмет и значение науки логики Логика – одна из древнейших наук. Более 2300 лет назад древнегреческий философ Аристотель впервые систематизировал формы и правила мышления, тем самым, заложив основы науки логики. Впоследствии его основополагающие трактаты по логике были объединены под названием «Органон». Логика Аристотеля носит название формальной логики. Логика (от греческого logos – слово, понятие, рассуждение, разум) или формальная логика – наука о законах и формах правильного мышления. Основной принцип логики гласит, что правильность рассуждения определяется только его логической формой или структурой и не зависит от конкретного содержания входящих в него утверждений. Первые идеи «о математизации» логики появились в XVII в. Первоначально математическая логика рассматривалась как базис для логического обоснования различных областей математики. Большой вклад в становление и развитие математической логики внесли Аугустус де Морган (1806-1871), Уильям Стенли Джевонс (1835-1882), Платон Сергеевич Порецкий (1846-1907), Чарлз Сандерс Пирс (1839-1914) и др. Отцом математической логики по праву считается английский математик XIX в. Джордж Буль (1815 – 1864), его именем назван раздел математической логики – булева алгебра. Сегодня математическая (символическая) логика находит применение во многих областях, в частности, в кибернетике, теории электронных вычислительных машин, теории алгоритмов, электронике. В ЭВМ информация подвергается не только арифметической, но и логической обработке. Основу работы логических схем и устройств ЭВМ составляет специальный математический аппарат - раздел математической логики, называемый алгеброй логики. Математическая логика рассматривает схематизированные и в известной степени идеализированные понятия. В логических задачах исходными данными являются не только числа, но и сложные, иногда весьма запутанные высказывания. Во многих случаях для решения логических задач необходим компьютер. Умение грамотно использовать логические операции повышает эффективность программирования.
Задача 2. Коля, Боря, Вова и Юра заняли первые четыре места в спортивном соревновании. На вопрос, какие места они заняли, они ответили: 1) " Коля не занял ни первое, ни четвертое места". 2) «Боря занял второе место». 3) «Вова не был последним». Какое место занял каждый мальчик? Решение. По условию:
Так как второе место занял Боря, то больше никто из мальчиков не мог его занять, а также это значит, что Боря не занял ни одно из других мест:
Отсюда следует, что Коля занял третье место и, значит, никто другой его не занял:
Значит, четвертое место занял Юра, и, следовательно, он не занял первое, т.е. - первое место занял Вова:
Ответ. Места распределились следующим образом: первое - Вова, второе - Боря, третье-Коля, четвертое - Юра. Задача 3. В симфонический оркестр приняли на работу трех музыкантов – Брауна, Смита и Вессона, умеющих играть на скрипке, флейте, альте, кларнете, гобое и трубе. Известно, что: 1) Смит - самый высокий; 2) играющий на скрипке меньше ростом играющего на флейте; 3) играющие на скрипке и флейте и Браун любят пиццу; 4) когда между альтистом и трубачом возникает ссора, Сит мирит их; 5) Браун не умеет играть ни на трубе, ни на гобое. На каких инструментах играет каждый из музыкантов, если каждый владеет двумя инструментами? Решение. Так как музыкантов трое, инструментов шесть и каждый владеет только двумя инструментами, получается, что каждый музыкант играет на инструментах, которыми остальные не владеют. Составим таблицу и отразим в ней условия задачи. Из условия 4 следует, что Смит не играет ни на альте, ни на трубе, а из условий 3 и 5, что Браун не умеет играть на скрипке, флейте, трубе и гобое. Следовательно, инструменты Брауна - альт и кларнет. Значит, на альте и кларнете никто больше не играет.
Из таблицы видно, что на трубе может играть только Вессон. Из условий 1 и 2 следует, что Смит не скрипач. Т.к. на скрипке не играет ни Браун, ни Смит, то скрипачом является Вессон. Получаем таблицу:
Из этой таблицы видно, что на флейте и гобое может играть только Смит. Ответ: Браун играет на альте и кларнете, Смит - на флейте и гобое, Вессон - на скрипке и трубе.
Задача 4. Три одноклассника - Влад, Тимур и Юра встретились спустя 10 лет после окончания школы. Выяснилось, что один из них стал врачом, другой - физиком, а третий - юристом. Один увлекся туризмом, другой - бегом, третий - регби. Юра сказал, что, на туризм ему не хватает времени, хотя его сестра - единственный врач в семье, заядлый турист. Врач сказал, что он разделяет увлечение коллеги. Забавно, но у двоих из друзей в названиях их профессий и увлечений не встречается ни одна буква их имен. Кто чем любит заниматься в свободное время и у кого какая профессия? Решение. Исходные данные разбиваются на тройки (имя - профессия - увлечение). Из слов Юры ясно, что он не врач и он не увлекается туризмом.
Буква «а», присутствующая в слове «врач», указывает на то, что Влад тоже не врач, следовательно врач - Тимур. В его имени есть буквы «т» и «р», встречающиеся в слове «туризм», следовательно, второй из друзей, в названиях профессии и увлечения которого не встречается ни одна буква его имени, - Юра. Юра не юрист и не регбист (в его имени есть буквы «ю» и «р». Получаем окончательную таблицу:
Задача 5. Три товарища — Иван, Дмитрий, Степан преподают различные предметы (химию, биологию, физику) в школах Москвы, Ленинграда и Киева. Известно: 1) Иван работает не в Москве, а Дмитрий не в Ленинграде; 2) москвич преподает не физику; 3) тот, кто работает в Ленинграде, преподает химию; 4) Дмитрий преподает не биологию. Какой предмет и в каком городе преподает каждый из товарищей? Решение. Составим таблицу и отразим в ней условия 1 и 4:
Далее рассуждаем: т.к. Дмитрий не живет в Ленинграде, то, согласно условию 3, он не преподает химию. Значит, Дмитрий преподает физику:
Согласно условию 2 - Дмитрий не москвич (преподает физику), а по условию 1 – не ленинградец, значит он из Киева:
В результате дальнейшего заполнения получаем итоговую таблицу:
Ответ: Иван живет в Ленинграде, преподает химию; Дмитрий – в Киеве, физику; Степан – в Москве, биологию. Задача 6. Три дочери писательницы Дорис Кей - Джуди, Айрис и Линда тоже очень талантливы. Они приобрели известность в разных видах искусств - пении, балете и кино. Все они живут в разных городах, поэтому Дорис часто звонит им в Париж, Рим и Чикаго. Известно, что: 1) Джуди живет не в Париже, а Линда — не в Риме; 2) парижанка не снимается в кино; 3) та, кто живет в Риме, певица; 4) Линда равнодушна к балету. Где живет Айрис и какова ее профессия? Решение. Задача аналогична предыдущей. Самостоятельно составьте таблицу и отразите в ней все условия. Ответ: Айрис балерина. Живет в Париже.
Рассмотрим такую задачу: Задача 7. Разбирается дело Батончика, Ленчика и Пончика. Кто-то из них нашел и утаил клад. На следствии каждый из них сделал два заявления: a) Батончик: я не делал этого, это Пончик; b) Ленчик: Пончик невиновен. Виноват Батончик; c) Пончик: Я не делал этого. Ленчик тоже. Суд установил, что один из них дважды солгал, другой дважды сказал правду, третий один раз солгал, один раз сказал правду. Кто из них утаил клад? Эту задачу решим немного позже, после того, как познакомимся с основами логики высказываний (булевой алгебры).
Логические операции 1) Инверсия (операция отрицания или логическое отрицание, НЕ). Обозначается ù, `. Если А - истинное высказывание, то `А – ложное высказывание, и наоборот.
2) Конъюнкция (логическое умножение, соответствует союзу И). Обозначается Ù, × , & , математическим знаком умножения или опуская его. Например: С = «Солнце светит и нет дождя». Обозначим А = «Солнце светит», В= «нет дождя». Тогда высказывание С можно записать: А Ù В (или А& В, А× В, АВ).
3) Дизъюнкция (логическое сложение, ИЛИ), имеет два различных значения. Следует различать исключающее «или» и неисключающее «или».
В русском языке союз «или» используется в двояком смысле. Например, в предложении «Обычно в 8 вечера я смотрю телевизор или пью чай» союз «или» взят в неисключающем (объединительном) смысле, так как вы можете только смотреть телевизор или только пить чай, но вы можете также пить чай и смотреть телевизор одновременно, потому что мама у вас нестрогая. Такая операция называется нестрогой дизъюнкцией или просто дизъюнкцией. (Если бы мама была строгая, то она разрешила бы или только смотреть телевизор, или только пить чай, но не совмещать прием пищи с просмотром телепередач.) В высказывании «Данный глагол I или II спряжения» союз «или» используется в исключающем (разделительном) смысле.Такаяоперация называется строгой дизъюнкцией. Примеры строгих и нестрогих дизъюнкций:
а) Операция дизъюнкция (логическое сложение, нестрогая дизъюнкция), соответствует неисключающему ИЛИ, обозначается Ú , +.
Таким образом, простая дизъюнкция АÚ В (А + В) ложна тогда и только тогда, когда ложны оба высказывания А и В. б) Для высказывания, соответствующего исключающему ИЛИ (строгая дизъюнкция), используется словосочетание или…, или (либо…, либо). Строгая дизъюнкция обозначается А" В.
Строгая дизъюнкция истинна только тогда, когда одно высказывание истинно, а другое ложно.
4) Импликация. Выражается словосочетанием «если … то». Импликация А ® В истинна всегда, за исключением случая, когда А истинно, а В ложно. Таблица истинности импликации имеет следующий вид:
( Из опыта : Операция импликации (логического следования) является наиболее сложной для учащихся, так как она самая «формально определенная» и не подкрепляется «здравым смыслом». В процессе ее изучения имеет смысл поговорить о формальном исполнителе и его отличии от неформального.) Примеры импликаций: 1) Если клятва дана, то она должна выполняться. 2) Если число делится на 9, то оно делится на 3. В логике допустимо рассматривать и бессмысленные с житейской точки зрения высказывания. Приведем примеры суждений, которые не только правомерно рассматривать в логике, но и которые к тому же имеют значение «истина»; 1) Если коровы летают, то 2 + 2 = 5. 2) Если я — Наполеон, то у кошки четыре ноги. Объяснить операцию импликацию можно, например, следующим образом. Пусть даны высказывания: А = На улице дождь. В = Асфальт мокрый. А®В = «Если на улице дождь, то асфальт мокрый.» Тогда, если идет дождь (А = 1) и асфальт мокрый (В = 1), то это правильно. Но если вам скажут, что на улице идет дождь (А = 1), а асфальт остается сухим (В = 0), то вы посчитаете это ложью. А вот когда дождя на улице нет (А = 0), то асфальт может быть и сухим, и мокрым (например, только что проехала поливальная машина).
5) Операция эквиваленция обозначается знаками «, =, Û. Сложное высказывание А«В
Сводная таблица логических операций (заполняется учащимися самостоятельно):
Ниже приведена таблица логических операций и их перевода на естественный язык.
Приоритет выполнения операций: при отсутствии скобок первой всегда выполняется операция отрицания, затем конъюнкция, дизъюнкция, импликация и в последнюю очередь эквиваленция.
Упражнения. 1. Даны два высказывания: А={Число 5 - простое}, В={Число 4 - нечетное}, Очевидно, что А=1, В=0. В чем заключаются высказывания: а) Ā, б) `В, в) АВ, г) А+В д) А®В Какие из высказываний а) – г) истинны? Составьте таблицы истинности. 2. Найдите значения выражений: а) (1 + 1) Ú (1 + 0); б) ((1 + 0) + 1) + 1; в) (А + 1) + (В + 0); г) (0 Ù 1) Ù 1; д) 1 Ù (1 Ù 1) Ù 1; е) ((1 Ú 0) Ù (1 Ù 1) Ù (0 Ú 1); ж) ((1 Ù А) Ú (В Ù 0)) Ú 1; з) ((1 Ù 1) Ú 0) Ù (0 Ú 1); и) ((0 Ù 0) Ú 0) Ù (1 Ú 1); к) ((0 × 1) + (1 + 1)) × 1. 3. Переведите на язык алгебры логики высказывания: I. 1) «Я поеду в Москву, и если встречу там друзей, то мы интересно проведем там время» 2) «Если я поеду в Москву и встречу там друзей, то мы интересно проведем там время» 3) «Неверно, что если дует ветер, то солнце светит только тогда, когда нет дождя». 4) «Если будет солнечная погода, то ребята пойдут в лес, а если будет пасмурно, то пойдут в кино» 5) «Неверно, что если погода пасмурная, то дождь тогда и только тогда, когда нет ветра». 6) «Если урок по информатике будет интересным, то ни Миша, ни Света, ни Вика не будут смотреть в окно»
1) М × (В ® И); 2) (М × В) ® И; 3) В ® С ®`Д;
II. 1) «Вам никогда не удастся создать мудрецов, если будете убивать в детях шалунов» (Ж.Руссо). 2) «Чтение художественной литературы – неоценимый источник познания жизни и законов ее борьбы». 3) Согласно легенде, право считаться родиной Гомера оспаривали семь городов: Смирна, Хиос, Колофон, Саламин, Родос, Аргос, Афины. 4) «Мудрость – это способность предвидеть отдаленные последствия совершаемых действий, готовность пожертвовать сиюминутной выгодой ради больших благ в будущем и умение управлять тем, что управляемо, не сокрушаясь из-за того, что неуправляемо» (Ракофф). 5) «Кто утратил стыд, того нужно считать погибшим» (Плавт). 6) «Верность друга нужна и в счастье, в беде же она совершенно необходима».
4. Являются ли высказываниями русские народные пословицы и поговорки? Приведите примеры. ( Из опыта: Объявляется конкурс «Знаешь ли ты пословицы, которые являются высказываниями». Победителей обычно несколько, поощряются оценками и поощрительными аплодисментами одноклассников) 5. На конкурс авторских логических задач принимаются письменные работы учащихся (условие задачи + решение) в течение учебного года.
Самостоятельная работа №1. (примерные задания в приложении 1, некоторые решения и ответы в приложении 2) 1) Решить логическую задачу табличным способом; 2) Записать сложные высказывания на языке алгебры логики; 3) Найти значение выражения.
Таблицы истинности Итак, сложное высказывание принимает значение 1 или 0 в зависимости от значений простых высказываний, входящих в него. Таблицу, показывающую, какие значения принимает сложное высказывания при всех сочетаниях (наборах) значений входящих в него простых высказываний, называют таблицей истинности сложного высказывания .
Составим таблицу истинности сложного высказывания А & `В ® А. Для этого: 1) составим таблицу всевозможных значений переменных А и В, входящих в данную формулу; 2) затем выпишем и проанализируем все подформулы:
Из полученной таблицы видно, что значения формулы А`В ® А совпадают со значениями формулы А. Такие формулы называются равносильными. Для обозначения равносильности используют обычно знак равенства.
Для составления таблицы истинности сложного высказывания, в которое входит более двух переменных, можно воспользоваться следующим алгоритмом: 1. Подсчитать n - количество переменных в формуле; 2. Определить число строк в таблице m= 2n. 3. Определить количество столбцов в таблице: число переменных плюс число операций. 4. Выписать наборы входных переменных с учетом того, что они представляют собой натуральный ряд n–разрядных двоичных чисел от 0 до 2n -1. 5. Провести заполнение таблицы истинности по столбцам, выполняя логические операции в соответствии приоритета операций.
Пример. Построить таблицу истинности для формулы F=A ® B& C
Упражнения. 1. Проверьте равносильность следующих формул с помощью таблиц истинности: 1) А (А + В) = А 2) А + АВ = А 3) А ® В = Ā + В 4) А ® В = `А ®`В 5) 6)
2. Определите значение формулы: F= ((С+В)®В) × (АВ) ®В.
Самостоятельная работа №2. 1) Проверить равносильность формул; 2) Составить таблицу истинности для формулы; 3) Решить задачу. Основные законы логики Существует 2 способа определения истинного значения формулы. Первый – с помощью таблиц истинности, а второй – с помощью приведения формулы к нормальной форме. Формула имеет нормальную форму, если в ней отсутствуют знаки эквиваленции, импликации, исключающей дизъюнкции, двойного отрицания, при этом знаки отрицания находятся только при переменных. Приведение формулы к нормальной форме основывается на применении основных формул алгебры логики.
Доказать законы можно, упросив левую (правую) часть тождества.
Справедливы также равенства:
Эти законы, а также равенства записанные ниже, можно доказать с помощью таблиц истинности, выписав все входящие в формулу подформулы. При преобразовании логических выражений, содержащих операции строгой дизъюнкции, импликации и эквиваленции, удобно использовать равенства:
Пример. Доказать тождество: ( А + В + С )( А +`В + С )(А +`В +`С )(`А +`В + С )(`А +`В +`С ) =А`В +`ВС
( А + В + С ) ( А +`В + С ) (А +`В +`С ) ( `А +`В + С ) ( `А +`В +`С ) Выполним действия, применяя логические законы: 1) ( ( А + С ) + В ) ( ( А + С ) +`В ) = А + С (по закону исключения) 2) ( (`А +`В )+С ) ( (`А +`В ) +`С ) = `А +`В (по закону исключения) 3) ( А + С ) ( ( А +`В +`С ) = (А + А`В + А`С + АС) + `ВС +`СС = А + `ВС
= А (з-н поглощения)
4) ( А + `ВС ) (`А +`В ) = А`В + (А`ВС +`ВС) = А`В +`ВС (по закону поглощения)
Упражнения. 1. С помощью таблиц истинности докажите 9-12 законы алгебры логики. 2. Упростите формулы, используя законы склеивания: 1) 2) A B C + B C; 3) (`А +`В + С )(`А + В C).
3. Упростите формулы, используя законы поглощения: 1) A + A B + A B C + A D F; 2) A B+A B C+A B D; 3) A (A+B) (A+C); 4) A B (A C+A B).
4. Упростите формулы, используя законы алгебры логики: 1) A `C + C ( B +`C) + ( A +`B) C; 2) A ( B +`C) + `A B;
3)
4) A + B + C +`B + (A +`B + C `A + B + C) + `A `B;
5) (А®В)«(`А®(`В + С));
6) (А + В) ®(`В + С).
Решение логических задач
Разнообразие логических задач очень велико. Способов их решения тоже немало. Но наибольшее распространение получили следующие способы: 1) с помощью таблиц истинности; 2) путем составления логического уравнения (формулы) и приведения его к нормальной форме; 3) путем составления логического уравнения и решения его с помощью ЭВМ. Выбор метода решения задачи определяется самостоятельно, учитывая формулировку задачи. Следует отметить, что метод, основанный на построении и анализе таблиц истинности, имеет ограниченное применение при увеличении количества переменных, поскольку усложняется построение и анализ этой таблицы.
Упражнения Задача 1. Внимание Андрея, Дениса и Марата привлек промчавшийся мимо них автомобиль. – Это английская машина марки «Феррари», — сказал Андрей. – Нет, машина итальянская марки «Понтиак», — возразил Денис. – Это «Сааб», и сделан он не в Англии, –сказал Марат. Оказавшийся рядом знаток автомобилей сказал, что каждый из них прав только в одном из двух высказанных предположений. Какой же марки этот автомобиль и в какой стране изготовлен?
Решение: Рассмотрим простые высказывания: А= «Английская машина», F= «Феррари», I= «Итальянская», Р= «Понтиак», С= «Сааб». Запишем на языке логики условие задачи, учитывая высказывания мальчиков и то, что верно указана либо страна либо марка автомобиля: 1) A" F = A`F +`A F = 1 (Слова Андрея) 2) I" P = I`P +`I P=1 (Слова Дениса) 3) `A" C =`A`C + AC=1 (Слова Марата) Если все эти истинные высказывания перемножить, то получится истинное сложное высказывание. (A`F +`A F) & (I`P +`I P) & (`A`C + AC) = 1 Учитывая, что AI=0; FP=0; PC=0; FC=0 (машина не может быть одновременно итальянской и английской, «Феррари», «Понтиак» и «Сааб»),. получаем выражение: I`A F`P`C = 1 Делаем вывод: машина «Феррари», изготовлена в Италии. Популярное:
|
Последнее изменение этой страницы: 2016-07-13; Просмотров: 1707; Нарушение авторского права страницы
1
Решение: 
4) (С ® Л) × (`С ® К); 5) П ® (Д « `В); 6) И ® `М × `С × `В
`А +`В = А В
А + В = Ā × `В
9. Законы
де Моргана
A B C+`А B C; 
(`А+C) A C ( B +`C) B C; 