Ostatnio natknąłem się na problem, który wymagał ode mnie programowego zdefiniowania logicznego operatora „OR”, ale bez użycia samego operatora.

Wymyśliłem to:

OR(arg1, arg2)
  if arg1 = True and arg2 = True
     return True

  else if arg1 = True and arg2 = False
     return True

  else if arg1 = False and arg2 = True
     return True

  else:
     return False

Czy ta logika jest poprawna, czy coś przeoczyłem?

Powiedziałbym, że to prawda, ale czy nie możesz tego skondensować do czegoś takiego?

or(arg1, arg2)
    if arg1 == true
        return true
    if arg2 == true
        return true

    return false

Ponieważ robisz porównanie lub nie sądzę, że naprawdę musisz sprawdzać kombinację. Liczy się tylko to, czy jeden z nich jest prawdziwy, aby zwrócić prawdę. W przeciwnym razie chcemy zwrócić wartość false.

Jeśli szukasz krótszej wersji, która jest mniej szczegółowa, zadziała to również:

or(arg1, arg2)
    if arg1
        return arg1
    return arg2

Oto rozwiązanie bez lub bez porównań i literałów boolowskich:

or(arg1, arg2)
  if arg1
    return arg1
  else
    return arg2

Prawdopodobnie nie ma to bardziej fundamentalnego znaczenia;)

Jedna linia kodu:

return not (not arg1 and not arg2)

Bez rozgałęzień, bez OR.

W języku C byłoby to:

return !(!arg1 && !arg2);

Jest to po prostu zastosowanie praw De Morgana :(A || B) == !(!A && !B)

Jeśli masz tylko andi not, możesz użyć prawa DeMorgan do odwracania and:

if not (arg1 = False and arg2 = False)
  return True
else
  return False

... lub (jeszcze prościej)

if arg1 = False and arg2 = False
  return false
else
  return true

...

A ponieważ najwyraźniej wszyscy jesteśmy skupieni na optymalizacji czegoś, co i tak prawie zawsze jest dostępne jako instrukcja maszyny, sprowadza się to do:

return not(not arg1 and not arg2)

return arg1 ? true : arg2

itd. itd. itd.

Ponieważ większość języków zapewnia warunki warunkowe, a szanse są operatorem „, a” oznacza i tak oddział.

...

Jeśli wszystko co masz to nand(patrz wikipedia ):

return nand (nand (arg1, arg1), nand (arg2, arg2))

Funkcje (ECMAScript)

Potrzebujesz tylko definicji funkcji i wywołań funkcji. Nie potrzebujesz żadnych rozgałęzień, warunków, operatorów ani wbudowanych funkcji. Zademonstruję implementację przy użyciu ECMAScript.

Najpierw zdefiniujmy dwie funkcje o nazwie truei false. Możemy zdefiniować je w dowolny sposób, są one całkowicie arbitralne, ale zdefiniujemy je w bardzo specjalny sposób, który ma pewne zalety, co zobaczymy później:

const tru = (thn, _  ) => thn,
      fls = (_  , els) => els;

trujest funkcją z dwoma parametrami, która po prostu ignoruje swój drugi argument i zwraca pierwszy. flsjest także funkcją z dwoma parametrami, która po prostu ignoruje swój pierwszy argument i zwraca drugi.

Dlaczego kodować trui flsw ten sposób? Cóż, w ten sposób dwie funkcje reprezentują nie tylko dwie koncepcje truei false, nie, jednocześnie reprezentują także koncepcję „wyboru”, innymi słowy, są również wyrażeniem if/ then/ else! Oceniamy ifwarunek i przekazujemy thenblok i elseblok jako argumenty. Jeśli warunek oceni się na tru, zwróci thenblok, jeśli oceni fls, to zwróci elseblok. Oto przykład:

tru(23, 42);
// => 23

Zwraca 23i to:

fls(23, 42);
// => 42

zwraca 42, tak jak można się spodziewać.

Jest jednak zmarszczka:

tru(console.log("then branch"), console.log("else branch"));
// then branch
// else branch

To drukuje zarówno then branch i else branch! Czemu?

Cóż, to zwraca wartość zwracaną pierwszego argumentu, ale ocenia oba argumenty, ponieważ ECMAScript jest surowe i zawsze ocenia wszystkie argumenty do funkcji przed wywołaniem funkcji. IOW: ocenia pierwszy argument console.log("then branch"), który po prostu zwraca undefinedi wywołuje efekt uboczny drukowania then branchna konsoli, i ocenia drugi argument, który również zwraca undefinedi drukuje na konsoli jako efekt uboczny. Następnie zwraca pierwszy undefined.

W rachunku λ, w którym wymyślono to kodowanie, nie stanowi to problemu: rachunek λ jest czysty , co oznacza, że ​​nie ma żadnych skutków ubocznych; dlatego nigdy nie zauważysz, że drugi argument również jest oceniany. Ponadto rachunek λ jest leniwy (a przynajmniej często jest oceniany w normalnej kolejności), co oznacza, że ​​tak naprawdę nie ocenia argumentów, które nie są potrzebne. IOW: w rachunku λ drugi argument nigdy nie byłby oceniany, a gdyby tak było, nie zauważylibyśmy.

ECMAScript jest jednak ścisły , tzn. Zawsze ocenia wszystkie argumenty. Właściwie nie zawsze: na przykład if/ then/ elseocenia thengałąź tylko wtedy, gdy jest spełniony warunek truei ocenia elsegałąź tylko wtedy, gdy jest spełniony warunek false. I chcemy powtórzyć to zachowanie z naszym iff. Na szczęście, mimo że ECMAScript nie jest leniwy, ma sposób na opóźnienie oceny fragmentu kodu, tak samo jak prawie każdy inny język: zawija go w funkcję, a jeśli nigdy nie wywołasz tej funkcji, kod będzie nigdy nie zostanie stracony.

Tak więc zawijamy oba bloki w funkcję, a na końcu wywołuje zwracaną funkcję:

tru(() => console.log("then branch"), () => console.log("else branch"))();
// then branch

wydruki then branchi

fls(() => console.log("then branch"), () => console.log("else branch"))();
// else branch

odbitki else branch.

Możemy wdrożyć tradycyjny if/ then/ w elseten sposób:

const iff = (cnd, thn, els) => cnd(thn, els);

iff(tru, 23, 42);
// => 23

iff(fls, 23, 42);
// => 42

Ponownie potrzebujemy dodatkowego zawijania funkcji podczas wywoływania ifffunkcji i dodatkowych nawiasów wywoływania funkcji w definicji z ifftego samego powodu, co powyżej:

const iff = (cnd, thn, els) => cnd(thn, els)();

iff(tru, () => console.log("then branch"), () => console.log("else branch"));
// then branch

iff(fls, () => console.log("then branch"), () => console.log("else branch"));
// else branch

Teraz, gdy mamy te dwie definicje, możemy je wdrożyć or. Najpierw przyjrzymy się tabeli prawdy dla or: jeśli pierwszy operand jest prawdziwy, wynik wyrażenia jest taki sam jak pierwszy operand. W przeciwnym razie wynik wyrażenia jest wynikiem drugiego operandu. W skrócie: jeśli pierwszym operandem jest true, zwracamy pierwszy operand, w przeciwnym razie zwracamy drugi operand:

const orr = (a, b) => iff(a, () => a, () => b);

Sprawdźmy, czy to działa:

orr(tru,tru);
// => tru(thn, _) {}

orr(tru,fls);
// => tru(thn, _) {}

orr(fls,tru);
// => tru(thn, _) {}

orr(fls,fls);
// => fls(_, els) {}

Świetny! Jednak ta definicja wygląda trochę brzydko. Pamiętajcie, trui flsjuż sami zachowują się jak warunek, więc naprawdę nie ma takiej potrzeby iff, a zatem wszystkie te funkcje są w ogóle opakowane:

const orr = (a, b) => a(a, b);

orOto on: (plus inne operatory logiczne) zdefiniowane za pomocą definicji funkcji i wywołań funkcji w zaledwie kilku liniach:

const tru = (thn, _  ) => thn,
      fls = (_  , els) => els,
      orr = (a  , b  ) => a(a, b),
      nnd = (a  , b  ) => a(b, a),
      ntt = a          => a(fls, tru),
      xor = (a  , b  ) => a(ntt(b), b),
      iff = (cnd, thn, els) => cnd(thn, els)();

