Математика. Раздел 1. Дискретная математика. Тетрадь 1.2. Казанцев Э.Ф. - 50 стр.

UptoLike

ВУЗ: 

МУМ | Москва

Составители: 

Рубрика: 

б) Пусть A — фор му ла. То гда (ØA) то же фор му ла. Сво бод ные и
свя зан ные пе ре мен ные фор му лы (ØA) — это со от вет ст вен но сво бод ные
и свя зан ные пе ре мен ные фор му лы A.
в) Пусть A и B — фор му лы, при чем нет та ких пред мет ных пе ре -
мен ных, ко то рые бы ли бы свя за ны в од ной фор му ле и сво бод ны в
другой. Тогда
(A Ú B), (A & B), (A É B), (A ~ B) (1.5.1)
— есть фор му лы, в ко то рых сво бод ные пе ре мен ные фор мул A и B
ос та ют ся сво бод ны ми, A свя зан ные пе ре мен ные A и B ос та ют ся
связанными.
г) Пусть A — фор му ла, со дер жа щая сво бод ную пе ре мен ную x.
Тогда
("x) A, ($x) A (1.5.2)
— то же фор му лы. Пе ре мен ная x в них свя за на. Ос таль ные же пе -
ре мен ные, ко то рые в фор му ле A сво бод ны, ос та ют ся сво бод ны ми и в
формулах (1.5.2).
Пе ре мен ные, ко то рые в фор му ле A свя за ны, ос та ют ся свя зан ны -
ми и в фор му лах (1.5.2). В фор му ле ("x) A, фор му ла A на зы ва ет ся об ла -
стью дей ст вия кван то ра "x, а в фор му ле ($x) A — об ла стью дей ст вия
кван то ра $x.
д) Сло во в ал фа ви те ло ги ки пре ди ка тов яв ля ет ся фор му лой толь -
ко в том слу чае, это сле ду ет из правил а)–г).
5) Кван то ры "x и $x свя зы ва ют пе ре мен ную x, пре вра щая од но -
ме ст ный пре ди кат в вы ска зы ва ние. Оче вид но, что "xP(x) ис тин но толь -
ко при ус ло вии, что P(x) то ж де ст вен но ис тин ный пре ди кат, а во всех ос -
таль ных слу ча ях это вы ска зы ва ние лож но. Вы ска зы ва ние $x P(x) все гда
ис тин но, кро ме един ст вен но го слу чая, ко гда P(x) — то ж де ст вен но лож -
ный пре ди кат.
При ме ры.
а) Трех ме ст ный пре ди кат P(x
1
, x
2
, x
3
) = «x
1
есть сум ма x
2
и x
3
» при
под ста нов ке x
1
= 5 пе ре хо дит в двух ме ст ный пре ди кат P(5, x
2
, x
3
) =
= «5 есть сум ма x
2
и x
3
», а при даль ней шей под ста нов ке x
2
= 2 — в од но -
ме ст ный пре ди кат P(5, 2, x
3
) = «5 есть сум ма 2 и x
3
». Оче вид но, при
x
3
= 3 он ста но вит ся ис тин ным вы ска зы ва ни ем, а при всех x
3
¹ 3 — лож -
ным.
50
      б) Пусть A — формула. Тогда (ØA) тоже формула. Свободные и
связанные переменные формулы (ØA) — это соответственно свободные
и связанные переменные формулы A.
      в) Пусть A и B — формулы, причем нет таких предметных пере-
менных, которые были бы связаны в одной формуле и свободны в
другой. Тогда
      (A Ú B), (A & B), (A É B), (A ~ B)                           (1.5.1)
      — есть формулы, в которых свободные переменные формул A и B
остаются свободными, A связанные переменные A и B остаются
связанными.
      г) Пусть A — формула, содержащая свободную переменную x.
Тогда
      ("x) A, ($x) A                                               (1.5.2)
      — тоже формулы. Переменная x в них связана. Остальные же пе-
ременные, которые в формуле A свободны, остаются свободными и в
формулах (1.5.2).
      Переменные, которые в формуле A связаны, остаются связанны-
ми и в формулах (1.5.2). В формуле ("x) A, формула A называется обла-
стью действия квантора "x, а в формуле ($x) A — областью действия
квантора $x.
      д) Слово в алфавите логики предикатов является формулой толь-
ко в том случае, это следует из правил а)–г).

      5) Кванторы "x и $x связывают переменную x, превращая одно-
местный предикат в высказывание. Очевидно, что "xP(x) истинно толь-
ко при условии, что P(x) тождественно истинный предикат, а во всех ос-
тальных случаях это высказывание ложно. Высказывание $x P(x) всегда
истинно, кроме единственного случая, когда P(x) — тождественно лож-
ный предикат.

       Примеры.
       а) Трехместный предикат P(x1, x2, x3) = «x1 есть сумма x2 и x3» при
подстановке x1 = 5 переходит в двухместный предикат P(5, x2, x3) =
= «5 есть сумма x2 и x3», а при дальнейшей подстановке x2 = 2 — в одно-
местный предикат P(5, 2, x3) = «5 есть сумма 2 и x3». Очевидно, при
x3 = 3 он становится истинным высказыванием, а при всех x3 ¹ 3 — лож-
ным.
50

Страницы