Diskretne strukture

Pozdravljeni,imam 2 primera iz diskretnih struktur ki sta verjetno relativno lahka vendar sem nekako vseeno naletel na tezave, tako da bi bil vsakrsne pomoci neizmerno hvalezen!

1.)
Pri naslednjem vprašanju je potrebno vnašati logične izraze. Pri tem veznike vpisujte z besedami, vrednost resnično navedete kot 1, vrednost neresnično pa kot 0. Izberite čim krajši zapis.Primer: izraz p∧¬(q∨r) vnesete kot p in ne (q ali r).

Veznik A je definiran z A(p,q,r)=¬p∧¬q∧¬r.Izrazi Ai, i=0,1,…, so definirani rekurzivno z
A0=0
A1=p
A2=q
An=A(An−1,An−2,An−3)za n=3,4,….Izračunaj A2004.

Pri tej nalogi ce imam prav pride A = p ? In potem samo vstavis in pride A(0, q,p). Resitev pa pride: ena in ne q in ne r
Ali se motim in me lahko popravite?


2.)
Namig: število naborov, pri katerih je izraz resničen, je enako številu osnovnih konjukcij pri zapisu izraza v DNO.

Določi število naborov logičnih vrednosti spremenljivk p, q, r, s, t inu pri katerih je izjavni izraz p⇒(q⇒(r⇒(s⇒(t⇒u))))resničen.

Kako to nalogo sploh resim? Mislim da se da z tabelo ampak je postopek zelo dolg in baje nezazelen. Kako naj to resim? Z zakoni izjavnega racuna spremenim implikacije negacijo prvega clena in disjunkcija, samo kaj naj potem z tem? Ali pa ce kdo lahko objavi samo rezultat...


Vsakrsna pomoc je zazeljena. Hvala v naprej

Pri nalogah tipa druge naloge lahko kar kombinatorično sešteješ vse nabore (to je lahko, saj se vsaka spremenljivka v izrazu pojavi samo enkrat).

Za koliko naborov je p => (q => (r => (s => (t => u)))) ~ 1?

Če je p = 0, logična vrednost q => (r => (s => (t => u))) ni važna. Končno število naborov je vsaj 2^5 (spremenljivke q, r, s, t in u so proste; p je fiksirana na 0).

Če je p = 1, mora biti q => (r => (s => (t => u))) ~ 1.

Za koliko naborov je q => (r => (s => (t => u))) ~ 1?

Če je q = 0, ... Končno število naborov je vsaj 2^4 (p in q sta fiksirana na 0, ostale spremenljivke so proste) + 2^5 (od prej).

... ... ...

Če je t = 0, ... Končno število naborov je vsaj 2 (edino spremenljivka u je prosta) + 2^2 + 2^3 + 2^4 + 2^5.

Če je t = 1, mora biti u = 1. Končno število naborov je 1 + 2 + 2^2 + 2^3 + 2^4 + 2^5 = 2^6 - 1 = 63.

Torej trditev ne velja samo za en nabor. Lahko tudi preveriš:

>>> def f(p, q):
... return not p or q
...
>>> def h(x):
... return f(x[0], f(x[1], f(x[2], f(x[3], f(x[4], x[5])))))
...
>>> for n in range (0, 2 ** 6 + 1):
... o = []
... for i in range(0, 6):
... o.append(bool(n & (1 << i)))
... if h(o) == False:
... print(n)
...
31
<<