Pet polaznika, kvantifikatori i mentorstvo
Koordinacija radionica provjerava pet prijavljenih polaznika. Neka P(x) znači 'x je položio sigurnosnu provjeru', a Q(x) 'x ima pisanu suglasnost'. Podaci su: A1 ima P i Q; A2 ima P, ali nema Q; A3 nema P, ali ima Q; A4 nema ni P ni Q; A5 ima P i Q. Voditeljica tvrdi: 'Svaki polaznik koji je položio sigurnosnu provjeru ima i pisanu suglasnost.' Pomoćnik odgovara: 'Postoji polaznik koji je položio sigurnosnu provjeru, ali nema suglasnost.' Uz to, mentorstvo je zadano ovako: A5 mentorira A1, A1 mentorira A2, A5 mentorira A3, A3 mentorira A4, A1 mentorira A5. Rasprava je o tome hoće li se radionica održati ako barem jedan polaznik nema suglasnost i hoće li svi imati mentora koji je položio provjeru. Odluka mora biti donesena do petka.
1. Prevedite tvrdnju voditeljice i tvrdnju pomoćnika na jezik predikatne logike. Kakav je njihov odnos?
Read the worked answer
Voditeljica: S1 = ∀x(P(x) → Q(x)).
Pomoćnik: S2 = ∃x(P(x) ∧ ¬Q(x)).
S2 je logička negacija S1: ¬∀x(P(x) → Q(x)) = ∃x(P(x) ∧ ¬Q(x)). Zato one ne mogu biti istinite zajedno. U zadanom modelu dovoljno je pronaći jednog polaznika s P i bez Q.
2. Procijenite istinitost S1, S2 i S3 = ∀x∃y(R(x,y) ∧ P(y)) u zadanom modelu.
Read the worked answer
S1 je lažna jer A2 ima P, a nema Q.
S2 je istinita jer A2 zadovoljava P ∧ ¬Q.
S3 provjeravamo po polaznicima:
- A1 ima mentora A5, a A5 ima P;
- A2 ima mentora A1, a A1 ima P;
- A3 ima mentora A5, a A5 ima P;
- A4 ima mentora A3, ali A3 nema P;
- A5 ima mentora A1, a A1 ima P.
Budući da A4 nema mentora s P, S3 je lažna. Ni dopuštanje više mentora ne bi pomoglo jer A4 nema nijednog mentora s P.
3. Objasnite razliku između 'svaki polaznik ima mentora koji je položio provjeru' i 'postoji mentor koji je položio provjeru i mentorira svakog polaznika'.
Read the worked answer
Prva formula: ∀x∃y(R(x,y) ∧ P(y)) - svaki polaznik ima nekog mentora, a taj mentor je položio provjeru; mentor može biti različit za različite polaznike.
Druga formula: ∃y(P(y) ∧ ∀x R(x,y)) - postoji jedan te isti mentor koji je položio provjeru i mentorira svakoga.
Druga je jača: uz neprazan skup polaznika iz druge slijedi prva, ali obratno ne. U zadanom modelu obje su lažne, ali to ne znači da su ekvivalentne.