LOGIKA KOKSY.

Każdy kto wejdzie na tą stronę, wisi autorowi CZTEROPAK BROWARU. Może być puszka, wtedy zasilicie PROJEKT PUSZKA.

Które ze zdefiniowanych relacji są relacjami równoważności?

  1. X - zbiór osób zdających egzamin, o1, o2 należą do X
    o1 R o2 <=> o2 siedzi po prawej stronie o1
  2. X - zbiór samochodów na parkingu, s1, s2 należą do X
    s1 R s2 <=> s1 przejechał co najmniej tyle km co s2
  3. X - zbiór wszystkich krzeseł w sali, k1, k2 należą do X
    k1 R k2 <=> gdy oba krzesła są zajęte lub oba krzesła są wolne
  4. X - zbiór funkcji zmiennej x, f1, f2 należą do X
    f1 R f2 <=> dla każdego x zachodzi: f1(x) = f2(x)

Relacja jest relacją równoważności <=> jest zwrotna, symetryczna i przechodnia.

A-fałsz (nie jest chociażby symetryczna, bo jeśli o2 siedzi po prawej od o1, to o1 nie może siedzieć po prawej od o2)
B-fałsz (z podobnego powodu. Jeśli s1 przejechał co najmniej tyle co s2, to relacja w drugą stronę zachodzi tylko wtedy, gdy przejechali równą trasę)
C-prawda (relacja jest zwrotna, symetryczna i przechodnia, czego chyba nie trzeba udowadniać)
D-prawda (oczywiście zwrotna, bo f1(x)=f1(x). Symetryczna, bo jeśli f1(x)=f2(x), to f2(x)=f1(x) i przechodnia, bo jeśli f1(x)=f2(x) i f2(x)=f3(x), to f1(x)=f3(x).

Dana jest gramatyka G opisana za pomocą notacji BNF (symbole terminalne są ujęte w apostrofy, R jest symbolem początkowym gramatyki):

R ::= X '-' R | X '+' R | X
X ::= LX | L
L ::= '0'|'1'|...|'9'

Które z poniższych słów należą do języka L(G):

  1. +012
  2. 0-1+0
  3. 1++1
  4. -1+0-1

Trzeba sprawdzić, czy da się wyprowadzić dane słowo w gramatyce.

A-fałsz (z symbolu początkowego R możemy stworzyć tylko słowo zaczynające się od liczby)
B-prawda (R-> X-R -> L-R -> 0-R -> 0-X+R -> 0-L+R -> 0-1+R -> 0-1+X -> 0-1+L -> 0-1+0)
C-fałsz (nie da się wyprowadzić dwóch plusów koło siebie, z wyprowadzenia R::=X+R wynika, że przed i po plusie musi być liczba.)
D-fałsz (z tego samego powodu co w A)

Niech relacje R1, R2 będą relacjami równoważności na zbiorze X. Wówczas relacjami równoważności są również relacje

  1. R1 n R2 (iloczyn R1 i R2)
  2. R1 - R2
  3. (R1 n R2) u R2
  4. (X2 - R1) n R2

A-prawda (jeśli mamy relację równoważności, to biorą z niej połączenia, które spełniają inną zasadę równoważności będziemy nadal mieć zawsze równoważność)
B-fałsz (jeśli z relacji równoważności wytniemy połączenia, które są inną relacja równoważności, to pozbędziemy się zwrotności, czyli relacja przestanie być równoważnością)
C-prawda ( bo (R1nR2)uR2 jest relacją R2, która jest równoważnością.
D-fałsz(ponownie nie będzie zwrotności w relacji (zostaje ucięta po odjęciu z X2\R1))

Niech A =df= {a, b}, B =df= {b, c}. Prawdą jest, że

  1. card(2^(A u B)) = 2^3
  2. (A\B) u B = {a, b, c}
  3. 2^A n 2^B = 2^(A n B)
  4. { null, a, {b}} zawiera się w 2^a

PODPOWIEDZ

A-prawda (bo card(2A)=2card(A))
B-prawda (bo (A\B)uB=AuB)
C-prawda (z prostych przekształceń - 2A={Ø,{a},{b},{a,b}}, 2B={ Ø,{b},{c},{b,c}}, AnB={b},2AnB={ Ø,{b}})
D-fałsz (zbiór potęgowy zawiera zbiory, więc nie ma elementu a.

Relacja binarna R zawiera się w 2^Nat x 2^Nat jest zdef następująco: <A,B> należy do R <=> A zawiera się w B. Wskaż które z własności posiada relacja R:

  1. R zwrotna
  2. R antysymetryczna
  3. R spójna

PODPOWIEDZ

A-prawda (bo A=A)
B-fałsz (bo gdy A=B to relacja jest symetryczna)
C-fałsz(nie ma połączenia między każdą parą zbiorów)

Niech formuły a i b będą tautologiami rachunku kwantyfikatorów. Które z poniższych formuł również są taut. rach. kw.

  1. nie a i nie b
  2. nie a lub b
  3. a <=> b
  4. a => b

A-fałsz(ani ~A ani ~B nie są tautologiami)
B-prawda (B jest tautologią, więc alternatywa jest prawdziwa)
C-prawda (bo po obu stronach mamy zawsze prawdę)
D-prawda (z prawdy wynika prawda)

Wskazać wyrażenia, które są tautologiami

  1. p=>q <=> ((nie p) i q)
  2. (p lub q) => p
  3. (p v q v r) => (nie p => ((qvr) i (nie p)))

A-prawda (chyba nie trzeba tłumaczyć)
B-fałsz (np. dla p=0 i q=1 mamy z prawdy wynika fałsz, czyli fałsz)
C-prawda(zakładamy, że następnik jest fałszywy, więc ~p=1 i (qvr)^~p=1, czyli mamy wartościowanie krytyczne p=0, q=0 i r=0. Dla tego wartościowania poprzednik nie może być 1, więc jest to tautologia.

PYTANIE

  1. AAAAAAAAAAAAAAAAAAAA
  2. BBBBBBBBBBBBBBBBB
  3. CCCCCCCCCCCCCCCCCC
  4. DDDDDDDDDDDDDDDDDD

A^(BvA) =A^BvA=A(Bv1)=A

A-fałsz, ponieważ dla B=0 i A=1 mamy również prawdę.
B-fałsz, bo A musi być prawdziwe
C-prawda(jak wyżej)
D-prawda(bo A jest prawdziwe)

Poniższe drzewo ilustruje zastosowanie rachunku sekwentów do spr... Zakładając że poprz. węzeł jest popr okresl czy poprawnie wyprowadzono węzeł

  1. 2
  2. 3
  3. 4
  4. 5

A-fałsz – złe zastosowanie implikacji (powinno być ~(A^B)v(AvB)
B-prawda – w następniku sekwensu spójnik lub zamieniamy na przecinek
C-prawda – usunięcie negacji w następniku
D-fałsz, w poprzedniku sekwensu spójnik lub nie zamienia się na przecinek, tylko rozbija na 2 warunki

Zakładając, że x, y, z ...

  1. AAAAAAAAAAAAAAA
  2. BBBBBBBBBBBBBBBBB
  3. CCCCCCCCCCCCCCCCCC
  4. DDDDDDDDDDDDDDDDDD

A-prawda
B-fałsz – y jest zmienną wolną
C-prawda
D-fałsz – w drugim nawiasie są zmienne wolne

Zakładając, że P, Q są predykatami, x = zmienną indywidualną wskaż, które z poniższych form zdaniowych są tauto

  1. dla każdego x P(x) => istnieje x taki że nie P(x)
  2. dla każdego x P(x) => istnieje x taki że nie P(x) => dużo tekstu
  3. Ax | P(x) <=>Q(x) => Ax | P(x) <=> Ax | Q(x)

PODPOWIEDZ

A-fałsz (jeśli dla każdego x P(x) to nie może istnieć x, takie, że ~P(x)
B-prawda (implikacja w poprzedniku implikacji głównej jest fałszem (co jest pokazane w p. A), więc cała implikacja zawsze będzie prawdziwa.
C-prawda (z własności działań na kwantyfikatorach)

PYTANIE

  1. AAAAAAAAAAAAAAAAAAAA
  2. BBBBBBBBBBBBBBBBB
  3. CCCCCCCCCCCCCCCCCC
  4. DDDDDDDDDDDDDDDDDD

PODPOWIEDZ

Tego zadania do końca nie zrozumiałem, więc to może być jedno z tych co miałem źle. Sprawdzałem czy dla wartościowania x=a i y=a formuła w poleceniu jest spełniona, ale czy o to chodziło to nie wiem… A-fałsz B-fałsz C-prawda

PYTANIE

  1. AAAAAAAAAAAAAAAAAAAA
  2. BBBBBBBBBBBBBBBBB
  3. CCCCCCCCCCCCCCCCCC
  4. DDDDDDDDDDDDDDDDDD

PODPOWIEDZ

Co do podpunktów B,C,D: pytanie jest czy można już stwierdzić, że formuła jest tautologią. To pytanie wydaje mi się nieprecyzyjne, tzn. czy chodzi o to czy już w danym momencie wszystkie gałęzie powinny być aksjomatami, czy chodzi o to, że widać już, że jakieś drobne przekształcenia wystarczą. Ja przyjąłem 2 sposób, ale nie wiem czy to było dobre wyjście) A-prawda (np. liść nr 2 lub 4 są aksjomatami (czyli to samo wyrażenie występuje po prawej i po lewej) B-fałsz(bo formuła nie jest tautologią – 3 liść jest fałszem) C-fałsz (zgodnie z uwagą) D-fałsz (bo wg mnie można to stwierdzić

PYTANIE

  1. AAAAAAAAAAAAAAAAAAAA
  2. BBBBBBBBBBBBBBBBB
  3. CCCCCCCCCCCCCCCCCC
  4. DDDDDDDDDDDDDDDDDD

PODPOWIEDZ

A-fałsz (z jednej strony na druga można przenieść formułę, negując ją. Tutaj nie jest to negacja) B-prawda (bo można Zamienic w następniku sekwensu v na ,) C- fałsz (coś źle z negacjami) D-prawda (przecinki zamiast lub w następniku)

PYTANIE

  1. AAAAAAAAAAAAAAAAAAAA
  2. BBBBBBBBBBBBBBBBB
  3. CCCCCCCCCCCCCCCCCC
  4. DDDDDDDDDDDDDDDDDD

PODPOWIEDZ

A-fałsz – nie można włączyć B(y,z) pod kwantyfikator szczegółowy y, ponieważ związalibyśmy y w B) B-prawda – zmiana nazwy zmiennej x w każdym miejscu i wciągnięcie pod kwantyfikator predykatu, w którym są tylko zmienne SA niezależne od kwantyfikatora C-fałsz – znów wykonując ta operację związujemy zmienną w predykacie D-fałsz – nie znam takich praw, które pozwoliły by tak zrobić.

PYTANIE

  1. AAAAAAAAAAAAAAAAAAAA
  2. BBBBBBBBBBBBBBBBB
  3. CCCCCCCCCCCCCCCCCC
  4. DDDDDDDDDDDDDDDDDD

PODPOWIEDZ

A-fałsz – wiązanie zmiennej B-fałsz – złe zastosowanie metody na pozbycie się kwantyfikatora szczegółowego, gdy stoi na początku zmieniamy zmienną na stałą C-prawda – dla dowolnego z istnieje y, także można zamienić zmienną y funkcją od z D-fałsz – zmieniła się funkcja, a tak chyba nie można

PYTANIE

  1. AAAAAAAAAAAAAAAAAAAA
  2. BBBBBBBBBBBBBBBBB
  3. CCCCCCCCCCCCCCCCCC
  4. DDDDDDDDDDDDDDDDDD

PODPOWIEDZ

A-fałsz – X,Y-> nie jest równoważne X=>y-> B-fałsz – przy X nie może w ten sposób pojawić się negacja, gdy ten pozostaje w następniku C-prawda – X i Y zostały przeniesione z zanegowaniem. Wszystko ok. D-fałsz – takie przejście byśmy mogli zrobić, gdyby nad kreska było …->~X^~Y,…, a mamy X,Y (czyli X v Y)

PYTANIE

  1. AAAAAAAAAAAAAAAAAAAA
  2. BBBBBBBBBBBBBBBBB
  3. CCCCCCCCCCCCCCCCCC
  4. DDDDDDDDDDDDDDDDDD

PODPOWIEDZ

Najbardziej ogólny unifikator pozwala pod zmienną podstawić określoną wartość, tak aby obie klauzule były identyczne. Więc w tym przypadku:
A-fałsz
B-fałsz
C-prawda
D-fałsz

PYTANIE

  1. AAAAAAAAAAAAAAAAAAAA
  2. BBBBBBBBBBBBBBBBB
  3. CCCCCCCCCCCCCCCCCC
  4. DDDDDDDDDDDDDDDDDD

PODPOWIEDZ

A-prawda ( z klauzul ~rvq i pvr)
B-prawda (z klauzul ~pvq i pvr tworzymy klauzule qvr i łączymy ją z klauzulą ~rvq i otrzymujemy q)
C-fałsz (w żaden sposób nie uzyskamy ~q, bo nie występuje w żadnej klauzuli)
D-prawda – bo to jest to samo co w A

TEST II – to ten co ja rozwiązywałem na egzaminie

PYTANIE

  1. AAAAAAAAAAAAAAAAAAAA
  2. BBBBBBBBBBBBBBBBB
  3. CCCCCCCCCCCCCCCCCC
  4. DDDDDDDDDDDDDDDDDD

PODPOWIEDZ

A-prawda (bo zwrotna, symetryczna i przechodnia) B-fałsz (nie jest przechodnia, np. dla k=10001 gdy samochód s1 kosztuje 10000, s2 20000 (czyli s1Rs2 zachodzi), i s3 kosztuje 30000 (czyli s2Rs3), to różnica cen s1 i s3 = 20000, czyli nie ma s1Rs3) C-fałsz (nie ejst przechodnia, wytłumaczenie podobne jak w B) D-fałsz – nie jest przechodnia – to że f1 i f2 maja punkt wspólny i f2 i f3 maja punkt wspólny, wcale nie znaczy że f1 i f3 takowy mają