Высказывания и предикаты

Материал этого и некоторых из следующих параграфов в значительной мере основан на подходе к программированию, применяемом в книге [4], знакомство с которой весьма полезно. Что же касается собственно математической теории предикатов, то нам необходимы только ее основы, и поэтому обращение к какой-либо специальной дополнительной литературе по этой тематике не требуется.

Зачем программисту предикаты

Все знают, что в программах бывают ошибки (bugs). Существуют специальные теории, посвященные тому, как лучше их находить и исправлять ( debugging дословно означает "выведение клопов"). Зачастую нахождение ошибки — очень нетривиальная задача, так как ее последствия могут сказываться совершенно в другом месте программы и быть весьма неожиданными.

При этом часто забывается тот очевидный факт, что ошибку гораздо легче предотвратить при написании программы, нежели найти и исправить потом. Существуют методы проектирования программ (по крайней мере, небольших), позволяющие не только написать правильную программу, но и получить одновременно с этим совершенно строгое доказательство ее правильности. Изучению таких методов и будет посвящена в основном вторая глава данной книги.

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

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

случайно выберите из банки два зерна и

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

если они разного цвета, поместите белое зерно обратно в банку и отбросьте черное зерно.

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

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

Знание теории позволяет получить ответ на вопрос задачи почти мгновенно, однако объяснить это решение практически невозможно без привлечения такого понятия, как инвариант цикла, речь о котором пойдет в нашем курсе значительно позже. Инвариант цикла — это предикат, обладающий некоторыми специальными свойствами. Интересно, что при этом даже пятиклассник может справиться с рассматриваемой задачей, решив ее как-то. Под этим понимается по существу правильное решение, правильность которого доказать абсолютно невозможно.

Теперь рассмотрим вопрос о том, насколько сложно протестировать уже написанную программу. При этом мы будем предполагать для простоты, что для линейной программы (без ветвлений) достаточно всего одного теста, для программы с одним оператором if — двух (чтобы протестировать правильность каждой из его ветвей) и так далее.

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

Вернемся к нашей модели. Если в программе 10 операторов if, то нужно выполнить $$2^{10}=1024$$ теста, а если их 20, то уже $$2^{20}\approx 10^6$$! Можно ли надеяться на то, что в процессе тестирования реальной большой программы удастся проверить все возможные варианты ее работы? Нет, конечно. Именно поэтому так важно не делать ошибок, так как потом их скорее всего просто не обнаружить.

В заключение поговорим о правильности большой программы, состоящей из многих небольших частей. Предположим, что для каждой из этих частей мы можем гарантировать правильность ее работы с вероятностью 99%. Это значит, что в среднем только в одном случае из ста что-то может быть не так, а в 99 случаях каждая часть будет работать абсолютно правильно. Пусть всего таких частей $$n$$. Какова вероятность правильной работы программы в целом?

Это — простейшая задача по курсу теории вероятностей и ответ у нее такой: $$P = p^n$$. Здесь $$p$$ — вероятность правильной работы каждой из частей, а $$P$$ — вероятность правильной работы программы в целом. При $$p=0.99$$ получаем результаты, приведенные в таблице 3.1.

Вероятность правильной работы программы, содержащей n ветвлений

n	10	100	1000
P	0.904	0.366	0.00004

При $$n=100$$ программа будет работать правильно чуть более, чем в одной трети всех ситуаций, а при $$n=1000$$ увидеть ее работающей вообще вряд ли удастся. Этот пример показывает, что нужно всеми силами стараться избегать написания почти правильных программ!

Синтаксис языка предикатов

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

Определение 3.1. Высказывание или предикат — это функция, действующая из некоторого множества значений переменных программы (идентификаторов) в множество из двух значений { $$T$$, $$F$$ } ( Да и Нет ).

В соответствии с ним предикатами будут следующие фразы:

значение переменной i равно двум;

переменная k положительна, а значение переменной m при этом не превосходит 100;

значения всех целочисленных переменных программы являются нулевыми;

неправда, что значение переменной i неположительно.

Чуть менее понятно, можно ли считать предикатами такие фразы:

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

данная программа является правильной;

данное высказывание ложно.

