?

Log in

No account? Create an account
nyaload

Журнал Пушыстого

Журнал Пушыстого

Previous Entry Share Next Entry
и/или
nyaload
_winnie
Осознал, что союз 'и' может означать как 'и', так и 'или':

А) Холодное и огнестрельное оружие, охотник на птиц и зверей
Б) Длинная и сухая палка, любитель молодых и красивых

В каких-то контекстах - понять значение невозможно: "Запрещено красное и большое".

В каком-то французском фильме обыгрывалась эта неоднозначность:
Полицейский (негр) и его помощник (араб) входят в клуб, и натыкаются на охранника-вышибалу.
Вышибала: Неграм и арабам вход воспрещен!
Полицейский-негр: А я не араб!
Полицейский-араб: А я не негр!
Затем парой ударов отправляют его в нокаут и проходят мимо него.


  • 1
Там сопряженность имеет место

XY+Z == XY * X Z

Таким образом сумма (дизъюнкция) может превращаться в произведение (конъюнкцию).

Частный случай - законы де Моргана.

Функциональные программисты это иной раз путают, и сообщают что-нибудь вроде, что экзистенциальный квантор в хаскеле записывается через универсальный.


Edited at 2015-07-01 02:05 pm (UTC)

Не очень понял. Неоднозначность 'и' в этих примерах - из-за того что 'и' используется и для объединения множеств, и для логического 'and':
{x : A(x) & B(x)}
{x : A(x)} ⋃ {x: B(x)}
Хотя эти две операции - совершенно разные, и смысл меняется в них наоборот с 'или'.

Кстати, этими неоднозначность не исчерпывается: "в сумке были красные и зелёные яблоки" (подразумеваетсся, что и тех, и других - не нулевое количество).

Edited at 2015-07-01 02:36 pm (UTC)

ну как же, стрелку из ко-продукта можно описать парой стрелок.

f : Either a b -> c -- здесь у нас "или"

можно эквивалентно задать с помощью

f' : (a->c, b->c) -- здесь у нас "и", из-за изоморфизма с f это "и" в смысле "или"

От меня скрылся какой-то кусок математики, так как слово "изоморфизм", нотация хаскеля и суть "¬A & ¬B = ¬(A ∨ B)" понятны.
Но "стрелка из ко-продукта" для меня не отличается от "белка в кар-производство".

Я прочитал определение категорий, стрелок (стрелка и морфизм одно и то же?), копродукта. Ну как прочитал, примерно так же как компилятор читает мою программу, связи между словами нашёл, а понимания нет. Видимо нужно ещё знать какой-то "общепризнаный" способ как операции над объектами - переводить в какие-то категории. У меня 0 понимания, с какими стрелками связаны эти Either a b -> c и логическая операци 'и'.

Так же не ясно, каким образом связали табличку истинности {0∨0=0, 0∨1=1, 1∨0=1, 1∨1=1} с типом функции хаскеля. 'Или' - это вот такая табличка истинности. А почему это ещё и функция из Either a b - неясно. Ну кроме как совпадения по словам "Either a b - это a или b, (a, b) - это и a, и b".


