Докажите методом математической индукции

  • ID: 01810 
  • 9 страниц

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

Докажите методом математической индукции

Задача 1.

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

1)…

2)…

Решение:

1) По определению:

2)…

Задача 2.

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

…,…

Решение:

По определению разности множеств имеем:

Задача 3.

Докажите методом математической индукции

…кратно 6 для всех…

Решение:

При…получаем справедливое тождество: 7 – 1=6 – делится на 6

Установим справедливость индукционного шага. Предположим, что…кратно 6 при всех….

Докажем справедливость утверждения при…, т.е. что…кратно 6

Имеем:

…– так как оба слагаемые кратны 6, то число…кратно 6.

Задача 4.

Изобразите…и…графически. Найдите…. Проверьте с помощью матрицы…, яв-ляется ли отношение…рефлексивным, симметричным, транзитивным?

…,…,…,….

Решение:

Изобразим…графически:

Изобразим…графически:

Составим матрицы бинарных отношений:

…и…

По свойству бинарных отношений имеем

Проверим, является ли отношение…рефлексивным, симметричным, транзитивным.

Отношение…называется рефлексивным, если…для всех…, т.е. матрица бинарно-го отношения должна быть единичной, что не выполняется:

Отношение…называется симметричным, если для любых…из…следует…, т.е.…или…. В нашей задаче имеем:

Значит, отношение…не является симметричным.

Отношение…называется антисимметричным, если из…и…, следуетт.е.…или…. В нашей задаче имеем:

Отношение…называется транзитивным, если из…и…следует, что…, т.е.…. По-лучаем:

Отношение не является транзитивным.

Задача 5.

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

Решение:

Областью определения отношения…называется множество

Областью значений отношения…называется множество

В нашей задаче получаем:

Проверим рефлективность, симметричность, антисимметричность и транзитив-ность.

Запишем матрицу бинарного отношения…:

Отношение…является рефлексивным, т.к. для всех….

Отношение…является симметричным, т.к. для любых…из…следует, что…

Отношение…является антисимметричным, т.к.…и…, следует….

Отношение…является транзитивным, потому, что…и…имеем

…и…, т.е.…. Следовательно, отношение…является транзитивным.

Задача 9.

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

Решение: По условию задачи имеем:

Находим:

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

Матрица смежности –…

Матрица инцидентности –…

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

Маршруты длины 2: (1,1), (1,2), (1,3)

Задача 10.

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

Решение:

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

диаметр графа G равен:…

радиус графа равен:…

Задача 11. Составьте таблицу истинности формул.

Решение:

Будем строить таблицу истинности последовательно в соответствии с шагами по-строения формул:

0 0 0 0 1 0 0 0 1 1 1

0 1 1 0 0 1 0 0 0 1 1

1 0 1 1 0 0 1 0 1 1 1

1 1 1 0 1 0 0 1 1 0 0

1 1 0 1 0 0

1 0 1 0 0 1

0 1 1 1 0 0

1 1 1 1 1 1

Задача 12.

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

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

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

…и…

Решение:

1) составим таблицы истинности

0 0 0 0 1 0 0 0 1 1 0

0 0 1 1 1 0 0 1 1 1 0

0 1 0 1 1 0 1 0 1 1 0

0 1 1 0 1 0 1 1 1 1 0

1 0 0 0 0 1 0 0 0 0 0

1 0 1 1 1 1 0 1 0 1 1

1 1 0 1 1 1 1 0 1 0 1

1 1 1 0 0 1 1 1 1 1 0

2) приведем формулу…к ДНФ:

выражаем все логические операции, участвующие в построении формулы через дизъюнкции, конъюнкции и отрицания, используя эквивалентности

Приведем полученные формулы к СДНФ

Данные формулы не являются эквивалентными.

Задача 13.

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

Решение:

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

Полученную ДНФ приведем к СДНФ:

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

Полученную КНФ приведем к СКНФ:

построим полином Жегалкина из СДНФ:…

Задача 14.

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

1) методом Квайна

2) с помощью карт Кардано

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

Решение:

Для данной функции запишем СДНФ:

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

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

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

* *

* *

* *

* *

Получаем следующую минимальную ДНФ:…

Построим карту Кардано:

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

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