Zapisz negację/doprowadź do najprostszej postaci.

[Tomek496]

Mam problem z wykonaniem tych zadań.
Zapisz negację poniższych zdań
1. (\(\displaystyle{ q⇒r\land p) \lor ∼r}\)
2. \(\displaystyle{ ∼(p\lor r)⇒(q⇒p)}\)
3. \(\displaystyle{ p⇒(q⇒r)}\)
Doprowadź do najprostszej postaci:
1. \(\displaystyle{ (p\land q) \lor∼(∼p⇒q)}\)
2. \(\displaystyle{ (p\lor q) \lor∼(∼p⇒q)}\)
3. \(\displaystyle{ (p⇒((∼p\lor q)⇒p))\land q}\)

[Jan Kraszewski]

A na czym ten problem polega?

JK

[Tomek496]

Miałem pokazaną metodę 0-1 i tylko tyle a potem w zbiorze to zadanie i nie wiem jak się za niego zabrać
np. negacja z 3-ego przykładu: \(\displaystyle{ p→q}\) jest równoważne zapisowi \(\displaystyle{ \sim p\lor q}\), a potem korzystam z praw de morgana?

[Jan Kraszewski]

Tak, korzystasz z prawa negacji implikacji (lub z prawa eliminacji implikacji), prawa podwójnej negacji i z praw de Morgana.

I używaj \(\LaTeX\)-a, bo w końcu przestanę po Tobie poprawiać i zacznę wyrzucać posty do Kosza.

JK

[rafal3006]

Chciałbym zaprezentować minimalizację dowolnej funkcji logicznej \(\displaystyle{ Y}\) przy wykorzystaniu logiki dodatniej (bo \(\displaystyle{ Y}\)) i ujemnej (bo \(\displaystyle{ \neg Y}\)).

Skrócony algorytm przejścia z logiki dodatniej (bo \(\displaystyle{ Y}\)) to ujemnej (bo \(\displaystyle{ \neg Y}\)) (albo odwrotnie) to:
1.
Uzupełniamy brakujące nawiasy
2.
Negujemy zmienne i wymieniamy spójniki na przeciwne

Mnożenie wielomianów logicznych jest identyczne jak mnożenie wielomianów arytmetycznych, tak więc z tym nie powinno być kłopotu.

Każdą nową metodę minimalizacji funkcji logicznej najlepiej zaprezentować na konkretnym przykładzie co niniejszym czynię - w razie jakichkolwiek wątpliwości proszę o pytania.

W poniższej minimalizacji korzystam z definicji znaczka \(\displaystyle{ \Rightarrow }\):
\(\displaystyle{ p \Rightarrow q \Leftrightarrow \neg p \vee q}\)

Przykład zaczerpnięty z tytułowego postu to:

Doprowadź do najprostszej postaci:
\(\displaystyle{ (q \Rightarrow r \wedge p) \vee \neg r}\)

Rozwiazanie:
Zapiszmy nasze wyrażenie w postaci funkcji logicznej \(\displaystyle{ Y}\):
\(\displaystyle{ Y \Leftrightarrow (q \Rightarrow r \wedge p) \vee \neg r = \neg q \vee r \wedge p \vee \neg r}\)
Uzupełniamy brakujące nawiasy bo kolejność wykonywania działań w logice to:
nawiasy, \(\displaystyle{ \wedge }\), \(\displaystyle{ \vee }\)
\(\displaystyle{ Y \Leftrightarrow \neg q \vee (r \wedge p) \vee \neg r}\)
Wydzielmy funkcję cząstkową \(\displaystyle{ Y1}\):
\(\displaystyle{ Y1 \Leftrightarrow (r \wedge p) \vee \neg r}\)
Przejście do logiki ujemnej (bo \(\displaystyle{ \neg Y1}\)) poprzez negację zmiennych i wymianę spójników
\(\displaystyle{ \neg Y1 \Leftrightarrow ( \neg r \vee \neg p) \wedge r}\)
Po wymnożeniu wielomianu logicznego mamy:
\(\displaystyle{ \neg Y1 \Leftrightarrow \neg r \wedge r \vee r \wedge \neg p}\)
\(\displaystyle{ \neg Y1 \Leftrightarrow r \vee \neg p}\)
Powrót do logiki dodatniej (bo \(\displaystyle{ Y1}\)) poprzez negację zmiennych i wymianę spójników:
\(\displaystyle{ Y1 \Leftrightarrow \neg r \wedge p}\)
Odtwarzając podstawienie mamy:
\(\displaystyle{ Y \Leftrightarrow \neg q \vee \neg r \wedge p}\)
Stąd w zapisie \(\displaystyle{ p \Rightarrow q}\):
\(\displaystyle{ Y \Leftrightarrow q \Rightarrow ( \neg r \wedge p)}\)