Особенно показательным является последний пример. Если мы согласимся с тем, что он представляет из себя предикат, то возникает естественный вопрос о его истинности. Предположение о том, что он истинен, заставляет считать его ложным, и наоборот. Получаемое противоречие говорит о том, что определение 3.1 не является достаточно корректным.

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

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

Определение 3.2. Алфавит $$\Sigma$$ — произвольное непустое множество.

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

Определение 3.3. Символом алфавита $$\Sigma$$ называют любой его элемент, а цепочкой над алфавитом — произвольную последовательность символов $$\omega$$.

Цепочки часто называют также словами, фразами и предложениями. Пустая цепочка обозначается специальным символом $$\varepsilon$$, а множество всех цепочек над алфавитом $$\Sigma$$ принято обозначать $$\Sigma^*$$. Если в качестве $$\Sigma$$ взять множество букв русского алфавита, дополненное символом пробела и знаками пунктуации, то в $$\Sigma^*$$ будут содержаться все фразы русского языка.

Определение 3.4. Длиной $$|\omega|$$ цепочки $$\omega \in \Sigma^*$$ называется количество входящих в нее символов.

Длина пустой цепочки равна нулю, а длины всех остальных цепочек над любым алфавитом положительны.

Определение 3.5. Операция $$\circ\colon \Sigma^*\times \Sigma^* \rightarrow \Sigma^*$$ конкатенации двух цепочек определена следующем образом. Пусть $$\omega_1 = a_1 a_2 \ldots a_n$$, $$\omega_2 = b_1 b_2 \ldots b_m$$, тогда $$\omega_1 \circ w_2 = a_1 a_2 \ldots a_n b_1 b_2 \ldots b_m$$.

Операция конкатенации, называемая также операцией сцепления или дописывания, обладает следующими свойствами.

Предложение 3.1. Для любых цепочек $$\omega$$, $$\omega_1$$, $$\omega_2$$ и $$\omega_3$$ справедливы следующие равенства:

1) $$\varepsilon\circ \omega = \omega\circ \varepsilon = \omega$$,

2) $$(\omega_1\circ \omega_2) \circ \omega_3 = \omega_1 \circ (\omega_2 \circ \omega_3)$$.

Имея все эти определения, уже можно дать формальное определения языка над алфавитом $$\Sigma$$.

Определение 3.6. Язык $$L$$ — это произвольное подмножество множества цепочек $$\Sigma^*$$.

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

Определение 3.7. Пусть $$\Sigma$$ — некоторый алфавит, $$N$$ — метаалфавит, т.е. какой-то другой алфавит, не пересекающийся с $$\Sigma$$ ( $$\Sigma \cap N = \varnothing$$ ). Элементы метаалфавита $$N$$ называются метасимволами. Грамматикой $$G$$ называется набор ( $$\Sigma, N, P, S$$ ), где $$\Sigma$$ — множество символов, $$N$$ — множество метасимволов, $$P$$ — множество правил вывода вида: $$\alpha\rightarrow\beta$$, где $$\alpha\in N$$ — какой-то метасимвол, $$\beta \in (\Sigma \cup N)^*$$ — произвольная цепочка над объединением двух алфавитов, и для каждого $$\alpha\in N$$ встречается хотя бы одно правило с $$\alpha$$ в левой части (до стрелочки), а $$S \in N$$ — так называемый стартовый метасимвол.

Содержательно каждое правило грамматики имеет смысл подстановки. Например, строка $$\alpha\rightarrow\alpha\gamma\alpha$$ означает возможность замены метасимвола $$\alpha$$ на цепочку $$\alpha\gamma\alpha$$. Начав со стартового символа и пользуясь различными правилами грамматики, мы можем получать различные цепочки из символов, которые называются выводимыми цепочками.

Заметим, что если в цепочке встречается метасимвол, то ее можно преобразовать дальше, применив одно из правил грамматики с этим метасимволом в левой части. Если же метасимволов в цепочке не осталось, то процесс ее преобразования закончен и больше с цепочкой ничего сделать нельзя. По этой причине обычные символы (из алфавита $$\Sigma$$ ) часто называют терминалами, а метасимволы (из $$N$$ ) — нетерминалами.