Niestety, ta implementacja jest raczej bezużyteczna: w ECMAScript nie ma żadnych funkcji ani operatorów, które zwracają trulub flswszystkie zwracają truelub false, więc nie możemy ich używać z naszymi funkcjami. Ale wciąż możemy wiele zrobić. Na przykład jest to implementacja pojedynczo połączonej listy:

const cons = (hd, tl) => which => which(hd, tl),
      car  = l => l(tru),
      cdr  = l => l(fls);

Obiekty (Scala)

Być może zauważyliście coś dziwnego: trui flsodgrywają podwójną rolę, działają zarówno jako wartości danych truei false, ale w tym samym czasie, ale także działać jako wyrażenie warunkowe. Są to dane i zachowanie , połączone w jeden… uhm… „rzecz”… lub (ośmielę się powiedzieć) obiekt !

Rzeczywiście, trui flssą obiektami. A jeśli kiedykolwiek używałeś Smalltalk, Self, Newspeak lub innych języków zorientowanych obiektowo, zauważysz, że implementują booleany w dokładnie taki sam sposób. Zademonstruję taką implementację tutaj w Scali:

sealed abstract trait Buul {
  def apply[T, U <: T, V <: T](thn: ⇒ U)(els: ⇒ V): T
  def &&&(other: ⇒ Buul): Buul
  def |||(other: ⇒ Buul): Buul
  def ntt: Buul
}

case object Tru extends Buul {
  override def apply[T, U <: T, V <: T](thn: ⇒ U)(els: ⇒ V): U = thn
  override def &&&(other: ⇒ Buul) = other
  override def |||(other: ⇒ Buul): this.type = this
  override def ntt = Fls
}

case object Fls extends Buul {
  override def apply[T, U <: T, V <: T](thn: ⇒ U)(els: ⇒ V): V = els
  override def &&&(other: ⇒ Buul): this.type = this
  override def |||(other: ⇒ Buul) = other
  override def ntt = Tru
}

object BuulExtension {
  import scala.language.implicitConversions
  implicit def boolean2Buul(b: ⇒ Boolean) = if (b) Tru else Fls
}

import BuulExtension._

(2 < 3) { println("2 is less than 3") } { println("2 is greater than 3") }
// 2 is less than 3

To BTW jest powodem, dla którego funkcja Zastąp warunkowe refaktoryzacją polimorfizmu zawsze działa: zawsze możesz zastąpić dowolny warunek w twoim programie polimorficzną wysyłką wiadomości, ponieważ, jak właśnie pokazaliśmy, polimorficzna wysyłka wiadomości może zastąpić warunki warunkowe, po prostu je wdrażając. Języki takie jak Smalltalk, Self i Newspeak są tego dowodem na istnienie, ponieważ te języki nie mają nawet warunkowych. (Nie mają też pętli, BTW ani żadnych struktur kontrolnych wbudowanych w język, z wyjątkiem polimorficznego wysyłania komunikatów, czyli wirtualnych wywołań metod.)

Dopasowywanie wzorów (Haskell)

Można również zdefiniować orza pomocą dopasowania wzorca lub czegoś w rodzaju częściowych definicji funkcji Haskella:

True ||| _ = True
_    ||| b = b

Oczywiście dopasowanie wzorca jest formą wykonania warunkowego, ale z drugiej strony, podobnie jak obiektowe wysyłanie wiadomości.

Oto inny sposób zdefiniowania OR, a nawet dowolnego operatora logicznego, przy użyciu najbardziej tradycyjnego sposobu jego zdefiniowania: użyj tabeli prawdy.

Jest to oczywiście dość trywialne w językach wyższego poziomu, takich jak Javascript lub Perl, ale piszę ten przykład w C, aby pokazać, że technika nie zależy od funkcji języka wysokiego poziomu:

#include <stdio.h>

int main (void) {
    // Define truth table for OR:
    int OR[2][2] = {
        {0,   // false, false
         1},  // false, true
        {1,   // true, false
         1}   // true, true
    }

    // Let's test the definition
    printf("false || false = %d\n",OR[1==2]['b'=='a']);
    printf("true || false = %d\n",OR[10==10]['b'=='a']);

    // Usage:
    if (OR[ 1==2 ][ 3==4 ]) {
        printf("at least one is true\n");
    }
    else {
        printf("both are false\n");
    }
}

Możesz zrobić to samo z AND, NOR, NAND, NOT i XOR. Kod jest wystarczająco czysty, aby wyglądać jak składnia, dzięki czemu możesz robić takie rzeczy:

if (OR[ a ][ AND[ b ][ c ] ]) { /* ... */ }

Kolejny sposób wyrażenia operatorów logicznych jako liczb całkowitych wyrażeń arytmetycznych (tam, gdzie jest to możliwe). W ten sposób można uniknąć wielu rozgałęzień, aby uzyskać większą ekspresję wielu predykatów.

Niech prawda będzie 1 Niech fałszem będzie 0

jeśli suma obu jest większa niż 1, zwracane jest prawda lub fałsz.

boolean isOR(boolean arg1, boolean arg2){

   int L = arg1 ? 1 : 0;
   int R = arg2 ? 1 : 0;

   return (L+R) > 0;

}

Dwie formy:

OR(arg1, arg2)
  if arg1
     return True
  else:
     return arg2

LUB

OR(arg1, arg2)
  if arg1
     return arg1
  else:
     return arg2

Mają, podobnie jak golfową przewagę, bycie nieco mniejszym niż inne dotychczasowe sugestie, o jedną gałąź mniej. Mikrosopt nie jest nawet tak głupi, aby zmniejszyć liczbę rozgałęzień, jeśli rozważamy stworzenie prymitywu, który byłby w związku z tym bardzo intensywnie wykorzystywany.

Definicja JavaScript ||jest podobna do tego, co w połączeniu z luźnym pisaniem oznacza, że ​​wyrażenie false || "abc"ma wartość "abc"i 42 || "abc"ma wartość 42.

Chociaż jeśli masz już inne operatory logiczne, osoby takie nand(not(arg1), not(arg2))mogą mieć tę zaletę, że w ogóle nie mają rozgałęzień.

Oprócz wszystkich zaprogramowanych rozwiązań wykorzystujących konstrukcję if, możliwe jest zbudowanie bramki OR poprzez połączenie trzech bramek NAND. Jeśli chcesz zobaczyć, jak to się robi w wikipedii, kliknij tutaj .

Z tego wyrażenia

NIE [NIE (A I A) I NIE (B i B)]

który używa NOT i AND daje taką samą odpowiedź jak OR. Zauważ, że użycie zarówno NOT, jak i AND jest niejasnym sposobem wyrażania NAND.

Wszystkie dobre odpowiedzi zostały już podane. Ale nie pozwolę, żeby mnie to powstrzymało.

// This will break when the arguments are additive inverses.
// It is "cleverness" like this that's behind all the most amazing program errors.
or(arg1, arg2)
    return arg1 + arg2
    // Or if you need explicit conversions:
    // return (bool)((short)arg1 + (short)arg2)

Alternatywnie:

// Since `0 > -1`, negative numbers will cause weirdness.
or(arg1, arg2)
    return max(arg1, arg2)

Mam nadzieję, że nikt nigdy nie użyłby takich podejść. Są tutaj tylko po to, aby promować świadomość alternatyw.

Aktualizacja:

Ponieważ liczby ujemne mogą złamać oba powyższe podejścia, oto kolejna okropna sugestia:

or(arg1, arg2)
    return !(!arg1 * !arg2)

To po prostu wykorzystuje prawa DeMorgan i narusza fakt, który *jest podobny do tego, &&kiedy truei falsesą traktowane odpowiednio 1i 0. (Czekaj, mówisz, że to nie jest golf golfowy?)

Oto przyzwoita odpowiedź:

or(arg1, arg2)
    return arg1 ? arg1 : arg2

Ale to zasadniczo identyczne z innymi już udzielonymi odpowiedziami.

Jednym ze sposobów zdefiniowania orjest użycie tabeli odnośników. Możemy to wyraźnie zaznaczyć:

