 |
Порядок выполнения работы и форма отчетности
|
|
|
|
Задание 1. Определить дизъюнктивные и конъюнктивные нормальные формы
a) Найти ДНФ для формул:
| I вариант | II вариант | III вариант | IV вариант |
| (xÚy&z)&(xÚz) | хÚ  (xÚy)
| x& ÚxÚy
| (xÚz)( )Úx
|
б) Найти КНФ для формулы:
| I вариант | II вариант | III вариант | IV вариант |
 ÚyxÚx
| Ú  xÚyz
| (( z)®y)( ®z)
| (z®y )( y®z)
|
Задание 2. Решить с помощью преобразований
I вариант
Задача 1. Кто играет в шахматы? Определите, кто из трёх мальчиков Александр, Борис и Сергей играет в шахматы, если известно:
1) играет Александр или Борис;
2) если играет Александр, то играет и Борис;
3) Александр и Сергей оба играют или оба не играют.
Задача 2. Три ученика, Саша, Коля и Вова, прогуляли информатику. Когда их спросили, кому пришла в голову эта идея, они ответили следующее:
1) Саша: «Я никогда не призывал к прогулу, это была идея Коли».
2) Коля: «Я никогда не предложил бы это первым, во всем виноват Вова».
3) Вова: «Эта идея пришла в голову Коле. Я просто пошел за компанию».
Внутренним чутьем учитель почувствовал, что два ученика говорят правду, а третий – лжет. Кто из учеников был инициатором прогула?
II вариант
Задача 1. Компьютер вышел из строя. Известно, что:
1) Если монитор неисправен, то исправна видеокарта, но несправна оперативная память.
2) Если видеокарта исправна, то исправна оперативная память, но неисправен монитор.
3) Если оперативная память исправна, то исправна видеокарта, но неисправен монитор.
Что неисправно в компьютере?
Задача 2. Три школьника, Миша, Коля и Сергей, остававшиеся в классе на перемене, были вызваны к директору по поводу разбитого в это время окна в кабинете. На вопрос директора о том, кто это сделал, мальчики ответили следующее:
|
|
|
1) Миша: «Я не бил окно, и Коля тоже…»
2) Коля: «Миша не разбивал окно, это Сергей разбил футбольным мячом!»
3) Сергей: «Я не делал этого, стекло разбил Миша».
Стало известно, что двое ребят сказали правду, а третий оба факта соврал. Зная это, директор смог докопаться до истины. Кто разбил стекло в классе?
III вариант
Задача 1. По телевизору синоптик объявляет прогноз погоды на завтра и утверждает следующее:
1)Если не будет ветра, то будет пасмурная погода без дождя.
2)Если будет дождь, то будет пасмурно и без ветра.
3)Если будет пасмурная погода, то будет дождь и не будет ветра.
Какая же погода будет завтра?
Задача 2. Один из 3 братьев: Алеша, Витя и Семен поставил на скатерть кляксу. Кто запачкал скатерть? - спросила бабушка.
1) Витя не ставил кляксу, - сказал Алеша, - Это сделал Семен.
2) Это Витя поставил кляксу, - сказал Семен, - А Алеша не пачкал скатерть.
3) Я знаю, что Семен не мог этого сделать. - сказал Витя.
Оказалось, что двое мальчиков сказали правду, а один сказал неправду. Кто поставил на скатерть кляксу?
IV вариант
Задача 1. Определите, кто из подозреваемых участвовал в преступлении, если известно:
1) если Иванов не участвовал или Петров участвовал, то Сидоров участвовал;
2) если Иванов не участвовал, то Сидоров не участвовал.
3) в преступлении участвовал только один из трех подозреваемых.
Задача 2. Аня, Вика и Сергей решили пойти в кино. Учитель, хорошо знавший ребят, высказал предположения:
1) Аня пойдет в кино, а Вика останется дома;
2) Сергей пойдет в кино, но Аня не пойдет;
3) Сергей не пойдет в кино и Вика не пойдет в кино.
Когда ребята пошли в кино, оказалось, что учитель немного ошибся: из трех его утверждений истинным оказались только два. Кто из ребят пошел в кино?
Задание 3. Решить табличным способом
I вариант
Задача 1. Воронов, Павлов, Левицкий и Сахаров — 4 талантливых молодых человека. Один из них — танцор, другой — художник, третий — певец, а четвертый — писатель. О них известно следующее:
|
|
|
1) Воронов и Левицкий сидели в зале консерватории в тот вечер, когда певец дебютировал в сольном концерте.
2) Павлов и писатель вместе позировали художнику.
3) Писатель написал биографическую повесть о Сахарове и собирается написать о Воронове.
4) Воронов никогда не слышал о Левицком.
Задача 2. Марина, Валерия, Анна и Дарья - подруги детства. Они умеют играть на разных инструментах (пианино, гитаре, арфе и скрипке), но каждая только на одном. Они же знают иностранные языки, но каждая только один. Известно еще вот что:
1) Анна не играет на скрипке, но знает французский язык.
2) Валерия не знает английского языка и не играет ни на арфе, ни на скрипке.
3) Девушка, которая говорит по-немецки, не играет на арфе.
4) Марина не знает ни английского, ни немецкого и не играет ни на скрипке, ни на арфе.
5) Девушка, которая играет на гитаре, говорит по-итальянски.
На каком языке говорит, и на каком инструменте играет каждая девочка?
II вариант
Задача 1. Атос, Портос, Арамис и Д’Артаньян – четыре талантливых молодых мушкетёра. Один из них лучше всех сражается на шпагах, другой не имеет равных в рукопашном бою, третий лучше всех танцует на балах, четвертый без промаха стреляет с пистолетов. О них известно следующее:
1) Атос и Арамис наблюдали на балу за их другом – прекрасным танцором.
2) Портос и лучший стрелок вчера с восхищением следили за боем рукопашника.
3) Стрелок хочет пригласить в гости Атоса.
4) Портос был очень большой комплекции, поэтому танцы были не его стихией.
Кто чем занимается?
Задача 2. Жили-были на свете три поросёнка, три брата: Ниф-Ниф, Наф-Наф, Нуф-Нуф. Построили они три домика: соломенный, деревянный и кирпичный. Все три брата выращивали возле своих домиков цветы: розы, ромашки и тюльпаны. Известно, что:
1) Ниф-Ниф живет не в соломенном домике, а Наф-Наф – не в деревянном;
2) возле соломенного домика растут не розы, а тот, у кого деревянный домик, выращивает ромашки.
3) У Наф-Наф аллергия на тюльпаны, поэтому он не выращивает их.
Узнайте, кто в каком домике живет, и какие цветы выращивает.
III вариант
|
|
|
Задача 1. «Город мастеров». В нашем городе живут 5 друзей: Иванов, Петров, Сидорчук, Веселов и Гришин. У них разные профессии: маляр, мельник, парикмахер, почтальон, плотник. Но я точно знаю, что:
1) Петров и Гришин никогда не держали в руках малярной кисти
2) Иванов и Гришин давно собираются посетить мельницу, где работает их товарищ.
3) Петров и Веселов живут в одном доме с почтальоном.
4) Сидорчук недавно был в загсе одним из свидетелей, когда Петров и дочка парикмахера сочетались законным браком
5) Иванов и Петров каждое воскресенье играют в городки с плотником и маляром
6) Гришин и Веселов по субботам встречаются в парикмахерской, где работает их друг.
7) Почтальон же предпочитает бриться дома.
Помогите мне установить профессию каждого из друзей.
Задача 2. Три товарища, Иван, Дмитрий и Степан преподают различные предметы в школах Москвы, Санкт-Петербурга и Киева. Известно, что:
1) Иван работает не в Москве, а Дмитрий не в Ленинграде;
2) Москвич преподает не физику;
3) Тот, кто работает в Ленинграде, преподает химию;
4) Дмитрий преподает не биологию.
Какой предмет, и в каком городе преподает каждый товарищ?
IV вариант
Задача 1. В авиационном подразделении служат Потапов, Щедрин, Семенов, Коновалов и Самойлов. Их специальности: пилот, штурман, бортмеханик, радист и синоптик. Об этих людях известно следующее:
1) Щедрин и Коновалов не умеют управлять самолетом.
2) Потапов и Коновалов пока не штурманы.
3) Щедрин и Самойлов живут в одном доме с радистом.
4) Семенов был в доме отдыха вместе со Щедриным и сыном синоптика.
5) Потапов и Щедрин в свободное время любят играть в шахматы с бортмехаником.
6) Коновалов, Семенов и синоптик увлекаются боксом.
7) Радист боксом не увлекается.
Кто какой профессии?
Задача 2. Маша, Женя, Лида и Катя умеют играть на различных инструментах (виолончели, рояле, гитаре и скрипке). Они же владеют различными иностранными языками (английским, французским, немецким, испанским), но каждая только одним. Известно, что:
1) девушка, которая играет на гитаре, говорит по-испански.
|
|
|
2) Лида не играет ни на скрипке, ни на виолончели и не знает английского языка, так же как и Маша.
3) Девушка, которая говорит по-немецки, не умеет играть на виолончели,
4) Женя знает французский язык, но не умеет играть на скрипке.
Кто же из девушек, какой язык знает, и на каком инструменте играет?
КОНТРОЛЬНЫЕ ВОПРОСЫ
1. Какие законы логики Вы использовали при представлении булевой функции в виде ДНФ и КНФ?
2. Методом рассуждений решите задачу. Сегодня не воскресенье, а завтра не среда. Вчера была не пятница, а позавчера был не понедельник. Завтра не воскресенье, и вчера было не воскресенье. Послезавтра не суббота и не воскресенье. Вчера был не понедельник, и не среда. Позавчера была не среда, а завтра не вторник. Да, и сегодня не среда. Какой же сегодня день недели, если учесть, что одно утверждение в списке - ложно?
Литература
1. В.И. Игошин Математическая логика и теория алгоритмов: учеб. пособие. – М.: Издательский центр «Академия», 2008.
2. В. И. Игошин Задачи и упражнения по математической логике и теории алгоритмов: учеб. пособие для студ. высш. учеб. заведений. - М.: Издательский центр «Академия», 2007
Практическая работа № 3
|
|
|
