Практическое занятие №6

Практическая работа №6 (1К, 1ТО)

Тема: Графический метод алгебры логики

Цель работы: научиться выполнять равносильные преобразования, используя законы логики; научиться решать логические задачи различными способами.

Оборудование: компьютер с установленной операционной системой Windows и подключенным интернетом.

Краткие теоретические сведения

1. Закон тождества: А = А

2. Закон непротиворечия: А& = 0

3. Закон исключенного третьего: А = 1

4. Закон двойного отрицания: .

5. Законы коммутативности: AB BA

AB BA

1. Законы дистрибутивности: А(ВC) = (AB)(AC)

А (ВC) = AB AC

1. Ассоциативные законы: А(ВC) = (AB)C

А(ВC) = (AB)C

1. Законы идемпотентности: A*A A

AA A

1. Законы де Моргана:

1. AB= B (снятие импликации)

2. A↔B=AB (снятие эквиваленции)

3. Свойства констант: А1 = 1 А1 = A А0 = А А0 = 0

Разнообразие логических задач очень велико. Способов их решения тоже немало. Но наибольшее распространение получили следующие три способа решения логических задач: средствами алгебры логики с помощью равносильных преобразований; табличный; с помощью рассуждений.

Пример Решить задачу табличным способом

Три дочери писательницы Дорис Кей — Джуди, Айрис и Линда, тоже очень талантливы. Они приобрели известность в разных видах искусств — пении, балете и кино. Все они живут в разных городах, поэтому Дорис часто звонит им в Париж, Рим и Чикаго.

Известно, что:

1. Джуди живет не в Париже, а Линда — не в Риме;

2.  парижанка не снимается в кино;

3.  та, кто живет в Риме, певица;

4. Линда равнодушна к балету.

Где живет Айрис, и какова ее профессия?

Решение. Составим таблицу и отразим в ней условия 1 и 4, заполнив клетки цифрами 0 и 1 в зависимости от того, ложно или истинно соответствующее высказывание:

Так как Линда живет не в Риме, то, согласно условию 3, она не певица. В клетку, соответствующую строке "Линда" и столбцу "Пение", ставим 0. Из таблицы сразу видно, что Линда киноактриса, а Джуди и Айрис не снимаются в кино.

Согласно условию 2, парижанка не снимается в кино, следовательно, Линда живет не в Париже. Но она живет и не в Риме. Следовательно, Линда живет в Чикаго. Так как Линда и Джуди живут не в Париже, там живет Айрис. Джуди живет в Риме и, согласно условию 3, является певицей. А так как Линда киноактриса, то Айрис балерина.

В результате постепенного заполнения получаем следующую таблицу:

Ответ. Айрис балерина, живет в Париже.

Ход работы!

Задание 1. Решить табличным способом

1 подгруппа

Задача 1. Воронов, Павлов, Левицкий и Сахаров — 4 талантливых молодых человека. Один из них — танцор, другой — художник, третий — певец, а четвертый — писатель. О них известно следующее:

1. Воронов и Левицкий сидели в зале консерватории в тот вечер, когда певец дебютировал в сольном концерте.

2. Павлов и писатель вместе позировали художнику.

3. Писатель написал биографическую повесть о Сахарове и собирается написать о Воронове.

4. Воронов никогда не слышал о Левицком.

Задача 2. Марина, Валерия, Анна и Дарья - подруги детства. Они умеют играть на разных инструментах (пианино, гитаре, арфе и скрипке), но каждая только на одном. Они же знают иностранные языки, но каждая только один. Известно еще вот что:

1. Анна не играет на скрипке, но знает французский язык.

2. Валерия не знает английского языка и не играет ни на арфе, ни на скрипке.

3. Девушка , которая говорит по-немецки, не играет на арфе.

4. Марина не знает ни английского, ни немецкого и не играет ни на скрипке, ни на арфе.

5. Девушка, которая играет на гитаре, говорит по-итальянски.

На каком языке говорит, и на каком инструменте играет каждая девочка?

