Решение:

Составим таблицу истинности функции

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

По таблице истинности составим СДНФ:

Преобразуем полученную СДНФ и получим минимальную ДНФ:

Задача 6

Записать утверждение на языке логики предикатов

Для любых 3 точек существует содержащая их плоскость

Решение:

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

То есть это означает, что каждая из трех точек принадлежит плоскости.

Задача 7

Проверить истинность формулы ( и - прямые, - точка)

Решение:

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

Формула не является истинной.

Задача 8

Определить область истинности предиката

Решение:

Поскольку все переменные натуральные числа, то получаем что может принимать следующие значения (для того чтобы предикат был истинным):

, тогда и

, тогда и

, тогда и

Запишем область истинности:

Задача 9

Для схемы переключателей составить формулу (функцию проводимости). Упростить схему.

Решение:

Составим формулу:

Для того чтобы упростить схему, упростим формулу, а затем построим новую схему:

Таким образом, новая схема выглядит так:

Задача 10

Граф задан матрицей смежности

1) Составить матрицу смежности дополнительного графа

2) Задать и графически и матрицами инцидентности и . Рассчитать степени вершин графов.

3) Изоморфны ли графы и ?

4) Являются ли графы и связными? Определить количество компонент связности, найти мосты и точки сочленения.

5) Привести пример цикла в графе и цепи, не являющейся циклом в графе

6) Являются ли графы и а) планарными, б) двудольными, в) эйлеровыми, г) гамильтоновыми?

7) Привести пример остовного ациклического подграфа графа