forum.zadania.info

Witam. Mam problem z dwoma zadaniami. Prosiłbym o jakieś wskazówki, które doprowadzą mnie do rozwiązania.
1. Ile jest spójników dwuargumentowych "*" takich, że formuła zdaniowa jest tautologią:
a) (p*r)*(p*r)
b) (p*p)*(r*r)
2. Zaznacz na płaszczyźnie zbiór \(D = \left\{ (x,y) \in R^2 : [(x^2 + y^2 =4) \So y>1 \wedge y \neq 1] \So (x^2 + y^2 = 9)\right\}\)

Trzeba to zamienić na alternatywy i /lub koniunkcje.
Prawdą jest, że
\(p \So q \iff \neg p \vee q\) oraz \(\neg(p\So q) \iff p \wedge \neg q\)
W takim razie zbiór z zadania można określić tak:
\(D= \left\{(x,y) \in \rr ^2: x^2+y^2=4 \wedge y \le 1 \vee x^2+y^2=9 \right\}\).
na obrazku to wygląda tak:

Jeżeli masz przed sobą otwarty np zbiorek Elementy logiki i teorii mnogości w zadaniach : MAREK, ONYSZKIEWICZ to na pierwszej stronie masz podane w tabeli te 16-naście funktorów dwuargumentowych.
Możesz zadziałać zachłannie umiejętnie sprawdzając wszystkie .
Np formuła \((p*p)*(r*r)\) dla wartościowania \((0*0)*(0*0)\) dla pierwszych ośmiu funktorów : od \(B_0\) do \(B_7\) daje \(0\) \(\\)\(\\)bo \(00 \to 0\) ( nie są tautologiami)
pozostaje sprawdzić pozostałe osiem od \(B_8\) do \(B_{14}\), co idzie błyskawicznie mając te formuły przed oczami.
Oczywiście \(B_{15}\) jest natychmiast tautologią .

Mam otwarty ten zbiór i widzę tę tabelkę, ale szczerze mówiąc nie bardzo wiem, jak to odnieść do mojego przykładu. Mógłbym prosić o jakieś dokładniejsze wytłumaczenie? Mam sobie "podstawiać" kolejno za 'p' i 'r' '0' i '1', a potem odczytywać wartość logiczną?
Czyli np. przydzielam wartość logiczną dla p=1 i dla r=1, czyli formuła zdaniowa: (p*r)*(p*r) przyjmuje wartość 1. Oznaczałoby to że wyrażenie jest tautologią.

formuła ma być tautologią : czyli wystarczy wskazać jedno wartościowanie na NIE

Twoja formuła b) ma postać (p*p)*(r*r)
bierzesz np ze zbioru funktor \(B_0\) i dla niego wartościowanie \(p=0,r=0\)
wtedy \((0*0)*(0*0)=0*0=0\) zgodnie z definicją tego funktora. Czyli na NIE
Widać z oglądu tabeli funktorów ,że powyższe wartościowanie \(p=0,r=0\) kwalifikuje na NIE funktory do \(B_7\)
Patrzysz na funktor \(B_8\) i bierzesz wartościowanie \(p=0,r=0\).
Wtedy zgodnie z definicją tego funktora jest \(( 0*0)*(0*0)=1*1=0\) czyli na NIE
Funktor \(B_9\) jest tu tautologią .
Funktor \(B_{10}\) . Weź wartościowanie \(p=0,r=0\) . Wtedy zgodnie z definicją funktora \((0*0)*(0*0)=(1*1)=0\) . Czyli na NIE
To leci błyskawicznie.

Myślę, że tu chodzi o wstawienie zamiast gwiazdek operatorów, tak, żeby powstało zdanie zawsze prawdziwe (tautologia)
Przykład: \((p \iff r) \So (p \So r)\)

A czy potem muszę sprawdzać np. dla p=1 i r=0, czy wystarczy jeden przypadek (tak jak podałeś p=0 i r=0)

Może autor zadania potrafi odpowiedzieć panb na Twoje spostrzeżenie ?

Myślę, że w niektórych przypadkach można wstawić operatory. Jednak patrzę na podaną przez Panko tabelkę i tam tylko niektóre z nich są opisane konkretną nazwą.
Ale już chyba wiem jak to ogarnąć, jednak to trochę pracochłonna metoda. Będę kolejno sprawdzał wartość logiczną całego wyrażenia np. dla p=0 i r=0. Jeśli wyrażenie przybierze wartość "1" to następnie sprawdzę np. dla p=0 i r=1. Jeśli zaś wyjdzie "0", to wiem, że takie wyrażenie nie jest tautologią. Czy taki tok rozumowania jest poprawny?

Trochę NIE tak.
Obszar na który zwrócił uwagę pnb zdecydowanie utrudnia i jednocześnie robi ciekawszym Twoje zadanie.

Ja potraktowałem symbol \(*\) w zapisie \((p*p)*(r*r)\) jako j e d e n funktor.

pnb traktuje \(*\) jak zmienną co pokazał w swoim poście.

NIE potrafię wskazać algorytmu szukającego tautologii dla stanu opisanego przez pnb