[Jan Kraszewski]

Uzupełniamy brakujące nawiasy bo kolejność wykonywania działań w logice to:
nawiasy, \(\displaystyle{ \wedge }\), \(\displaystyle{ \vee }\)

Nieprawda. Według standardowej konwencji spójniki \(\displaystyle{ \wedge }\), \(\displaystyle{ \vee }\) są równorzędne, więc Twoje zapisy są niepoprawne formalnie.

Odtwarzając podstawienie mamy:
\(\displaystyle{ Y \Leftrightarrow \neg q \vee \neg r \wedge p}\)
Stąd w zapisie \(\displaystyle{ p \Rightarrow q}\):
\(\displaystyle{ Y \Leftrightarrow q \Rightarrow ( \neg r \wedge p)}\)

Nieprawda, to jest zła odpowiedź.

Lepiej nie wprowadzaj zamieszania, proponując błędne rozwiązanie.

JK

[rafal3006]

\(\displaystyle{ \begin{array}{ccccccccc}
q&r&p& \neg q& \neg r& \neg p&r \wedge p&q \Rightarrow r \wedge p&(q \Rightarrow r \wedge p) \vee \neg r&q& \neg r \vee p&q \Rightarrow ( \neg r \vee p)\\
1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\
1 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 1 & 1 \\
0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \\
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 \\
0 & 0 & 1 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \\
0 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 0 & 1 & 1 \\
A & B & C & D & E & F & G & H & I & J & K & L \\
\end{array}}\)

Przepraszam bardzo, ale tożsamość kolumn zero-jedynkowych:
\(\displaystyle{ I = L}\)
Jest dowodem zachodzącego tu prawa rachunku zero-jedynkowego:
\(\displaystyle{ (q \Rightarrow r \wedge p) \vee \neg r \Leftrightarrow q \Rightarrow ( \neg r \vee p)}\)
cnd

Zatem:
W którym miejscu w rachunku zero-jedynkowym popełniam błąd?

EDIT!
Dodano po 43 minutach 42 sekundach:
Bardzo wszystkich przepraszam za literówkę zrobioną w tym poście:
viewtopic.php?p=5589298#p5589298

Niniejszym koryguję ewidentną literówkę, z poprawnym rozwiązaniem końcowym:

Chciałbym zaprezentować minimalizację dowolnej funkcji logicznej \(\displaystyle{ Y}\) przy wykorzystaniu logiki dodatniej (bo \(\displaystyle{ Y}\)) i ujemnej (bo \(\displaystyle{ \neg Y}\)).

Skrócony algorytm przejścia z logiki dodatniej (bo \(\displaystyle{ Y}\)) to ujemnej (bo \(\displaystyle{ \neg Y}\)) (albo odwrotnie) to:
1.
Uzupełniamy brakujące nawiasy
2.
Negujemy zmienne i wymieniamy spójniki na przeciwne

Mnożenie wielomianów logicznych jest identyczne jak mnożenie wielomianów arytmetycznych, tak więc z tym nie powinno być kłopotu.

Każdą nową metodę minimalizacji funkcji logicznej najlepiej zaprezentować na konkretnym przykładzie co niniejszym czynię - w razie jakichkolwiek wątpliwości proszę o pytania.

