Прикол для любителей логики

[psilogic]

Превращаем кванторы в *юнкции и обратно. ;)


Квантор всеобщности

∀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 конечная, то этот вывод - строгий. Если бесконечная, то это жульничество с моей стороны, так как я фактически распространил законы Де Моргана на формулы бесконечной длины, а формулы бесконечной длины - это фишка рискованная. Но все равно зобавно :)

Comments

[miss-lenchick.livejournal.com]

Ну, не то чтобы бесконечной...
Если уж обозначать х1, х2, х3, ... - то не более чем счетной. Там тоже не все так хорошо, но все же лучше, чем на континууме.
А вот насчет того, что можно действие кванторов сводить только к не более чем счетному множеству... Надо подумать.

[psilogic.livejournal.com]

Угу, для несчетного даже непонятно, как обозначить серию конъюнкций/дизъюнкций, но принцип тот же :)

[miss-lenchick.livejournal.com]

Вот я вроде помню, было вполне строгое доказательство для правила отрицания кванторов... Иэххх, где ж мой первый курс :)
Вечером в книжке посмотрю, а то не успокоюсь :)

ну загнул, я даже слов таких гне знаю (кванторы)

[sarich.livejournal.com]

вот фишька для обычных людей, вот это реально прикольно
Докажем, что выражение:
a=b+c абсолютно тождественно a=c
(причем все числа не равны нулю)
ДОКОЗАТЕЛЬСТВО:
a=b+c домножиме обе части уравнения
на множитель (a-c) получим:
a(a-c)=(b+c)(a-c) далее получим:
a2-ac=ab-bc+ac-с2 перенесем ab в левую
часть уравнения соответственно изменив
знак, получим:
a2 –ac – ab = ac – c2 – bc
упростим это выражение вынеся одинаковые
множители за скобки
a(a – c – b)=c(a – c – b) одинаковые множители
с обеих сторон можно сократить и получим
a=c что и требовалось доказать :-)

Старый прикол

[alex-semenov.livejournal.com]

Очень старый прикол.
(a – c – b)=0
a(a – c – b)=c(a – c – b)
a/0=c/0
на ноль делить нельзя...
:)

Re: ну загнул, я даже слов таких гне знаю (кванторы)

[psilogic.livejournal.com]

про страшные слова кажись в прошлом или позапрошлом посте :)

Re: ну загнул, я даже слов таких гне знаю (кванторы)

[kzerza.livejournal.com]

умножая на ноль можно что угодно приравнять.

Кванторы? Для украшения аллей?.. Для устрашения людей?..

[alex-semenov.livejournal.com]

Про формулу бесконечной длинны согласен.
Рискованно. У самого есть несколько рассуждений, где хочется но...
Хотя в этом случае все получается верно.
Вот еще одна популяризация понятия "квантор".
Давайте будем рассматривать некое бесконечное и счетное множество Х как бесконечный массив. Теперь рассмотрим некий предикат (логическую функцию) P(x). Пускай для некоторых x он может быть истинным: P(x[i])=true, а для некоторых ложным P(x[i]) = false. Хотя возможно, что ни для какого или для всех.
Утверждение:

Ax: P(х)

означает для всякого х, P(x) истинно. Это значит, что следующий цикл надежно зациклится:

. . .
i=1
While  not(P(x[i])) do
   Begin
      i=i+1
   End;
. . .

Нигде на бесконечности не встретится такой x что бы P(x) = ложь.
Утверждение:

Ex: P(х)

Существует такой х что P(x) истинно. Это значит что наш цикл:

. . .
i=1
While  not(P(x[i])) do
   Begin
      i=i+1
   End;
. . .

Обязательно когда-нибудь остановится.
То есть кванторы множено рассматривать как утверждения о программных циклах. И не каких-то там примитивно-рекурсивных For, а о настоящих итерациях. :)
Как-то читал статью самого папы Вирта, где он пытался научить программистов отлавливать ошибки в программах с помощью кванторов. Но почин не зачался и остался чисто академическим мудрствованием великого и ужасного. Хотя статья написана была толково без нашей расейской зауми. Кстати, реакция ваших, Мирослав, читателей на страшилку под названием "квантор" говорит о многом. Запугали наукообразы простой люд своим крючкотворчеством. Теперь попробуй ему, люду, объясни, что крючки эти придуманы не для устрашения людей, а облегчения их же уму понимания идей... Не верят же, гады!.. :)(

Re: Кванторы? Для украшения аллей?.. Для устрашения людей

[psilogic.livejournal.com]

Запугали наукообразы простой люд своим крючкотворчеством. Теперь попробуй ему, люду, объясни, что крючки эти придуманы не для устрашения людей, а облегчения их же уму понимания идей... Не верят же, гады!.. :)(

Ну не гады, но не верят, в натуре! :)))