Определение 3.8. Языком $$L(G)$$, порожденным грамматикой $$G$$, называется множество всех терминальных выводимых цепочек.

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

В качестве примера дадим строгое определение языка предикатов, или, как принято еще говорить, зададим синтаксис этого языка.

Определение 3.9. Множество предикатов — это язык, порожденный следующей грамматикой:

$$e$$ $$\rightarrow$$ $$T$$ (1-е правило: истина)

$$\mid$$ $$F$$ (2-е правило: ложь)

$$\mid$$ $$id$$ (3-е правило: идентификатор)

$$\mid$$ $$(! e)$$ (4-е правило: отрицание)

$$\mid$$ $$(e \lor e)$$ (5-е правило: дизъюнкция)

$$\mid$$ $$(e \lors e)$$ (6-е правило: условное Или )

$$\mid$$ $$(e \land e)$$ (7-е правило: конъюнкция)

$$\mid$$ $$(e \lands e)$$ (8-е правило: условное И )

$$\mid$$ $$(e \limp e)$$ (9-е правило: импликация)

$$\mid$$ $$(e = e)$$ (10-е правило: эквивалентность)

Единственным метасимволом данной грамматики является $$e$$, а алфавит $$\Sigma = \{T, F, !, \lor, \lors, \land, \lands, \limp, =, (, )\} \cup M_{id}$$, где множество $$M_{id}$$ состоит из всех возможных идентификаторов (имен) переменных программ логического типа.

Приведем пример цепочки вывода в данной грамматике: $$e \rightarrow (e \Rightarrow e ) \rightarrow ((e\lor e) \Rightarrow e ) \rightarrow ((a\lor e) \Rightarrow e )\rightarrow ((a\lor T) \Rightarrow e ) \rightarrow ((a\lor T) \Rightarrow a )$$. Этo показывает, что выражение $$((a\lor T) \Rightarrow a )$$ является предикатом. Легко построить другой вывод этого же предиката: $$e \rightarrow (e \Rightarrow e )\rightarrow ((e\lor e) \Rightarrow e ) \rightarrow ((e\lor T) \Rightarrow e ) \rightarrow ((a\lor T) \Rightarrow e ) \rightarrow ((a\lor T) \Rightarrow a )$$. Существует и еще несколько других цепочек вывода для предиката $$((a\lor T) \Rightarrow a )$$, отличающихся порядком замены метасимвола $$e$$ на идентификатор $$a$$ и значение $$T$$. Ясно, что в определенном смысле, который мы не будем сейчас уточнять, все эти цепочки эквивалентны. Говорят, что множество эквивалентных цепочек задает дерево вывода данного предиката, изображенное на рисунке 3.1.

(рис 3.1) Дерево вывода предиката $$(a\lor T) \Rightarrow a)$$

Рассмотрим следующую задачу.

Задача 3.2. Докажите, что выражение $$((a\land b) = (b\lor a))$$ является предикатом.

Решение Для доказательства достаточно предъявить вывод в грамматике 3.9 предложенного выражения, что не слишком трудно: $$e \rightarrow (e=e) \rightarrow ((e\land e)=e) \rightarrow ((e\land e)= (e\lor e)) \rightarrow ((a\land e)=(e\lor e)) \rightarrow((a\land b)=(e\lor e)) \rightarrow((a\land b)=(b\lor e))\rightarrow((a\land b)=(b\lor a))$$.

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

Задача 3.3. Докажите, что выражение $$a\lor a$$ — не предикат.

Решение В самом деле, для того, чтобы в предикате появился символ $$\lor$$, необходимо применить правило $$e \rightarrow (e \lor e)$$, а его применение вызывает появление пары скобок, которых нет в выражении $$a \lor a$$. Ни один из терминальных символов, появившись в процессе вывода, не может измениться в дальнейшем (или исчезнуть). Таким образом, если 5-е правило грамматики 3.9 не применять, то мы не сумеем получить в итоговой цепочке символ $$\lor$$, а если его применить хотя бы раз, то в цепочке будут присутствовать скобки. Полученное противоречие и показывает, что выражение $$a\lor a$$ предикатом не является.

Семантика предикатов

