Файл: Дискретная_мат._пос.pdf

 106 
 

ПРИЛОЖЕНИЕ 2 

Контрольная работа № 2 

 107 
 

Вариант 1 

1. Построить таблицу истинности для формулы: 

)

)

((

&

)

(

&

B

A

B

A

B

A

∨

→

¬

¬

∨

. 

2. С помощью равносильных преобразований убедиться, что формула за-

дачи 1 равносильна формуле 

B

A &

. Перечислить используемые законы. 

3. Проверить правильность логического рассуждения сокращенным  спо-

собом. Какими другими способами можно решить эту задачу? 

“Известно, что Петр и Иван братья, или они однокурсники. Если Петр и 

Иван братья, то Сергей и Иван не братья. Если Петр и Иван однокурсники, то 
Иван и Михаил тоже однокурсники. Следовательно, или Сергей и Иван братья, 
или Иван и Михаил однокурсники”. 

4. Используя два предиката, запишите предложение в виде формулы ло-

гики  предикатов: “Все  солдаты  храбрые”.  Запишите  отрицание  полученной 
формулы и приведите ее к предваренной нормальной форме. 

5.  Для  орграфа 

0

G

(рис. 1) найдите  множество  достижимости  и  множе-

ство контрдостижимости вершины 

1

x

. Выясните, какими свойствами обладает 

бинарное отношение, заданное графом 

0

G

.  Постройте  матрицу  смежности  и 

матрицу инцидентности, занумеровав дуги орграфа 

0

G

. 

6. Занумеруйте вершины графа 

1

G

(рис. 1) и определите степени всех его 

вершин. Нарисуйте какой-либо остовный подграф графа 

1

G

. Запишите матри-

цу смежности и матрицу инцидентности графа 

1

G

, занумеровав его ребра. 

7. Покажите, что графы G

1

 и G

2

(рис.1) изоморфны. Планарен ли граф G

2

?  

8. Определите цикломатическое число графа 

1

G

(рис. 1). Выясните, мож-

но ли нарисовать граф 

1

G

, не отрывая руки от бумаги и не проходя ни по од-

ному ребру дважды. Ответ обоснуйте. 

9. Выясните, сколько ребер нужно удалить из графа 

1

G

 (рис. 1) при по-

строении  его  каркаса.  Занумеруйте  вершины  графа 

1

G

  и  постройте  каркас 

двумя способами (обход “в ширину”, обход “в глубину”), начав обход из вер-
шины с максимальной степенью. 

 108 
 

Вариант 2 

1. Определить с помощью таблицы истинности, равносильны  ли форму-

лы:       

B

A

F

~

1

=

и 

)

&

(

)

&

(

2

B

A

B

A

F

∨

¬

¬

=

. 

2.  В  формуле 

B

B

C

B

A

F

&

)

(

&

)

(

¬

→

→

=

  избавиться  от  операции 

импликации и упростить с помощью равносильных преобразований. Перечис-
лить используемые законы. 

3. Проверить правильность логического рассуждения сокращенным  спо-

собом. Какими другими способами можно решить эту задачу? “Прямые 

a

 и  

b

или параллельны, или пересекаются, или скрещиваются. Прямые 

a

 и 

b

 лежат в 

одной плоскости и не пересекаются. Если прямые лежат в одной плоскости, то 
они не скрещиваются. Следовательно, прямые 

a

 и 

b

 параллельны”. 

4. Используя два предиката, запишите предложение в виде формулы ло-

гики предикатов: “Некоторые хвастуны трусливы”. Запишите отрицание полу-
ченной формулы и приведите ее к предваренной нормальной форме. 

5.  Для  орграфа 

0

G

(рис. 2) найдите  множество  достижимости  и  множе-

ство контрдостижимости вершины 

1

x

. Выясните, какими свойствами обладает 

бинарное отношение, заданное графом 

0

G

.  Постройте  матрицу  смежности  и 

матрицу инцидентности, занумеровав дуги орграфа 

0

G

. 

6.  Занумеруйте  вершины  графа 

1

G

  (рис. 2) и  определите  степени  всех 

его  вершин.  Нарисуйте  какой-либо  остовный  подграф  графа 

1

G

.  Запишите 

матрицы смежности и  инцидентности графа 

1

G

, занумеровав его ребра. 

7. Покажите, что графы 

1

G

 и 

2

G

 (рис. 2) изоморфны. Планарен ли 

2

G

? 

8.  Определите  цикломатическое  число  графа 

1

G

  (рис. 2). Выясните, 

можно ли нарисовать граф 

1

G

, не отрывая руки от бумаги и не проходя ни по 

одному ребру дважды. Ответ обоснуйте. 

9. Выясните, сколько ребер нужно удалить из графа 

1

G

 (рис. 2) при по-

строении  его  каркаса.  Занумеруйте  вершины  графа 

1

G

  и  постройте  каркас 

двумя способами (обход “в ширину”, обход “в глубину”), начав обход из вер-
шины с максимальной степенью. 

 109 
 

Вариант 3 

1. Построить таблицу истинности для формулы: 
    

B

A

A

B

A

F

∨

→

¬

→

¬

=

))

