Найдите множество .

Билет № 1

1. Логические операции. Формулы логики.

2. Найдите множество .

3. Дана булева функция f (x₁, x₂, x₃)=(10001010). Представьте данную булеву функцию в виде СДНФ и СКНФ с помощью таблицы истинности.

Преподаватель _______________

Билет № 2

1. Законы логики. Равносильные преобразования. Упрощение формул логики с помощью равносильных преобразований.

2. Д ана подстановка = 1 5 3 4 2 . Найти

4 3 2 1 5

3. Пусть граф G задан матрицей смежности А. Построить диаграмму этого графа, если

Преподаватель _______________

Билет № 3

1. Булевы функции. Способы задания булевых функций.

2. Определите следующие логические законы:

1) ав=ва;

2) ;

3)

3. Зашифруйте, используя теорию вычетов, сообщение «ДЕВА»

Преподаватель _______________

Билет № 4

1. Дизъюнктивные нормальные формы (ДНФ). Конъюнктивные нормальные формы (КНФ)

2. Ориентированный граф. Основные понятия.

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

Преподаватель _______________

Билет № 5

1. Совершенные дизъюнктивные нормальные формы (СДНФ).

2. Найдите множество .

3. Постройте матрицу смежности и матрицу инцидентности для отношений, заданных графом G. Найдите число степеней входа и выхода этого графа.

Преподаватель _______________

Билет № 6

1. Представление булевых функций в виде СДНФ.

2. Количество рёбёр графа G(V,X) равно 24. Найдите сумму степеней всех вершин графа.

3. Даны два множества А={4, 3, 6, 9, 11, 13, 15, 17} и

В={0, -5, 9, 12, 13, 21, 30, 34}. Найдите следующие множества:

, , А\В, В\А, А∆В.

Преподаватель _______________

Билет № 7

1. Операция двоичного сложения. Многочлен Жегалкина.

2. Найдите множество .

3. Пусть граф G задан матрицей инцидентности В. Построить диаграмму

этого графа, если

Преподаватель _______________

Билет № 8

1. Понятие множества. Основные операции над множествами.

2. Сумма степеней всех вершин графа G(V,X) равна 42. Найдите количество рёбёр данного графа.

3. Дана булева функция f (x₁, x₂, x₃)=(01100110).

Необходимо:

• Представить данную булеву функцию тремя способами: аналитически, геометрически, с помощью таблицы истинности.

• Определить существенность и фиктивность переменных в булевой функции.

• Представить данную булеву функцию в виде СДНФ и СКНФ с помощью таблицы истинности.

Преподаватель _______________

Билет № 9

1. Предикаты. Основные понятия.

2. Определите следующие логические законы:

1)а в в а

2) а(вс)=(ав)с

3)

3. В классе 40 человек. Играют в баскетбол 26 человек, занимаются плаванием 25, ходят на лыжах 27. Одновременно занимаются плаванием и баскетболом 15, баскетболом и лыжами 16, плаванием и лыжами 18 человек. Один из учащихся освобождён от занятий по физкультуре. Сколько человек занимается всеми указанными видами спорта?

Преподаватель _______________

Билет № 10

1. Логические и кванторные операции над предикатами.

2. Какой булевой функции соответствует геометрическая интерпретация?

3. Проверить принадлежность к классам S₀, S₁, S, L, M

функцию

Преподаватель _______________

Билет № 11

1. Бинарные отношения. Основные понятия. Примеры.

2. Какой булевой функции соответствует геометрическая интерпретация?

3. Зашифруйте, используя теорию вычетов, сообщение «САВА»

Преподаватель _______________

Билет № 12

1. Теория отображений. Основные понятия.

2. Переведите в символическую форму следующее сложное высказывание:

«Если ваза упадёт, то она разобьется. Ваза разбита, значит, она упала»

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

Преподаватель _______________

Билет № 13

1. Алгебра подстановок. Основные понятия, свойства.

2. Какой вид имеет логическая функция F( )=( )

3. Составить предикат функционального отношения:

при х=2 у=5;

при х=3 у=10;

при х=4 у=17.

Преподаватель _______________

Билет № 14

1. Основы алгебры вычетов.

2. Определите логические операции и оформите таблицу истинности для данных логических операций: а) ; б) ; в) ; г)

3. Граф G задан диаграммой. Составьте для него матрицу смежности,

постройте матрицу инцидентности, укажите степени вершин графа.

Преподаватель _______________

Билет № 15

