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

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

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

Задание 1

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

[image]

Решение:

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

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

Задание 2

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

[image]

Решение:

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

[image]

[image]

Поскольку [image], [image], [image], [image], то

[image]

[image]

Задание 3

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

[image], [image], [image]

Решение:

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

[image] - «на предыдущем такте поступил 0»,

[image] - «на предыдущем такте поступила 1».

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

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

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

[image]