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: 1745
Rejestracja: 14 cze 2011, o 11:34
Płeć: Mężczyzna
Lokalizacja: Sosnowiec

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

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

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

Jako ilustrację, o co chodzi w tym twierdzeniu dodam, że dla formuły \(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:

\((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