В предыдущей секции мы разобрались с синтаксисом языка предикатов. Теперь нужно обсудить семантику этого языка, то есть придать смысл каждой из цепочек, ему принадлежащих. Иными словами, нам необходимо придать смысл каждому из предикатов. Сделаем это в три этапа, рассмотрев сначала простейшие предикаты $$T$$ и $$F$$, затем константные предикаты, а уж затем определим значение произвольного высказывания.

Определение 3.10. Предикат $$F$$ имеет значение $$False$$ ( Ложь ), а предикат $$T$$ — значение $$True$$ ( Истина ).

Определение 3.11. Назовем предикат константным, если в нем не содержится ни одного идентификатора. Значение любого такого предиката находится с помощью таблицы истинности 3.2 и дерева вывода для него.

Таблица истинности

$$\ b$$	$$\ c$$	$$\ !{} b$$	$$\ b \lor c $$	$$\ b \lors c$$	$$\ b \land c $$	$$\ b \lands c$$	$$\ b \limp c $$	$$\ b = c$$
T	T	F	T	T	T	T	T	T
T	F	F	T	T	F	F	F	F
F	T	T	T	T	F	F	T	F
F	F	T	F	F	F	F	T	T

Рассмотрим, например, константный предикат $$((F\lor T) \Rightarrow F )$$. Изобразим дерево вывода для него и будем, двигаясь снизу вверх, заменять результаты операций в соответствии с таблицей истинности, пока не дойдем до самого корня дерева. Это последнее значение и будет считаться значением предиката (см. рис. 3.2).

(рис 3.2) Определение истинности предиката $$((F\lor T) \Rightarrow F )$$

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

Определение 3.12. Состояние $$s$$ — это отображение из множества идентификаторов в множество { $$T$$, $$F$$ }. Пространство состояний переменных программы — это прямое произведение множеств состояний всех переменных программы.

Теперь можно дать определение значения любого предиката в заданном состоянии.

Определение 3.13. Значение предиката $$e$$ в состоянии $$s$$ (записывается как $$e(s)$$ или $$s(e)$$ ) совпадает со значением константного предиката, который получается из предиката $$e$$ заменой всех идентификаторов на их значения в состоянии $$s$$.

Предикат $$((a \lor T) \Rightarrow b )$$, например, в состоянии $$s=\{(a,T), (b,F)\}$$ имеет значение $$F$$, ибо именно таково значение константного предиката $$((T \lor T) \Rightarrow F )$$.

Из таблицы истинности следует, что операции дизъюнкции $$\lor$$ и условного Или $$\lors$$, а также конъюнкции $$\land$$ и условного И $$\lands$$ попарно эквивалентны. Это действительно так, но только до тех пор, пока мы остаемся в рамках действия определения 3.12. Для нужд описания реального мира, однако, полезно его несколько ослабить и разрешить некоторым переменным оставаться неопределенными.

Определение 3.14. Состояние $$s$$ в расширенном смысле — отображение из множества идентификаторов в множество { $$T$$, $$F$$, $$U$$ }, где символ $$U$$ означает неопределенное (undefined) значение.

Большинство предикатов не имеют определенного значения в таком состоянии, в котором не определены некоторые из переменных, входящих в него. В частности, операции $$!$$, $$\lor$$, $$\land$$, $$\Rightarrow$$ и $$=$$ дают результат $$U$$, если хотя бы один из операндов имеет значение $$U$$. Совершенно другая ситуация с условными операторами. Для них справедлива таблица истинности 3.3.

Таблица истинности для условных операторов

b	T	T	F	F	T	F	U	U	U
c	T	F	T	F	U	U	T	F	U
b || c	T	T	T	F	T	U	T	U	U
bc	T	F	F	F	U	F	U	U	U

Таблица истинности предиката $$((a \lor b) = (b \lor a))$$

$$\ a$$	$$\ b$$	$$\ (a \lor b)$$	$$\ (b \lor a)$$	$$\ ((a \lor b) = (b \lor a))$$
F	F	F	F	T
T	F	T	T	T
F	T	T	T	T
T	T	T	T	T

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

Определение 3.15. Предикат называется тавтологией, если он истинен во всех состояниях, в которых он определен.

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

