Значение логических выражений. Часть 6 развивает изложение программного исчисления для условных выражений программ, что позволяет нам сформулировать правила проектирования условных

ИСЧИСЛЕНИЕ УСЛОВНЫХ ВЫРАЖЕНИЙ.

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

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

Значение условных операторов.

Значения операторов IF зависят от значения < условия>, которое проверяется при их выполнении. < условие> - логическое выражение, значение которого может быть определено подобно тому как было определено значение символьного выражения. Значение оператора IF может быть представлено через его составные части: < условие> и операторы, которые выполняются в зависимости от результатов его проверки.

Условные выражения - значительная составляющая мощи (и сложности) компьютерных программ. Они предоставляют возможность принимать решения на основе анализа входных данных программы или промежуточных, полученных в результате выполнения программы. Но сами по себе условные выражения не являются сложными, и их значение может быть легко определено.

Значение логических выражений.

Поскольку условные выражения включают в себя логические выражения, мы расширяем box-нотацию, чтобы покрыть условные выражения. Если значение символьного выражения – соответствие символьного значения определенному состоянию выполнения, то значение условного выражения (boolean expression) g - соответствие логического значения определенному состоянию выполнения. Логические выражения принимают значения из множества {TRUE, FALSE}.

Значения логических выражений TRUE и FALSE здесь и далее будут представлены символами T и F соответственно. Поскольку логические выражения могут объединяться с использованием операторов OR, AND, NOT в более сложные выражения, со скобками, определение должно быть рекурсивным.

Простейшее < условие> - это выражение из двух символьных выражений с одним < оператором сравнения> или одна файловая операция EOLN или EOF.

Пусть f – файловый идентификатор, x и y – строки. Определим:

EOF(f) = {< s, T>: s(f) = < x, ††, R> } U {< s, F>: s(f) = < x, y, R>, y ¹ ††}

EOLN(f) = {< s, T>: s(f) = < x, y, R>, Θ y = /} U {< s, F>: s(f) = < x, y, R>, y ¹ ††, Θ y ¹ /}

Когда идентификатор f отсутствует, условия применяются к INPUT и их значения могут быть получены заменой f на INPUT:

EOF(f) = EOF(INPUT)

EOLN(f) = EOLN(INPUT)

Заметим, что когда EOF имеет значение T, текущая строка пуста и значение EOLN не определено.

Например, для определения значения EOF(f) (s) в состоянии s, содержащем пару F1·< A2, 345/, R>, должно быть выбрано одно из двух множеств, объединение которых приведено в определении EOF(f). В данном случае подходит второе множество, потому что y = †345/† ¹ ††, т.е. F находится в паре c s.

EOF(f) (s) = F

Три операции сравнения символов определяются следующим образом:

c = d = {< s, T>: c (s) тот же символ, что и d (s)}

U {< s, F>: c (s) иной символ, чем d (s)}

c < d = {< s, T>: c (s) предшествует d (s)}

U {< s, F>: c (s) не предшествует d (s)}

c > d = d < c

Например, пусть s будет состояние содержащее Ch·A, Ch (s) = A, тогда:

Ch = ‘A’ (s) = T

Ch = ‘X’ (s) = F

Ch < ‘A’ (s) = F

Ch > ‘A’ (s) = F

В определении c < d результат выражения зависит от того, предшествует ли первое символьное значение второму. Эта идея распространяется на все Паскаль-машины, для всех возможных символьных значений. Тем не менее, стандартного определения предшествования не существует, за исключением того, что не существует символа, предшествующего себе и мы знаем, что:

A предшествует B предшествует C … предшествует Z

a предшествует b предшествует c … предшествует z

0 предшествует 1 предшествует 2 … предшествует 9

Отношение предшествования между другими символами зависит от реализации Паскаль-машины. В нашем случае нам будет достаточно случаев описанных выше.

Основываясь на вышесказанном, мы можем определить значение для композиции логических < условий>. Пусть b логическое условие, значение которого нам известно, тогда:

NOT (b) = {< s, T>: b(s) = F} U {< s, F>: b(s) = T}

Для логических условий b и c, определим:

b AND c = {< s, T>: b(s) = T, c(s) = T}

U {< s, F>: b(s) = T, c(s) = F}

U {< s, F>: b(s) = F, c(s) = T}

U {< s, F>: b(s) = F, c(s) = F}

b OR c = {< s, T>: b(s) = T, c(s) = T}

U {< s, T>: b(s) = T, c(s) = T}

U {< s, T>: b(s) = T, c(s) = T}

U {< s, F>: b(s) = F, c(s) = F}

Таким образом, мы определили логические операции NOT, AND, OR, рассмотренные в части 3, обозначив TRUE как T и FALSE как F. Далее, это определение может быть представлено в следующей форме.

NOT b (s) = NOT b (s)

b AND c (s) = b (s) AND c (s)

b OR c (s) = b (s) OR c (s)

Выражения NOT, AND и OR в правой части – операторы языка Паскаль, в левой им соответствуют логические (математические) операции, применяемые к значениям выражений b и с языка Паскаль. Таким образом, мы определили соответствие между значением операторов в языке Паскаль и их математическим (булевским) значением.

Некоторые примеры значений логических выражений:

NOT(Ch = ‘A’) ({Ch·A, …})= F

(Ch1 = ‘A’) AND (Ch2 < > Ch1) = ({Ch1·A, C2·F …}) = T

(Ch1 = ‘A’) OR (Ch2 < > Ch1) = ({Ch1·B, C2·F …}) = T

Частные значения оставшихся логических выражений могут быть определены через уже определенные:

c < > d = NOT (c = d)

c < = d = NOT (c > d)

c > = d = NOT (c < d)

Чтобы вычислить значение составного логического выражения необходимо применить правила в определенном порядке, так чтобы на каждом шаге выражение приближалось к одному из базовых выражений, которые мы можем легко вычислить. Например, пусть:

s= {Ch·F, INPUT·< Line□, 34/ R>, …}

тогда

Ch < > ‘#’ AND (NOT(EOLN)) (s)

= Ch < > ‘#’ (s) AND (NOT(EOLN)) (s)

= NOT Ch = ‘#’ (s) AND (NOT(EOLN)) (s)

= NOT(Ch = ‘#’ (s)) AND (NOT(EOLN)) (s)

= NOT(F) AND (NOT(F)) = T AND T = T

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

Рассмотренные на данный момент частные значения могут иметь следующие области определения и значений: