Wrocław, 28 listopada 2012
Wydział Informatyki i Zarządzania, rok I
Logika dla informatyków
Zadania lista 8
1. Które z poniższych stwierdzeń są prawdziwe. Jeżeli INTv(a b) = prawda, to:
a) INTv(a) = prawda lub INTv(b) = prawda
b) INTv(a)=prawda oraz INTv(b) = prawda
c) istnieje takie v różniące się od v wartościowaniem zmiennej x, że
INTv (a) = prawda oraz INTv (a) = prawda
d) dla każdego v różniącego się od v wartościowaniem zmiennej y, zachodzi
INTv (a) = prawda oraz INTv (a) = prawda
2. Które z poniższych stwierdzeń są prawdziwe. Jeżeli INTv(a Ł b) = prawda to:
a) INTv(a) = prawda oraz INTv(b) = prawda
b) INTv(a) = prawda lub INTv(b) = prawda
c) istnieje takie v różniące się od v wartościowaniem zmiennej x, że
INTv (a) = prawda oraz INTv (a) = prawda
d) dla każdego v różniącego się od v wartościowaniem zmiennej y, zachodzi
INTv (a) = prawda oraz INTv(a) = prawda
3. Stosując metodę zerojedynkową wykazać, że następujące formuły są tautologiami:
a) p (q p)
b) (pŁ q) (p q)
c) (p q) (p Ł q)
4. Sprawdz (w dowolny sposób), czy są tautologiami następujące formuły:
a) p (q Ł r) (p Ł q) (p Ł r)
b) p Ł (q r) (p Ł q) (p Ł r)
5. Niech a oraz b będą tautologiami rachunku zdań. Które z następujących formuł są tautolo-
giami rachunku zdań:
a) a a
b) a b
c) a b
d) a b
6. Dane są dwa dwuargumentowe funktory logiczne NAND oraz NOR zdefiniowane następu-
jąco:
NAND(a, b) = (a Ł b)
oraz
NOR(a, b) = (a b).
Pokazać, w jaki sposób, za pomocą tych funktorów, można wyrazić spójniki logiczne negacji,
koniunkcji i alternatywy. Narysować sieci logiczne realizujące funkcje prawdziwościowe f1,
f2 zdefiniowane przedstawioną poniżej tabelą, w której symbolami 0 oraz 1 oznaczono od-
powiednio fałsz oraz prawdę.
a b f1(a,b) f2(a,b
0 0 1 1
0 1 0 0
1 0 1 1
1 1 0 1
7. Dana jest gramatyka G =df
, gdzie:
S =df {0, 1, @, #, +, *, (, )}
N =df {wyr, op_unarny, op_binarny}
P =df { wyr ::= 0 | 1| (wyr op_binarny wyr) | op_unarny wyr
op_binarny ::= + | *
op_unarny ::= @ | #}
S =df wyr
a) Podać przykład wyprowadzenia dowolnego słowa generowanego przez gramatykę G o
długości większej od 2.
b) Stosując zasadę rekursji strukturalnej zdefiniować funkcję left(a), która dla dowolnego
napisu aL(G) określa liczbę lewostronnych nawiasów występujących w napisie a.
8. Przedstawić algorytm, który dla danej formuły rachunku zdań wyznacza spójnik główny, to
znaczy taki, który całą formułę dekomponuje na formuły składowe (jedną, gdy spójnikiem
głównym jest negacja, oraz dwie, gdy spójnikiem głównym jest spójnik binarny).
Wyszukiwarka
Podobne podstrony:
Lista 2012 9
Lista 2012 5
Lista 2012 2
Lista 2012 4
Lista 2012 7
Lista 2012 10
Lista 2012 6
Lista 2012 1
Lista 2012 3
Lista 2012 11
ElsaWin?tabase SEAT 2012 Lista plikow real
DVD 2of2 ElsaWin AUDI 2 2012 Lista plikow real
DVD 2of2 AUDI 2 2012 Lista plikow ogolna
Lista licencji trenerskich nr 20 z dnia 26 07 2012 (2)
DVD 3of3 VW 2 2012 Lista plikow
DVD 1of3 VW 2 2012 Lista plikow
Lista de temas Lektorat I junio y septiembre 2012(1)
DVD 1of2 ElsaWin AUDI 2 2012 Lista plikow real
więcej podobnych podstron