Предисловие

Данное пособие является переработкой и дополнением части 1 пособия "Практические занятия по алгебре и теории чисел", вышедшей в 1987 году. Оно дополнено значительным количеством новых упражнений как для аудиторных занятий, так и для самостоятельной работы студентов. Переработке подверглась структура пособия. Оно теперь разбито на темы. В каждой теме приведены краткие сведения из теории, необходимые для решения упражнений. Сами упражнения разбиты на три части. В части "Практические задания" даются типовые задачи для решения студентами всей группы, в части "Самостоятельная работа" – задачи для домашнего задания и более трудные, адресованные сильным студентам. Каждая тема заканчивается третьей частью – хотя бы одной задачей повышенной трудности, для решения которой нужны интуиция, способности и интерес к предмету.

Последовательность рекомендуемых тем не является обязательной.

Данное пособие разработано в соответствии с документами:

1) ГОС ВПО. Специальность 032100.00 – Математика с дополнительной специальностью. – М., 2000.

2) Министерство Народного Образования РСФСР. Программы педагогических институтов. Алгебра и теория чисел. – М., 1990.

Некоторые из приведенных тем могут быть пропущены или изучаться в обзорном порядке.

Тема 1. Исчисление высказываний

Понятие "высказывание" первично. Любое высказывание либо истинно (и), либо ложно (л).

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

А	В	АВ	А  В	А  В	А  В
и и л л	и л и л	и л л л	и и и л	и л и и	и л л и

АВ (иначе А  В, А  В) – конъюнкция высказываний;

А В – дизъюнкция высказываний;

А  В – импликация высказываний;

А  В – эквиваленция высказываний;

(иначе  А) – отрицание, задается следующей таблицей

А
и л	л и

Основные равносильности

1. АА  А, А  А  А – законы идемпотентности;

2. АВ  ВА, А  В  В  А – законы коммутативности;

3. А(ВС)  (АВ)С, А  (В  С)  (А  В)  С – законы ассоциативности;

4. А(В  С)  АВ  АС, А  ВС  (А  В)(А  С) – законы дистрибутивности;

5. А  В   В – закон освобождения от стрелки;

6. А  В  (А  В)(В  А) – закон освобождения от двусторонней стрелки;

7. – законы де Моргана;

8. А   1 – закон исключенного третьего;

9. А  0 – закон противоречия;

10. А(  В)  АВ, А  В  А  В – законы вытеснения;

11. А  АВ  А, А(А  В)  А – законы поглощения;

12. А  1  1, А  0  0 – аннулирующие свойства 1 и 0;

13. А  0  А, А  1  А – нейтральность 0 и 1;

14. АВ  А  ВС  А  ВС – нарушение симметрии по одному атому;

15. А  АС   А  – нарушение симметрии по двум атомам.

Если F  1, то F называется тавтологией (обозначение ╞ F), если F  0, то F называется противоречием.

F – логическое следствие (система посылок), если F принимает значение И во всех случаях, когда все посылки принимают значение И (обозначение ╞ F).

Теорема: ╞ F тогда и только тогда, когда ╞  F (то есть  F  1).