« nazaj
Diskretne strukture (FiM) - vaje 21.10.2020
Enakovrednost in poenostavljanje izrazov
Naloga 1
Poenostavi izjavna izraza:
- ¬(p∨q⇒p)∨¬p∧q,
- ¬(¬(p⇔¬r⇔(q⇔r))⇔p).
-
¬(p∨q⇒p)∨¬p∧q∼¬(¬(p∨q)∨p)∨(¬p∧q)∼((p∨q)∧¬p)∨(¬p∧q)∼(¬p∧q)∨(¬p∧q)∼¬p∧q
-
¬(¬(p⇔¬r⇔(q⇔r))⇔p)∼p⟺¬r⟺q⟺r⟺p∼p⟺p⟺q⟺r⟺¬r∼1⟺q⟺0∼¬q
Naloga 2
Poenostavi izraz Ak≡a↑a↑…↑a (k veznikov) za vsak k≥1.
- Ak+1∼Ak↑a
- A0∼a
- A1∼a↑a∼¬(a∧a)∼¬a
- A2∼¬a↑a∼¬(¬a∧a)∼1
- A3∼1↑a∼¬(1∧a)∼¬a
- Ak∼{¬ak lih1k sod (k≥1)
Naloga 3
S pomočjo izpeljevanja pokaži, da so naslednji pari izjavnih izrazov enakovredni:
- (p⇒q)∧(p⇒r) in (p⇒q∧r),
- (p⇒q)∨(p⇒r) in (p⇒q∨r),
- (p⇒r)∧(q⇒r) in (p∨q⇒r),
- (p⇒r)∨(q⇒r) in p⇒(q⇒r) in (p∧q)⇒r.
-
(p⇒q)∧(p⇒r)∼(¬p∨q)∧(¬p∨r)∼¬p∨(q∧r)∼p⇒q∧r
-
(p⇒q)∨(p⇒r)∼(¬p∨q)∨(¬p∨r)∼¬p∨q∨r∼p⇒q∨r
-
(p⇒r)∧(q⇒r)∼(¬p∨r)∧(¬q∨r)∼(¬p∧¬q)∨r∼¬(¬p∧¬q)⇒r∼p∨q⇒r
-
(p⇒r)∨(q⇒r)∼(¬p∨r)∨(¬q∨r)∼¬p∨¬q∨r∼¬p∨(q⇒r)∼¬(p∧q)∨r∼p⇒(q⇒r)∼p∧q⇒r
q∧r∼¬(¬q∨¬r)∨¬(q↓r)
Normalne oblike
- konjunktivna normalna oblika: (p∨¬q∨r)∧(¬p∨q∨r)∧…
- disjunktivna normalna oblika: (p∧¬q∧¬r)∨(¬p∧¬q∧r)∨…
Naloga 4
S pomočjo izpeljevanja zapiši izraz v konjunktivni normalni obliki ali v disjunktivni normalni obliki.
- ¬(p∨q)∧(p⇒r)
- (p↑q)↓r
- ((p⇒q)∨¬r)↑p
-
¬(p∨q)∧(p⇒r)∼(¬p∧¬q)∧(¬p∨r)∼¬p∧¬q∼(¬p∧¬q∧r)∨(¬p∧¬q∧¬r)
- disjunktivna normalna oblika
-
(p↑q)↓r∼¬(¬(p∧q)∨r)∼(p∧q)∧¬r∼p∧q∧¬r
- disjunktivna normalna oblika
-
((p⇒q)∨¬r)↑p∼¬(((¬p∨q)∨¬r)∧p)∼¬((q∨¬r)∧p)∼¬(q∨¬r)∨¬p∼(¬q∧r)∨¬p∼(p∧¬q∧r)∨(¬p∧¬q∧r)∨(¬p∧q∧r)∨(¬p∧q∧¬r)∨(¬p∧¬q∧¬r)(¬q∧r)∨¬p∼(¬p∨¬q)∧(¬p∨r)∼(¬p∨¬q∨r)∧(¬p∨¬q∨¬r)∧(¬p∨q∨r)