1. Zdanie prawdziwe. Załóżmy nie wprost, że \phi \Rightarrow \psi i \neg \phi \Rightarrow \psi są tautologiami, a \psi nie jest. Oznacza to, że istnieje wartościowanie \sigma takie, że \sigma(\psi)=F. Wtedy \sigma(\phi \Rightarrow \psi)=F albo \sigma(\neg \phi \Rightarrow \psi)=F, a więc jedna z tych formuł nie jest tautologią, co jest sprzeczne z założeniem.
  2. Zdanie nieprawdziwe. Niech \phi = p, a \psi = q \wedge \neg q. Wtedy \phi \Rightarrow \psi jest spełniona dla p fałszywego i niespełnione dla p prawdziwego, a \neg \phi \Rightarrow \psi jest spełniona dla p prawdziwego i niespełniona dla p fałszywego, jednak q \wedge \neg q jest formułą sprzeczną.
  3. Zdanie prawdziwe. Załóżmy nie wprost, że \psi nie jest spełnialna, a więc jest sprzeczna albo tautologią.
    • Jeśli \psi jest sprzeczna, to aby \phi \Rightarrow \psi była tautologią, \phi również musi być sprzeczna. Ale wtedy \neg \phi \Rightarrow \psi jest sprzeczna.
    • Jeśli \psi jest tautologią, to skoro \phi \Rightarrow \psi jest tautologią, \phi również jest tautologią. Ale wtedy \neg \phi \Rightarrow \psi jest tautologią.
      W obydwu przypadkach \neg \phi \Rightarrow \psi nie jest spełnialna, co stanowi sprzeczność z założeniem.
  4. Zdanie nieprawdziwe. Niech \phi = p \wedge \neg p, a \psi = q. Wtedy \phi \Rightarrow \psi jest tautologią, a \neg \phi \Rightarrow \psi jest spełnialna i zależy od q. Niemniej \phi nie jest tautologią.
 
logika_dla_informatykow/skrypt/13.txt · ostatnio zmienione: 2009/10/10 17:43 przez iwan
 
Wszystkie treści w tym wiki, którym nie przyporządkowano licencji, podlegają licencji:MIT License
Recent changes RSS feed