4. gyakorlat

"Logikai alapok"

\(H \subseteq A \sim \chi_H: A \to \mathbb{L}\)

• \(\chi_H(a)=\begin{cases}\text{igaz, ha } \quad a \in H \\ \text{hamis, ha } \quad a \not\in H\end{cases}\)

Megyjegyzés: \(\; \chi - \text{ejtsd.: kí}\)

\(R: A \to \mathbb{L} \sim [R]\) - Az \(R\) igazsághalmaza

\([R]=\{a \in A \; | \; R(a)\}\)

Karakterisztikus függvény

Amikor teljesül az \(R(a)\)

Megoldás

A megoldás fogalmát logikai alapokra helyezzük.

Így egyszerűbb lesz bizonyítani

Példák

1. példa

• \(A = [1 \ldots 5]\)
• \(Q, R: A \to \mathbb{L}\)
• \([Q]=\{1,2\}\)
• \([R]=\{2,3,4\}\)

a. \([Q \land R] = [Q] \cap [R] = \{2\}\)

Amelyre a \(Q\) és az \(R\) is igazat ad \(\Rightarrow\) metszet

b. \([Q \lor R] = [Q] \cup [R] = \{1,2,3,4\}\)

Amelyre \(Q\) vagy \(R\) igazat ad \(\Rightarrow\) unió

c. \([\lnot Q] = A\setminus[Q] = \{3,4,5\}\)

A \(Q\) igazsághalmazán kívül eső értékek

d. \([Q \to R] = [\lnot Q \lor R] = (A\setminus[Q])\cup[R]=\{2,3,4,5\}\)

Implikáció: Ha a \(Q\) igazsághalmazában benne vannak, akkor az \(R\)-ében is benne kell, hogy legyenek. Illetve azok, amelyek a \(Q\)-ban nincsenek benne.

"\(Q \to R\) akkor igaz minden \(a\)-ra, ha a \(Q\) igazsághalmaza az része az \(R\) igazsághalmazának." \(Q \to R \; \text{ igaz } \; \forall a \in A \iff [Q] \subseteq [R]\)

Leggyengébb előfeltétel

\(lf(S,R): A \to \mathbb{L}\) - Az \(S\) programnak az \(R\) feltételre vett leggyengébb előfeltétele

"Azokra az állapotokra ad igazat, amelyre az \(S\) program BIZTOSAN beleterminál az \(R\) igazsághalmazába"

\([lf(S,R)]=\{a \in D_{p(S)} \; | \; p(S)(a) \subseteq [R]\}\)

2. példa

• \(A = [1 \ldots 5]\)
• \(R: A \to \mathbb{L}\)
• \([R]=\{1,2\}\)
• \(S=\{1 \to <1> \; <1,3>, <2> \to <2,1> \; <2>, <3> \to <3,2> \; <3, fail>, 4 \to <4,1> \; <4,2> \; <4,4,4,\ldots>, 5 \to <5,1>\}\)
• S átláthatóbban:
  • 1
    • \(1 \to <1>\)
    • \(1 \to <1,3>\)
  • 2
    • \(2 \to <2,1>\)
    • \(2 \to <2>\)
  • 3
    • \(3 \to <3,2>\)
    • \(3 \to <3, fail>\)
  • 4
    • \(4 \to <4,1>\)
    • \(4 \to <4,2>\)
    • \(4 \to <4,4,4,\ldots>\)
  • 5
    • \(5 \to <5,1>\)

lfs(S, R) : \(A \to \mathbb{L}\)

\(D_{p(S)} = \{1, 2, 5\}\)

• \(p(S)(1) = \{1, 3\}\)
• \(p(S)(2) = \{1, 2\}\)
• \(p(S)(5) = \{1\}\)

\([lf(S,R)]=\{2, 5\}\)

3. példa

\(S\) program \(A\) állapottér felett

\(R: A \to \mathbb{L}\)

\(Q: A \to \mathbb{L}\)

a. \([lf(S, R)] \cup [\lnot lf(S, R)] = A\)

b. \([lf(S,R)] \cup [lf(S, \lnot R)] = A\)

Hamis: ellenpéldát mutatunk

Előző feladat szerint

\([\lnot R] = \{3,4,5\}\)

\([lf(S, \lnot R)] = \varnothing\)

Tehát \([lf(S,R)] \cup \varnothing \neq A\)

c. Igaz-e, hogy ha \([Q] \subseteq [R]\), akkor \([lf(S, Q)] \subseteq [lf(S, R)]\)?

Igaz

Bizonyítás: Meggondolandó

d. \(lf(S, Q) \lor lf(S, R) \quad ? \quad lf(S, Q \lor R)\)

Van-e közöttük kapcsolat? (Mi van a kérdőjel helyén?)

\(lf(S, Q) \lor lf(S, R) \quad \subseteq \quad lf(S, Q \lor R)\) igaz, de

