LISTA ZADAC
NR 1 Z MATEMATYKI DYSKRETNEJ
Logika
1. Które z następujących sformułowań są zdaniami w sensie logicznym? Uzasadnij odpowiedz
.
a) Juliusz Cezar był prezydentem USA.
b) 2n+ n jest liczbą pierwszą dla nieskończenie wielu n " N .
c) x + y = y + x dla wszystkich liczb rzeczywistych x, y.
d) Jeśli okrąg jest czworokątem, to 2 + 2 = 4 .
e) Dlaczego logika jest ważna?
f) Idz
prosto do szpitala.
g) A2 = 0 implikuje A = 0 dla wszystkich A.
2. Niech p, q, r będą następującymi zdaniami: p =  pada deszcz , q =  słońce świeci , r =  na
niebie są chmury . Przetłumacz następujące zdania na język polski:
a) ( p '" q) Ò! r ,
b) ~ p Ò! (q (" r) ,
c) ~ ( p (" q) '" r ,
d) ( p Ò! r) Ò! q ,
e) ~ ( p Ô! (q (" r)).
3. Wykaż, że następujące wyrażenia są tautologiami:
a) p Ô! ~ (~ p) prawo podwójnego przeczenia,
b) p(" ~ p prawo wyłączonego środka,
c) ~ ( p'" ~ p) prawo sprzeczności,
d) ~ ( p (" q) Ô! (~ p'" ~ q) prawo de Morgana,
e) ~ ( p '" q) Ô! (~ p(" ~ q) prawo de Morgana,
f) ( p '" p) Ô! p ,
g) ( p (" p) Ô! p ,
h) ( p (" q) Ô! (q (" p) , przemienność alternatywy,
i) ( p '" q) Ô! (q '" p) , przemienność koniunkcji,
j) ( p Ò! q) Ô! (~ q Ò! ~ p) ,
k) ( p Ò! q) Ô! (~ p (" q) ,
l) ~ ( p Ò! q) Ô! ( p'" ~ q) ,
Å‚) [ p '" ( p Ò! q)] Ò! q ,
m) [( p (" q)'" ~ p] Ò! q ,
n) ( p Ò! F) Ò! ~ p , gdzie F  dowolne zdanie sprzeczne,
o) [ p (" (q (" r)] Ô! [( p (" q) (" r] Å‚Ä…czność alternatywy,
p) [ p '" (q '" r)] Ô! [( p '" q) '" r] Å‚Ä…czność koniunkcji,
r) [ p '" (q (" r)] Ô! [( p '" q) (" ( p '" r)] rozdzielność koniunkcji wzglÄ™dem alternatywy,
s) [ p (" (q '" r)] Ô! [( p (" q) '" ( p (" r)] rozdzielność alternatywy wzglÄ™dem koniunkcji,
t) [( p Ò! q) '" (q Ò! r)] Ò! ( p Ò! r) przechodniość implikacji.
4. Sprawdz
, czy następujące wyrażenia są tautologiami:
a) ( p Ò! q) Ô! (q Ò! p) ,
b) [( p Ò! q) '" (q Ò! p)] Ò! ( p (" q) ,
c) [( p (" q) Ò! r] Ò! [( p Ò! r) (" (q Ò! r)].
5. Określ:
a) koniunkcjÄ™ za pomocÄ… alternatywy i negacji,
b) alternatywÄ™ za pomocÄ… koniunkcji i negacji,
c) alternatywÄ™ za pomocÄ… implikacji i negacji.
6. Czy następujące zdanie jest prawdziwe? Jakie można zapisać jego zaprzeczenie?
a) Istnieje liczba naturalna n, której kwadrat wynosi 7.
b) Istnieje liczba rzeczywista x taka, że x +1 + x + 2 = 0.
Jak równoważnie zapisać zdanie ~ [(" W (x)], gdzie W (x) jest pewną formą zdaniową.
x
7. Czy następujące zdanie jest prawdziwe? Jakie można zapisać jego zaprzeczenie?
a) Każda liczba naturalna n jest złożona.
b) Każda liczba rzeczywista spełnia warunek x2 e" x .
Jak równoważnie zapisać zdanie ~ ['" W (x)] , gdzie W (x) jest pewną formą zdaniową.
x
8. Podaj wartości logiczne następujących wyrażeń:
a) '" (" 2m = n ,
n"N m"N
b) '" (" 2n = m ,
n"N m"N
c) (" '" 2n = m .
m"N n"N
Czy prawdziwa jest implikacja
(" '" W (x, y) Ò! '" (" W (x, y) ?
x y y x
Czy prawdziwa jest implikacja odwrotna? Jeśli nie, podaj kontrprzykład.
9. Podaj wartości logiczne następujących wyrażeń, gdzie dziedziną jest zbiór R .
a) "x "y xy = 1,
b) "x "y xy = 1,
c) "x "y (x + y)2 = x2 + y2 .
d) "x "y (x + y)2 = x2 + y2 ,
e) "y "x (x + y)2 = x2 + y2 ,
Dorota Majorkowska-Mech