формы. Назовем скобочной нормальной формой (с.н.ф.) булевой функции f такое представление f в базисе {&, \/, }, при котором операция инверсии применяется только к отдельным переменным.

Назовем сингулярной (или особенной) такую с.н.ф., в которой никакие две подформулы, входящие в одну конъюнкцию, не содержат одинаковых переменных [1, 2, 17, 18].

В [18] показано, что задача выполнимости к.н.ф. сводится к построению сингулярной с.н.ф. для исследуемой к.н.ф.

Литература

1.Анкудинов Г.И. Синтез структуры сложных объектов: логикокомбинаторный подход. – Л.: Изд-во Ленингр. ун-та, 1986.- 260с.

2.Анкудинов Г.И., Золотов О.А., Петухов О.А. Логическое программирование на языке Prolog: Учеб.пособие. – СПб.: СЗТУ, 2001. – 172с.

3.Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. – М.: Мир, 1982. – 416с.

4.Заде Л. Понятие лингвистической переменной и его применение к принятию приближенных решений. – М.: Мир, 1976. – 150с.

5.Ковальски Р. Логика в решении проблем: Пер. с англ.- М.: Наука, 1990.– 280с.

6.Лингер Р., Миллс Х., Уитт Б. Теория и практика структурного программирования: Пер. с англ. – М.: Мир, 1982.− 406с.

7.Мендельсон Э. Введение в математическую логику. – М.: Наука, 1984. – 320с.

8.Минский М. Вычисления и автоматы. − М.: Мир, 1971. – 368с.

9.Нильсон Н. Искусственный интеллект: Пер. с англ. − М.: Мир, 1973.– 270с.

10.Новиков П.С. Элементы математической логики. – М.: Физматгиз, 1959.

– 400с.

11.Основы кибернетики. Математические основы кибернетики: Учеб.пособие. Под ред. К.А.Пупкова. - М.: Высш.шк., 1974. – 413с.

12.Сигорский В.П. Математический аппарат инженера. – Киев: Технiка, 1977. – 768с.

13.Формальная логика: Учеб.пособие / Под ред. И.Я.Чупахина, И.Н.Бродского. - Л.: Изд-во Ленингр. ун-та, 1977. – 360с.

14.Шоломов Л.А. Основы теории дискретных логических и вычислительных устройств: Учеб.пособие. – М.: Наука, 1980. – 400с.

15.Turing, A.M. On computable numbers, with an application to the Entscheidungsproblem // Proc. London Math. Soc., ser.2, 42, 1936. – P.230– 265.

181

16. Ankoudinov, G.I. On one general approach to structural synthesis of algorithms, devices and systems // Kibernetika.- Kiev, No.1, 1982.– P.65-68 (English translation by The Plenum Publishing Corporation, USA).

17.Ankoudinov, G.I. Symbolic-numerical methods in discrete programming problems with logical constraints // Kibernetika.- Kiev, No.3, 1989. (English translation by The Plenum Publishig Corporation, USA).– P.51–55.

18.Ankoudinov, G. Advanced morphological approach to systems structural modelling // the Fourth St.Petersburg Workshop on Simulation, St.Petersburg State University, June 18-23, 2001.– P.145–150.

182

102

103

Анкудинов Георгий Иванович Анкудинов Иван Георгиевич Петухов Олег Александрович

МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ

Учебное пособие

Редактор И.Н.Кочугина

Сводный темплан 2003 г.

Лицензия ЛР №020308 от 14.02.97

Северо-Западный государственный заочный технический университет

РИО СЗТУ, член Издательско-полиграфической ассоциации вузов Санкт-Петербурга

191186, Санкт-Петербург, ул.Миллионная, 5

2