W poniższej minimalizacji korzystam z definicji znaczka \(\displaystyle{ \Rightarrow }\):
\(\displaystyle{ p \Rightarrow q \Leftrightarrow \neg p \vee q}\)

Przykład zaczerpnięty z tytułowego postu to:

Doprowadź do najprostszej postaci:
\(\displaystyle{ (q \Rightarrow r \wedge p) \vee \neg r}\)

Rozwiazanie:
Zapiszmy nasze wyrażenie w postaci funkcji logicznej \(\displaystyle{ Y}\):
\(\displaystyle{ Y \Leftrightarrow (q \Rightarrow r \wedge p) \vee \neg r = \neg q \vee r \wedge p \vee \neg r}\)
Uzupełniamy brakujące nawiasy bo kolejność wykonywania działań w logice to:
nawiasy, \(\displaystyle{ \wedge }\), \(\displaystyle{ \vee }\)
\(\displaystyle{ Y \Leftrightarrow \neg q \vee (r \wedge p) \vee \neg r}\)
Wydzielmy funkcję cząstkową \(\displaystyle{ Y1}\):
\(\displaystyle{ Y1 \Leftrightarrow (r \wedge p) \vee \neg r}\)
Przejście do logiki ujemnej (bo \(\displaystyle{ \neg Y1}\)) poprzez negację zmiennych i wymianę spójników
\(\displaystyle{ \neg Y1 \Leftrightarrow ( \neg r \vee \neg p) \wedge r}\)
Po wymnożeniu wielomianu logicznego mamy:
\(\displaystyle{ \neg Y1 \Leftrightarrow \neg r \wedge r \vee r \wedge \neg p}\)
Poniżej jest ewidentna literówka!
\(\displaystyle{ \neg Y1 \Leftrightarrow r \vee \neg p}\)
Powrót do logiki dodatniej (bo \(\displaystyle{ Y1}\)) poprzez negację zmiennych i wymianę spójników:
\(\displaystyle{ Y1 \Leftrightarrow \neg r \wedge p}\)
Odtwarzając podstawienie mamy:
\(\displaystyle{ Y \Leftrightarrow \neg q \vee \neg r \wedge p}\)
Stąd w zapisie \(\displaystyle{ p \Rightarrow q}\):
\(\displaystyle{ Y \Leftrightarrow q \Rightarrow ( \neg r \wedge p)}\)

Poprawna końcówka mojego postu jest taka:
\(\displaystyle{ \neg Y1 \Leftrightarrow r \wedge \neg p}\)
Powrót do logiki dodatniej (bo \(\displaystyle{ Y1}\)) poprzez negację zmiennych i wymianę spójników:
\(\displaystyle{ Y1 \Leftrightarrow \neg r \vee p}\)
Odtwarzając podstawienie mamy:
\(\displaystyle{ Y \Leftrightarrow \neg q \vee \neg r \vee p}\)
Stąd w zapisie \(\displaystyle{ p \Rightarrow q}\):
\(\displaystyle{ Y \Leftrightarrow q \Rightarrow ( \neg r \vee p)}\)

Dodano po 48 minutach 34 sekundach:

Uzupełniamy brakujące nawiasy bo kolejność wykonywania działań w logice to:
nawiasy, \(\displaystyle{ \wedge }\), \(\displaystyle{ \vee }\)

Nieprawda. Według standardowej konwencji spójniki \(\displaystyle{ \wedge }\), \(\displaystyle{ \vee }\) są równorzędne, więc Twoje zapisy są niepoprawne formalnie.

Proszę spojrzeć na takie zdanie:
Jutro pójdziemy do parku lub do kina i do teatru
\(\displaystyle{ Y \Leftrightarrow P \vee K \wedge T}\)
Kodowanie tożsame:
\(\displaystyle{ Y \Leftrightarrow P \vee (K \wedge T)}\)
Kodowanie matematycznie błędne:
\(\displaystyle{ Y \Leftrightarrow (P \vee K) \wedge T}\)
Ewidentnie zachodzi tu kolejność wykonywania działań:
nawiasy, \(\displaystyle{ \wedge}\), \(\displaystyle{ \vee}\)

[Jan Kraszewski]

Proszę spojrzeć na takie zdanie:
Jutro pójdziemy do parku lub do kina i do teatru
\(\displaystyle{ Y \Leftrightarrow P \vee K \wedge T}\)
Kodowanie tożsame:
\(\displaystyle{ Y \Leftrightarrow P \vee (K \wedge T)}\)
Kodowanie matematycznie błędne:
\(\displaystyle{ Y \Leftrightarrow (P \vee K) \wedge T}\)
Ewidentnie zachodzi tu kolejność wykonywania działań:
nawiasy, \(\displaystyle{ \wedge}\), \(\displaystyle{ \vee}\)

Nieprawda. Uparcie piszesz nieprawdziwe stwierdzenia. W zapisie formalnym w ogóle każde użycie spójnika wymaga zastosowania nawiasów. Żeby napis nie był nieczytelny, stosuje się pewne konwencje upraszczające zapis i taką powszechnie używaną w matematyce konwencją jest ta, w której najwyższy priorytet ma negacja, potem równorzędnie alternatywa i koniunkcja, a na końcu równorzędnie implikacja i równoważność. A Twoje "kodowania" to wytwór Twojej pomysłowości. Oczywiście, każdy może używać na własny użytek takiej notacji, na jaką ma ochotę. Nie powinieneś jednak wprowadzać innych użytkowników w błąd twierdząc, że jest to metoda powszechnie stosowana oraz wygłaszać nieprawdziwych stwierdzeń na temat poprawności bądź błędności pewnych zapisów, bo potem ktoś Cię zacytuje i będzie miał problemy.

A podawanie przykładów z języka potocznego jako uzasadnienia prawdziwości swoich wywodów dotyczących logiki formalnej jest dość niepoważne.

JK

[rafal3006]

Weźmy funkcję alternatywno-koniunkcyjną:
\(\displaystyle{ Y = p \wedge q \vee \neg p \wedge r}\)
Proszę zauważyć, że tu nie mamy wyboru, nie możemy sobie postawić nawiasów jak nam się podoba.
Jedyne poprawne wstawienie nawiasów do powyższej funkcji logicznej to:
\(\displaystyle{ Y = (p \wedge q) \vee (\neg p \wedge r)}\)
Każde inne wstawienie nawiasów jest tu błędem czysto matematycznym!
Stąd mamy znowu.
Kolejność wykonywania działań w logice matematycznej to:
nawiasy \(\displaystyle{ \wedge , \vee }\)
cnd

Na koniec proszę zauważyć, że wyłącznie przy powyższej kolejności wykonywania działań banalna metoda minimalizacji funkcji logicznej z użyciem logiki dodatniej (bo \(\displaystyle{ Y}\)) i ujemnej (bo \(\displaystyle{ \neg Y}\)) opisana w tym poście:
viewtopic.php?p=5589305#p5589305
działa fenomenalnie.

[Jan Kraszewski]

Weźmy funkcję alternatywno-koniunkcyjną:
\(\displaystyle{ Y = p \wedge q \vee \neg p \wedge r}\)
Proszę zauważyć, że tu nie mamy wyboru, nie możemy sobie postawić nawiasów jak nam się podoba.

To nie jest postać alternatywno-koniunkcyjna, tylko niepoprawny zapis.

Jedyne poprawne wstawienie nawiasów do powyższej funkcji logicznej to:
\(\displaystyle{ Y = (p \wedge q) \vee (\neg p \wedge r)}\)
Każde inne wstawienie nawiasów jest tu błędem czysto matematycznym!
Stąd mamy znowu.
Kolejność wykonywania działań w logice matematycznej to:
nawiasy \(\displaystyle{ \wedge , \vee }\)
cnd

Przykro mi, ale to bzdura.

Temat zamykam.

JK