Доказательство. 1. Необходимость: <a, b> (P · Q) · R <a, z> (P · Q) &<z, b> R <a, x> P&<x

1. Необходимость: < a, b> (P · Q) · R < a, z> (P · Q) & < z, b> R < a, x> P& < x, z> Q& < z, b> R < a, x> P& < x, b> (Q· R) < a, b> (P · (Q · R)) перваячастьдоказана

2. Достаточность: < a, b> (P · (Q · R)) < a, x> P& < x, b> (Q· R) < a, x> P& (< x, d> Q& < d, b> R) < a, x> P& < x, d> Q& < d, b> R < a, d> (P · Q) & < d, b> R < a, b> ((P · Q) · R) втораячастьдоказана.

3. Значит, исходное тождество справедливо.

Основные свойства графиков:

· График Р называется функциональным, если в нем нет пар с одинаковыми первыми и разными вторыми компонентами. Например, Р ={< b, а>, < с, а>, < d, a> }.

· График Р называется инъективным, если в нем нет пар с различными первыми и одинаковыми вторыми компонентами. Например, Р ={< а, b>, < а, c>, < a, d> }.

Композиция функциональных графиков есть функциональный график, т.е. композиция сохраняет функциональность. Композиция инъективных графиков инъективна.

Итак, говорят, что график Р функционален тогда и только тогда, когда Р-1 инъективен. График Р инъективен тогда и только тогда, когда Р-1 функционален.