bool Or( bool a, bool b } {
  bool retval[] = {b,true}; // or {b,a};
  return retval[a];
}

tworzymy tablicę z wartościami, które powinna zwracać wartość w zależności od tego, co ajest. Następnie sprawdzamy. W językach podobnych do C ++, boolpromuje się do wartości, która może być używana jako indeks tablicowy z trueistnieniem 1i falsebytem 0.

Następnie możemy rozszerzyć to na inne operacje logiczne:

bool And( bool a, bool b } {
  bool retval[] = {false,b}; // or {a,b};
  return retval[a];
}
bool Xor( bool a, bool b } {
  bool retval[] = {b,!b};
  return retval[a];
}

Ich wadą jest to, że wymaga notacji przedrostkowej.

namespace operators {
  namespace details {
    template<class T> struct is_operator {};
    template<class Lhs, Op> struct half_expression { Lhs&& lhs; };
    template<class Lhs, class Op>
    half_expression< Lhs, Op > operator*( Lhs&&lhs, is_operator<Op> ) {
      return {std::forward<Lhs>(lhs)};
    }
    template<class Lhs, class Op, class Rhs>
    auto operator*( half_expression<Lhs, Op>&& lhs, Rhs&& rhs ) {
    return invoke( std::forward<Lhs>(lhs.lhs), Op{}, std::forward<Rhs>(rhs) );
    }
  }
  using details::is_operator;
}

struct or_tag {};
static const operators::is_operator<or_tag> OR;

bool invoke( bool a, or_tag, bool b ) {
  bool retval[] = {b,true};
  return retval[a];
}

a teraz możesz pisać true *OR* falsei to działa.

Powyższa technika wymaga języka obsługującego wyszukiwanie zależne od argumentów i szablony. Prawdopodobnie można to zrobić w języku zawierającym generyczne i ADL.

Poza tym możesz rozszerzyć *OR*powyższe, aby pracować z zestawami. Wystarczy utworzyć bezpłatną funkcję invokew tej samej przestrzeni nazw, co or_tag:

template<class...Ts>
std::set<Ts...> invoke( std::set<Ts...> lhs, or_tag, std::set<Ts...> const& rhs ) {
  lhs.insert( rhs.begin(), rhs.end() );
  return lhs;
}

a teraz set *OR* setzwraca związek dwóch.

Ten pamięta mi funkcje charasteristyczne:

or(a, b)
    return a + b - a*b

Dotyczy to tylko języków, które mogą traktować logiczne jako (1, 0). Nie dotyczy Smalltalk ani Python, ponieważ wartość logiczna jest klasą. W smalltalk idą jeszcze dalej (zostanie to zapisane w formie pseudokodu):

False::or(a)
    return a

True::or(a)
    return self

Istnieją podwójne metody dla:

False::and(a)
    return self

True::and(a)
    return a

Zatem „logika” jest całkowicie poprawna w instrukcji OP, chociaż jest pełna. Uwaga, nie jest źle. Jest idealny, jeśli potrzebujesz funkcji, która działa jak operator matematyczny oparty na powiedzmy pewnego rodzaju macierzy. Inni zaimplementowaliby rzeczywistą kostkę (jak instrukcja Quine-McCluskey):

or = array[2][2] {
    {0, 1},
    {1, 1}
}

I ocenisz lub [a] [b]

Tak więc, każda logika tutaj jest poprawna (oprócz tej opublikowanej jako przy użyciu w języku operatora OR xDDDDDDDD).

Ale moim ulubionym jest prawo DeMorgan: !(!a && !b)

Spójrz na standardową bibliotekę Swift i sprawdź ich implementację skrótu OR i skrótu AND, które nie oceniają drugich operandów, jeśli nie są potrzebne / dozwolone.

Logika jest całkowicie poprawna, ale można ją uprościć:

or(arg1, arg2)
  if arg1 = True
     return True
  else if arg2 = True
     return True
  else
     return False

I prawdopodobnie w twoim języku jest operator OR, więc - o ile nie jest to sprzeczne z duchem pytania - dlaczego nie

or(arg1, arg2)
  if arg1 = True or arg2 = True
     return True
  else
     return False