Дискретная математика

КОНТРОЛЬНАЯ РАБОТА № 1

Вариант 1

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

((A∧B)→C)↔(A→(¬B∨C)).

2.    Установите эквивалентность формул с помощью таблиц истинности:

¬A∧B∨¬C∧B и B∧¬(A∧C).

3.    Равносильными преобразованиями приведите формулу к ДНФ и КНФ:

F(X,Y,Z)=X∨(¬(X∧Z)) ∧(X∨Y).

4.    Проверьте, являются ли булевы функции F₁ и F₂ эквивалентными:

F₁=x₁*(x₂≡x₃) и F₂=(x₁x₂)≡(x₁x₃).

5.    Представьте в виде полинома Жегалкина булеву функцию, заданную таблично:

6.    Постройте полином Жегалкина для функции:

¬((x↔y)*(y↔z)).

Вариант 2

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

(A→B∨C))↔((A→B)∨(A→C)).

2.    Установите эквивалентность формул с помощью таблиц истинности:

(¬A∧(A∨B))→C и (A∨B)→C.

3.    Равносильными преобразованиями приведите формулу к ДНФ и КНФ:  

F(X,Y,Z)=X∨Y∨X∧Z∨(¬X∧Y).

4.    Проверьте, являются ли булевы функции F₁ и F₂ эквивалентными:

F₁=x₁→(x₂∨x₃) и F₂=(x₁→x₂)∨(x₁→x₃).

5.    Представьте в виде полинома Жегалкина булеву функцию, заданную таблично:

6.    Постройте полином Жегалкина для функции:

¬((x*y)(x→z)).

Вариант 3

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

¬(A→(B∧A))→(A∨C).

2.    Установите эквивалентность формул с помощью таблиц истинности: 

A↔B и (¬A∧¬B)∨(A∨B).

3.    Равносильными преобразованиями приведите формулу к ДНФ и КНФ:

F(X,Y,Z)=X∧Y∨(¬(X∧Y∨(¬X)))∧Z∨X.

4.    Проверьте, являются ли булевы функции F₁ и F₂ эквивалентными:

F₁= ¬(x₁x₃)∨x₁x₂∨x₁¬x₃ и F₂=x₁¬(x₂x₃)∨¬x₁x_3.

5.    Представьте в виде полинома Жегалкина булеву функцию, заданную таблично:

6.    Постройте полином Жегалкина для функции: 

(x↔y)¬((¬y↔z)).

Вариант 4

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

((A∧¬B)→B)→(A→C).

2.    Установите эквивалентность формул с помощью таблиц истинности:

(A∧B)↔(B∧¬C) и (A∨B→¬C)→A.

3.    Равносильными преобразованиями приведите формулу к ДНФ и КНФ:

F(X,Y,Z)=(X∨Z)∧(¬(X∧Y))∨X.

4.    Проверьте, являются ли булевы функции F₁ и F₂ эквивалентными:

F₁=x₁≡x₃ и F₂=(x₁∨x₂∨x₃)→(x₁∨x₂)(x₂∨x₃).

5.    Представьте в виде полинома Жегалкина булеву функцию, заданную таблично:

6.    Постройте полином Жегалкина для функции:  

¬((x↔y))(y↔z).

КОНТРОЛЬНАЯ РАБОТА № 2

Вариант 1

Задание

1. Дайте определение графа.

2. Перечислите вершины графа.

3. Перечислите ребра графа.

4. Назовите ребро или ребра, инцидентные вершинам V₁ и V₃.

5. Являются ли вершины V₄ и V₂, V₄ и V₆ смежными? Почему?

6. В какой вершине существует петля?

7. Перечислите кратные ребра.

8. Определите кратность ребра V₁V₃.

9. Какова степень вершины V₁? Является ли она четной или нечетной?

10. Содержит ли граф изолированные и висячие вершины? Перечислите.

11. Является ли граф полным?

12. Содержит ли граф мост? Если да, назовите.

Дайте определение гамильтонова цикла.

Вариант 2

Задание

1. Дайте определение графа.

2. Перечислите вершины графа.

3. Перечислите ребра графа.

4. Назовите ребро или ребра, инцидентные вершинам V₁ и V₂.

5. Являются ли вершины V₇ и V₁₀, V₇ и V₈ смежными? Почему?

6. В какой вершине существует петля?

7.  Перечислите кратные ребра.

8. Определите кратность ребра V₁V₂.

9. Какова степень вершины V₂? Является ли она четной или нечетной?

10. Содержит ли граф изолированные и висячие вершины? Перечислите.

11. Является ли граф полным?

12. Содержит ли граф мост? Если да, назовите.

13. Дайте определение эйлерова цикла.