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

UptoLike

ВУЗ: 

МУМ | Москва

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

Рубрика: 

2) Кро ме опе ра ций ло ги ки вы ска зы ва ний вве дем еще опе ра цию
свя зы ва ния кван то ром.
а) Кван тор общ но сти. Пусть P(x) — не ко то рый пре ди кат, при ни -
маю щий зна че ния И или Л для ка ж до го эле мен та x мно же ст ва M. То гда
под вы ра же ни ем ("x)P(x) бу дем под ра зу ме вать вы ска зы ва ние ис тин -
ное, ко гда P(x) ис тин но для ка ж до го эле мен та из мно же ст ва M, и лож -
но — в про тив ном слу чае. Чи та ет ся это вы ра же ние так: «для всех x из
P(x)». Это вы ска зы ва ние уже не за ви сит от x. Сим вол "x на зы ва ет ся
кван то ром общ но сти: все х Î М об ла да ют свой ст ва ми P(x).
б) Кван тор су ще ст во ва ния. Пусть P(x) — не ко то рый пре ди кат.
Под вы ра же ни ем ($x)P(x) бу дем по ни мать вы ска зы ва ние ис тин ное, ко -
гда су ще ст ву ет хо тя бы один эле мент мно же ст ва M, для ко то ро го P(x)
ис тин но, и лож ное — в про тив ном слу чае. Чи та ет ся так: «су ще ст ву ет x
та кое, что P(x)», или «су ще ст ву ет x, для ко то ро го P(x)». Сим вол $x на зы -
ва ет ся кван то ром су ще ст во ва ния.
При мер (ус ло вие пре ды ду ще го при ме ра):
а) ($x)(P
(1)
(x) & Q
(1)
(x)) — ис тин ное вы ска зы ва ние;
б) ("x)(P
(1)
(x) & Q
(1)
(x)) — лож ное вы ска зы ва ние.
На язы ке пре ди ка тов мож но со ста вить го раз до бо лее слож ные
пред ло же ния, чем на язы ке ло ги ки вы ска зы ва ний. Пе ре мен ные, к ко то -
рым при ме ня ют ся кван то ры на зы ва ют ся свя зан ны ми, а ос таль ные —
сво бод ны ми.
3) Ал фа вит ло ги ки пре ди ка тов со дер жит сле дую щие сим во лы:
•
сим во лы пред мет ных пе ре мен ных: x
1
, x
2
,..., x
n
, ... ;
•
сим во лы пре ди ка тов:
A
t
1
( )
,
A
t
2
( )
, ... ,
A
k
t( )
; t = 0, 1, 2, ... ;
•
ло ги че ские сим во лы: &, É , Ú, ~;
•
сим во лы кван то ров: " , $;
•
скоб ки и за пя тую: ),(.
4) Сло во в ал фа ви те ло ги ки пре ди ка тов на зы ва ет ся фор му лой, ес -
ли оно удов ле тво ря ет сле дую ще му оп ре де ле нию:
а) Ес ли
A
j
t( )
— сим вол пре ди ка та, а (x
1
, x
2
, ..., x
n
) — сим во лы пред -
мет ных пе ре мен ных (не обя за тель но раз лич ные), то
A
j
t( )
(x
1
, x
2
, ... , x
n
) —
фор му ла. Та кая фор му ла на зы ва ет ся ато мар ной. Все пред мет ные пе ре -
мен ные ато мар ных фор мул сво бод ные, свя зан ных пе ре мен ных нет.
49
      2) Кроме операций логики высказываний введем еще операцию
связывания квантором.
      а) Квантор общности. Пусть P(x) — некоторый предикат, прини-
мающий значения И или Л для каждого элемента x множества M. Тогда
под выражением ("x)P(x) будем подразумевать высказывание истин-
ное, когда P(x) истинно для каждого элемента из множества M, и лож-
но — в противном случае. Читается это выражение так: «для всех x из
P(x)». Это высказывание уже не зависит от x. Символ "x называется
квантором общности: все х Î М обладают свойствами P(x).
      б) Квантор существования. Пусть P(x) — некоторый предикат.
Под выражением ($x)P(x) будем понимать высказывание истинное, ко-
гда существует хотя бы один элемент множества M, для которого P(x)
истинно, и ложное — в противном случае. Читается так: «существует x
такое, что P(x)», или «существует x, для которого P(x)». Символ $x назы-
вается квантором существования.
      Пример (условие предыдущего примера):
      а) ($x)(P (1)(x) & Q(1)(x)) — истинное высказывание;
      б) ("x)(P (1)(x) & Q(1)(x)) — ложное высказывание.
      На языке предикатов можно составить гораздо более сложные
предложения, чем на языке логики высказываний. Переменные, к кото-
рым применяются кванторы называются связанными, а остальные —
свободными.

      3) Алфавит логики предикатов содержит следующие символы:
      • символы предметных переменных: x1, x2,..., xn, ... ;
                               (t) (t)       (t)
      • символы предикатов: A1 , A2 , ... , Ak ; t = 0, 1, 2, ... ;
      • логические символы: &, É, Ú, ~;
      • символы кванторов: ", $;
      • скобки и запятую: ),(.

     4) Слово в алфавите логики предикатов называется формулой, ес-
ли оно удовлетворяет следующему определению:
     а) Если A (j t ) — символ предиката, а (x1, x2, ..., xn) — символы пред-
метных переменных (не обязательно различные), то A (j t ) (x1, x2, ... , xn) —
формула. Такая формула называется атомарной. Все предметные пере-
менные атомарных формул свободные, связанных переменных нет.
                                                                           49

Страницы