Определение 3.16. Высказывания $$e1$$ и $$e2$$ эквивалентны, если предикат $$e1=e2$$ является тавтологией.

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

Предложение 3.2. Законы коммутативности:

$$((e_1\land e_2) = (e_2\land e_1));$$ $$((e_1\lor e_2) = (e_2\lor e_1));$$ $$((e_1=e_2) = (e_2=e_1)).$$

Предложение 3.3. Законы ассоциативности:

$$((e_1\land (e_2\land e_3)) = ((e_1\land e_2)\land e_3));$$ $$((e_1\lor (e_2\lor e_3)) = ((e_1\lor e_2)\lor e_3));$$ $$(e_1 \lands (e_2 \lands e_3)) = ((e_1 \lands e_2) \lands e_3));$$ $$((e_1 \lors (e_2 \lors e_3)) = ((e_1 \lors e_2) \lors e_3)).$$

Предложение 3.4. Законы дистрибутивности:

$$((e_1\land (e_2\lor e_3)) = ((e_1\land e_2)\lor (e_1\land e_3)));$$ $$((e_1\lor (e_2\land e_3)) = ((e_1\lor e_2)\land (e_1\lor e_3)));$$ $$((e_1 \lands (e_2 \lors e_3)) = ((e_1 \lands e_2) \lors (e_1 \lands e_3)));$$ $$((e_1 \lors (e_2 \lands e_3)) = ((e_1 \lors e_2) \lands (e_1 \lors e_3))).$$

Предложение 3.5.Законы де Моргана:

$$((!(e_1\land e_2)) = ((! e_1) \lor (! e_2)));$$ $$((!(e_1\lor e_2)) = ((! e_1) \land (! e_2)));$$ $$((!(e_1 \lands e_2)) = ((! e_1) \lors (!e_2)));$$ $$((!(e_1 \lors e_2)) = ((! e_1) \lands (! e_2))).$$

Предложение 3.6. Закон отрицания:

$$((!(!e)) = e).$$

Предложение 3.7. Законы исключенного третьего:

$$(e \lor \, (! e) = T)$$ ;

$$(e \lors (! e) = T)$$, если $$e$$ определено.

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

$$(e \land \, (! e) = F)$$ ;

$$(e \lands (! e) = F)$$, если $$e$$ определено.

Предложение 3.9. Закон импликации:

$$((e_1 \Rightarrow e_2) = ((! e_1) \lor e_2)).$$

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

$$((e_1 = e_2)= ((e_1 \Rightarrow e_2)\land (e_2 \Rightarrow e_1))).$$

Предложение 3.11. Законы упрощения дизъюнкции:

$$((e\lor e) = e);$$ $$((e\lor T) = T);$$ $$((e\lor F) = e);$$ $$((e_1\lor (e_1\land e_2)) = e_1).$$

Предложение 3.12. Законы упрощения конъюнкции:

$$((e\land e) = e);$$ $$((e\land T) = e);$$ $$((e\land F) = F);$$ $$((e_1\land (e_1\lor e_2)) = e_1).$$

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

$$((e \lors e) = e)$$ ;

$$((e \lors T) = T)$$, если $$e$$ определено;

$$((e \lors F) = e)$$ ;

$$((e_1 \lors (e_1 \lands e_2)) = e_1)$$.

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

$$((e \lands e) = e)$$ ;

$$((e \lands T) = e)$$ ;

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

$$((e_1 \lands (e_1 \lors e_2)) = e_1)$$.

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

$$(e = e).$$

Расширение понятия предиката

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

Определение 3.17. Будем называть предикатом с переменными любых типов выражение, которое может быть получено из предиката $$P$$ (в смысле определения 3.9 ) заменой произвольного идентификатора $$id$$ на любое заключенное в скобки выражение логического типа с переменными различных типов. Вычисление значения получившегося предиката в произвольном состоянии немедленно сводится к вычислению значения исходного предиката $$P$$.