Так же я наверное не понял определение копродукта, так как кусочек определения "such that f1 = f ∘ i1 and f2 = f ∘ i2" кажется тавтологией из-за требования ассоциативности стрелок в определении категории. (определения целиком отсюда: "Let C be a category and let X1 and X2 be objects in that category. An object is called the coproduct of these two objects, written X1 ∐ X2 or X1 ⊕ X2 or sometimes simply X1 + X2, if there exist morphisms i1 : X1 → X1 ∐ X2 and i2 : X2 → X1 ∐ X2 satisfying a universal property: for any object Y and morphisms f1 : X1 → Y and f2 : X2 → Y, there exists a unique morphism f : X1 ∐ X2 → Y such that f1 = f ∘ i1 and f2 = f ∘ i2"

Я это понял так: Z это копродукт X1 и X2, если есть стрелки из X1 и из X2 в Z, и из Z есть единственная стрелка куда угодно. Получается, что копродукт - это свойство тройки X1, X2, Z а не операция над X1 и X2 для получения Z.



Edited at 2015-07-02 12:12 am (UTC)

я тоже этот кусок математики "пропустил" - у нас такого в универе не было, а своего ума не хватало подучить. Потом несколько лет назад купил подержанную книжечку Пирса, страниц сто, и горя не знаю.

В том-то и дело, что "что такое ко-продукт" пощупать можно в каких-то конкретных реализациях, а они зависят от того, что такое стрелки в конкретной категории. Хаскелл и Агду удобно брать в виде категории, т.к. "другие" языки гораздо менее консистентны. Именно поэтому копродуктом называют Either, но можно и любой другой data с парой типов и конструкторов. Тогда "объекты" X1 и X2 - это конкретные типы, Z - это Either, параметризованный этими типами (Either X1 X2), стрелки "инъекции" i1 и i2 - это конструкторы Left и Right, а стрелки из Z не куда угодно, а туда, куда есть стрелки из X1 и X2. В Хаскелле это выражение эквивалентно демонстрации, как можно построить стрелку из Either X1 X2 в любой тип, куда есть стрелки из X1 и X2 одновременно:

Для любых функций f1 и f2 мы всегда можем построить
f :: (a -> c, b -> c) -> Either a b -> c
f (f1, f2) (Left x) = f1 x
f (f1, f2) (Right y) = f2 y

Эта конструкция и удовлетворяет условию, что f1 = f . Left, и f2 = f . Right

Возвращаясь к логическим выражениям. Карри-Говард изоморфизм поминался многократно. Так вот, он и говорит, что всякой программе соответствует некоторая логическая формула, и наоборот. Логические функции можно, конечно, описать табличками истинности, но это не единственный способ. По изоморфизму Карри-Говарда получается, что функции Хаскелля можно представить как импликацию, утверждения - типы, а истинность утверждений - это возможность их доказать, т.е. построить элемент типа, соответствующего утверждению.

Например, тогда что такое A∧B? А это такое утверждение, что если его можно доказать, то можно доказать и A, и B поотдельности. Формально так: из (A∧B) следует A, и из (A∧B) следует B. По Карри-Говарду это значит, что для типа, представляющего конъюнкцию двух типов есть стрелки в каждый из этих типов. Смотрим на определение продукта: некий объект - это продукт двух объектов, если есть из него проекции в эти объекты (такие, что...). Под это определение подходит, например, тупль: есть стрелка-проекция (a,b)->a, которую называют fst, и есть стрелка-проекция (a,b)->b, которую называют snd (и они как раз такие, что...). Так можно положить, что A∧B в программировании представляется туплем.

Что такое A∨B? Можно снова повертеть типами, но можно и взять правило де-Моргана (хотя на самом деле правило следует из верчения типами): из A∨B следует ¬((¬A)∧(¬B)). ∧ уже определили, что это тупль. ¬ можно представить через импликацию (т.к. ¬A = A→false). Тогда вот это самое ¬((¬A)∧(¬B)) можно записать как ((A→⊥)∧(B→⊥)→⊥ или A∨B→C как (a→c,b→c)

А именно, (смотрим определение) что стрелке из копродукта Z куда-нибудь соответствует пара стрелок из компонент копродукта туда же:

f :: (Either a b -> c) -> (a->c, b->c)
f h = (h . Left, h . Right)

ну, а то, что ivan_gandhi записал через экспоненты - это то же самое, просто типы функций A→B записаны как BA - тогда появляется некая аналогия со сложением и умножением: в алгебре a^(x+y)=a^x * a^y, и в логике-программировании, получается, тоже, если экспонента - это функция, сумма - это копродукт, а произведение - тупль.

вот, а можно вернуться к верчению типами.

Что такое A∨B? Это такое высказывание, истинность которого следует из истинности A или истинности B: т.е. речь о том, что A∨B - это такой объект, в который есть стрелка из A и из B (плюс требование универсальности - что там со следствиями из A и B коммутировать должно). Разве не очевидна связь с инъекциями i1 и i2 из определения копродукта?

A→A∨B, B→A∨B

Конструкторы Left и Right удовлетворяют типам этих стрелок.

Чтобы это был именно копродукт, нужно, чтобы для любых высказываний, истинность которых следует из A и из B, была и импликация из A∨B (такая, что... - условие, определяющее, что объект A∨B - универсальный, предельный).

Но в самой формулировке присутствует это самое "из (A→C)∧(B→C) следует (A∨B)→C" - это же определение ∨. А по Карри-Говарду получаем (a->c,b->c)->(Either a b->c). Нетрудно убедиться в универсальности - т.е. f1 = f . i1, f2 = f . i2 - для той самой f = uncurry either

о, ещё один важный момент - о понятии "универсальности".

Итак, таблица истинности - это такой прикладной подход. На самом деле в определении операций ∨ и ∧ никаких таблиц истинности нет.

A∨B - это такое утверждение Z, которое следует из A и из B.

Но тогда и утверждение A∨B∨C тоже удовлетворяет такому условию, т.е. оно следует и из A, и из B. Так вот, чтобы среди всех них различать некоторый специальный случай, который ровно A∨B и ничего более, вводится понятие универсальности. Его можно назвать пределом или ко-пределом (в зависимости от контекста) - (ко-)пределом в том смысле, что это в некотором смысле экстремальный случай, некий (минимум/) максимум.

Тогда A∨B - это не просто утверждение Z, которое следует из A и из B, а ещё и является ко-пределом среди всех таких утверждений, т.е. все остальные утверждения также следуют из Z. (Например, A∨B∨C следует из A∨B) Из последнего, среди прочего, следует ассоциативность и коммутативность операции ∨.


Похожим образом определяется ∧:

A∧B - это такое утверждение Z, из которого следует A и из которого следует B.

Утверждение A∧B∧C тоже удовлетворяет этому определению, поэтому мы говорим именно о пределе - о таком Z, который следует из всех других (смотрите, здесь стрелки наоборот: ко-предел - все другие следуют из; предел - следует из всех других). Например, из A∧B∧C следует A∧B. Таким образом мы находим такое Z, которое является A∧B и ничем более. Отсюда следует, кстати, ассоциативность и коммутативность ∧.


Поскольку в определении нигде не фигурируют ни таблицы истинности, ни конкретные представления истины, лжи, реализации импликации, логика получается обобщённой - и это хорошо. Сюда подходят тогда помимо Булевой алгебры, алгебры Heyting (утверждения - действительные числа в диапазоне [0,1]; импликация - отношение ≤), посеты, системы типов.

"Осознал, что союз 'и' может означать как 'и', так и 'или':

А) Холодное и огнестрельное оружие, охотник на птиц и зверей
Б) Длинная и сухая палка, любитель молодых и красивых"


а нету ли примера типа А, где "или" не исключающее? (птицо-зверей не бывает - значит, имеется в виду "или"; но поскольку птицо-зверей не бывает, то это "или" - исключающее)

Запросто. Бесплатный вход для женщин и студентов.

гм, да. Есть ещё "с".

Места для инвалидов и пассажиров с детьми

Вот тут-то и надо бы выдать аттестат о среднем (полном) общем образовании. :)

В пивной в Петергофе висело объявление:

"Пиво относится к алкогольным напиткам. Продажа пива лицам моложе 21 года, в рабочей одежде и в нетрезвом состоянии запрещена."

Я внимательно оглядел помещение. В нем были лица моложе 21 года в рабочей одежде, но относительно трезвые. Были лица в рабочей одежде и в распиздос пьяные, но старше 21 года. Были лица моложе 21 года и пьяные, но не в рабочей одежде. Узнать, действительно ли не дадут пива тому, кто выполнит все три условия в тот день так и не удалось.

  • 1