Шифр 47. На кафедре иностранных языков работают 18 преподавателей, из них 12 преподают английский язык, 11 – немецкий, 9 – французский

  • ID: 29832 
  • 6 страниц
x

Часть текста скрыта. После покупки Вы получаете полную версию

Фрагмент работы:

Шифр 47. На кафедре иностранных языков работают 18 преподавателей,…

КОНТРОЛЬНОЕ ЗАДАНИЕ ПО КУРСУ

"ТЕОРИЯ АЛГОРИТМОВ"

ВАРИАНТ 47

ЗАДАЧА 1.

Решить задачу, построив диаграммы Эйлера-Венна.

На кафедре иностранных языков работают 18 преподавателей, из них 12 преподают английский язык, 11 - немецкий, 9 - французский. Только английский и немецкий преподают 5 человек, только английский и французский - 4 человека. Три преподавателя преподают немецкий и французский языки. Сколько преподавателей преподают все три языка?

РЕШЕНИЕ:

Введем следующие обозначения:

А - множество всех преподавателей, преподающий английский;

В - множество всех преподавателей, преподающий немецкий;

С - множество всех преподавателей, преподающих французский;

U - множество всех преподавателей кафедры.

По условию нам дано следующее:

Количество преподавателей, преподающих все языки:

Нам неизвестно... и...:

Тогда

То есть 2 преподавателя преподают все языки.

Подсчитаем также, сколько преподавателей преподают только немецкий и французский языки:

а также количество преподавателей, преподающих только 1 язык:

Полученные результаты представим диаграммой Эйлера-Венна:

ЗАДАЧА 2.

Исходная формула имеет вид:

1. Приведите исходную формулу к СДНФ и СКНФ.

2. Выполните упрощение исходной формулы и полученных формул СДНФ и СКНФ.

3. Проверьте, равнозначны ли полученные три упрощенные формулы.

РЕШЕНИЕ:

1. Преобразуем исходную формулу:

Приведем к СДНФ:

Приведем к СКНФ:

2. Упростим исходную формулу, используя результаты п.1:

Упростим СДНФ:

Упростим СКНФ:

Упрощенная исходная формула и упрощенная СДНФ совпадают, построим для полученной формулы таблицу истинности и сравним с таблицей истинности полученной упрощенной СКНФ:

А В С.........

0 0 0 1 0 0

0 0 1 1 1 1

0 1 0 1 0 1

0 1 1 1 1 1

1 0 0 0 0 0

1 0 1 0 0 0

1 1 0 0 0 1

1 1 1 0 0 1

А В С............

0 0 0 1 1 0 0

0 0 1 1 1 1 1

0 1 0 1 1 1 1

0 1 1 1 1 1 1

1 0 0 0 0 0 0

1 0 1 0 0 1 0

1 1 0 0 1 1 1

1 1 1 0 1 1 1

Таблицы истинности совпадают, значит, три упрощенные формулы равнозначны.

ЗАДАЧА 3.

Проверьте правильность рассуждений.

Если бы Косоротов совершил это убийство, то он был бы на месте преступления в ту ночь, когда оно было совершенно. В ту ночь, когда оно было совершенно, Косоротов не был на месте преступления. Он был в другом месте. Следовательно, Косоротов не совершил этого убийства.

РЕШЕНИЕ:

Проверим правильность рассуждения графическим способом. Введем следующие обозначения для высказываний:

X - высказывание "Косоротов совершил это убийство";

Y - высказывание "Косоротов был на месте преступления в ту ночь, когда оно было совершенно";

Z - высказывание "Косоротов был в другом месте".

Тогда рассуждение можно записать в формализованном виде:

Данное рассуждение F будет истинным, если из конъюнкции посылок следует заключение, т.е. если импликация... тождественно истинна. Для проверки правильности рассуждения построим таблицу истинности:

Таблица истинности высказывания F

Х Y Z............ F

0 0 0 1 1 0 1 1

0 0 1 1 1 1 1 1

0 1 0 1 0 0 1 1

0 1 1 1 0 0 1 1

1 0 0 0 1 0 0 1

1 0 1 0 1 0 0 1

1 1 0 1 0 0 0 1

1 1 1 1 0 0 0 1

Видим, что функция... принимает значение "истина" на всех допустимых значениях простых операндов, следовательно, рассуждение F является правильным.

ЗАДАЧА 5.

Имеется грамматика: G = (?A, B, C, D?; ?a, b, c?; P; S), где Р состоит из правил:

S ? CB

B ? aCa

aC ? аcc

cc ? BCaaaa

Ca ? bbcc

bb ? e

Построить вывод в этой грамматике.

РЕШЕНИЕ:

Вывод:

S ? CB

? СаСа

? Сaccа

? СaBCaaaaа

? СaaCaCaaaaа

? Сaаccаccaaaaа

? bbccаccаccaaaaа

? ccаccаccaaaaа

Эта грамматика порождает язык: