Вопросы и упражнения для самостоятельной работы

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

1. На множестве натуральных чисел :

а) — четное};

б) — нечетное};

в) }; г)}.

2. На множестве точек действительной плоскости :

а) |инаходятся на одинаковом расстоянии от оси};

б) | векторыиколлинеарны};

в) в без начала координат| векторыиколлинеарны}.

3. На множестве всех подмножеств универсального множества :

а) |является дополнениемв}.

4. На множестве людей:

а) |моложе}; б)|знаком с};

в) |— прямой потомок}.

Пусть , аи— отношения на:

;

;

.

Указать все отношения, которые являются

а) симметричными; б) рефлексивными;

в) транзитивными; г) антисимметричными.

В условиях предыдущей задачи найти ,,,.

Построить отношение на множестве , которое

а) рефлексивно и симметрично, но не транзитивно;

б) симметрично и транзитивно, но не рефлексивно;

в) транзитивно и рефлексивно, но не симметрично.

§1.4. Логика высказываний

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

Логические операции над высказываниями

1. Отрицание. Обозначаетсяили, читается «не»,.

2. Конъюнкция. Обозначается, читается «и»,.

3. Дизъюнкция. Обозначается, читается «или»,.

4. Импликация. Обозначается, читается «если, то» или «изследует»,.

Эти определения можно свести в следующие таблицы истинности:

Примеры

1. Найти значение истинности следующих высказываний:

а) ; б);

в) .

Решение.а) Имеем:,. Поскольку из лжи следует все что угодно, тои.

б) Имеем: ,. Поскольку из истины никогда не следует ложь, тои.

в) Имеем: ,. Так как, то. Далее:, откуда. Поскольку, то и все высказывание истинно.

2.Построить таблицу истинности для следующей формулы логики высказываний:.

Решение.Имеем:

0 0 0	1	1	1
0 0 1	1	1	1
0 1 0	1	0	0
0 1 1	1	1	1
1 0 0	0	1	0
1 0 1	0	1	0
1 1 0	1	0	0
1 1 1	1	1	1

3.Используя таблицы истинности, доказать эквивалентность формули.

Решение.Формулы эквивалентны, если они принимают одинаковые значения при одинаковых значениях входящих в них элементарных высказываний. Построим таблицу истинности:

0 0	1 1	0	1	1
0 1	1 0	1	0	0
1 0	0 1	1	0	0
1 1	0 0	1	0	0

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

4.Доказать, что из формуллогически следует.

Решение.Воспользуемсяметодом резолюций. Покажем, что набор формул(последняя формула — это отрицание формулы) невыполним, т.е. ни при каком наборе значений истинности элементарных высказыванийформулы этого набора не могут оказаться истинными одновременно. Будем строить список дизъюнктов следующим образом: каждый дизъюнкт в списке либо входит в первоначальный набор, либо является резолюцией выписанных ранее дизъюнктов. При этом мы пользуемся тем, что из формулилогически следует формула, называемая ихрезолюцией.

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

Составим соответствующий список дизъюнктов (около резолюций в скобках указаны номера дизъюнктов, из которых они получены):

(1) ; (2); (3); (4);

(5) (2, 3); (6)(4, 5); (7)(1, 6);

(8) (5, 7); (9)(3, 8).

Следовательно, набор формул невыполним, и утверждение доказано.