Wyznaczyc APN I KPN - kilka pytań

[itsonlylogic]

1. Jak z tego zrobić KPN? doszedłem do APN ale nie jestem pewny czy w ogóle dobrze to zrobiłem.
\(\displaystyle{ ¬(𝑝→𝑞)→𝑝∨𝑞 \\
¬[¬(𝑝→𝑞)] ∨ p ∨ q\\
𝑝→𝑞 \lor (p ∨ q)\\
¬p \lor q \lor p ∨ q}\)

2. Czy dobrze wyznaczyłem KPN? mam wątpliwości co do fragmentu:
\(\displaystyle{
(p∧¬q) ∨ (𝑞 ∨ ¬p)\\
(p∧¬q) ∨ 𝑞 ∨ ¬p\\
(p ∨ q) ∧ (¬q ∨ q) ∨ ¬p \\
(p ∨ q ∨ ¬p) ∧ (¬q ∨ q ∨ ¬p )}\)

3. W jednym z podręczników widziałem takie zadanie:
\(\displaystyle{ (¬p ∧ ¬q) ∨ (s ∧ p) \\
(¬p \vee s) ∧ (¬p \vee p) ∧ (¬q \vee s) ∧ (¬q \vee p)}\)
Było napisane że jest to podstawienie pod wzór:
\(\displaystyle{ \alpha \vee ( \beta \wedge Y) }\) przekształcamy na \(\displaystyle{ ( \alpha \vee \beta ) \wedge ( \alpha \vee Y)}\)
Mógłby ktoś jakoś bardziej to rozpisać? bo dla mnie zastosowanie powyższego przekształcenia by było jedynie w przypadku:
np.
\(\displaystyle{ (¬p ∧ ¬q) ∨ s }\)
zamieniłbym na:
\(\displaystyle{ (s ∨ ¬p) ∧ (s ∨ ¬q)}\)

[Jan Kraszewski]

1. Jak z tego zrobić KPN? doszedłem do APN ale nie jestem pewny czy w ogóle dobrze to zrobiłem.
\(\displaystyle{ ¬(𝑝→𝑞)→𝑝∨𝑞 \\
¬[¬(𝑝→𝑞)] ∨ p ∨ q\\
𝑝→𝑞 \lor (p ∨ q)\\
¬p \lor q \lor p ∨ q}\)

To jest tautologia. Sprawdź może, jak zapisywaliście APN/KPN tautologii.

2. Czy dobrze wyznaczyłem KPN? mam wątpliwości co do fragmentu:
\(\displaystyle{ (p∧¬q) ∨ 𝑞 ∨ ¬p\\
(p ∨ q) ∧ (¬q ∨ q) ∨ ¬p \\
(p ∨ q ∨ ¬p) ∧ (¬q ∨ q ∨ ¬p )}\)

To też jest tautologia. Uwaga jw.

3. W jednym z podręczników widziałem takie zadanie:
\(\displaystyle{ (¬p ∧ ¬q) ∨ (s ∧ p) \\
(¬p ∧ s) ∧ (¬p ∧ p) ∧ (¬q ∧ s) ∧ (¬q ∧ p)}\)
Było napisane że jest to podstawienie pod wzór:
\(\displaystyle{ \alpha \vee ( \beta \wedge Y) }\) przekształcamy na \(\displaystyle{ ( \alpha \vee \beta ) \wedge ( \alpha \vee Y)}\)

Po prostu trzykrotnie stosujesz wspomnianą rozdzielność alternatywy względem koniunkcji, przy czym za pierwszym razem przyjmujesz \(\displaystyle{ \alpha=(¬p ∧ ¬q)}\).

JK

[itsonlylogic]

1. No właśnie nie wiem jak to zapisać, mieliśmy przykłady w ktorych tak jak w dwójce wychodziło mi po prostu, ze widziałem APN I KPN, wystarczyło oznaczyć jako APN/KPN i tyle. A w jaki sposób Pan by to zapisał? Po prostu dać odpowiedź, że "jest to tautologia rachunku zdań"?? Ewentualnie jak inaczej mogę zapisać KPN tautologii?

2. Czyli jak wyszło mi:
\(\displaystyle{
(p∧¬q) ∨ (𝑞 ∨ ¬p)\\
}\)
To po prostu oznaczam jako APN

\(\displaystyle{ (p ∨ q ∨ ¬p) ∧ (¬q ∨ q ∨ ¬p )}\)
To po prostu oznaczam jako KPN?

