Számítástudomány epizód tartalma:
Nem csak a halmazok komplementereire léteznek De Morgan azonosságok, hanem a matematikai logikában állítások tagadására is. Nézzük meg a konjunkció, a diszjunkció, az implikáció és az ekvivalencia tagadását a De Morgan azonosságok segítségével. Sőt, a De Morgan azonosságok arra is jók, hogy diszjunktív normálformákat készítsünk...
Van itt ez az állítás:
Az áldozat a szobában van, és ha nem találják meg, akkor holnap is ott lesz.
Lássuk, mi lesz ennek a tagadása.
Ehhez egy kicsit formalizáljuk:
A tagadás pedig a mi kis képleteink segítségével…
Ez valahogy így szól, hogy:
Az áldozat nincs a szobában, vagy nem találják meg és holnap nem lesz ott.
Ezeket a képleteket De Morgan azonosságoknak hívják.
Voltak már ilyenek a halmazoknál is…
De ezek most a logikai De Morgan azonosságok.
Azon kívül, hogy segítenek nekünk leírni egy állítás tagadását még rengeteg mágikus dolgot tudnak.
Nézzük meg például ezt:
Ha most ezt újra tagadjuk…
A dupla tagadás éppen kiejti egymást.
Itt pedig használhatjuk ezt.
És ezzel egy „Ha akkor” típusú állítást le tudtunk írni egy tagadás és egy „vagy” segítségével.
Ezzel az új kis képletünkkel az eredeti állítás egész jól átalakítható…
Az állítás pedig így szól…
Az áldozat a szobában van, és megtalálják vagy holnap is ott lesz.
De nem csak a „Ha akkor” típusú állításokat tudjuk lecserélni…
A De Morgan azonosságokkal ugyanis képesek vagyunk az „és”-t átalakítani „vagy”-ra és fordítva.
Nézzük meg például, hogyan nézne ki egy olyan világ, amiben csak tagadás meg „vagy” létezik:
Itt túl sok dolgunk nincsen…
És az ekvivalencia…
Na, itt még szükség van egy kis trükkre.
Az ekvivalencia azt jelenti, hogy A és B is egyszerre igaz…
vagy egyszerre hamis.
Ezzel fogjuk folytatni.