Методические указания к выполнению лабораторных работ 1-3 по дисциплине «Математическая логика и теория алгоритмов»

А или В, но не обаЛибо А, либо В и С; А, разве что В и СЛибо А и В, либо С и DЕсли А, то В; В, если А; А, только, если В; А, только тогда, когда В; А достаточно для В; A, только при условии, что В; В необходимо для А; А, значит В; для В достаточно А; А влечет В; для А необходимо В; все А есть В; из А следует В; В, тогда, когда А 11 Продолжение табл.2 А эквивалентно В; А, если и только если В; А, тогда и только тогда, когда В; А необходимо и достаточно для В При переводе высказываний естественного языка на язык алгебры логики нужно выделить сначала элементарные высказывания и обозначить их символами так, чтобы по этим обозначениям можно было восстановить полный текст составного высказывания. Нужно стремиться к введению минимального количества элементарных высказываний, пытаясь выражать одни элементарные высказывания через другие. Покажем на примере, как осуществлять перевод выражений с естественного языка на язык алгебры логики и работать с полученными формулами. Пример: Мать принесла яблоки. Дети стали гадать, какие яблоки она принесла, и высказали ряд предположений: 1. Если яблоки будут сладкими, то для того, чтобы они были большими, достаточно, чтобы они были не зелеными. 2. Яблоки будут маленькими, если они не кислые, но зеленые. 3. Для того, чтобы яблоки были зелеными, необходимо, чтобы они были большими тогда и только тогда, когда они сладкие. Мать сказала, что эти высказывания можно свести к двум простейшим условиям, из которых истинно только одно. Кроме того, мать сказала, что яблоки, принесенные ее, либо кислые и маленькие, либо зеленые. Какие яблоки принесла мать? Решение: Выделим элементарные высказывания: C - сладкие; - большие; З - зеленые. Тогда - кислые; - маленькие. 12 Рассуждения (1-3) на языке алгебры логики будут представлены так 1. ; 2. ; 3. . Условия (1-3) должны выполняться одновременно, значит, должна быть истинной их конъюнкция . Приводим это выражение к минимальной ДНФ, пользуясь изложенными раннее правилами. = = Поскольку из двух простейших высказываний истинным является только одно, то для однозначной записи этого условия необходимо перейти от минимальной ДНФ к КНФ, пользуясь основными эквивалентностями алгебры логики . Так из двух простейших условий истинным может быть только одно, то это возможно только в том случае, если истинно первое условие и одновременно ложно второе или ложно первое условие и одновременно истинно второе: . Объединяя полученный результат с дополнительным условием, высказанным матерью , получаем: . 13 КОНТРОЛЬНЫЕ ВОПРОСЫ И ЗАДАНИЯ 1.Обсуждая приход в класс новичка, школьники высказывали ряд предположений: 1.1. Для того, чтобы новичок был добрым, достаточно, чтобы он был умным и сильным. 1.2. Если новичок силач, то он либо глупый, либо злой. 1.3. Если новичок умный, то для того чтобы он был добрым, необходимо, чтобы он был сильным. Учитель предложил свести эти высказывания к двум простейшим условиям, а из двух условий, как сказал учитель, выполнено только одно. Кроме того, учитель сказал: “Необходимое условие доброты – это ум. Значит, новичок умный, но слабый”. Каким был новичок? 2. Семья решила купить новый шкаф. Все хотели, чтобы шкаф был либо дубовый, либо березовый; либо желтый, либо коричневый; либо светлый, либо темный. Отцу дали рекомендации: 2.1. Ты можешь купить светлый шкаф, если только он будет березовым желтого цвета. 2.2. Если шкаф будет березовым, то светлый тон должен быть достаточным признаком желтой окраски. 2.3. Если шкаф будет коричневым, то для того, чтобы он был темным, необходимо, чтобы он был сделан из дуба. Все эти условия можно свести к двум простейшим. Отцом был куплен шкаф, который удовлетворял только одному из этих условий. Он поступил так, потому что хотел, чтобы шкаф был светлым и березовым или темным, но желтым. И это условие действительно оказалось выполненным. Какой шкаф был куплен? 3. По поводу приглашения гостей были высказаны следующие соображения: 3.1. Если мы пригласим Андрея, то Володю приглашать не надо. 14 3.2. Но Сережу можно пригласить только тогда, когда будет приглашен Володя. 3.3. А если мы пригласим Андрея с Володей, то Сережу пригласить нельзя. На следующий день было решено, что нужно сделать противоположное. Упростить новую инструкцию и свести ее к простейшим условиям. 4. В коробке лежат шары: большие и маленькие, красные и зеленые, темные и светлые. Из коробки надо достать шар, удовлетворяющий условиям: 4.1. Если шар светлый, то он может быть маленьким только тогда, когда он красный. 4.2. Шар может быть большим и светлым, если он зеленый. 4.3. Если шар большой, то для того чтобы он был зеленым, достаточно, чтобы он был темным. Свести эти условия к двум простейшим. 5. Мать попросила сына купить цветы: либо гвоздики, либо розы; либо бордовые, либо красные; либо светлые, либо темные. Кроме того, должны быть выполнены следующие условия: 5.1. Чтобы цветок был красным или гвоздикой, достаточно, чтобы он был темным. 5.2. Цветок может быть бордовым, если он светлый 5.3. Цветок может быть розой, если только он светлый и красный. Сын мог выполнить только одно из условий. Какие цветы заказала мать и как сын выполнил ее заказ? 6. Мать требовала, чтобы сын писал письма чаще и старался выполнять следующие условия: 6.1. Все короткие письма должны быть написаны на голубой бумаге фиолетовыми чернилами. 15 6.2. Ты можешь мне написать длинные письма черными чернилами, если воспользуешься голубой бумагой. 6.3. Если письмо не будет длинным, то пиши фиолетовыми чернилами. Однако ни одно из этих условий не было выполнено. Какие письма хотела получать мать и какие письма писал сын? 7. Можно было купить костюм: черный либо синий; шерстяной либо хлопчатобумажный; с красными полосками либо без них. При покупке костюма были высказаны следующие соображения: 7.1. Я согласен купить шерстяной или синий костюм только в том случае, если он будет с красной полоской. 7.2. Можно купить синий хлопчатобумажный костюм, если он будет с полоской. Если же костюм будет без полоски, то он должен быть черным, если он не шерстяной. 7.3. Если выберешь хлопчатобумажный костюм, то он должен быть черным с красной полоской. Но лучше купить синий костюм. Значит, он будет шерстяным с красной полоской. Продавец сказал, что все эти требования могут быть сведены к трем простейшим, а из этих трех, он может выполнить только одно. Кроме того, он сказал, что придется выбрать либо шерстяной, либо синий хлопчатобумажный костюм. Какой костюм хотел купить покупатель? Какой костюм предложил продавец? 8. При покупке дыни или арбуза были высказаны следующие соображения: 8.1. Все большие плоды спелые. 8.2. Если ты купишь маленький плод, то это будет спелая дыня. 8.3. Дыню ты сможешь купить только при условии, что она будет спелой, хотя и маленькой. А мы хотим, чтобы ты 16 купил большой плод. Значит, надо купить спелый арбуз. Эти соображения сводятся к двум простейшим условиям. Выполнить удалось лишь одно. Кроме того, купленный плод оказался спелым. Какой плод был куплен, и что хотели купить? 9. Учитель сказал ученику: 9.1. Если у тебя есть определенные способности, то для успешной сдачи экзаменов тебе необходимо еще и трудолюбие. 9.2. Если у тебя способностей нет, то ты сможешь сдать экзамены только при условии, что ты будешь трудолюбив или увлечен учебой. 9.3. Я заметил нечто парадоксальное: отсутствие увлеченности учебой является у тебя необходимым условием наличия способностей и трудолюбия. Значит, ты экзамен не сдашь. Ученик ответил, что согласен только с первым утверждением. К какой формулировке сводятся утверждения учителя. Как расшифровывается ответ ученика. 10. По поводу погоды были высказаны соображения: 10.1. Если будет жарко, то необходимым условием пасмурной погоды будет отсутствие ветра. 10.2. Пасмурное небо бывает только при холодной и безветренной погоде. 10.3. Если будет ветрено, то достаточным условием жаркой погоды будет ясное небо. 10.4. Если небо будет ясным, то погода будет холодной, если будет дуть ветер. 10.5. Пасмурное небо является необходимым условием ветреной и холодной погоды. Первые три высказывания сводятся к двум простейшим условиям, из которых истинным будет только одно. Из четвертого и пятого истинным будет тоже только одно. Какая будет погода? 17 11. Сестра по поводу предполагаемого подарка высказала следующие предположения: 11.1. Чтобы зверек был черным и вредным, достаточно, чтобы это была кошка. 11.2. Если зверек будет белым, то, для того чтобы это была собака, достаточно чтобы он был послушным. 11.3. Если зверек будет вредным, то он может быть белым только тогда, когда это кошка. 11.4. Если это кошка, то она будет послушной, если она черная. 11.5. Зверек может быть собакой, если он послушный и черный. Первые три высказывания свести к двум простейшим условиям, из которых истинно только одно. Из четвертого и пятого условия истинно тоже только одно. Какого зверька подарили сестре? 12. Дети знали, что отец купил либо яблоки, либо груши. Они высказали ряд предположений: 12.1. Если отец купил яблоки, то они будут спелыми только тогда, когда они красные. 12.2. Для того, чтобы плода были зелеными, достаточно, чтобы это были неспелые груши. 12.3. Все зеленые плоды – это неспелые яблоки. 12.4. Если отец купил яблоки, то для того, чтобы они были спелыми, необходимо, чтобы они были зелеными. 12.5. Все спелые яблоки всегда бывают красными. Первые три предположения сводятся к двум простейшим условиям, из которых справедливо только одно. Из четвертого и пятого условий выполнено только одно. Какой была покупка? 13. Обсуждая погоду, дети высказывали следующие предположения: 13.1. Града не будет, если не будет ни снега, ни дождя. 18 13.2. Если снега не будет, то нельзя утверждать, что дождь идет тогда и только тогда, когда идет град. 13.3. Если будет дождь с градом, то снега не будет. Но снег все же пойдет. Значит, будет, либо дождь, либо град. Эти предположения сводятся к двум простейшим условиям, из которых оказалось выполненным только одно. Кроме того, должно быть выполнено дополнительное условие: будет либо град, либо дождь со снегом. Какая была погода? 14. По поводу погоды были высказаны предположения: 14.1. Если погода будет пасмурной, то для того, чтобы было холодно, необходимо, чтобы дул ветер. 14.2. Если погода будет холодной, то не может быть, чтобы солнце светило только тогда, когда нет ветра. 14.3. Для того, чтобы было пасмурно и ветрено достаточно, чтобы было холодно. Но погода будет жаркой. Значит, пасмурно будет только тогда, когда нет ветра. Известно, что эти предположения сводятся к двум простейшим условиям. Оказалось, что может быть выполнено лишь одно из этих условий. Кроме того, известно, что было либо жарко и безветренно, либо пасмурно и холодно. Какая была погода? 15. В коробке лежат шары: красные и зеленые, большие и маленькие, деревянные и пластмассовые. Из коробки надо достать шар, соблюдая условия: 15.1. Для того, чтобы шар был красным, достаточно, чтобы он был большим и пластмассовым. 15.2. Шар может быть пластмассовым только тогда, когда он маленький и красный. 15.3. Если шар деревянный, то для того, чтобы он был зеленым, достаточно, чтобы он был большим. 15.4. Если шар зеленый, то не может быть, чтобы он был большим и пластмассовым. 19 Известно, что эти условия сводятся к двум простейшим. Когда вынули шар, оказалось, что выполнено только одно из этих условий. Кроме того, вынутый шар был либо красным пластмассовым, либо зеленым и маленьким. Какой шар вынули из коробки? 16. В коробке лежат шары: деревянные и пластмассовые, большие и маленькие, зеленые и красные. Из коробки надо достать шар, соблюдая следующие правила: 16.1. Шар может быть деревянным только тогда, когда он маленький и зеленый. 16.2. Если шар маленький, то для того, чтобы он был пластмассовым, достаточно, чтобы он не был зеленым. 16.3. Если шар красный и маленький, то он деревянный. Эти правила сводятся к двум простейшим условиям. Из двух условий оказалось возможным выполнить только одно. Кроме того, о вынутом шаре известно, что он либо зеленый, либо большой и деревянный. Какой шар вынули из коробки? 17. Школьники собрались в поход: либо в лес, либо на озеро. Погода могла быть либо жаркой, либо холодной; либо солнечной, либо пасмурной. В связи с этим были высказаны некоторые суждения: 17.1. Мы пойдем на озеро, если будет жарко и солнечно. 17.2. Чтобы пойти на озеро, достаточно, чтобы погода была солнечной. Но погода будет пасмурной. Значит, мы пойдем в лес, если будет холодно. 17.3. Если солнечная погода будет достаточным условием для похода в лес, нельзя утверждать, что поход на озеро является необходимым условием холодной погоды. Эти условия сводятся к двум простейшим условиям, из которых может быть выполнено только одно. Кроме того, известно, что: либо было жарко и школьники пошли в лес, 20 либо было холодно, но солнечно и они пошли на озеро. Куда пошли школьники, и какой была погода?

