M2_zadania.pdf

Zadania dodatkowe

Zadanie 1

Rozważmy formułę ( ¬ p ⇒ ¬ q ) ⇔ ¬ q oraz zbiór formuł X = { ¬ p , q }. Czy dana formuła

wynika ze zbioru X ?

Zadanie 2

Przeprowadź następujące wnioskowania metodą wprost:

(a) q ⇒ r , ¬ r ∨ ( s ∧ p ) ׀ − DNZ ( s ⇒ t ) ⇒ [ q ⇒ ( p ∧ t )],

(b) q ⇒ r , ¬ ( ¬ p ⇒ ¬ s ), r ∧ s ⇒ t ׀ − DNZ q ⇒ ( u ⇒ t ),

Zadanie 3

Przeprowadź następujące wnioskowania metodą nie wprost:

(a) p , ¬ p ∨ s , s ⇒ t ∧ q , q ⇒ u ׀ − DN u ∧ t ,

(b) q ⇒ r , ¬ r ∨ ( s ∧ p ) ׀ − DNZ ( s ⇒ t ) ⇒ [ q ⇒ ( p ∧ t )],

Zadanie 4

Dla zadanych form zdaniowych znajdź zakresy, aby były one spełnialne, prawdziwe,

fałszywe.

(a) ϕ 1 ( x ) : (2 x + 2 = 10),

(b) ϕ 2 ( x ) : ( x + 1 ≠ 5),

Zadanie 5

W podanych wyrażeniach kwantyfikatorowych wskaż zakresy poszczególnych

kwantyfikatorów. Jakie zmienne są wolne, a jakie związane w tych wyrażeniach?

(a) ∃ y (2 x + y = z ) ⇒ ∀ x ( x = 2 z ),

(b) ∀ x ∀ z [ ∃ y (2 x + 1 = 2 z ) ∧ ( x = y )],