Výroková logika

Výroková logika

Výrok
Základným pojmom výrokovej logiky je výrok. Výrok je tvrdenie, o ktorého pravdivosti má zmysel
uvažovať, teda viem rozhodnúť, či je pravdivé alebo nepravdivé (nemusím vedieť rozhodnúť hneď).

Pravdivostná hodnota výroku:
• pravda, lož
• 1,0
• true, false

Príklady

Tráva je zelená.

výrok, pravdivý

2 + 2 = 5

výrok, nepravdivý

Zatvor dvere.

nie je výrok

Je vonku teplo?

nie je výrok

Táto veta je nepravdivá.

nie je výrok

x>2

nie je výrok, lebo neviem, čo je x

Logické operátory (spojky)
Logické operátory umožňujú vytvárať z jednoduchých výrokov zložené. Logický operátor nerobí
nič so zmyslom viet. Najpoužívanejšie logické operátory sú: negácia, konjunkcia, disjunkcia,
implikácia a ekvivalencia.

Nech A,B sú výroky. Potom

a) negáciou výroku A nazývame výrok „Nie je pravda, že A“ a označujeme ho

¬A,

b) konjunkciou výrokov A, B nazývame výrok „A a B“ a označujeme ho A

∧B,

c) disjunkciou výrokov A, B nazývame výrok „A alebo B“ a označujeme ho A

∨B,

d) implikáciou výrokov A, B nazývame výrok „Ak A, potom B.“ a označujeme ho A

⇒B,

e) ekvivalenciou výrokov A, B nazývame výrok „A práve vtedy, keď B“ a označujeme ho A

⇔B.

Príklady

a) Nie je pravda, že prší.

b) Prší a svieti slnko.

c) Prší alebo svieti slnko.

d) Ak si napíšeš úlohu, pôjdeme na zmrzlinu.

e) Prirodzené číslo je deliteľné tromi práve vtedy, keď je jeho ciferný súčet deliteľný tromi.

Pravdivostné tabuľky

A

¬A

0

1

1

0

A B

A

∧B A∨B A⇒B A⇔B A⊕B A↓B

A

↑B

0 0

0

0

1

1

0

1

1

0 1

0

1

1

0

1

0

1

1 0

0

1

0

0

1

0

1

1 1

1

1

1

1

0

0

0

AND

min

OR

max

≤

=

XOR

<

≠>

NOR NAND

Poznámka
⊕ - sčítanie modulo 2
XOR - vylučujúce alebo, dáva 1, keď je pravdivý práve jeden

<

≠> - negácia ekvivalencie

↓ - Peirce, A↓B =

¬(A∨B)

↑- Sheffer, A↑B =

¬(A∧B)

Výpo

čet hodnoty zloženého výroku

Pr.

((0 XOR 1)

⇒ (1∨0)) ∧ (1⇔1) = (1⇒1) ∧1 = 1∧1 = 1

Pr.

Urči hodnotu zloženého výroku (A

∨ (B∧C)) ⇔ ((A∨B) ∧ (A∨C)) pre všetky možné hodnoty

A,B,C.

A B C

(A

∨

(B

∧C))

⇔

((A

∨B)

∧

(A

∨C))

0

0

0

0

0

0

1

0

0

0

0

0

1

0

0

0

1

0

0

1

0

1

0

0

0

0

1

1

0

0

0

1

1

0

1

1

1

1

1

1

1

0

0

1

1

0

1

1

1

1

1

0

1

1

1

0

1

1

1

1

1

1

0

1

1

0

1

1

1

1

1

1

1

1

1

1

1

1

1

1

Výroková formula a iné spôsoby zápisu zložených výrokov
A, B, p, q, … výrokové premenné

Df. výroková formula (logický výraz)

1. Každá výroková premenná a konštanta (0, 1) sú výrokové formuly.

2. Ak p, q sú výrokové formuly, potom aj

¬p,(p∧q), (p∨q), (p⇒q), (p⇔q), (p↑q), (p↓q), (p⊕q) sú

výrokové formuly.

3. Nič iné nie je výroková formula.

Pr.

• A, B, C, 0, 1, ¬B, (1∧¬B), ((A∨C) ∧(B∨D)) sú výrokové formuly
• (A∨) C ⇒ nie je výroková formula

Spracovanie logického výrazu v zásobníku

ide po 1. pravú zátvorku

zásobník

Vstup

(1

↑ ( ( (0 ∨ 1) ⇒ 0) ⊕ 0))

(1

↑ ( ( (0 ∨ 1)

⇒ 0) ⊕ 0))

(1

↑ ( (

(0

∨ 1)

⇒ 0) ⊕ 0))

(1

↑ ( ( 1

⇒ 0) ⊕ 0))

(1

↑ ( ( 1⇒ 0)

⊕ 0))

(1

↑ (

( 1

⇒ 0) ⊕ 0))

(1

↑ ( 0

⊕ 0))

(1

↑ ( 0 ⊕ 0)

)

(1

↑

( 0

⊕ 0) )

(1

↑ 0)

(1

↑ 0)

1

Df. logická schéma

1. LS(0) = 0 , LS(1) = 1 , LS(x) = x

2. LS(

¬α) = LS((α∨β)) =

Pr.

LS(((

¬A∨B) ⇒ C)) = = =

Df. poľský zápis

1. PZ(0) = 0, PZ(1) = 1, PZ(x) = x

2. PZ(

¬α) = PZ(α)¬

PZ((

α∨β)) = PZ(α) PZ(β)∨

...

Pr.

PZ(((

¬A∨B) ⇒ C)) = PZ((¬A∨B)) PZ(C) ⇒ = PZ(¬A) PZ(B) ∨PZ(C) ⇒ =

PZ(A)

¬PZ(B) ∨ PZ(C) ⇒ = A¬B ∨C ⇒

LS(

β)

LS(

α)

¬

LS(

α)

∨

LS(C)

LS((

¬A∨B))

⇒

⇒

LS(B)

LS(

¬A)

∨

⇒

∨

C

C

B

¬

A

Vyhodnotenie poľského zápisu v zásobníku

ide po 1. operátor

zásobník

vstup

0

¬1∨1⇒

0

¬

1

∨1⇒

0

¬

1

∨1⇒

11

∨

1

⇒

11

∨ 1⇒

11

⇒

11

⇒

1

Poznámka

bežný zápis

funkcionálny zápis

poľský zápis

sin (x)

a + b

+ (a, b)

a b +

a * b

* (a, b)

a b *

a

∨ b

∨ (a, b)

a b

∨

¬a

¬(a)

a

¬