РАЗРАБОТКА БНФ ДЛЯ РАЗБОРА ЛОГИЧЕСКИХ ВЫРАЖЕНИЙ

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

• '  – отрицание, инверсия;
• *  – конъюнкция, логическое умножение,‘И’;
• +  – дизъюнкция, логическое сложение, ‘ИЛИ’.

Для этих целей было необходимо определить БНФ для ввода логических выражений. В данной статье приводится описание этой БНФ и блок-схемы реализующие эту БНФ.

БНФ для описания логических выражений

Форма Бэкуса — Наура это формальная система описания синтаксиса, в которой одни синтаксические категории последовательно определяются через другие категории.

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

Функ = Блок Зн.1 ... Блок

Зн.1 = '+'

Блок= Часть Зн.2 ... Часть

Зн.2 = '*'

Часть = </ ' ' ' /> Частица

Частица = Пер ! Цел ! (Функ)

Пер = Б </C…C/>

C = Б ! Ц

Цел = '0'  !  '1'

Б = 'А' ! 'B' ! 'C' ! ... ! 'Z'

Ц = '0' ! '1' ! '2' ! ... ! '9' .

Будем записывать выражение из БНФ и следом блок-схему реализующую алгоритм разбора этого выражения.

Выражение БНФ: Функ = Блок Зн.1 ... Блок ; Зн.1 = '+'.

Выход из цикла: не +.

Блок схема изображена на рисунке 1:

Рисунок 1. Блок схема БНФ

Выражение БНФ:  Блок= Часть Зн.2 ... Часть

Зн.2 = '*'.

Выход из цикла: не *.

Блок схема изображена на рисунке 2:

Рисунок 2. Блок схема БНФ

Выражение БНФ: Часть = </ ' ' ' /> Частица.

Блок схема изображена на рисунке 3:

Рисунок 3. Блок схема БНФ

Выражение БНФ: Частица = Пер ! Цел ! (Функ)

Блок схема изображена на рисунке 4:

Рисунок 4. Блок схема БНФ.

Список литературы:

1. Кретова Л.Д. Элементы математической логики: методические указания к практическим и индивидуальным занятиям / Л.Д. Кретова, Н.Б. Ускова, В.В. Посметьев. Воронеж: ВГТУ, 2005.
2. Нефедов В.Н. Курс дискретной математики / В.Н. Нефедов, В.А. Осипова: Изд-во МАИ, 1992.
3. Яблонский С. В. Введение в дискретную математику. — М.: Наука, 1986.
4. J. C. Madre, O. Coudert, “A Logically Complete Reasoning Maintenance System Based on Logical Constrain Solver”, in Proc. of Int’l Join Conf. on Art. Int., Sydney, Australia, 1991.
5. O. Coudert, J. C. Madre, “Fault Tree Analysis: 1020 Prime Implicants and Beyond”, in Proc. of Annual Reliability and Maintainability Symp, Atlanta GA, 1993.
6. R. Reiter, J. de Kleer, “Foundations for AssumptionBased Truth Maintenance Systems” in Proc. of AAAI National Conf.’87, SeattleWA, 1987.