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

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

Часть 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

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

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

Часть программы	Область определения	Область значений
Программа	список строк	список строк
заголовок программы	список строк	состояния выполнения
Точка	состояния выполнения	список строк
Блок	состояния выполнения	состояния выполнения
Объявление	состояния выполнения	состояния выполнения
Оператор	состояния выполнения	состояния выполнения
символьное выражение	состояния выполнения	символьное значение
логическое выражение	состояния выполнения	логическое значение

начение оператора IF

Частное значение оператора IF теперь может быть выражено как функция. Как и для других операторов, его значение – соответствие между состояниями выполнения. Пусть b – логическое выражение и T и E – операторы. Определим:

IF b THEN T ELSE E = {<s, T (s)>: b (s) = T} È {<s, E (s)>: b (s) = F}

Первое множество содержит в себе пары, где выражение b истинно для аргумента s, второе множество содержит пары, где b ложно для s. Поскольку b не может быть одновременно T и F, не существует состояния, которое может оказаться одновременно в обоих множествах.

Важно заметить, что вариант, когда значение данного выражения не определено. Приведенные множества могут содержать или не содержать определенные пары, и возможен вариант, когда b(s) не вычислимо, поскольку s не содержит нужной пары, следовательно значение оператора IF не может быть вычислено. Но даже если b(s) определено на s, частное значение может оказаться неопределенным, поскольку в случае b(s) = T может оказаться, что на s не определено T или в случае b(s) = F неопределенным может оказаться E.

Например, пусть u будет:

IF V1 < V2

THEN

V1 := V2

ELSE

V2 := V1

Тогда:

u = {<s, V1 := V2(s)>: V1 < V2 (s) = T} È {<s, V2 := V1(s)>: V1 < V2 (s) = F}

Для состояния s = {V1·A, V2·B, …}

V1 < V2 ({V1·A, V2·B, …}) = T

и значение u для такого состояния будет представлено значением V1 := V2:

u({V1·A, V2·B, …}) = V1 := V2({V1·A, V2·B, …}) = {V1·B, V2·B, …}

Определение частного значения оператора IF согласуется с результатами таблицы выполнения, но идеи разные. В таблице выполнения фиксируется определенная последовательность действий: вычислить выражение V1 < V2, потом выполнить присваивание V1 := V2 и т.д. Функциональное представление наоборот не содержит концепции последовательности действий.

Оператор IF без ELSE состоит только из логического условия b и выражения T:

IF b THEN T = {<s, T (s)>: b (s) = T} È {<s, s>: b (s) = F}

Например:

IF EOF THEN WRITELN(‘Ooops…’) ({INPUT ·<XXX, XX/, R>, OUTPUT ·<††, ††, W>, …})

= {INPUT ·<XXX, XX/, R>, OUTPUT ·<††, ††, W>, …}

Потому что

EOF({INPUT ·<XXX, XX/, R>, OUTPUT ·<††, ††, W>, …}) = F

Т.е. получаем второй вариант в определении IF b THEN T когда исходное состояние находится в паре с самим собой.

нализ условных выражений.

Значения операторов IF может быть представлено условным присваиванием, расширением идеи одновременного присваивания (concurrent assignment). Выполнение программ с условными выражениями может быть записано в виде набора трассировочных таблиц с новым столбцом, добавляемым для отслеживания условия.

словные присваивания.

Условное присваивание – это обобщение идеи одновременного присваивания, которое позволяет анализировать операторы IF напрямую, подобно тому как одновременное присваивание позволяет легче анализировать операторы BEGIN. Частное значение оператора IF имеет две возможности, определяемые по <условию>. Условное присваивание показывает альтернативы вместе с логическим условием, которое определяет выбор между ними. Синтаксис условного присваивания также не является частью синтаксиса Паскаля, но может быть присоединен к оператору в комментариях.

Условные присваивания могут быть определены рекурсивно по следующим правилам:

1. Одновременное присваивание это условное присваивание.
2. Если b логическое условие b и с – условное присваивание, то (b -> c ) является условным присваиванием.
3. Если b логическое условие b и с и d – условные присваивания, то (b -> c ) | d является условным присваиванием.

Условное присваивание, которое оказывается одновременным присваиванием C может быть записано в виде (T –> С) [T = TRUE].

Условное присваивание будет в форме

(b₁ -> c₁) | (b₂ -> c₂)| … | (b_n -> c_n)

для любого количества условий (b_1, b_2, …,b_n) и условных присваиваний (c₁, c₂, …, c_n)

его значением будет первое условное присваивание, скажем c₁ , такое что:

i. все логические условия до b_i т.е (b₁,b_{2, .} …, b_i-1) имеют значение F в состоянии s, и

ii. Логическое условие b_i имеет значение T

Значение не определено для состояния s, в любом из следующих случаев:

i. Ни одно из логических условий b₁,b_{2, .} …, b_n не принимает значения T в s;

ii. Первое логическое выражение, которое не принимает значение F не определено на s.

iii. условное присваивание, выбранное логическим выражением, не определено на s.

Например, оператор IF

IF V1 <= V2

THEN

V1 :=’2’

ELSE

BEGIN

V1 := V2;

V2 := ‘A’

END

имеет условное присваивание:

(V1 <= V2 - > V1 := ‘2’) | (T -> V1, V2 := V2, ‘A’)

выражая знание, что для начального состояния s при V1 <= V2 (s) = T, результат описывается одновременным присваиванием:

V1 := ‘2’

если V1 <= V2 (s) = F, то

V1, V2 := V2, ‘A’

Описывает результат, потому что его условие T.

С другой стороны,

(NOT (EOLN) -> Ch := ‘Z’) | (EOF -> Ch := ‘A’)

описывает выражение, которое прерывает состояние выполнения

{INPUT·<All□gone/, ††, R>, …}

потому что EOLN не определено на этом состоянии, поэтому и условное присваивание не определено.

Логические условия называются охранниками присваиваний, в общем виде каждый элемент состоит из защищенного присваивания.

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

((V1 = V3) OR (V1 <>V3) -> Ch1, V3 := ‘A,’V1,)

это то же самое, что одновременное присваивание:

(Ch1, V3 := ‘A’, V1)

Такое условное присваивание называют незащищенным, поскольку оно всегда выполняется.

Например, оператор IF, рассмотренный выше может быть записан как:

{(V1 <= V2 - > V1 := ‘2’) | (V1, V2 := V2, ‘A’)}

IF V1 <= V2

THEN

V1 :=’2’

ELSE

BEGIN

V1 := V2;

V2 := ‘A’

END

Второй компонент условного присваивания является незащищенным. Он может быть записан как:

(V1 <= V2 - > V1 := ‘2’) | (V1 > V2 -> V1, V2 := V2, ‘A’)

Если первый охранник принимает F, второй должен принимать T.

Условное присваивание

< > := < >

в котором не изменяются значения переменных, с защитником T

(T -> < > := < >)

может быть записано просто

( )

и выражает значение пустого оператора, функцию эквивалентности.

Включение такого выражения в конце условного присваивания гарантирует нам, что значение будет всегда определено. Если все предыдущие защитники вычисляются в F, значение будет I благодаря последнему выражению.

Оператор IF без ELSE может быть описан условным присваиванием, как показано в следующем примере:

{(V1 < V2 -> V1 := V2) | ()}

IF V1 < V2

THEN

V1 := V2

Последний элемент, пустое одновременное присваивание, важен, поскольку когда условие равно F, оператор IF имеет значение функции эквивалентности.

(V1 < V2 -> V1 := V2)

не является значением данного оператора IF, потому что оно утверждает, что когда значение V1 не предшествует V2, оператор IF не определен, что не соответствует действительности.