Начиная с этого момента выражение $$((i<3)\lor(j=0))$$ — предикат, так как для него можно указать следующую цепочку вывода: $$e \rightarrow (e\lor e) \rightarrow (id_1 \lor e) \rightarrow (id_1 \lor id_2) \rightarrow ((i<3) \lor id_2) \rightarrow ((i<3) \lor (j=0))$$. Множеством состояний этого предиката является пространство $$\mathbb{Z}^2$$, так как каждая из двух входящих в него целых переменных может изменяться независимо от другой. Если $$i$$ и $$j$$ — программные переменные, то пространство $$\mathbb{Z}^2$$ следует заменить на $$\mathbb{Z}_M^2$$.

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

if (a==0 || b/a > 0) ...

Следующим шагом в направлении расширения понятия предиката будет использование кванторов существования $$\exists$$ и всеобщности $$\forall$$.

Если $$P(x)$$ — предикат в смысле определения 3.17, зависящий от переменной $$x$$ произвольного типа, а $$X$$ — некоторое множество, то будем считать предикатами выражения $$(\exists x ( x \in X \land P(x)))$$ и $$(\forall x ( x \in X \Rightarrow P(x)))$$. Первое из них означает, что существует хотя бы одно $$x \in X$$ для которого выполнено $$P(x)$$, а второе — что для всех $$x \in X$$ справедливо $$P(x)$$.

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

$$((\exists x \in X) P(x)) = (\exists x (x \in X \land P(x))),$$ $$((\forall x \in X) P(x)) = (\forall x (x \in X \Rightarrow P(x))).$$

Когда используемое множество $$X$$ понятно из контекста, его опускают, что приводит к выражениям $$(\exists x\ P(x))$$ и $$(\forall x\ P(x))$$.

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

$$((\exists !x ) P(x)) = (\exists x (P(x) \land \forall y (P(y) \Rightarrow (y = x)))).$$

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

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

Третьим шагом в направлении расширения множества языка предикатов будет ослабление требования на наличие в предикате всех тех скобок, которые возникают в процессе его вывода. Напомним, что с точки зрения определения 3.9 выражение $$a\lor b$$, например, предикатом не является, что не слишком удобно с практической точки зрения.

Разрешим удалять из предиката все те пары скобок, которые можно опустить без потери его однозначного толкования. При этом семантика полученного предиката определяется приоритетом операций: сначала вычисляются выражения внутри скобок, затем — логические выражения, заменившие логические идентификаторы $$id$$ в смысле определения 3.17, после этого — кванторы существования и всеобщности, а затем — логические операции $$!$$, $$\lands$$ и $$\land$$, $$\lors$$ и $$\lor$$, $$\Rightarrow$$ и, наконец, $$=$$.

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

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

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

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

Задача 3.4. Вычислите значения предикатов $$P_1 = (x=0\ \land\ x/(y-2)=0)$$ и $$P_2 = (x=0 \ \lands \ x/(y-2)=0)$$ в состоянии $$s = \{(x, 7), (y, 2)\}$$.

Решение Если восстановить в этих предикатах все недостающие скобки, то мы получим предикаты $$P_3 = ((x=0) \land ((x/(y-2))=0))$$ и $$P_4 = ((x=0) \lands ((x/(y-2))=0))$$ соответственно. В состоянии $$s$$ выражение $$(x=0)$$ является ложным, ибо $$(7=0) = F$$, а $$x/(y-2)$$ имеет значение $$U$$ (не определено). В соответствии с таблицами истинности для операций $$\land$$ и $$\lands$$ можно сделать вывод, что $$P_1(s) = U$$, а $$P_2(s) = F$$.

Задача 3.5. Вычислите значения предиката $$P = (\exists i \ 0 \leqslant i \leqslant 9 \ (i^2 \leqslant 0)) \land (\forall j \ j^2 \geqslant k)$$ в состоянии $$s = \{(k, 0)\}$$.

Решение Предикат $$P$$ представляет из себя конъюнкцию двух предикатов, первый из которых — это $$\exists i\ 0 \leqslant i \leqslant 9\ i^2 \leqslant 0$$, а второй в состоянии $$s$$ совпадает с $$\forall j\ j^2 \geqslant 0$$. Так как при $$i=0$$ выполнено $$i^2 \leqslant 0$$, то первый из них истинен, а истинность второго предиката не вызывает сомнений. Таким образом, предикат $$P(s)$$, являющийся конъюнкцией двух истинных выражений, сам является истинным, — $$P(s) = T$$.

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

