Udowodnij, że nie istnieje formuła rachunku zdań

Zdania. Tautologie. Język matematyki. Wszelkie zagadnienia związane z logiką matematyczną...
matmatmm
Użytkownik
Użytkownik
Posty: 1755
Rejestracja: 14 cze 2011, o 11:34
Płeć: Mężczyzna
Lokalizacja: Sosnowiec
Podziękował: 68 razy
Pomógł: 240 razy

Udowodnij, że nie istnieje formuła rachunku zdań

Post autor: matmatmm » 11 lut 2019, o 12:41

Literałem nazywamy zmienną zdaniową lub negację zmiennej zdaniowej. Zadanie brzmi:

Dana jest formuła \(\displaystyle{ A=p_1\vee p_2\vee p_3}\). Udowodnić, że nie istnieje formuła \(\displaystyle{ S}\) postaci \(\displaystyle{ S=U_1\wedge\ldots\wedge U_n}\), gdzie \(\displaystyle{ n\ge 1}\) oraz \(\displaystyle{ U_i}\) jest literałem lub alternatywą dwóch literałów dla każdego \(\displaystyle{ i\in\{1,\ldots,n\}}\), a także

(i) Dla każdego wartościowania \(\displaystyle{ \nu}\): Jeśli \(\displaystyle{ \nu(A)=1}\), to istnieje wartościowanie \(\displaystyle{ \nu'}\) takie, że \(\displaystyle{ \nu'(p_j)=\nu(p_j)}\) \(\displaystyle{ (j=1,2,3)}\) oraz \(\displaystyle{ \nu'(S)=1}\) (można to inaczej wyrazić mówiąc, że wartościowanie zmiennych \(\displaystyle{ p_1,p_2,p_3}\), które daje \(\displaystyle{ 1}\) na \(\displaystyle{ A}\) może być rozszerzone do wartościowania pozostałych zmiennych, które daje \(\displaystyle{ 1}\) na \(\displaystyle{ S}\))

(ii) Dla każdego wartościowania \(\displaystyle{ \nu}\): Jeśli \(\displaystyle{ \nu(S)=1}\), to \(\displaystyle{ \nu(A)=1}\).

Jako ilustrację, o co chodzi w tym twierdzeniu dodam, że dla formuły \(\displaystyle{ p_1\vee p_2\vee p_3\vee p_4}\) jeśli dopuścimy, żeby każdy składnik koniunkcji był złożony z trzech literałów, to formuła o podanych własnościach istnieje. Taką formułą jest na przykład:

\(\displaystyle{ (p_1\vee p_2\vee a_1)\wedge (\neg a_1\vee p_3\vee a_2)\wedge (\neg a_2 \vee p_4\vee \neg a_1)}\)

ODPOWIEDZ