- •Предикаты
- •Действия над предикатами
- •Теорема о представлении квантора общности через конъюнкцию
- •Теорема о представление квантора существования через дизъюнкцию
- •Теорема о тождественной истинности предикатов
- •Теорема о тождественной ложности предикатов
- •Теорема о перестановке одноимённых кванторов
- •Теорема о перестановке кванторов общности
- •Теорема о перестановке кванторов существования
- •Теорема о перестановке разноимённых кванторов
- •Теорема об отрицании кванторов
- •Теорема об отрицании квантора общности
- •Теорема об отрицании квантора существования
- •Дистрибутивные свойства кванторов
- •Теорема о дистрибутивности квантора общности относительно конъюнкции
- •Теорема о дистрибутивности квантора существования относительно дизъюнкции
- •Теорема о полудистрибутивности квантора общности относительно дизъюнкции
- •Теорема о полудистрибутивности квантора существования относительно конъюнкции
- •Теорема о представлении предикатной формулы в приведённой форме
- •Теорема о переименовании связанных переменных
- •Теорема о распространении области действия квантора
- •Теорема о представлении предикатной формулы в предваренной нормальной форме
- •Комбинаторика
- •Основные правила комбинаторики
- •I. Выбор с возвращением
- •II. Выбор без возвращения
- •Размещения с повторениями
- •Размещения без повторений
- •Перестановки без повторений
- •Перестановки с повторениями
- •Сочетания с повторениями
- •Сочетания с повторениями
- •Формула бинома Ньютона
- •Свойства
- •Полиномиальная формула
- •Формула включений и исключений
- •Задачи о смещениях
- •Задачи о распределениях
- •Арифметический треугольник
- •Теорема о связи арифметического треугольника и m-ичной системы счисления
- •Свойства обобщённых арифметических коэффициентов
- •Рекуррентные соотношения
- •Задача Фибоначчи
- •Лемма о линейной комбинации решений
- •Теорема о виде общего решения соотношения (38)
- •Теорема о виде общего решения соотношения (40)
- •Элементы формальных теорий
Предикаты
Высказывание – предложение, про которое можно сказать, истинно оно или
ложно.
0 – ложь, 1 – истина.
Предикат – это функция от n переменных, имеющая своей областью прибытия множество {0, 1}.
Другими словами, предикат – это формула, содержащая n переменных, которая при их фиксировании принимает значение «ложь» или «истина».
Предикат P(x1 ,..., xn ) называется тождественно ложным, если на любом наборе значений своих аргументов он принимает значение «ложь».
Пример: x, y Z, P(x, y) : x2 2y 2 .
Предикат Q(x1 ,..., xn ) называется тождественно истинным, если на любом наборе своих аргументов он принимает значение «истина».
Пример: x, y N, Q(x, y) : (2x 6y) 2.
Предикат R(x1 ,..., xn ) называется выполнимым, если хотя бы на одном наборе
своих аргументов он принимает значение «истина».
Пример: человек x имеет возраст y лет. R(x,18) 0 или = 1; R(x,3000) 0.
Действия над предикатами
Пусть P(x1 ,..., xn ) - предикат. Тогда P(x1 ,..., xn ) или |
|
|
|
|
- |
|
отрицание |
|||||||
P(x ,..., x |
n |
) |
|
|
||||||||||
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
предиката P(x1,..., xn ) . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Отрицанием предиката |
P(x1 |
,..., xn ) будем называть предикат |
|
|
|
|
, который |
|||||||
P(x ,..., x |
n |
) |
||||||||||||
|
|
|
|
|
1 |
|
|
|
|
|
|
|
||
принимает значение |
«истина» |
на |
тех и только тех наборах |
аргументов, |
|
на |
которых |
|||||||
P(x1,..., xn ) принимает значение «ложь». |
|
|
|
|
|
|
|
|
|
|
|
|||
Пусть даны два предиката P(x1,..., xn ) и Q(x1 ,..., xm ) . |
|
|
|
|
|
|
|
|
|
|
|
|||
Импликацией |
предикатов |
P(x1,..., xn ) и Q(x1 ,..., xm ) называется |
|
|
предикат |
P(x1,..., xn ) →Q(x1 ,..., xm ) , который принимает значение «ложь» на тех и только тех наборах аргументов, на которых P(x1,..., xn ) - «истина», а Q(x1 ,..., xm ) - «ложь».
Аналогично вводятся операции конъюнкции, дизъюнкции и т.п.- квантор общности («для любого»).
- квантор существования («существует»).y P(y, x1 ,..., xn ) T (x1 ,..., xn ), где
T (a1 ,..., an ) 1 P(y, a1 ,..., an ) 1,
T (b1 ,...,bn ) 0 P(y,b1 ,...,bn ) не всегда равен 1.y P( y, x1 ,..., xn ) R(x1 ,..., xn ), где
R(a1 ,..., an ) 1 P( y, a1 ,..., an ) |
- выполним, |
R(b1 ,...,bn ) 0 P( y,b1 ,...,bn ) |
0. |
Пример: x, y R, y (xy 1), |
P(x) - зависит только от x, т.к. навешен квантор. |
Покажем, что P(x) - выполним.
P(2) 1 2y 1 - выполним (при y 12 ),
P(0) 0 (0 y 1) 0,
Следовательно, P(x) - выполнимый, но не тождественно истинный.
1
Операции навешивания квантора общности и квантора существования называются операциями квантификации.
Порядок выполнения действий: , , , , , , .
Теорема о представлении квантора общности через конъюнкцию
P(x, y1 ,..., yn ), x {a1 , a2 ,..., ak }.
x P(x, y1 ,..., yn ) P(a1 , y1 ,..., yn ) P(a2 , y1 ,..., yn ) ... P(ak , y1 ,..., yn ) (1) Доказательство.
Зафиксируем b1 ,...,bn .
x P(x,b1 ,...,bn ) 1 P(x,b1 ,...,bn ) 1
P(a1 ,b1 ,...,bn ) 1, P(a2 ,b1 ,...,bn ) 1,..., P(ak ,b1 ,...,bn ) 1
P(a1 ,b1 ,...,bn ) P(a2 ,b1 ,...,bn ) ... P(ak ,b1 ,...,bn ) 1
Илевая, и правая части уравнения (1) принимают значение «истина» на одних и тех же наборах аргументов.
Теорема о представление квантора существования через дизъюнкцию
P(x, y1 ,..., yn ), x {a1 , a2 ,..., ak }.
x P(x, y1 ,..., yn ) P(a1 , y1 ,..., yn ) P(a2 , y1 ,..., yn ) ... P(ak , y1 ,..., yn ) (2) Доказательство.
Зафиксируем b1 ,...,bn .
x P(x,b1 ,...,bn ) 0 P(x,b1 ,...,bn ) 0
P(a1 ,b1 ,...,bn ) 0, P(a2 ,b1 ,...,bn ) 0,..., P(ak ,b1 ,...,bn ) 0
P(a1 ,b1 ,...,bn ) P(a2 ,b1 ,...,bn ) ... P(ak ,b1 ,...,bn ) 0
Илевая, и правая части уравнения (2) принимают значение «ложь» на одних и тех же наборах аргументов.
Теорема о тождественной истинности предикатов
P(x, y1 ,..., yn ) 1 x P(x, y1 ,..., yn ) 1 |
(3) |
Доказательство. |
|
P(x, y1 ,..., yn ) 1 для любых b1 ,...,bn |
P(x,b1 ,...,bn ) 1 |
для любых b1 ,...,bn x P(x,b1 ,...,bn ) |
1 x P(x, y1 ,..., yn ) 1 |
Теорема о тождественной ложности предикатов
P(x, y1 ,..., yn ) 0 x P(x, y1 ,..., yn ) 0 (4) Доказательство.
P(x, y1 ,..., yn ) 0 для любых b1 ,...,bn P(x,b1 ,...,bn ) 0
для любых b1 ,...,bn x P(x,b1 ,...,bn ) 0 x P(x, y1 ,..., yn ) 0
2