Számítás tudomány alapjai, tudna segíteni valaki ezen feladatok megoldásában?

1.

Bal oldal: (A-B)∪(B-A)

Mivel (X-Y) = X ∩ ¬Y

ezért a bal oldal: (A ∩ ¬B)∪(B ∩ ¬A)

Mivel (X∩Y)∪Z = (X∪Z)∩(Y∪Z)

ezért tovább alakítva:

(A∪(B ∩ ¬A)) ∩ (¬B∪(B ∩ ¬A))

még egyszer ugyanez a szabály:

((A∪B) ∩ (A∪¬A)) ∩ ((¬B∪B) ∩ (¬B∪¬A))

Mivel X ∪ ¬X = 1, ezért leegyszerűsödik:

(A∪B) ∩ (¬B∪¬A)

Jobb oldal: (A∪B)-(A∩B)

Mivel (X-Y) = X ∩ ¬Y

ezért a jobb oldal: (A∪B) ∩ ¬(A∩B)

Mivel ¬(X∩Y) = ¬X ∪ ¬Y

(A∪B) ∩ (¬A∪¬B)

Ez ugyanaz, készen vagyunk.

3.

p hamis (az üres gráfnak éle nincs, csúcsa lehet)

q hamis (egyébként az üres halmaznak eleme lenne az üres halmaz, tehát nem lenne üres)

r hamis

Ezt kell tehát kiszámolni:

0 <=> 0 => ¬0 ∧ (¬0 => 0 ∨ 0)

Itt az a bajom, hogy nem tudom, hogy hogyan tanultátok, van-e valamilyen precedencia a műveletek sorrendjében, vagy egyszerűen ahol nincs zárójel, az balról jobbra megy? Az ∧ (és) és ∨ (vagy) között szokott lenni, az és-t kell korábban elvégezni, de ez se biztos, hogy így tanultátok.

Ha balról jobbra:

0 <=> 0 = 1

1 => ¬0 = 1

1 ∧ (¬0 => 0 ∨ 0)

A zárójel:

¬0 => 0 = 0

0 ∨ 0 = 0

1 ∧ 0 = 0

4. Megint nem tudom, balról jobbra kell-e. Ha igen:

p => ¬q ugyanaz, mint ¬p ∨ ¬q

Tehát az egész:

¬p ∨ ¬q ∨ r

Ez a konjunktív normálforma. Perfekt is egyben, mert mindhárom logikai változó megvan benne.

Ha más a precedencia:

p => (¬q ∨ r)

¬p ∨ (¬q ∨ r)

¬p ∨ ¬q ∨ r

most ez is ugyanaz lett...

6. Itt nem tudok gráfot rajzolni, de lista-szerűen fel tudom írni:

*(-(a,b),+(/(a,b),c))

Ebből ugye tudsz gráfot rajzolni, meg az 5-ösből is? Ebből mindenhol 2 elágazás lesz, az 5-ösnél meg kétszer 3, kétszer 2.

Általános esetben a direkt szorzat nem asszociatív egyszerűen azért, mert (AxB)xC olyan rendezett pár, aminek első tagja maga is egy rendezett pár, míg Ax(BxC) pont fordítva van, ott a rendezett pár második tagja rendezett pár. Tehát ezek a halmazok eleve nem lehetnek azonosak minden esetben.

Egyszerűbb talán abba belegondolni, hogy a direkt szorzat általános esetben nem is kommutatív. Mondjuk az A halmaz az egyjegyű pozitív egészek halmaza, B meg a kétjegyűeké. AxB rendezett számpárban az első szám kisebb, mint a második, míg BxA-ban pont fordítva. Nem lehetnek azonosak.

Speciális esetekben (csoportelmélet izomorfizmussal) teljesülhet mind a kommutativitás, mind az asszociativitás, de általánosan nem.