Проверить, является ли тавтологией формула

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

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

Задание 1

Проверить, является ли тавтологией формула:

Решение:

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

0 0 0 1 1 0 1 1 1

0 0 1 1 1 0 1 1 1

0 1 0 1 0 1 1 1 1

0 1 1 1 1 0 1 1 1

1 0 0 0 1 0 0 0 1

1 0 1 0 1 0 1 1 1

1 1 0 1 0 1 0 1 1

1 1 1 1 1 0 1 1 1

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

Задание 2

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

Решение:

Для решения применим преобразование:... и закон де Моргана:....

Поскольку............, то

Задание 3

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

Решение:

Поскольку выходное значение y(t) в заданной функции зависит от текущего входного значения x(t), то будем строить автомат Мили. Так как в заданной функции каждое выходное значение зависит от текущего входного значения и от входного значения в момент, непосредственно предшествующий моменту t, поэтому будем рассматривать состояния автомата, соответствующие различным значениям x(t-1):

- "на предыдущем такте поступил 0"

- "на предыдущем такте поступила 1".

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

0... 0

1... 0

0... 0

1... 1

0... 0

1... 0

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

0... 0

1... 0

0... 0

1... 1

Запишем канонические уравнения полученного автомата: