mat ele zombi: Matematyka elementarna, Jan Kraszewski. Rachunek zdań. Definiujemy spójnik | zwany kreską Sheffera następująco: p|q ⇔ ¬p∨¬ q. Uzasadnić, że spójniki ¬,∧,∨,⇒,⇔ są definiowalne przy pomocy tego spójnika. Z idempotentności alternatywy mamy: I^o p ⇔ p∨p, zatem ~p ⇔ ~p∨~p ⇔ p|p. II^o p∧q ⇔ ~(~p∨~q) ⇔ ~(p|q) i tu pytanie czy można to jeszcze rozpisać jako (p|q|) | (p|q)? III^o p∨q ⇔ (~p|~q) i znowu czy można to doprowadzić do postaci (p|p)|(q|q) ? IV^o p⇒q ⇔ ~p∨q ⇔ (p|~q) i dalej p|(q|q) ? "⇔" już sobie sam zrobię.

Saizou : zombi widzę że już do studiów ćwiczysz xd

zombi: Szkoda zmarnować 4 miechy wakacji

Saizou : ale trochę wakacji się należy xd

zombi: Spoko, robię sobie przerwy wychodzę na zewnątrz, więc jeszcze źle nie jest.

Saizou : jeszcze czyli mamy apokalipsę zombi od października na studiach xd

zombi: Pewnie tak Trochę żałuje, że nie poszło lepiej z maturki, ale ta maturka na studiach ważna przez pierwszy tydzień. A gdzie zamierzasz iść PWr?

zawodus: Jak ja nie lubię logiki

Maslanek: Jeżeli masz zdefiniować innych spójniki przy użyciu pewnych określonych, to tylko i wyłącznie one mogą znaleźć się w definicji. Stąd p⋀q ⇔~(p|q) jest złą definicją. W koncu nie znamy czegoś takiego jak "~" Ale p⋀q ⇔(p|q) | (p|q) jest dobrą definicją.

zombi: No właśnie, bo w odpowiedziach, zostało ~(p|q), więc coś mi nie pasowało.

Maslanek: Chyba, że korzystamy z definicji wcześniejszych. Wtedy "~" byłaby już znana Ale generalnie myślę, że zapis ~(p|q) jest nie taki jak trzeba

zombi: No okej spoko, czyli rozwalić w drobny mak trzeba. Dzięki. Jak coś będę jeszcze wrzucał, bo jest tutaj parę mocniejszych.

Saizou : Zombi jeszcze do końca nie wiem, muszę wybrać Pozek czy Wrocek

zombi: Ja zdecydowałem się w końcu, UWr na 100%

zombi: Mam kolejne, nie jest trudne, ale chodzi mi o zapis, żeby był formalny: □ − alternatywa wykluczająca, zdefiniowana tak, że: p□q ⇔ (~p∧q) ∨ (p∧~q). Pokaż, żę p□p jest tautologią ~(p□p) ⇔ ~[(~p∧p)∨(p∧~p)] ⇔ ~(~p∧p)∧~(~p∧p) ⇔ ~(~p∧p) <− prawo sprzeczności, które jest tautologią, zatem również ~(p□p) jest tautologią tak?

zombi: Pokaż, że ~(p□p) jest tautologią*

Trivial: zombi, po co Ci logika, przejdź od razu do teorii typów, teorii dowodu i teorii kategorii.

Trivial: A z tego co widzę, to kreska Shaffera to zwykły NAND. a NAND b = NOT (a AND b)

zombi: Noo, zwyczajna negacja koniunkcji z prawa de Morgana pyka. Wolę przerobić wszystko Trivial bo logikę ostatnio miałem w pierwszej klasie.

Trivial: A odnośnie tematu, to skoro zdefiniowałeś ~x jako operację korzystającą tylko z | to nie widzę powodu czemu nie miałbyś jej używać w kolejnych definicjach. Rozpisana forma jest dużo bardziej zawiła.

Trivial: W klasycznej logice: ~a⋀a = 0 zatem: ~(p□p) ⇔ ~[(~p∧p)∨(p∧~p)] ⇔ ~[0∨0] ⇔ 1

zombi: Tak, też chciałem, ale nie widziałem czy mogę zapisać. Rozwiałeś wątpliwości, dzięki.

zombi: Pomógłbyś mi jeszcze to zrozumieć? "Uzasadnić, że implikacja nie jest definiowalna przez alternatywę i koniunkcję" Odp. Wynika to z symetrii alternatywy i koniunkcji. O co chodzi z tą symetrią?

fx: Co oznacza, że działanie jest symetryczne i dlaczego implikacja nie jest symetryczna? Co do odpowiedzi do tego podręcznika. Polecam zapoznać się z obszerną erratą dostępną na stronie autora. Sporo różnych błędów się wkradło w treści, przykładach i odpowiedziach.

Trivial: To wcale nie wynika z samej symetrii. NAND jest również symetryczny, a pozwala zdefiniować dowolną funkcję logiczną. Potrzebny jest inny dowód.

Trivial: fx, pewnie chodzi o a♦b = b♦a. Z kolei a⇒b ≠ b⇒a.

zombi: No właśnie tak rozkminiałem, że możesz rozpisać implikację, dostaniesz ∨ albo ∧ a one są przemienne i dostaniesz z powrotem inną implikację np. w drugą stronę, która zajść nie musi.

Trivial: Mam inny dowód (nie wprost). Oznaczenia: * oznacza ⋀ + oznacza ∨ Załóżmy, że da się zdefiniować a⇒b za pomocą: 0, 1, *, +, a, b. Wtedy da się również zdefiniować zaprzeczenie jako ~a = a⇒0. Ale zdefiniowanie zaprzeczenia jest niemożliwe, gdyż istnieją jedynie 3 funkcje logiczne zbudowane za pomocą 0, 1, *, +, a. Są to: φ(a) = 0, φ(a) = 1, φ(a) = a. Dowód (indukcyjny). Zdefiniujemy funkcję redukcji każdej możliwej funkcji logicznej zbudowanej przy pomocy 0, 1, *, +, a. Analiza strukturalna wszystkich wyrażeń logicznych: reduce 0 = 0 reduce 1 = 1 reduce a = a reduce (0 + x) = reduce x reduce (1 + x) = 1 reduce (a + a) = a reduce (a + x) = reduce ((reduce x) + a) reduce (0 * x) = 0 reduce (1 * x) = reduce x reduce (a * a) = a reduce (a * x) = reduce ((reduce x) * a) gdzie x oznacza dowolne podwyrażenie.

Trivial: Jak widać funkcja reduce ma 3 możliwości: 0, 1, a. Ponadto nigdy nie wpada w nieskończoną pętlę, zatem jest dowodem i jednocześnie formalnym sposobem uproszczania tego typu wyrażeń.

zombi: Kurde, to dla mnie za wysokie progi chyba

Trivial: Mam mały błąd. Wersja poprawiona: reduce 0 = 0 reduce 1 = 1 reduce a = a reduce (0 + x) = reduce x reduce (1 + x) = 1 reduce (a + a) = a reduce (x + y) = reduce ((reduce y) + (reduce x)) −− symetria reduce (0 * x) = 0 reduce (1 * x) = reduce x reduce (a * a) = a reduce (x * y) = reduce ((reduce y) * (reduce x)) −− symetria Przykład redukcji − bezmyślne stosowanie reguł (od góry do dołu próbujemy dopasować działającą regułę; R = reduce). R ((a*(1+0)) + (a*1)) = R ((R (a*1)) + (R (a*(1+0)))) = R ((R ((R 1) * (R a))) + (R (a*(1+0)))) = R ((R (1 * (R a))) + (R (a*(1+0)))) = R ((R (R a)) + (R (a*(1+0)))) = R ((R a) + (R (a*(1+0)))) = R (a + (R (a*(1+0)))) = R (a + (R ((R (1+0)) * (R a)))) = R (a + (R (1 * (R a)))) = R (a + (R (R a))) = R (a + (R a)) = R (a + a) = a Taka super formalna definicja umożliwia wykonanie tego przez komputer.

zombi: A jakoś bardziej po ludzku, nie komputerowo? Jak to krótko pokazać?

Trivial: Co Ci się nie podoba w moim dowodzie indukcyjnym? Nie jest jakiś długi.

zombi: Z nim wszystko okej, tylko czy tego nie da się krócej? Bo w erracie do tej książki nie ma poprawki, jeśli chodzi o odpowiedź "wynika to z symetrii koniunkcji i alternatywy". Czyli, że ona jest ok?

Trivial: Ale o co chodzi autorowi książki z tą symetrią? Zwykle symetria funkcji oznacza f(a,b) = f(b,a) a♦b = b♦a. Pokazałem już wcześniej że to nie wystarcza, bo NAND jest również symetryczny, a pozwala na definicję dowolnej funkcji logicznej.