Czyli dobrze przekształciłem? Czy po prostu już na etapie APN mogłem oznaczyć:
\(\displaystyle{
(p∧¬q) ∨ (𝑞 ∨ ¬p)\\
}\)
jako APN i dopisać, że jest to tautologia rachunku zdań?
Ale załóżmy gdybym nie zauważył, że jest to tautologia, to mógłbym tak przekształcić? z APN do KPN? Byłoby to poprawne?

PS. No jak sobie rozpisałem w tabelce to teraz widzę. Tak na szybko poznał Pan, ze jest to tautologia po tym że było p v ¬p i to zawsze musi być spełnione, a w drugim ¬q ∨ q też zawsze jest spełnione? No teraz nawet jak już się przyjże temu
\(\displaystyle{
(p∧¬q) ∨ (𝑞 ∨ ¬p)\\
}\)
to też widzę, że to zawsze będzie spełnione i jest to tautologia, ale wcześniej nawet o tym nie myślałem

3.
PS Jakby mógł Pan wyedytować pierwszy POST bo miało być zamiast:

\(\displaystyle{ (¬p ∧ ¬q) ∨ (s ∧ p) \\
(¬p ∧ s) ∧ (¬p ∧ p) ∧ (¬q ∧ s) ∧ (¬q ∧ p)}\)

to:

\(\displaystyle{ (¬p ∧ ¬q) ∨ (s ∧ p) \\
(¬p \vee s) ∧ (¬p \vee p) ∧ (¬q \vee s) ∧ (¬q \vee p)}\)

Ale dokładnie tak miał Pan rację, trzeba było trzy razy ten wzór zastosować, DZIĘKUJE!
Dla potomnych rozpisze:
\(\displaystyle{ (¬p ∧ ¬q) ∨ (s ∧ p) \\
(¬p ∧ ¬q ∨ s) ∧ (¬p ∧¬q ∨ p) \\
(¬p ∨ s) ∧ (¬q ∨ s) ∧ (¬p ∨ p) ∧ (¬q ∨ p)
}\)

[Jan Kraszewski]

1. No właśnie nie wiem jak to zapisać, mieliśmy przykłady w ktorych tak jak w dwójce wychodziło mi po prostu, ze widziałem APN I KPN, wystarczyło oznaczyć jako APN/KPN i tyle. A w jaki sposób Pan by to zapisał? Po prostu dać odpowiedź, że "jest to tautologia rachunku zdań"?? Ewentualnie jak inaczej mogę zapisać KPN tautologii?

Ja bym zapisał np. \(\displaystyle{ p\lor\neg p}\) - to jest zarówno APN, jak i KPN dla dowolnej tautologii.

Kod: Zaznacz cały

https://math.stackexchange.com/questions/64473/what-is-the-conjunction-normal-form-of-a-tautology

jest dyskusja na ten temat.

Stąd moje pytanie - może akurat u Ciebie oznacza się tautologię w specjalny sposób...

2. Czyli jak wyszło mi:
\(\displaystyle{ (p∧¬q) ∨ (𝑞 ∨ ¬p)}\)
To po prostu oznaczam jako APN

Tak, ale raczej bez jednych nawiasów: \(\displaystyle{ (p∧¬q) ∨q ∨ ¬p}\)

\(\displaystyle{ (p ∨ q ∨ ¬p) ∧ (¬q ∨ q ∨ ¬p )}\)
To po prostu oznaczam jako KPN?

Można.

Czyli dobrze przekształciłem? Czy po prostu już na etapie APN mogłem oznaczyć:
\(\displaystyle{
(p∧¬q) ∨ (𝑞 ∨ ¬p)
}\)
jako APN i dopisać, że jest to tautologia rachunku zdań?

To mogłoby być za mało. Spostrzeżenie, że coś jest tautologią, pozwala bez uciążliwego przekształcania użyć od razu postaci \(\displaystyle{ p\lor\neg p}\) jako APN/KPN. Samo w sobie nie stanowi formalnie rzecz biorąc odpowiedzi.

Ale załóżmy gdybym nie zauważył, że jest to tautologia, to mógłbym tak przekształcić? z APN do KPN? Byłoby to poprawne?

Tak.

Tak na szybko poznał Pan, ze jest to tautologia po tym że było \(\displaystyle{ p v ¬p}\) i to zawsze musi być spełnione, a w drugim \(\displaystyle{ ¬q ∨ q}\) też zawsze jest spełnione?

Mniej więcej, tylko ja nie muszę nic rozpisywać - mam trochę doświadczenia i wystarczy mi popatrzeć.

JK