&

(

(

. 

2. С помощью равносильных преобразований убедиться, что формула за-

дачи 1 является тавтологией. Перечислить используемые законы. 

3. Проверить правильность логического рассуждения сокращенным  спо-

собом. Какими другими способами можно решить эту задачу? 

“Если  в  параллелограмме  диагонали  взаимно  перпендикулярны,  то  этот 

параллелограмм – ромб.  В  данном  параллелограмме  диагонали  не  взаимно 
перпендикулярны. Следовательно, параллелограмм не есть ромб”. 

4. Используя два предиката, запишите предложение в виде формулы ло-

гики  предикатов: “Все  книги  полезные”.  Запишите  отрицание  полученной 
формулы и приведите ее к предваренной нормальной форме. 

5.  Для  орграфа 

0

G

(рис. 3) найдите  множество  достижимости  и  множе-

ство контрдостижимости вершины 

1

x

. Выясните, какими свойствами обладает 

бинарное отношение, заданное графом 

0

G

.  Постройте  матрицу  смежности  и 

матрицу инцидентности, занумеровав дуги орграфа 

0

G

. 

6.  Дан  неорграф 

1

G

  (рис. 3). Занумеруйте  вершины  графа  и  определите 

степени всех его вершин. Нарисуйте какой-либо остовный подграф графа 

1

G

. 

Запишите матрицу смежности и матрицу инцидентности графа 

1

G

, занумеро-

вав его ребра. 

7. Покажите, что графы 

1

G

 и 

2

G

 (рис. 3) изоморфны. Является ли граф 

2

G

 планарным? 

8.  Определите  цикломатическое  число  графа 

1

G

  (рис. 3). Выясните, 

можно ли нарисовать граф 

1

G

, не отрывая руки от бумаги и не проходя ни по 

одному ребру дважды. Ответ обоснуйте. 

9. Выясните, сколько ребер нужно удалить из графа 

1

G

 (рис. 3) при по-

строении  его  каркаса.  Занумеруйте  вершины  графа 

1

G

  и  постройте  каркас 

двумя способами (обход “в ширину”, обход “в глубину”), начав обход из вер-
шины с максимальной степенью. 

 110 
 

Вариант 4 

1. Построить таблицу истинности для формулы: 

A

B

A

B

A

F

~

)

&

(

&

)

(

¬

→

=

. 

2. С помощью равносильных преобразований убедиться, что формула за-

дачи 1 является противоречием. Перечислить используемые законы. 

3. Проверить правильность логического рассуждения сокращенным  спо-

собом. Какими другими способами можно решить эту задачу? 

“Если функция непрерывна на данном интервале и имеет разные знаки на 

его концах, то внутри данного интервала функция обращается в нуль. Функция 
не обращается в нуль на данном интервале, но на концах имеет разные знаки. 
Следовательно, функция не является непрерывной”.  

 4. Используя два предиката, запишите предложение в виде формулы ло-

гики предикатов: “Некоторые птицы умеют петь”. Запишите отрицание полу-
ченной формулы и приведите ее к предваренной нормальной форме. 

5.  Для  орграфа 

0

G

(рис. 4) найдите  множество  достижимости  и  множе-

ство контрдостижимости вершины 

1

x

. Выясните, какими свойствами обладает 

бинарное отношение, заданное графом 

0

G

.  Постройте  матрицу  смежности  и 

матрицу инцидентности, занумеровав дуги орграфа 

0

G

. 

6.  Занумеруйте  вершины  графа 

1

G

  (рис. 4) и  определите  степени  всех 

его  вершин.  Нарисуйте  какой-либо  остовный  подграф  графа 

1

G

.  Запишите 

матрицы смежности и инцидентности графа 

1

G

, занумеровав его ребра. 

7. Покажите, что графы 

1

G

 и 

2

G

 (рис. 4) изоморфны. Является ли граф 

2

G

 планарным? 

8.  Определите  цикломатическое  число  графа 

1

G

  (рис. 4). Выясните, 

можно ли нарисовать граф 

1

G

, не отрывая руки от бумаги и не проходя ни по 

одному ребру дважды. Ответ обоснуйте. 

9. Выясните, сколько ребер нужно удалить из графа 

1

G

 (рис. 4) при по-

строении  его  каркаса.  Занумеруйте  вершины  графа 

1

G

  и  постройте  каркас 

двумя способами (обход “в ширину”, обход “в глубину”), начав обход из вер-
шины с максимальной степенью.