Вариант 12. Докажите тождества, используя только определения операций над множествами

  • ID: 30064 
  • 25 страниц

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

Задача 1

Докажите тождества, используя только определения операций над множествами:

Решение:

...

Задача 2

Доказать утверждение:

Решение:

...

Задача 3

Доказать методом математической индукции:

Решение:

...

Задача 4

А={a,b,c}, B={1,2,3,4}; P1 ? A?B, P2 ? B2. Изобразить P1, P2 графически. Найти P = (P1?P2)–1. Проверить с помощью матрицы [P2], является ли отношение P2 рефлексивным, симметричным, антисимметричным, транзитивным. P1 = {(b,1),(b,3),(c,1),(c,2),(c,3),(c,4)}; P2 = {(1,1),(2,2),(2,3),(2,4),(3,2),(3,3),(3,4), (4,2),(4,3),(4,4)}.

Решение:

Изобразим множества графически:

...

Задача 5

Найти область определения и область значений отношения , кратно 3. Является ли это отношение рефлексивным, симметричным, антисимметричным, транзитивным?

Решение:

...

Задача 6

Является ли алгеброй следующий набор ?

Решение:

...

Задача 7

Построить подсистему B(Х), если B= .

Решение:

...

Задача 8

Используя многомодульную арифметику с вектором оснований , вычислить ... Каков знак числа ?

Решение:

...

Задача 9

Даны графы и . Найти ... Для графа найти матрицы смежности, инцидентности, сильных компонент, маршрутов длины 2 и все маршруты длины 2, исходящие из вершины 1:

Решение:

1) :

...

2) :

...

3) :

...

4) :

...

Для графа

Запишем матрицу смежности:

...

Матрица инцидентности:

...

Найдем матрицу сильных компонент.

...

Матрица достижимости:

...

Матрица сильных компонент:

...

Матрица маршрутов длины 2:

...

По матрице видно, что из вершины 1 в вершину существует 3 маршрута длины 2:

...

Задача 10

Найти матрицы фундаментальных циклов, матрицы фундаментальных разрезов, радиус и диаметр, минимальное множество покрывающих цепей графа G. Является ли изображенный граф эйлеровым? Является ли изображенный граф планарным?

Решение:

Найдем цикломатическое число графа:

...

Матрица фундаментальных циклов:

...

Матрица С имеет вид , тогда матрица фундаментальных разрезов будет иметь вид :

...

Пронумеруем вершины графа:

...

Составим матрицу расстояний между вершинами:

...

Определим эксцентриситеты вершин:

...

Диаметр графа:

...

Радиус:

...

Найдем степени всех вершин графа:

...

Задача 11

Составить таблицы истинности формул:

Решение:

Таблица истинности для формулы

0 0 1 0 1 1

0 1 0 1 1 1

1 0 1 1 0 0

1 1 0 0 1 1

Таблица истинности для формулы

...

Задача 12

Проверить двумя способами, будут ли эквивалентны формулы

а) составлением таблиц истинности;

б) приведением формул к СДНФ или СКНФ с помощью эквивалентных преобразований.

Решение:

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

...

Так как таблицы истинности не тождественны для этих формул, то формулы не эквивалентны.

б) Приведем формулы к СДНФ:

...

...

СДНФ одной формулы не равна СДНФ другой формулы, значит, формулы не эквивалентны.

Задача 13

С помощью эквивалентных преобразований привести формулы к ДНФ, КНФ, СДНФ, СКНФ. Построить полином Жегалкина.

Решение:

Преобразуем формулу:

...

Получили ДНФ. Перейдем к СДНФ:

...

Приведем исходную формулу к КНФ:

...

Перейдем к СКНФ:

...

Построим полином Жегалкина:

...

Задача 14

Найти сокращенную, все тупиковые и минимальные ДНФ булевой функции двумя способами:

а) методом Квайна; б) с помощью крат Карно.

К каким классам Поста принадлежит данная функция?

Решение:

а) Метод Квайна.

По таблице истинности запишем СДНФ:

Перейдем к сокращенной ДНФ:

...

Составим матрицу Квайна:

Импликанты Конституенты единицы

...

По матрице видно, что сокращенная ДНФ является и тупиковой, и минимальной:

б) Карта Карно:

...

Минимальная ДНФ:

Определим, к каким классам Поста принадлежит заданная функция:

...

5) Найдем полином Жегалкина по минимальной ДНФ:

...

Заданная функция не принадлежит ни одному из классов Поста.

Задача 15

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

(0011 1110 0101 0101)

Решение:

Определим СДНФ функции:

На карту Карно занесем единицы:

Сокращенная ДНФ:

Тупиковые ДНФ:

...

Минимальная ДНФ (импликанты обведены контуром):

...

Для получения КНФ занесем на карту нули:

...

Сокращенная КНФ:

...

Тупиковая и минимальная КНФ:

...

Задача 16

Является ли полной система функций? Образует ли она базис?

Решение:

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

Составим таблицу истинности функции :

...

1)

2)

3)

4)

5) Найдем полином Жегалкина:

...

Функция не принадлежит ни одному из классов Поста.

Таблицу истинности функции :

1)

2)

3)

4)

5) Полином Жегалкина:

...

Функция принадлежит к классу функций, сохраняющих единицу, и к классу линейных функций.

Так как для любого из классов Поста в заданной системе найдется функция, не принадлежащая этому классу, то система функций является полной. Но базисом эта система функций не является, так как при удалении из нее функции система останется полной (так как не принадлежит ни одному из классов Поста).

Задача 17

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

Решение:

Составим таблицы истинности для формул в левой и правой частях

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

Задача 18

С помощью алгебры логики докажите тождество

Решение:

...

Таблицы истинности для выражений в левой и правой части соотношения одинаковы, значит, левая и правая части тождественны.