Эквивалентность формул алгебры предикатов

Эквивалентность термов и формул алгебры предикатов. Основные равносильности формул. Канонические формы формул алгебры предикатов.

 

19.1.    Проверить эквивалентность термов  и  на алгебраической системе :

1) ,

;

2) ,

;

3) ,

;

4) ,

.

 

19.2.    Проверить эквивалентность термов  и  на классе алгебраических систем :

1) ,

;

2) ,

;

3) ,

;

4) ,

.

 

19.3.    Проверить эквивалентность формул алгебры предикатов  и  на алгебраической системе :

1) ,

;

2) ,

;

3) ,

.

 

19.4.    Проверить эквивалентность формул алгебры предикатов на классе алгебраических систем :

1) ,

;

2) ,

;

3) ,

;

4) ,

.

 

19.5.    Доказать следующие эквивалентности формул алгебры предикатов (формула  не содержит  свободно):

1) ;

2) ;

3) ;

4) ;

5) ;

6) ;

 

19.6.    Доказать эквивалентность формул алгебры предикатов, используя эквивалентные преобразования из упражнения 19.5 (формула  не содержит  свободно):

1) ;

2) ;

3) ;

4) ;

5) .

 

19.7.    Найти приведенные нормальные формы для следующих формул:

1) ;

2) ;

3) ;

4) .

 

19.8.    Найти предваренные нормальные формы для следующих формул:

1) ;

2) ;

3) ;

4) ;

5) .

 

19.9.      Формализовать утверждения, определив подходящие предикаты:

1) Сестры Мери дружат друг с другом.

2) Никто не является сестрой самого себя.

3) У Пола нет сестер.

4) Если три сестры Анны пойдут на концерт, то на концерт пойдут все сестры Анны.

5) Пол и Анна имеют не более двух общих друзей.

6) Все, идущие на концерт, являются чьими-нибудь сестрами.

7) Не все сестры Пола пойдут на концерт.

8) Сестра сестры индивида также является сестрой данного индивида.

9) У Мери ровно три сестры.

19.10.    Запишите на формальном языке, используя следующие предикаты:

,

,

,

1) Через каждые три точки, не лежащие на одной прямой, можно провести единственную плоскость.

2) Через каждые две точки можно провести прямую, и если эти точки различные, то прямая единственна.

3) Через точку, не лежащую на данной прямой, можно провести на плоскости не более одной прямой, параллельной данной.

4) Какова бы ни была прямая, существуют точки, принадлежащие этой прямой, и точки не принадлежащие ей.

5) Две различные прямые либо не пересекаются, либо пересекаются в одной точке.

6) Если две различные прямые имеют общую точку, то через них можно провести плоскость, и притом только одну.

7) Через прямую и не лежащую на ней точку можно провести плоскость, и притом только одну.

 

19.11.    Запишите в подходящей сигнатуре следующие определения:

1) параллельных прямых;

2) скрещивающихся прямых;

3) параллельных плоскостей;

4) точной верхней грани множества;

5) предела последовательности;

6) совместности системы уравнений ;

7) пересечения множеств;

8) объединения множеств;

9) пустого множества;

10) единичного множества.

 

19.12.    Запишите в подходящей сигнатуре следующие аксиомы:

1) полугруппы;                         6) кольца с единицей;

2) группы;                                 7) области целостности;

3) абелевой группы;                 8) тела;

4) кольца;                                  9) поля;

5) коммутативного кольца;      10) частично упорядоченного

                                                               множества;

                                                      11) линейно упорядоченного

                                                               множества.