Программирование на языке Java (стр. 3 )

ОПРЕДЕЛЕНИЕ. Состояние s в расширенном смысле — отобра­жение из множества идентификаторов в множество {Т, F, U}, где символ U означает неопределенное (undefined) значение.

Большинство предикатов не имеют определенного значения в таком состоянии, в котором не определены некоторые из переменных, входящих в него. В частности, операции!, V, Л, =>■ и = дают результат U, если хотя бы один из операндов имеет значение U. Совершенно другая ситуация с условными операторами. Для них справедлива таблица истинности 3.

Среди огромного множества всех предикатов особую роль играют те из них, которые всегда являются истинными, как, например ((!(!а)) = а).

ТАБЛИЦА 3. Таблица истинности для условных операторов

ъ	Т	т	F	F	Т	F	и	и	и
с	т	F	Т	F	и	и	Т	F	и
Ъ с	т	Т	Т	F	Т	и	и	и	и
bkkc	т	F	F	F	и	F	и	и	и

ТАБЛИЦА 4. Таблица истинности предиката ((а V 6) — (6 V а))

а	Ъ	(aVb)	(ЬУ а)	((aV6) = (6Va))
F	F	F	F	Т
Т	F	Т	Т	т
F	Т	Т	Т	т
Т	Т	Т	Т	т

ОПРЕДЕЛЕНИЕ. Предикат называется тавтологией, если он ис­тинен во всех состояниях, в которых он определен.

Один из простейших способов доказать, что предикат является тав­тологией, — это вычислить его значения во всех возможных состояниях. Таблица 4 является доказательством того факта, что предикат ((a V Ь) = (Ь V а)) — тавтология.

ОПРЕДЕЛЕНИЕ. Высказывания el и е2 эквивалентны, если пре­дикат el = е2 является тавтологией.

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

ПРЕДЛОЖЕНИЕ. Законы коммутативности: ((ei Л е2) - (е2 Л ei)); ((eiVe2) = (e2Vei)); ((ei = е2) = (е2 = ei)).

ПРЕДЛОЖЕНИЕ. Законы ассоциативности: ((ei Л (е2 Л еei Л е2) Л е3)); ((e1V(e2Ve3))-((e1Ve2)Ve3)); (ei&&(e2&&e3)) = ((е1&&е2)&&е3)); ((ei||(e2||e3)) = ((ei||e2)||e3)).

ПРЕДЛОЖЕНИЕ. Законы дистрибутивности: ((ei Л (е2 V еei Л е2) V (а Л е3)));

((ei V (е2 Л еei V е2) Л (б1 V е3))); ((ei&&(e2||e3)) = ((е1&&е2)||(е1&&е3))); ((ei||(e2&&e3)) = ((ei||e2)&&(ei||e3))).

ПРЕДЛОЖЕНИЕ. Законы де Моргана: ((!(eiAe2)) = ((!ei)V(!e2))); ((!(e1Ve2)) = ((!e1)A(!e2))); ((!(е1&&е2)) = ((!е1)||(!е2))); ((!(ei||e2)) = ((!ei)&&(!e2))).

Предложение Закон отрицания: ((!(!е)) = е).

ПРЕДЛОЖЕНИЕ. Законы исключенного третьего: (eV (!е)=Г); (е||(!е) = Т), если е определено.

Предложение. Законы противоречия:

(еЛ (\e) = F);

(е&&(!е) = F), если е определено.

Предложение. Закон импликации: ((ei=*e2) = ((!ei)Ve2)).

Предложение. Закон равенства: ((ei - е2) = ((ei =Ф - е2) Л (е2 =Ф ei))).

ПРЕДЛОЖЕНИЕ . Законы упрощения дизъюнкции:

((eVe) = e);

((eVT)=T);

((eVF) = e);

((ei V(eiAe2)) = ei).

ПРЕДЛОЖЕНИЕ. Законы упрощения конъюнкции:

((еЛе) = е); ((еЛГ) = е); ((eAF) = F); ((eiA (ei Ve2)) = ei).

Предложение Законы упрощения условного Или:

((е||е) - е);

((е||Т) = Г), если е определено;

((e\\F) = e);

((ei||(ei&&e2)) = ех).

ПРЕДЛОЖЕНИЕ . Законы упрощения условного И:

((е&&е) = е);

47

((е&&Т) = е);

((e&&F) = F), если е определено;

((ei&&(ei||e2)) = ег).

Предложение Закон тождества: (е = е).

Расширение понятия предиката. В реальных программах далеко не все переменные имеют логический тип, что означает невозможность их описания с помощью предикатов, введенных определением 3.9. Так, например, выражение г < 3 для целочисленной переменной г предикатом в смысле упомянутого определения заведомо не является, что плохо. Эти и некоторые другие причины побуждают расширить множество предика­тов, что и будет сейчас сделано в три этапа.