Задача 3. Атос, Портос, Арамис и Д’Артаньян – четыре талантливых молодых мушкетёра. Один из них лучше всех сражается на шпагах, другой не имеет равных в рукопашном бою, третий лучше всех танцует на балах, четвертый без промаха стреляет с пистолетов. О них известно следующее:

1. Атос и Арамис наблюдали на балу за их другом – прекрасным танцором.

2. Портос и лучший стрелок вчера с восхищением следили за боем рукопашника.

3. Стрелок хочет пригласить в гости Атоса.

4. Портос был очень большой комплекции, поэтому танцы были не его стихией.

Кто чем занимается?

Задача 4. Жили-были на свете три поросёнка, три брата: Ниф-Ниф, Наф-Наф, Нуф-Нуф. Построили они три домика: соломенный, деревянный и кирпичный. Все три брата выращивали возле своих домиков цветы: розы, ромашки и тюльпаны. Известно, что:

1. Ниф-Ниф живет не в соломенном домике, а Наф-Наф – не в деревянном;

2. возле соломенного домика растут не розы, а тот, у кого деревянный домик, выращивает ромашки.

3. У Наф-Наф аллергия на тюльпаны, поэтому он не выращивает их.

Узнайте, кто в каком домике живет, и какие цветы выращивает.

2 подгруппа

Задача 1. «Город мастеров». В нашем городе живут 5 друзей: Иванов, Петров, Сидорчук, Веселов и Гришин. У них разные профессии: маляр, мельник, парикмахер, почтальон, плотник. Но я точно знаю, что:

1. Петров и Гришин никогда не держали в руках малярной кисти

2. Иванов и Гришин давно собираются посетить мельницу, где работает их товарищ.

3. Петров и Веселов живут в одном доме с почтальоном.

4. Сидорчук недавно был в загсе одним из свидетелей, когда Петров и дочка парикмахера сочетались законным браком

5. Иванов и Петров каждое воскресенье играют в городки с плотником и маляром

6. Гришин и Веселов по субботам встречаются в парикмахерской, где работает их друг.

7. Почтальон же предпочитает бриться дома.

Помогите мне установить профессию каждого из друзей.

Задача 2. Три товарища, Иван, Дмитрий и Степан преподают различные предметы в школах Москвы, Санкт-Петербурга и Киева. Известно, что:

1. Иван работает не в Москве, а Дмитрий не в Ленинграде;

2. Москвич преподает не физику;

3. Тот, кто работает в Ленинграде, преподает химию;

4. Дмитрий преподает не биологию.

Какой предмет, и в каком городе преподает каждый товарищ?

Задача 3. В авиационном подразделении служат Потапов, Щедрин, Семенов, Коновалов и Самойлов. Их специальности: пилот, штурман, бортмеханик, радист и синоптик. Об этих людях известно следующее:

1. Щедрин и Коновалов не умеют управлять самолетом.

2. Потапов и Коновалов пока не штурманы.

3. Щедрин и Самойлов живут в одном доме с радистом.

4. Семенов был в доме отдыха вместе со Щедриным и сыном синоптика.

5. Потапов и Щедрин в свободное время любят играть в шахматы с бортмехаником.

6. Коновалов, Семенов и синоптик увлекаются боксом.

7. Радист боксом не увлекается.

Кто какой профессии?

Задача 4. Маша, Женя, Лида и Катя умеют играть на различных инструментах (виолончели, рояле, гитаре и скрипке). Они же владеют различными иностранными языками (английским, французским, немецким, испанским), но каждая только одним. Известно, что:

1. девушка, которая играет на гитаре, говорит по-испански.

2. Лида не играет ни на скрипке, ни на виолончели и не знает английского языка.

3. Маша не играет ни на скрипке, ни на виолончели и не знает английского языка.

4. Девушка, которая говорит по-немецки, не умеет играть на виолончели,

5. Женя знает французский язык, но не умеет играть на скрипке.

Кто же из девушек, какой язык знает, и на каком инструменте играет?

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Приведите примеры логических схем, используемых в ЭВМ.

2. Что называют функционально полной системой функций? Сформулируйте теорему Поста-Яблонского.

3. Что такое полином Жегалкина?