ВУЗ:
Составители:
Рубрика:
б) Пре ди кат P(x) = «x — про стое чис ло», оп ре де лен на мно же ст ве
на ту раль ных чи сел. Под став ляя вме сто x чис ла на ту раль но го ря да, по -
лу ча ем счет ное мно же ст во вы ска зы ва ний. Не ко то рое из них, на при мер,
P(1), P(2), P(3), P(5) и так да лее яв ля ют ся ис тин ны ми. Вы ска зы ва ние
"xP(x) = «все на ту раль ные чис ла про стые» — лож но, а $x P(x) = «не ко -
то рые из натуральных чисел — простые» — истинно.
6) По ря док сле до ва ния од но ме ст ных кван то ров не име ет зна че -
ния, но раз но имен ные кван то ры пе ре став лять нель зя.
При меры.
"x "y P(x,y) = "y "x P(x,y).
"x $y P(x,y) ¹ $y "x P(x,y).
$x $y P(x,y) = $y $x P(x,y).
7) Для фор мул ло ги ки пре ди ка тов со хра ня ют ся все рав но силь но -
сти ло ги ки вы ска зы ва ний. Кро ме то го су ще ст ву ют еще сле дую щие пра -
ви ла:
а) Пе ре нос кван то ра че рез от ри ца ние:
Ø("x) A(x) = ($x) ØA(x).
Ø($x) A(x) = ("x) ØA(x).
б) Вы нос кван то ра за скоб ки (В не со дер жит х):
($x) (A(x) & B) = ($x) A(x)& B.
("x) (A(x) & B) = ("x) A(x) & B.
($x) (A(x) Ú B) = ($x) A(x) Ú B.
("x) (A(x) Ú B) = ("x) A(x) Ú B.
За да ния для са мо стоя тель ной ра бо ты
1) Со ста вить таб ли цы ис тин но сти для фор мул:
а) (x
1
É Øx
2
) & (Øx
1
Ú x
2
);
б) (x
1
É (x
2
É x
3
)) É ((x
1
É x
2
) É (x
1
É
x
3
)).
2) За пи сать со став ные вы ска зы ва ния в ви де фор мул:
а) ес ли идет дождь, то ду ет ве тер;
б) не вер но, что ве тер ду ет то гда и толь ко то гда, ко гда нет дождя.
3) До ка зать рав но силь но сти:
а) Ø(A É B) = A & ØB;
51
б) Предикат P(x) = «x — простое число», определен на множестве
натуральных чисел. Подставляя вместо x числа натурального ряда, по-
лучаем счетное множество высказываний. Некоторое из них, например,
P(1), P(2), P(3), P(5) и так далее являются истинными. Высказывание
"xP(x) = «все натуральные числа простые» — ложно, а $x P(x) = «неко-
торые из натуральных чисел — простые» — истинно.
6) Порядок следования одноместных кванторов не имеет значе-
ния, но разноименные кванторы переставлять нельзя.
Примеры.
"x "y P(x,y) = "y "x P(x,y).
"x $y P(x,y) ¹ $y "x P(x,y).
$x $y P(x,y) = $y $x P(x,y).
7) Для формул логики предикатов сохраняются все равносильно-
сти логики высказываний. Кроме того существуют еще следующие пра-
вила:
а) Перенос квантора через отрицание:
Ø("x) A(x) = ($x) ØA(x).
Ø($x) A(x) = ("x) ØA(x).
б) Вынос квантора за скобки (В не содержит х):
($x) (A(x) & B) = ($x) A(x)& B.
("x) (A(x) & B) = ("x) A(x) & B.
($x) (A(x) Ú B) = ($x) A(x) Ú B.
("x) (A(x) Ú B) = ("x) A(x) Ú B.
Задания для самостоятельной работы
1) Составить таблицы истинности для формул:
а) (x1 É Øx2) & (Øx1 Ú x2);
б) (x1 É (x2 É x3)) É ((x1 É x2) É (x1 É x3)).
2) Записать составные высказывания в виде формул:
а) если идет дождь, то дует ветер;
б) неверно, что ветер дует тогда и только тогда, когда нет дождя.
3) Доказать равносильности:
а) Ø(A É B) = A & ØB;
51