ОПРЕДЕЛЕНИЕ. Будем называть предикатом с переменными лю­бых типов выражение, которое может быть получено из предиката Р (в смысле определения 3.9) заменой произвольного идентификатора id на любое заключенное в скобки выражение логического типа с переменны­ми различных типов. Вычисление значения получившегося предиката в произвольном состоянии немедленно сводится к вычислению значения ис­ходного предиката Р.

Начиная с этого момента выражение ((г < 3) V (j = 0)) — предикат, так как для него можно указать следующую цепочку вывода: е —> (eVe) —> {idi Ve)4 (idi V id2) -+ ((г < 3) V id2) ->• ((г < 3) V (j = 0)). Множеством состояний этого предиката является пространство Z2, так как каждая из двух входящих в него целых переменных может изменяться независимо от другой. Если г и j — программные переменные, то пространство Z2 следует заменить на Z2^-.

Примером предиката, который определен в состоянии, в котором одна из входящих в него переменных не является определенной, может слу­жить выражение Р = ((а = 0)||(6/а > 0)). В состоянии s — {(а, 0), (6, U)} он истинен: P(s) = Т. Подобные предикаты возникают при описании фрагментов программ типа

if (а==0 II Ъ/а >

Следующим шагом в направлении расширения понятия предиката бу­дет использование кванторов существования 3 и всеобщности V.

Если Р{х) — предикат в смысле определения 3.17, зависящий от пере­менной х произвольного типа, а X — некоторое множество, то будем счи­тать предикатами выражения (Эх(х 6 X А Р(х))) и (\/х (х £l=> Р(х))). Первое из них означает, что существует хотя бы одно х 6 X для кото­рого выполнено Р(х), а второе — что для всех х 6 X справедливо Р(х).

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

((Эх Е Х)Р(х)) = (Зх(х 6 X Л Р(х))),

((Уж е х)Р(х)) = (Ух(х е х =>■ Р(х))).

Когда используемое множество X понятно из контекста, его опускают, что приводит к выражениям (Эх Р(х)) и (Уж Р(х)).

Кроме кванторов существования и всеобщности иногда используют еще один квантор — квантор 3! существования и единственности, который может быть определен с помощью двух основных кванторов следующим образом:

((Э\х)Р(х)) = (Эх(Р(х) ЛЩР(у) =>(у = х)))).

Использование кванторов в предикатах должно удовлетворять некото­рым дополнительным ограничением. Связанным идентификатором бу­дем называть идентификатор, непосредственно следующий в предикате за квантором, а свободным идентификатор — идентификатор, не являю­щийся связанным. Ограничение на использование кванторов в предика­тах таково: в предикате один и тот же идентификатор не может быть как связанным, так и свободным, и, кроме того, идентификатор не может быть связан двумя различными кванторами.

В предикате R — (Уг(га ^ г < п =>- x*i > 0)) идентификатор г является связанным (квантором У), а идентификаторы т, п и х — свободными. Выражение (г > 0Л(Уг(га ^ г < п =>- ж*г > 0))) предикатом мы считать не можем, ибо г в нем является одновременно и свободным идентификатором и связанным, что недопустимо. Его легко слегка изменить так, чтобы оно стало предикатом: (г > 0 Л (\fk(m ^k<n^x*k> 0))) — уже предикат.

Третьим шагом в направлении расширения множества языка предика­тов будет ослабление требования на наличие в предикате всех тех скобок, которые возникают в процессе его вывода. Напомним, что с точки зрения определения 9 выражение а V 6, например, предикатом не является, что не слишком удобно с практической точки зрения.

Разрешим удалять из предиката все те пары скобок, которые можно опустить без потери его однозначного толкования. При этом семантика полученного предиката определяется приоритетом операций: сначала вы­числяются выражения внутри скобок, затем — логические выражения, заменившие логические идентификаторы id в смысле определения 3.17, после этого — кванторы существования и всеобщности, а затем — логиче­ские операции!, && и Л, || и V, =>- и, наконец, =.

Таким образом, мы принимаем следующее определение.

ОПРЕДЕЛЕНИЕ. Будем называть предикатом в расширенном смысле предикат с переменными любых типов (см. определение 3.17), ко­торый может содержать кванторы и не иметь скобок, не являющимися необходимыми для его однозначного толкования.

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

Рассмотрим, как решаются типичные задачи на вычисление значения предикатов в расширенном смысле в различных состояниях.

ЗАДАЧА 3.4. Вычислите значения предикатов Pi = (х = О Л х/(у—2) = 0) и Р2 = (х = 0 kk х/(у - 2) = 0) в состоянии s = {(>, 7), (у, 2)}.

