Информатика и математика, (для юристов), 2011. Информатика и математика проблемнотематический комплекс

• Название: Информатика и математика проблемнотематический комплекс
• Анкор: Информатика и математика, (для юристов), 2011.pdf
• Дата: 05.11.2017
• Размер: 3.34 Mb.
• Имя файла: Информатика и математика, (для юристов), 2011.pdf
• Тип: Учебное пособие; #10132
• страница: 21 из 23

Кванторы
Рассмотрим операции, преобразующие предикаты в высказывания.
Пусть имеется предикат Р(х), определенный на множестве М. Если
«а» – некоторый элемент из множества М, то подстановка его вместо х в предикат Р(х) превращает этот предикат в высказывание Р(а). Такое вы- сказывание называют единичным. Например, r(x): «х – четное число» – предикат, а r (6) – истинное высказывание, r (3) – ложное высказывание.
Это же относится и к n-местным предикатам: если вместо всех пред- метных переменных х
i
, i=
n
,
1
подставить их значения, то получим выска- зывание.
Наряду с образованием из предикатов высказываний в результате та- ких подстановок в логике предикатов рассматриваются еще две операции, которые превращают одноместный предикат в высказывание. Эти опера- ции называются операциями квантификации (или просто квантификацией, или связыванием кванторами, или навешиванием кванторов). При этом рассматриваются, соответственно, два типа так называемых кванторов.
Квантор всеобщности. Пусть Р(х) – предикат, определенный на мно- жестве М. Под выражением понимают высказывание истинное, ко- гда Р(х) истинно для каждого элемента х из множества М, и ложное в про- тивном случае. Это высказывание уже не зависит от х. Соответствующее ему словесное выражение звучит так: «Для всякого х Р(х) истинно».
)
(x
xP
∀
Символ называют квантором всеобщности (общности). Перемен- ную х в предикате Р(х) называют свободной (ей можно придавать различ- ные значения из М), в высказывании же
∀
)
(x
xP
∀
х называют связанной квантором всеобщности.
Квантор существования. Пусть P(x) – предикат, определенный на множестве М. Под выражением
)
(x
xP
∃
понимают высказывание, которое является истинным, если существует элемент
M
x
∈
, для которого P(x) ис- тинно, и ложным – в противном случае. Это высказывание уже не зависит от x. Соответствующее ему словесное выражение звучит так: «Существует
x, при котором P(x) истинно». Символ
∃
называют квантором существо-
вания. В высказывании переменная x связана этим квантором (на нее навешен квантор).
)
(x
xP
∃
Кванторные операции применяются и к многоместным предикатам.
Пусть, например, на множестве М задан двухместный предикат P(x,y).
Применение кванторной операции к предикату P(x,y) по переменной x ста- вит в соответствие двухместному предикату P(x,y) одноместный предикат
(или одноместный предикат
)
,
( y
x
xP
∀
)
,
( y
x
xP
∃
), зависящий от переменной
y и не зависящий от переменной x. К ним можно применить кванторные операции по переменной y, которые приведут уже к высказываниям сле- дующих видов:
).
,
(
),
,
(
),
,
(
),
,
(
y
x
xP
y
y
x
xP
y
y
x
xP
y
y
x
xP
y
∃
∃
∃
∀
∀
∃
∀
∀

2. План-конспект лекционного курса
207
Рассмотрим предикат P(x), определенный на множестве M={a
1
,…,a
n
}, содержащем конечное число элементов. Если предикат P(x) является тож- дественно-истинным, то истинными будут высказывания
P(a
1
),P(a
2
),…,P(a
n
). При этом истинными будут высказывания и конъюнкция
)
(x
xP
∀
)
(
)
(
)
(
2 1
n
a
P
a
P
a
P
∧
∧
∧
Если же хотя бы для одного элемента
M
a
k
∈
P(a
k
) окажется ложным, то ложными будут высказывание
)
(x
xP
∀
и конъюнкция
. Следова- тельно, справедлива равносильность
)
(
1
i
n
i
a
P
=
∧
)
(
)
(
)
(
)
(
)
(
1 2
1
i
n
i
n
a
P
a
P
a
P
a
P
x
xP
=
∧
=
∧
∧
∧
≡
∀
Численные кванторы. В математике часто встречаются выражения вида: «по меньшей мере n» («хотя бы n»), «не более чем n», «n и только n»
(«ровно n»), где n – натуральное число.
Эти выражения, называемые численными кванторами, имеют чисто логический смысл; они могут быть заменены равнозначными выражения- ми, не содержащими числительных и состоящими только из логических терминов и знака
≡
или

, означающего тождество (совпадение) объектов.
Пусть n=1. Предложение «По меньшей мере один объект обладает свойством P» имеет тот же смысл, что и предложение «Существует объект, обладающий свойством P», т.е.
)).
(
(
x
P
x
∃
(*)
Предложение «не более чем один объект обладает свойством P» рав- нозначно предложению «если есть объекты, обладающие свойством P, то они совпадают», т.е.
)
)
(
)
(
(
y
x
y
P
x
P
y
x
≡
⇒
∧
∀
∀
(**). Предложение «один и только один объект обладает свойством P» равнозначно конъюнкции вы- шеуказанных предложений (*) и (**).
Отрицание предложений с кванторами. Условимся отрицание пред- ложения записывать как
))
(
( x
P
x
∀
))
(
( x
P
x
∀
, а отрицание предложения
– как
))
(
( x
P
x
∃
))
(
( x
P
x
∃
. Очевидно, что предложение
))
(
( x
P
x
∀
имеет тот же смысл, а следовательно, то же значение истинности, что и предложение
)
)
(
( x
P
x
∃
, а предложение
))
(
( x
P
x
∃
– тот же смысл, что
)
)
(
( x
P
x
∀
. Иначе говоря,
))
(
( x
P
x
∀
равносильно
)
)
(
( x
P
x
∃
;
))
(
( x
P
x
∃
равносильно
))
(
( x
P
x
∀
Кванторы общности и существования называют двойственными отно- сительно один другого. Выясним теперь, как строить отрицание предложе- ния, начинающегося с нескольких кванторов, например, такого:
))
,
,
(
(
z
y
x
P
z
y
x
∀
∃
∀
Последовательно применяя сформулированное выше правило, полу- чим:
))
,
,
(
(
z
y
x
P
z
y
x
∀
∃
∀
равносильно
))
,
,
(
(
(
z
y
x
P
z
y
x
∀
∃
∃
, что равносильно
)))
,
,
(
(
(
z
y
x
P
z
y
x
∀
∀
∃
, что равносильно
))
,
,
(
(
z
y
x
P
z
y
x
∃
∀
∃

Информатика и математика
208 2. В логике предикатов будем пользоваться следующей символикой:
1.
Символы p, q, r, … – переменные высказывания, принимающие два значения: 1 – истина , 0 – ложь.
2.
Предметные переменные – x, y, z, … , которые пробегают значения из некоторого множества М;
x
0
, y
0
, z
0
– предметные константы, т.е. значения предметных пере- менных.
3.
P(·), Q(·), F(·), … – одноместные предикатные переменные;
Q(·,·,…,·), R(·,·, …,·) – n-местные предикатные переменные.
P
0
(·), Q
0
(·,·, …,·) – символы постоянных предикатов.
4.
Символы логических операций:
,
,
,
−
→
∨
∧
5.
Символы кванторных операций:
, x
x
∃
∀
6.
Вспомогательные символы: скобки, запятые.
Определение формулы логики предикатов.
1.
Каждое высказывание, как переменное, так и постоянное, является формулой (элементарной).
2.
Если F(·,·, …,·) – n-местная предикатная переменная или постоян- ный предикат, а x
1
, x
2
,…, x
n
– предметные переменные или предметные по- стоянные (не обязательно все различные), то F(x
1
, x
2
,…, x
n
) есть формула.
Такая формула называется элементарной, в ней предметные переменные являются свободными, не связанными кванторами.
3.
Если А и В – формулы, причем такие, что одна и та же предметная переменная не является в одной из них связанной, а в другой – свободной, то слова
B
A
есть формулы. В этих формулах те переменные, которые в исходных формулах были свободны, являются свободными, а те, которые были связанными, являются связанными.
B
A
B
A
→
∧
∨
,
,
4.
Если А – формула, то
A
– формула, и характер предметных пере- менных при переходе от формулы А к формуле
A
не меняется.
5.
Если А(х) – формула, в которую предметная переменная х входит свободно, то слова
)
(x
xA
∀
и
)
(x
xA
∃
являются формулами, причем предмет- ная переменная входит в них связанно.
6.
Всякое слово, отличное от тех, которые названы формулами в пунктах 1 – 5, не является формулой.
Например, если Р(х) и Q(x,y) – одноместный и двухместный предика- ты, а q, r – переменные высказывания, то формулами будут, например, слова (выражения):
r
q
y
x
Q
y
x
xQ
x
xP
y
x
Q
x
P
x
P
q
→
∨
∃
→
∀
∧
)
)
,
(
(
),
,
(
)
(
),
,
(
)
(
),
(
,
0
Не является формулой, например, слово:
)
(
)
,
(
x
P
y
x
xQ
→
∀
. Здесь нару- шено условие п. 3, так как в формулу
)
,
( y
x
xQ
∀
переменная х входит свя- занно, а в формулу Р(х) переменная х входит свободно.

2. План-конспект лекционного курса
209
Из определения формулы логики предикатов ясно, что всякая форму- ла алгебры высказываний является формулой логики предикатов.
Логическое значение формулы логики предикатов зависит от значе- ний трех видов переменных: 1) значений входящих в формулу переменных высказываний; 2) значений свободных предметных переменных из множе- ства М; 3) значений предикатных переменных.
При конкретных значениях каждого из трех видов переменных фор- мула логики предикатов становится высказыванием, имеющим истинное или ложное значение.
В качестве примера рассмотрим формулу
))
,
(
)
,
(
(
z
y
P
y
x
P
z
y
→
∀
∃
, в ко- торой двухместный предикат Р(x, y) определен на множестве M×M, где
M={0,1,2,…,n,…}, т.е. M×M=N×N.
В формулу входят переменный предикат P(x,y), предметные перемен- ные x,y,z, две из которых y и z – связанные кванторами, а x – свободная.
Возьмем за конкретное значение предиката P(x,y) фиксированный предикат P
0
(x,y): «x», а свободной переменной х придадим значение
. Тогда при значениях y, меньших x
0
=5, предикат P
0
(x
0
,y) прини- мает значение «ложь», а импликация при всех
M
x
∈
= 5 0
)
,
(
)
,
(
z
y
P
y
x
P
→
M
z
∈
при- нимает значение «истина», т.е. высказывание имеет значение «истина».
))
,
(
)
,
(
(
0 0
z
y
P
y
x
P
z
y
→
∀
∃
Две формулы логики предикатов А и В называются равносильными на
области М, если они принимают одинаковые логические значения при всех значениях входящих в них переменных, отнесенных к области М.
Две формулы логики предикатов А и В называются равносильными, если они равносильны на всякой области.
Ясно, что все равносильности алгебры высказываний будут верны, ес- ли в них вместо переменных высказываний подставить формулы логики предикатов. Но, кроме того, имеют место равносильности самой логики предикатов. Рассмотрим основные из этих равносильностей.
Пусть А(х) и В(х) – переменные предикаты, а С – переменное выска- зывание (или формула, не содержащая х). Тогда имеют место равносиль- ности:
1.
).
(
)
(
x
A
x
x
xA
∃
≡
∀
2.
).
(
)
(
x
A
x
x
xA
∀
≡
∃
3.
).
(
)
(
x
A
x
x
xA
∃
≡
∀
4.
).
(
)
(
x
A
x
x
xA
∀
≡
∃
5.
)]
(
)
(
[
)
(
)
(
x
B
x
A
x
x
xB
x
xA
∧
∀
≡
∀
∧
∀
6.
)]
(
[
)
(
x
B
C
x
x
xB
C
∧
∀
≡
∀
∧
7.
)]
(
[
)
(
x
B
C
x
x
xB
C
∨
∀
≡
∀
∨
8.
)]
(
[
)
(
x
B
C
x
x
xB
C
→
∀
≡
∀
→

Информатика и математика
210 9.
)
(
]
)
(
[
C
x
xB
C
x
B
x
→
∃
≡
→
∀
10.
).
(
)
(
)]
(
)
(
[
x
xB
x
xA
x
B
x
A
x
∃
∨
∃
≡
∨
∃
11.
).
(
)]
(
[
x
xB
C
x
B
C
x
∃
∨
≡
∨
∃
12.
).
(
)]
(
[
x
xB
C
x
B
C
x
∃
∧
≡
∧
∃
13.
)].
(
)
(
[
)
(
)
(
y
B
x
A
y
x
y
yB
x
xA
∧
∃
∃
≡
∃
∧
∃
14.
).
(
)]
(
[
x
xB
C
x
B
C
x
∃
→
≡
→
∃
15.
)
(
]
)
(
[
C
x
xB
C
x
B
x
→
∀
≡
→
∃
Равносильность 1 означает тот простой факт, что если не для всех х истинно А(х), то существует х, при котором будет истиной
)
(x
A
Равносильность 2 означает тот факт, что если не существует х, при ко- тором истинно А(х), то для всех х будет истиной
)
(x
A
Равносильности 3 и 4 получаются из равносильностей 1 и 2, соответ- ственно, если от обеих их частей взять отрицания и воспользоваться зако- ном двойного отрицания.
Подробнее см.: 1, 4.
З
АКЛЮЧЕНИЕ
Информатика является молодой быстроразвивающейся отраслью нау- ки и индустрии. Продукты и услуги информатики широко используются в юриспруденции.
Все это показывает, насколько важно современному юристу знать ос- новы информатики и уметь использовать ее достижения в своей профес- сиональной деятельности.
Л
ИТЕРАТУРА
Основная
1.
Дубинина Н.М., Казанцева С.Я. Информатика и математика для юристов:
Учебник для вузов. – М.: ЮНИТИ-ДАНА, 2011.
2.
Егоров А.В, Котов Э.М. Информационные системы в юриспруденции: Учеб- ник для вузов. – М.: Феникс, 2008.
3.
Информатика: практикум по работе на компьютере / Под ред. Н.В. Макарова. –
М.: Финансы и статистика, 2008.
4.
Колмогоров А.Н., Драгалин А.Г. Введение в математическую логику. – М.:
Изд-во МГУ, 2007.
5.
Мельников В.П. Информационная безопасность и защита информации. – М.:
ACADEMIA, 2007.
6.
Попов А.М., Сотников В.Н., Нагаева Е.И. Информатика и математика для юристов. – М.: ЮНИТИ-ДАНА, 2009.

3.
К
ОНСУЛЬТАЦИОННЫЙ КУРС
Авторы-составители: канд. физ.-мат. наук, проф. О.Ю. Худякова, канд. техн. наук, доц. В.А. Бужинский
В
ВЕДЕНИЕ
Для консультационного курса по дисциплине «Информатика и мате- матика» отобран комплекс вопросов, вызывающих у студентов особый практический интерес при изучении курса, а также наиболее сложные для самостоятельного изучения.