Похожие:

	Учебно-методический комплекс по дисциплине математическая логика и теория алгоритмов Курс математическая логика и теория алгоритмов обеспечивает приобретение знаний в соответствии с государственным образовательным...		Вопросы к экзамену по курсу «Математическая логика и теория алгоритмов» Методические указания предназначены для студентов, обучающихся по направлению 020400. 68 «Биология», магистерская программа 020400....
	Программа дисциплины «Информатика, математическая логика и теория... Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направлений подготовки 231000....		«Разработка алгоритмов и программирование на языке Pascal» Лабораторный практикум содержит методические указания к выполнению лабораторных работ по алгоритмизации и программированию на языке...
	Методические указания по выполнению контрольных работ для экономических специальностей Методические указания по выполнению контрольных работ по дисциплине "Экономическая теория" для студентов экономических специальностей–...		Методические указания к выполнению контрольных работ по дисциплине “ Методические указания к выполнению контрольных работ по дисциплине “Основы внешнеэкономической деятельности” для студентов экономических...
	Программа вступительных испытаний по дисциплине «Математика» Курс математическая логика и теория алгоритмов обеспечивает приобретение знаний в соответствии с государственным образовательным...		Методические указания по выполнению контрольных работ по дисциплине Методические указания по выполнению контрольных работ по дисциплине «Правовые основы российского государства» для студентов по специальности...
	Методические указания к выполнению контрольных работ по дисциплине «Информатика» Задания и методические указания к выполнению контрольных работ по дисциплине «Информатика». Екатеринбург, фгаоу впо «Российский государственный...		Рабочая программа по дисциплине В. В математическая логика и теория алгоритмов Рабочая программа составлена на основе фгос впо и учебного плана мгту по направлению 090900. 62 Информационная безопасность
	Рабочая программа по дисциплине В. В математическая логика и теория алгоритмов Рабочая программа составлена на основе фгос впо и учебного плана мгту по направлению 090900. 62 Информационная безопасность		Факультет экспертизы и товароведения методические указания к выполнению... «Нам дан во владение самый богатый, меткий, могучий и поистине волшебный русский язык». (К. Г. Паустовский)
	Сборник методических указаний для студентов по выполнению лабораторных работ дисциплина «химия» Методические указания для выполнения лабораторных работ являются частью основной профессиональной образовательной программы Государственного...		Рефератов по курсу «Математическая логика и теория алгоритмов» Темпоральные логики высказываний линейного времени и вычислительных деревьев: их синтаксис и семантика
	Методические указания по выполнению курсов ых работ по дисциплине «теория управления» Методические указания предназначены для выполнения курсовой работы студентами направления подготовки бакалавриат 081100. 62 «г осударственное...		Методические указания по выполнению реферативных работ по дисциплине «История и философия науки» Методические указания к выполнению реферативных работ аспирантов и соискателей по дисциплине «История и философия науки» /Уфимск...