1. Простейшие криптографические шифры.

2. Определите логические операции и оформите таблицу истинности для данных логических операций: а) ; б)

3. Граф G задан диаграммой. Составьте для него матрицу смежности,

постройте матрицу инцидентности, укажите степени вершин графа.

Преподаватель _______________

Билет № 16

1. Метод математической индукции.

2. Сколькими способами могут встать в очередь в билетную кассу 5 человек?

3. Построить полином Жигалкина для функции от трёх переменных

f (x₁, x₂, x₃)=(01110011) с помощью треугольника Паскаля.

Преподаватель _______________

Билет № 17

1. Сочетание, размещение, перестановки.

2. Базовые множества и принцип работы автоматов.

3. Проверить является ли формула суммой ряда (Метод математической индукции)

Преподаватель _______________

Билет № 18

1. Метод включений и исключений

2. Д ана подстановка = 1 5 2 4 3 . Найти

4 3 2 1 5

3. Доказать, что справедливо равенство: (Метод математической индукции)

Преподаватель _______________

Билет № 19

1. Неориентированный граф. Способы задания. Теорема о сумме степеней вершин

2. Какой вид имеет логическая функция F( )=

3. Даны два множества А={-2, -4, -6, -8, 2, 4, 6, 8} и

В={-3, -4, 1, 2, 6, 15, 16, 20}. Найдите следующие множества:

, , А\В, В\А, А∆В.

Преподаватель _______________

Билет № 20

1. Двудольные графы. Изоморфные графы. Эйлеровы графы.

2. Д ана подстановка = 1 3 4 5 2 . Найти

4 3 2 1 5

3. Построить полином Жигалкина для функции от трёх переменных

f (x₁, x₂, x₃)=(01110011) с помощью метода неопределенных

коэффициентов.

Преподаватель _______________

Билет № 21

1. Гамильтоновы графы. Плоские графы.

2. Какой вид имеет логическая функция F( )=

3. Даны два высказывания: А – спортсмен участвовал в авторалли; В – спортсмен разбил машину. Дайте словесную формулировку высказываний, соответствующих следующим логическим операциям:

а)

б)

Преподаватель _______________

Билет № 22

1. Ориентированный граф. Способы задания.

2. Перейти от ДНФ к КНФ:

3. Из110 студентов английский изучают 44 человека, немецкий-50 человек, французский-49, английский и немецкий-13, английский и французский-14, немецкий и французский-12, Все три языка изучают 5 учащихся. Сколько студентов изучают только один язык?

Преподаватель _______________

Билет № 23

1. Представление булевых функций в виде СКНФ.

2. Определите логические операции и оформите таблицу истинности для данных логических операций:

а) │Y

б)

3. Проверить принадлежность к классам S₀, S₁, S, L и М следующие

функции:

= , =

С помощью теоремы Поста проверить полноту системы .

Преподаватель _______________

Билет № 24

1. Правильный автомат (автомат Мура).

2. Переведите в символическую форму следующее сложное высказывание:

«Этот человек или джентльмен, или студент. Но он не джентльмен,

значит, он студент.»

3. Построить полином Жигалкина для функции от трёх переменных

f (x₁, x₂, x₃)=(00111110) с помощью треугольника Паскаля.

Преподаватель _______________

Билет № 25

1. Алгоритм фронта волны в графе. Расстояние между вершинами в графе.

2. Д ана подстановка = 1 5 3 4 2 . Найти

4 3 2 1 5

3. Построить полином Жигалкина для функции от трёх переменных

f (x₁, x₂, x₃)=(00010011) с помощью метода неопределенных

коэффициентов.

Преподаватель _______________

Билет № 26

1. Булев вектор. Единичный N-мерный куб.

2. Найдите множество .

3. Проверить принадлежность к классам S₀, S₁, S, L и М следующие функции:

= , =

С помощью теоремы Поста проверить полноту системы .

Преподаватель _______________

Билет № 27

1. Полнота и замыкание множества функций. Классы Поста. Теорема Поста. Шефферовские функции.

2. Перейти от КНФ к ДНФ

3. Пусть граф G задан матрицей инцидентности В. Построить диаграмму

этого графа, если

Преподаватель _______________

Билет № 28

1. Совершенные конъюнктивные нормальные формы (СКНФ).

2. Бином Ньютона и полиномиальная формула.

3. Зашифруйте, используя теорию вычетов, сообщение «БЕДА»

Преподаватель _______________

_______________

______