РЕШЕНИЕ. Если восстановить в этих предикатах все недостающие скобки, то мы получим предикаты Р3 = {{х — 0) Л {[х/{у — 2)) = 0)) и Р4 — ((# — 0)kk((x/(y — 2)) = 0)) соответственно. В состоянии s вы­ражение (х = 0) является ложным, ибо (7 — 0) — - F, а х/(у — 2) имеет значение U (не определено). В соответствии с таблицами истинности для операций Л и kk можно сделать вывод, что Pi(s) = С/, a ^(s) = F.

ЗАДАЧА. Вычислите значения предиката Р — (Зг 0 ^ г ^ 9 (г2 ^ 0)) Л (Vj j2 ^ к) в состоянии s = {(к, 0)}.

РЕШЕНИЕ. Предикат Р представляет из себя конъюнкцию двух пре­дикатов, первый из которых — это Зг 0 ^ г ^ 9 г2 ^ 0, а второй в состоянии s совпадает с Vj j2 ^ 0. Так как при г = 0 выполнено г2 ^ 0, то первый из них истинен, а истинность второго предиката не вызывает сомнений. Таким образом, предикат P(s), являющийся конъюнкцией двух истинных выражений, сам является истинным, — P{s) — Т.

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

ОПРЕДЕЛЕНИЕ. Подстановкой Е^ называется выражение, полу­чающееся одновременной подстановкой е вместо всех свободных вхожде­ний х в Е.

Вот несколько простых примеров: (х + y)xz = [z + у); для Е = х < у А (\/г г < п /(г) < у) имеем Е^+у — х < х -\- у /\(yi i < п /(г) < х + у)), но Е\, — Е, так как г не свободно в Е.

Для предикатов с кванторами справедливы дополнительные законы эквивалентности, называемые также правилами построения отрицания.

ПРЕДЛОЖЕНИЕ. Законы построения отрицания: !(ЗжР(ж)) = Уж(!Р(ж)); !(УжР(ж)) = Зж(!Р(ж)).

Приоритеты и ассоциативность операторов языка Java. При

вычислении значения выражения в языке Java важны не только приори­теты, но и ассоциативность операторов.

ОПРЕДЕЛЕНИЕ. Оператор @ является левоассоциативным, если выражение а © b 0 с вычисляется, как (а @ b) ® с; правоассоциатив-ным, если оно эквивалентно а © (Ь @ с) ; неассоциативным — если запись а @ b @ с не имеет смысла.

В этом определении символ @ означает любой из бинарных операторов языка.

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

В таблице 5 все операторы языка Java разбиты на группы с одина­ковым приоритетом (операторы с приоритетом 1 выполняются в первую очередь), левоассоциативность обозначена символом —у, а правоассоци-ативность — символом <—.

Таблица 5. Приоритеты и ассоциативность операторов

Пр-т	Оператор	Тип опер.	Асс-ть	Операция
1	++ +, - ! (type)	числовой числовой числовой целый логический любой		пре - и постинкремент пре - и постдекремент унарные плюс и минус побитовое дополнение логическое отрицание преобразование типа
2	*, /, %	числовой	—У	умножение, деление и оста­ток
3	+	числовой строковый	—У —У	сложение и вычитание конкатенация строк
4	« » >»	целый целый целый	—У —У —У	сдвиг влево сдвиг вправо с размножени­ем знакового бита сдвиг вправо с размножени­ем нуля

Таблица 5. Приоритеты и ассоциативность операторов

Пр-т	Оператор	Тип опер.	Асс-ть	Операция
5	instanceof	числовой числовой объект, тип		меньше, меньше или равно больше, больше или равно сравнение типов
6	! =	простой простой объект объект		равенство значений простых типов неравенство значений про­стых типов равенство ссылок на объек­ты неравенство ссылок на объ­екты
7	& &	целый логический		побитовое И логическое И
8	-	целый логический		побитовое исключающее Или логическое исключающее Или
9	1 1	целый логический		побитовое Или логическое Или
10	&&	логический		условное И
11	II	логический		условное Или
12	?:	логический, любой, любой	<—	оператор условия
13	*=, /=, 7.=, +=, -=, «=, »=, >»=, &=, - 1 =	любой	<—	присваивание, присваивание с операцией

С логическими и условными операторами мы уже знакомы, семанти­ка арифметических операторов объясняется в следующем параграфе, а с оператором instanceof мы разберемся в третьей главе книги.

Задачи для самостоятельного решения.

ЗАДАЧА. Докажите, что выражение ((ei Л (е2 V е3)) — ((ei Л е2) V (ei Л ез))) является предикатом.

ЗАДАЧА. Докажите, что выражение ((а V а) — не предикат.

ЗАДАЧА. Изобразите деревья вывода для каждого из законов экви­валентности

ЗАДАЧА. Покажите, что все законы эквивалентности являются тавтологиями.

ЗАДАЧА. Решите задачу о банке с кофейными зернами