Математическая логика и теория алгоритмов. Стенюшкина В.А. - 15 стр.

UptoLike

ВУЗ: 

ОГУ | Оренбург

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

Рубрика: 

Пусть Р(х, х
1
,…,х
n
) – (n+1) – местный предикат, определенный на мно-
жестве M (n≥0). Тогда запись
∀х Р(х, х
1
,…,х
n
) означает n – местный предикат
на М, зависящий от х
1
,…,х
n
(и не зависящий от х) и принимающий значение
«истина» для тех и только тех значений а
1
,…,а
n
∈М переменных х
1
,…,х
n
, для
которых одноместный предикат Р(х, а
1
,…,а
n
) является тождественно истинным
на М; запись
∃х Р(х, х
1
,…,х
n
) означает n-местный предикат на М, зависящий от
х
1
,…,х
n
(и независящий от х) и принимающий значение «истина» для тех и то-
лько тех значений а
1
,…,а
n
∈М переменных х
1
,…,х
n
, для которых одноместный
предикат Р(х, а
1
,…,а
n
) является выполнимым на М. Предикат Р в записях ∀х Р
∃х Р называется областью действия квантора.
Пример – Пусть Р(х,у):= «х<у», х, у
∈R – двухместный предикат на мно-
жестве действительных чисел. Тогда предикаты
∀х (x<y), ∀у (x<y), ∃х (x<y),
∃у (x<y) - одноместные предикаты (первые два – тождественно ложные, вто-
рые два – тождественно истинные), а предикаты
∀х ∀у (x<y), ∀у ∀х (x<y),
∃x∀y(х<y), ∃y∀(x<y) нульместные (ложные). Ещё можно составить че-
тыре нульместных предиката (они окажутся истинными).
Путем суперпозиций логических операций можно составлять все более
сложные предикаты. Порядок выполнения операций устанавливается с помо-
щью скобок и в соответствии с приоритетом операций:
, ∀, ∃, ∧, ∨, →, ↔
(в порядке убывания).
Примеры
1 Пусть предикат Р(х) задан таблицей на множестве М={1, 2}:Р(1)=1,
Р(2)=0. Тогда высказывание
∃хР(х) имеет значение «истина».
2 Определить истинностные значения высказывания
∀х(Р(х) → Q(f(х), а)
если х
∈{1,2}=М, а=1, а предикаты и функтор заданы таблицами 2.1 и 2.2.
Таблица 2.1 Таблица 2.2
x
1
2
x
1
1
2
2
f
(х)
2
1
у
1
2
1
2
Р
(х)
0
1
Q
1
1
0
1
Решение В результате подстановки значения константы получаем выс-
казывание
∀
х(Р(х)
→
Q(f (х), 1). Строим вспомогательную таблицу 2.3.
Таблица 2.3
х 1 2
Q(f(х),1) 0 1 
       Пусть Р(х, х1,…,хn) – (n+1) – местный предикат, определенный на мно-
жестве M (n≥0). Тогда запись ∀х Р(х, х1,…,хn) означает n – местный предикат
на М, зависящий от х1,…,хn (и не зависящий от х) и принимающий значение
«истина» для тех и только тех значений а1,…,аn∈М переменных х1,…,хn, для
которых одноместный предикат Р(х, а1,…,аn) является тождественно истинным
на М; запись ∃х Р(х, х1,…,хn) означает n-местный предикат на М, зависящий от
х1,…,хn (и независящий от х) и принимающий значение «истина» для тех и то-
лько тех значений а1,…,аn∈М переменных х1,…,хn, для которых одноместный
предикат Р(х, а1,…,аn) является выполнимым на М. Предикат Р в записях ∀х Р
∃х Р называется областью действия квантора.
       Пример – Пусть Р(х,у):= «х<у», х, у∈R – двухместный предикат на мно-
жестве действительных чисел. Тогда предикаты ∀х (x

Страницы