\(lf(S, Q) \lor lf(S, R) \quad \supseteq \quad lf(S, Q \lor R)\) nem igaz, hiszen

• \(p(S)(1) = \{1, 3\}\)
• \(p(S)(2) = \{1, 2\}\)

• \(p(S)(5) = \{1\}\)

• \([Q] = \{3,4,5\}\)

• \([R] = \{1,2\}\)

esetén

• \([lf(S, Q)] = \varnothing\)
• \([lf(S, R)] = \{2,5\}\)
• \([lf(S, Q \lor R)] = \{1,2,5\} \not\subseteq \varnothing \cup \{2,5\}\)

Tehát ebbe az irányban a nem-determinisztikusság miatt nem igaz.

e. \(lf(S, Q) \land lf(S, R) \quad ? \quad lf(S, Q \land R)\)

(Lecseréltük a vagy-ot és-re.)

\(\subseteq\) biztos igaz

\(\supseteq\) igaz-e?

Nézzük igazság halmazokkal:

\([lf(S, R)] \cap [lf(S, Q)] \quad ? \quad [lf(S, R \land Q)]\)

1. eset: \(\subseteq\)

   \(a \in [lf(S, R)] \cap [lf(S, Q)]\)

   \(a \in [lf(S, R)]\) és \(a \in [lf(S, Q)]\)

   Ebből következik:

   \(a \in D_{p(S)}\) és \(p(S)(a) \subseteq [R]\)

   \(a \in D_{p(S)}\) és \(p(S)(a) \subseteq [Q]\)

   Tehát

   \(A \in D_{p(S)}\) és \(p(S)(a) \subseteq [R] \cap [Q]\)

   Ami megegyezik az \(lf(S, R \land Q)\)

Mivel minden lépés ekvivalens, ezért a másik irányba is igaz: \(\supseteq\) is igaz.

Ezzel bizonyítottuk, hogy igaz

\([lf(S, R)] \cap [lf(S, Q)] \quad \subseteq \quad [lf(S, R \land Q)]\)

4. példa

1. \(lf(S, \text{hamis}) = \text{hamis}\)

   \([lf(S, \text{hamis})] = \varnothing\)

2. \(lf(S, \text{igaz}) = \chi_{D_{p(S)}}\)

   \([lf(S, \text{igaz})] = D_{p(S)}\)

3. \(\text{SKIP} = \{a \to <a>\}\)

   (Semmit sem csináló program. Rögtön terminál.)

   \(lf(\text{SKIP}, R) = R\)

4. \(\text{ABORT} = \{a \to <a, fail>\}\)

   (Bármilyen állapotból indítjuk el, azonnal fail-lel. "Helyből rosszul működő program.")

   \(lf(\text{ABORT}, R) = \text{hamis} \quad\) (másképp \(\empty\))

5. \(A = (x: \N, y: \N)\)

   \(lf(x := x-y, 2x+y < 5) = ?\)

   a. \((x := x-y)(3,1) = \{<(3,1), (2,1)>\}\)

   \((x := x-y)(3,3) = \{<(3,3), (0,3)>\}\)

   \((x := x-y)(1,3) = \{<(1,3), fail>\}\)

   b. \(D_{p(x := x-y)} = \{a \in A \; | \; x(a) - y(a) \geq 0 \}\)

   \(p(x := x-y)(a) = \{(x(a)-y(a), y(a))\}\)

   c. \((2 \cdot x + y < 5):A \to \mathbb{L}\)

   \((2x + y < 5)(3,1) = 2 \cdot 3 + 1 < 5 = \text{hamis}\)

   (Tulajdonképpen ez egy lambda kifejezés.)

   (\ x y -> 2 * x + y < 5)

   d. \(lf(x := x-y, 2x+y<5)\)

   • Először igazsághalmaz kiszámolása:
     • \([lf(x := x-y, 2x+y<5)] =\{a \in D_{p(x := x-y)} \; | \; p(x:=x-y)(a) \subseteq [2x+y<5]\}\)
     • \(= \{ a \in A \; | \; a \in D_{p(x := x - y)} \land (2x+y<5)(p(x:=x-y)(a))\}\)
     • \(= \{a \in A \; | \; x(a) - y(a) \geq 0 \; \land \; 2(x(a)-y(a))+y(a)<5\}\)
       • * \((p(x:=x-y)(a)) = x(a) - y(a), y(a)\)
     • \(= \{a \in A \; | \; x(a) - y(a) \geq 0 \; \land \; 2x(a)-y(a)<5\}\)
     • \(lf(x:=x-y, 2x+y<5) = (x \geq y \land 2x-y<5)\)

Fogalmak a következő órára

• állapot
• állapottér
• program
• program függvény
• megoldás
• Leggyengébb előfeltétel