Прикол для любителей логики
Превращаем кванторы в *юнкции и обратно. ;)
Квантор всеобщности
∀x P(x)
означает, что P(x) истинно для любых значений x. То есть, истинно для некоего x1, и для x2, и для x3, и т.д. То есть:
∀x P(x) = P(x1) & P(x2) & P(x3) & ...
Эта последовательность бесконечна, если область значений x бесконечна.
Квантор существования
∃x P(x)
означает, что P(x) истинно для каких-то значений x, хотя бы для одного. То есть, истинно для некоего x1, или для x2, или для x3, и т.д. То есть:
∃x P(x) = P(x1) \/ P(x2) \/ P(x3) \/ ...
А теперь поюзаем законы Де Моргана:
~∀x P(x) = ~(P(x1) & P(x2) & P(x3) & ...) = ~P(x1) \/ ~P(x2) \/ ~P(x3) \/ ... = ∃x ~P(x)
Выходит, что самое широко известное правило преобразования кванторов:
~∀x P(x) = ∃x ~P(x)
- выводится из законов Де Моргана. Если область определения для x конечная, то этот вывод - строгий. Если бесконечная, то это жульничество с моей стороны, так как я фактически распространил законы Де Моргана на формулы бесконечной длины, а формулы бесконечной длины - это фишка рискованная. Но все равно зобавно :)
Квантор всеобщности
∀x P(x)
означает, что P(x) истинно для любых значений x. То есть, истинно для некоего x1, и для x2, и для x3, и т.д. То есть:
∀x P(x) = P(x1) & P(x2) & P(x3) & ...
Эта последовательность бесконечна, если область значений x бесконечна.
Квантор существования
∃x P(x)
означает, что P(x) истинно для каких-то значений x, хотя бы для одного. То есть, истинно для некоего x1, или для x2, или для x3, и т.д. То есть:
∃x P(x) = P(x1) \/ P(x2) \/ P(x3) \/ ...
А теперь поюзаем законы Де Моргана:
~∀x P(x) = ~(P(x1) & P(x2) & P(x3) & ...) = ~P(x1) \/ ~P(x2) \/ ~P(x3) \/ ... = ∃x ~P(x)
Выходит, что самое широко известное правило преобразования кванторов:
~∀x P(x) = ∃x ~P(x)
- выводится из законов Де Моргана. Если область определения для x конечная, то этот вывод - строгий. Если бесконечная, то это жульничество с моей стороны, так как я фактически распространил законы Де Моргана на формулы бесконечной длины, а формулы бесконечной длины - это фишка рискованная. Но все равно зобавно :)
no subject
Если уж обозначать х1, х2, х3, ... - то не более чем счетной. Там тоже не все так хорошо, но все же лучше, чем на континууме.
А вот насчет того, что можно действие кванторов сводить только к не более чем счетному множеству... Надо подумать.
no subject
no subject
Вечером в книжке посмотрю, а то не успокоюсь :)