Вариант 6. Билет. Проверить, является ли отношением эквивалентности отношение

  • ID: 23231 
  • 3 страницы

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

Билет №6

Задание 1

Проверить, является ли отношением эквивалентности на множестве всех прямых на плоскости отношение "пересекающихся прямых".

Решение:

По условию А - множество всех прямых на плоскости, прямые х и у принадлежат А. Задано отношение... пересекает.... Отношение... является отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно. Отношение является рефлексивным, если.... То есть в нашем случае отношение будет рефлексивным, если прямая х пересекает саму себя. Но это невозможно, поскольку пересекающимися считаются прямые, имеющие только одну общую точку. Прямая х может только совпадать с собой, т.е. все точки будут общими, значит, заданное отношение не будет рефлексивным, следовательно, оно не является отношением эквивалентности. Можно также проверить, будет ли оно симметричным и транзитивным. Если отношение Р симметрично, то.... Это условие выполняется, так как если прямая х пересекает прямую у и имеет с ней только одну общую точку, то и прямая у имеет с прямой х только одну общую точку, т.е. пересекает ее. Отношение Р транзитивно, если..., т.е.если прямая х пересекает прямую у, а прямая у пересекает прямую z, то прямая х пересекает прямую z. Это условие не выполняется, так как прямая х, пересекающая прямую у, может быть параллельна прямой z, которую пересекает прямая у.

Задание 2

С помощью равносильных преобразований упростить булеву функцию

Решение:

Применим преобразование... и правила де Моргана......:

Задание 3

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

Решение:

Будем строить автомат Мили, так как заданная функция зависит от текущего значения x(t). Определим состояния автомата, соответствующие различным значениям x(t-1):

- "в момент времени t-1 поступил 0"

- "в момент времени t-1 поступила 1".

Составим таблицу переходов-выходов автомата:

Таблица 1

0... 0

1... 1

0... 1

1... 1

0... 1

1... 1

Значения выходных сигналов находим по формуле..., а значения состояний... - очередным состоянием x(t). Условие... определяет начальное состояние....

По таблице 1 видим, что состояние... эквивалентно состоянию..., поскольку выходные сигналы и состояния... при различных входных сигналах совпадают. Удаляя лишнее состояние..., получим таблицу переходов-выходов минимизированного автомата:

Таблица 2

0... 0

1... 1

0... 1

1... 1

Канонические уравнения полученного автомата имеют вид: