Глава 1. Реализация конечных функциональных преобразователей

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

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

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

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

• методы представления булевых функций.

Содержание: Постановка проблемы. Булевы функции. Свойства булевых функций. Нормальные формы представления булевых функций. Преобразование в нормальную форму. Реализация булевых функций. Минимизация булевых функций. Функциональная полнота. Алгебра Жегалкина и линейные функции. Замкнутые классы булевых функций. Теорема Поста. Формы представления булевых функций. Семантические деревья. Бинарные диаграммы решений. Булевы алгебры и их свойства.

Примеры задач к главе 1:

1. Выразить функцию xy zu с помощью стрелки Пирса.

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

Глава 2. Введение в математическую логику

Целью главы является демонстрация некоторых связей между продуктивным мышлением человека, порождающим новое знание, и алгоритмическим функционированием компьютеров. В результате изучения материала этой главы читатель должен получить:

• общее представление о построении и использовании формальных моделей для решения инженерных проблем;

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

• знание методов логического вывода;

• знание основ логики предикатов;

• понимание формального базиса логического программирования (в частности, языка Пролог);

• опыт построения на Прологе простых логических программ.

Содержание:

Формальные модели. Логика высказываний. Формулировка и доказательство теорем. Проверка доказательных рассуждений. Силлогизмы. Логическое следствие. Приведение к нормальным формам. Метод резолюции. Основы логики предикатов. Логический вывод в логике предикатов. Логическое программирование. Программирование на языке Пролог. Примеры программ на Прологе: анализ логических схем. Экспертные системы: система управления сложными вычислительными системами фирмы Хьюлетт-Паккард.

Примеры задач к главе 2:

1. [K78. Задача Кислера]. Браун, Джонс и Смит обвиняются в преступлении. На допросе они под присягой дали показания: Браун: Джонс виновен, а Смит невиновен. Джонс: Браун без помощи Смита это не смог бы сделать. Смит: Я невиновен, но кто-то из них виновен. (а) Виноват ли кто-нибудь? (б) Можно ли выдвинуть обвинение против Смита? (в) Если виновный лжет, а невиновный говорит правду, кто виновен?

2. Пусть справедлива теорема: “Сеть Петри согласована и инвариантна только если она жива и ограничена”. Как доказывать эту теорему? Определить, какие из следующих утверждений являются следствиями этой теоремы: (а) Сеть Петри ограничена только в случае, если она инвариантна; (б) Несогласованность сети Петри является достаточным условием отсутствия у нее живости и ограниченности; (а) Если сеть Петри не согласована, то она не может быть неживой, но ограниченной.