MATEMATYKA DYSKRETNA LISTA ZADAŃ NR 1
Logika zdań, metody dowodzenia twierdzeń, logika predykatów

1. Czy następujące wypowiedzi są zdaniami logicznymi?

a) Czy liczba
jest większa od 1?

b) Liczba
jest większa od 1.

c) Sprawdź, czy liczba
jest większa od 1.

d) Liczba
jest większa od pewnej liczby naturalnej.

e) Liczba
jest większa od każdej liczby naturalnej.

f) Liczba
jest niewiększa od x.

2. Zapisać za pomocą zmiennych zdaniowych i ocenić wartość logiczną zdań:

a) 3<4 ∧ 4<3, 3<4 ∨ 4<3, 3<4 ⇒ 4<3, 3<4 ⇔ 4<3.

b) Jeżeli x i y są liczbami rzeczywistymi, to x+y=y+x.

c) Jeśli czworokąt jest kwadratem, to 2+2=4.

d) Jeśli nie pada deszcz, to świeci słońce i na niebie są chmury.

e) Jeżeli liczba a dzieli się przez 3 lub a dzieli się przez 7, to z faktu, iż a nie dzieli się przez 3 wynika, że a dzieli się przez 7.

f) Jeżeli liczba a dzieli się przez 2 i a dzieli się przez 7, to z faktu, iż a nie dzieli się przez 7 wynika, że a dzieli się przez 3.

3. Niech zdanie p jest prawdą, zdanie q jest fałszem oceń wartość logiczną następujących zdań:

a) [(p⇒q)∧¬q]⇒¬p.

b) [(p∨q)∧(p⇒q)]⇒(q⇒p).

c) (p∨q⇔p∨¬q)⇒(¬p∧q).

4. Sprawdź, czy poniższe formuły są tautologiami rachunku zdań:

a) (¬p⇒p)⇒p

b) (p∨q⇒p∨¬q)⇒¬p∨q

c) (p∨q⇒r)⇒[(p⇒r)∨(q⇒r)]

5. Zdefiniuj

a) koniunkcję za pomocą alternatywy i negacji,

b) alternatywę za pomocą koniunkcji i negacji.

6. Udowodnić następujące twierdzenia korzystając z odpowiednich metod dowodzenia

a) Jeżeli a>0 to
, dowód „wprost”.

b)
jest liczbą niewymierną, dowód „nie wprost” lub dowód przez sprowadzenie do sprzeczności.

c) 1+3+5+…+(2n-1)=n², dla n∈N₊, dowód indukcyjny.

7. Podać, które zmienne są wolne, a które związane w następujących formułach:

a) ∃x ∀y [(x<y)⇒(x<z)∧(x<y)],

b) ∃x (x²+y²=1) ∨ (x<z),

c) ∃y ∀x (x²+y²=z²).

8. Zapisz za pomocą logiki predykatów następujące zdania i oceń ich wartość logiczną oraz zapisz zaprzeczenia tych zdań:

a) Istnieje naturalna liczba parzysta.

b) Każda liczba naturalna przy dzieleniu przez 2 daje resztę 0 lub 1.

c) Kwadrat każdej liczby całkowitej jest nie mniejszy od tej liczby.

9. Oceń wartość logiczną następujących formuł oraz zapisz ich zaprzeczenia:

a) ∃x∈R x⋅y=1,

b) ∀x∈R x²≥0,

c) ∀x∈R ∃y∈R x+y=2,

d) ∀x∈N ∃y∈N 2x=y,

e) ∃x∈N ∀y∈N 2x=y,

f) ∃y∈N ∀x∈N 2y=x.

Czy można przestawić kwantyfikatory w zdaniach c-f?

10. Narysuj wykresy następujących funkcji zdaniowych

a) ∃x∈Z x⋅y=1,

b) ∃x∈R x²+y²=1,

c) ∀x∈R ∃y∈R x²-y²=0,

d) ∀y∈R ∃x∈R x+y=4.