Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Программа дисциплины'
Одобрена на заседании кафедры Зав. кафедрой « » 0__ г Москва, 0__ г. * Число данных отметок должно соответствовать количеству кафедр,...полностью>>
'Документ'
Подписание соглашения между Правлением Зоны высоких и новых технологий г. Яньтай, Китай и Донским государственным техническим университетом об открыти...полностью>>
'Документ'
зеленый 700 Костюм «Автомастер» синий + василек 850 Костюм х/б «Производственник» СОП синий + василек (куртка + полукомбинезон) 900 Костюм "Патруль" к...полностью>>
'Документ'
Открытое акционерное общество «Радиотехнический институт имени академика А.Л.Минца» (ОАО РТИ) проводит конкурентную процедуру Запрос цен, и в этой свя...полностью>>

Главная > Документ

Сохрани ссылку в одной из сетей:
Информация о документе
Дата добавления:
Размер:
Доступные форматы для скачивания:

Самостоятельные задания по курсу

Математическая логика и теория алгоритмов

Задание 1 Эквивалентные преобразования булевых функций.

Запишите формулы 3-х булевых функций от 4-х аргументов.

Для каждой функции:

• построить таблицу истинности;

• построить ее СДНФ и СКНФ;

• минимизировать ее в классе ДНФ с помощью карты Карно;

• минимизировать ее в классе КНФ с помощью карты Карно;

• построить функциональную схему, ее реализующую;

• исходя из формулы, аналитически построить ее ДНФ, КНФ и полином Жегалкина;

• построить ее полином Жегалкина из таблицы истинности;

• построить ее семантическое дерево;

• построить ее бинарную диаграмму решений (BDD).

Задание 2. Базисы. Теорема Поста.

Постройте ТИ булевой функции от 3-х аргументов.

• проверить ее включение в пять замкнутых классов;

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

• по алгоритму Поста реализовать из функций этого набора константы, отрицание, конъюнкцию (дизъюнкцию);

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

Задание 3. Бинарные решающие диаграммы.

Запишите формулы двух булевых функций F1 и F2 от 4-х аргументов.

Постройте BDD каждой функции.

По этим BDD постройте BDD функции F1*F2, где * - какая-либо двоичная операция

Задание 4. Логический вывод в логике высказываний

По заданной схеме рассуждений, например:

р q

s  q

q p  r

s

--------------

 r

• построить рассуждение на естественном языке;

•проверить его правильность:

- с помощью таблиц истинности,

- сведением к нормальным формам,

- методом резолюции;

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

Задание 5. Логика предикатов

Для ППФ логики предикатов, например: "x Р(x, a )  $y Q(f(y), a )

постройте две интерпретации: одну – модель, а другую - контрмодель

Задание 6. Логический вывод в логике предикатов

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

По схеме каждого модуса:

• построить свое умозаключение на естественном языке;

• построить формальное представление умозаключения;

• при необходимости построить скулемовскую форму;

• проверить правильность рассуждения методом резолюции с помощью графа;

• построить обоснование доказательства правильности следствия из утверждений этого рассуждения на естественном языке на основе метода резолюции.

Задание 7. Метод Флойда верификации программ

По предусловию I, фрагменту программы S и постусловию R, например:

{z+a*b

проверить частичную корректность S относительно I и R двумя способами: построением сильнейшего постусловия и построением слабейшего предусловия.

Задание 8. Конечные автоматы: реализация

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

(а) программную:

• в виде блок-схемы;

• в виде программы на языке С.

(б) аппаратную:

• построить таблицу переходов и выходов;

• выполнить двоичное кодирование входов, состояний и выходов.

• построить двоично-кодированную таблицу переходов и выходов и структурную схему автомата;

• минимизировать все функции функционального блока с помощью карт Карно,

• построить функциональную схему автомата.

Задание 9. Конечные автоматы: минимизация

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

Задание 10. Построение решетки неподвижных точек отображения на конечном множестве

По заданной структуре Крипке М и отображению  построить все неподвижные точки 



Похожие документы:

  1. Задание формул деревьями, схемы из функциональных элементов (сфэ). Оценка числа формул и сфэ в базисе б 0 ={&,۷,ך} ([1: гл. 2,§§2,3])

    Документ
    ... на эквивалентные преобразования и структурное моделирование. По заданным эквивалентным формулам или КС построить эквивалентное преобразование, ... . М.: МГУ, 1984. Нигматулин Р.Г. Сложность булевых функций. М.: Наука, 1991. Яблонский С.В. Введение ...
  2. Задание в Mathcad сигналов в виде функций и векторов. В mathcad для задания различных функций

    Документ
    ... Задание в Mathcad сигналов в виде функций и векторов. В Mathcad для задания различных функций ... при использовании встроенных функций: преобразования Фурье (FFT(u)), ... с использованием булевых операторов ( ... ,0,1) будет эквивалентно функции Φ(t-τ_i) ...
  3. Эта глава описывает допустимые имена переменных и функций Mathcad, предопределенные переменные подобные, а также представления чисел

    Документ
    ... функции в заданной ... эквивалентный простой интеграл вместо двойного интеграла. Рисунок 10: Двойные интегралы. Булевы ... преобразования Функции, связанные с дискретным комплексным преобразованием Фурье и волновым преобразованием. Функции сортировки Функции ...
  4. Рабочая учебная программа по дисциплине теория дискретных устройств автоматики и телемеханики (название)

    Рабочая учебная программа
    ... функции алгебры логики (ФАЛ). 2.1.4. Способы задания ФАЛ. 2.1.5. Полные системы ФАЛ, понятие о булевом базисе. 2.2. Преобразование булевых функций ... которые можно изъять без нарушения эквивалентности исходной функции; минимальной ДНФ (МДНФ) называется ...
  5. Программа дисциплины Дискретная математика для направления Прикладная математика и информатика 010500 подготовки бакалавра Авторы О. П. Кузнецов, olkuznes@ipu rssi ru

    Программа дисциплины
    ... множеств. Понятие функции. Обратные функции. Суперпозиции и формулы. Способы задания функций. Общее понятие ... формы. Эквивалентные преобразования булевых формул. Алгебра Жегалкина. Функциональная полнота. Линейные и монотонные функции. Теорема ...

Другие похожие документы..