Определение 3.19. Подстановкой $$E^x_e$$ называется выражение, получающееся одновременной подстановкой $$e$$ вместо всех свободных вхождений $$x$$ в $$E$$.

Вот несколько простых примеров: $$(x+y)^x_z 0= (z+y)$$ ; для $$E = x<y \land (\forall i \ i<n \ f(i)<y)$$ имеем $$E^y_{x+y} = x<x+y \land (\forall i\ i<n \ f(i)<x+y))$$, но $$E^i_k = E$$, так как $$i$$ не свободно в $$E$$.

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

Предложение 3.16. Законы построения отрицания:

$$!(\exists x P(x)) = \forall x (! P(x));$$ $$!(\forall x P(x)) = \exists x (! P(x)).$$

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

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

Определение 3.20. Оператор @ является левоассоциативным, если выражение a @ b @ c вычисляется, как (a @ b) @ c ; правоассоциативным, если оно эквивалентно a @ (b @ c) ; неассоциативным — если запись a @ b @ c не имеет смысла.

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

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

В таблице 3.5 все операторы языка Java разбиты на группы с одинаковым приоритетом (операторы с приоритетом 1 выполняются в первую очередь), левоассоциативность обозначена символом $$\longrightarrow$$, а правоассоциативность — символом $$\longleftarrow$$.

Приоритеты и ассоциативность операторов

Пр-т	Оператор	Тип опер.	Асс-ть	Операция
1	++	числовой	$$\longleftarrow$$	пре- и постинкремент
	--	числовой	$$\longleftarrow$$	пре- и постдекремент
	+, -	числовой	$$\longleftarrow$$	унарныe плюс и минус
	~	целый	$$\longleftarrow$$	побитовое дополнение
	!	логический	$$\longleftarrow$$	логическое отрицание
	(type)	любой	$$\longleftarrow$$	преобразование типа
2	*, /, %	числовой	$$\longrightarrow$$	умножение, деление и остаток
3	+, -	числовой	$$\longrightarrow$$	сложение и вычитание
	+	строковый	$$\longrightarrow$$	конкатенация строк
4	<<	целый	$$\longrightarrow$$	сдвиг влево
	>>	целый	$$\longrightarrow$$	сдвиг вправо с размножением знакового бита
	>>>	целый	$$\longrightarrow$$	сдвиг вправо с размножением нуля
5	<, <=	числовой	$$\longrightarrow$$	меньше, меньше или равно
	>, >=	числовой	$$\longrightarrow$$	больше, больше или равно
	instanceof	объект,тип	$$\longrightarrow$$	сравнение типов
6	==	простой	$$\longrightarrow$$	равенство значений простых типов
	!=	простой	$$\longrightarrow$$	неравенство значений простых типов
	==	объект	$$\longrightarrow$$	равенство ссылок на объекты
	!=	объект	$$\longrightarrow$$	неравенство ссылок на объекты
7		целый	$$\longrightarrow$$	побитовое И
		логический	$$\longrightarrow$$	логическое И
8	^	целый	$$\longrightarrow$$	побитовое исключающее Или
	^	логический	$$\longrightarrow$$	логическое исключающее Или
9	|	целый	$$\longrightarrow$$	побитовое Или
	|	логический	$$\longrightarrow$$	логическое Или
10		логический	$$\longrightarrow$$	условное И
11	||	логический	$$\longrightarrow$$	условное Или
12	?:	логический, любой, любой	$$\longleftarrow$$	оператор условия
13	=	любой	$$\longleftarrow$$	присваивание, присваивание с операцией
	*=, /=, %=
	+=, -=
	<<=, >>=
	>>>=, =
	^=, |=

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

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

Задача 3.6.Докажите, что выражение $$((e_1\land (e_2\lor e_3)) = ((e_1\land e_2)\lor (e_1\land e_3)))$$ является предикатом.

Задача 3.7.Докажите, что выражение $$((a\lor a)$$ — не предикат.

Задача 3.8.Изобразите деревья вывода для каждого из законов эквивалентности.

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

Задача 3.9.Решите задачу о банке с кофейными зернами (см. задачу 3.1)