szukanie zaawansowane
 [ Posty: 1 ] 
Autor Wiadomość
Mężczyzna
PostNapisane: 11 lut 2019, o 13:41 
Użytkownik

Posty: 1717
Lokalizacja: Sosnowiec
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)
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2019
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 1 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 sprawdzić, czy następująca formuła jest tautologią.  hapadzid  4
 Wykaż, że następująca formuła jest prawem rachunku zdań. - zadanie 2  Voicer  6
 Formuła logiki I rzędu  RayJay  1
 Przykłady zdań logicznych  chimpo  3
 2 zadanka z rachunku kwantyfikatorów  dlm  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl