[DM 11]
[1/11] Jeżeli wiadomo, że zdania p → q, ~p → r, r → (p ∨ q) są prawdziwe to czy można rozstrzygnąć które ze zdań p, q, r są prawdziwe, a które nie?
[2/11] Jeżeli wiadomo, że zdanie
(a) ~p ∧ q jest fałszywe to co można powiedzieć o zdaniu: (p ∨ ~q) ∧ (q → p) ∧ (q → (~p → p))
(b) (p1 → (p2 → (p3 → ... (pn → q)...))) jest fałszywe to co można powiedzieć o zdaniach p1, p2, .., pn, q?
[3/11] Przedstaw schematy logiczne S, R, w których występują zmienne zdaniowe p, q, r i dla których w(S) w(R) są określone tabelą:
w(p) w(q) w(r) w(S) w(R)
0 0 0 0 1
0 0 1 0 0
0 1 0 1 1
0 1 1 0 1
1 0 0 1 0
1 0 1 1 1
1 1 0 1 1
1 1 1 0 0
[4/11] Udowodnij, że spójnik logiczny NAND ((p NAND q) ↔ ~(p ∧ q)) pozwala zastąpić wszystkie pozostałe spójniki przedstawione na wykładzie.
[5/11] Czy przy użyciu jedynie spójnika NAND można rozwiązać zadanie [3/3] z dowolnie zmienioną kolumną w(R) (inny układ zer i jedynek)?
[6/11] Rozwiąż zadanie [3/3] tak aby schematy S, R miały postać normalną CNF (tzn. żeby schemat był koniunkcją alternatyw dowolnych zdań spośród p, q, r, ~ p, ~q, ~r np. (p ∨ q) ∧ (~q ∨ p ∨ r) ∧ (~p ∨ ~r))
[7/11] Udowodnij poprawność dowolnie wybranych 3 praw rachunku zdań prezentowanych na wykładzie.
[8/11]* Zaproponuj algorytmiczną metodę dowodzenia praw algebry zbiorów, w których oprócz operatorów mnogościowych występują także spójniki logiczne. Przedstaw działanie algorytmu na następujących przykładach:
(a) Jeżeli A ⊆ B i B ⊆ C to A ∩ C = A
(b) Jeżeli A ∩ B = ∅ to A \ B = A
[9/11]* Udowodnij, że są tylko dwa spójniki logiczne, dwuargumentowe takie, że za pomocą każdego z nich można wyrazić każdy inny spójnik dwuargumentowy.
[10/11]* Udowodnij, że za pomocą równoważności i negacji nie można wyrazić koniunkcji.
[11/11]* Udowodnij, że schemat rachunku zdań zbudowany ze zmiennych zdaniowych wyłącznie za pomocą funktorów ~, ↔ jest tautologią wtedy i tylko wtedy, gdy każda zmienna zdaniowa występuje w niej parzystą liczbę razy i operatora negacji użyto parzystą liczbę razy.