Логіка предикатів

Задачі

На безлічі натуральних чисел визначені предикати P(x) = «число х поділяється на 8» і Q(x) = «х – парне число». Необхідно визначити наступні висловлення і з'ясувати які з них щирі:

"xP(x);

$xP(x);

"xQ(x);

$xù(Q(x));

"xù(Q(x));

"x(P(x)®Q(x));

"x(Q(x)®P(x));

$x(Q(x)®P(x)).

Нехай Х – безліч прямих на площині. На цій безлічі визначені предикати R(x, y) = «пряма х перетинається з прямой у», S(x, y) = «пряма х рівнобіжна прямої у», причому х,уÎХ. Необхідно визначити наступні висловлення і з'ясувати які з них щирі:

"x$yR(x, y);

$x$yù(S(x, y));

"x"y(R(x, y)®ù(S(x, y)));

"x"y(R(x, y)ÚS(x, y)).

На безлічі натуральних чисел визначені предикати P(x) = «число х - просте» і Q(x) = «х – парне число», R(x, y) = «х не дорівнює y». Необхідно перевести на розмовну мову формулу:

$x(P(x)ÙQ(x))Ù`$x(P(x)ÙQ(x)Ù$y(R(x, y)ÙP(y)ÙQ(y))).

Записати формули логіки предикатів для приведених тверджень:

«Кожен студент чи вивчає англійську мову, чи німецьку, чи французьку»;

«Деякі лабораторні стенди укомплектовані осцилографами»;

«Не всі комп'ютери працюють добре»;

«Жоден процесор не виявився забракованим»;

«Усі студенти, що виконали завдання, здали залік».

Граф G = (V, E) визначається завданням непорожньої безлічі вершин V, безлічі ребер Е і тримісного предиката P(x, e, y) = «ребро е з'єднує вершини х и у», що визначений на всіх упорядкованих трійках (x, e, y), причому х, уÎV і еÎЕ (для орграфа х вважається початкової вершиною дуги е, а y – кінцевою вершиною дуги е). Необхідно визначити предикати, що задають твердження:

«Підмножина дуг орграфа, що виходять з вершини а»;

«Підмножина дуг орграфа, що входять у вершину а»;

«Підмножина ребер графа, інцидентних вершині а»;

«Підмножина ребер графа, що з'єднує вершини а і b».

Відповідно до визначень графів із задачі 5 необхідно визначити висловлення для предикатів, показати, що для кожного е істинно одне і тільки одне з них, і назвати в термінології графів підмножини безлічі Е, що відповідають цим висловленням:

$x, y(x¹yÙP(x, e, y)Ùù(P(y, e, x)));

$x(P(x, e, x));

$x, y(x¹yÙP(x, e, y)Ù(P(y, e, x))).

ГРАФИ