Inleiding Logica 2013/2014 Opgaven 5: 30 april 2014 Opgave 1 Vertaal de volgende zinnen in de predikaatlogika. Gebruik daarbij de volgende vertaalsleutel: a ∼ Anna b ∼ Bouke M x ∼ x is een man Nx ∼ x is Nederlander Rx ∼ x is rijk Gxy ∼ x is getrouwd met y Kxy ∼ x is een kind van y (a) Anna heeft een buitenlandse man. (b) Anna heeft een zuster. (c) Alle Nederlanders zijn rijk. (d) Alle Nederlandse kinderen van Bouke zijn arm. (e) Alle dochters van Anna hebben kinderen. (f) Een grootvader van Bouke is getrouwd met een zuster van Anna. Opgave 2 Geef de betekenis van de onderstaande zinnen en formules uit de predikaatlogica. Gebruik hierbij de voor de hand liggende vertaalsleutel. (a) ∀x∃y y · y = x; (b) ∀x∀z (x < y → ∃z(x < z ∧ z < y)); (c) ∃x1 ∃x2 (x1 = x1 · x1 ∧ x2 = x2 · x2 ∧ ¬x1 = x2 ∧ ∀x3 (x3 = x3 · x3 → (x3 = x1 ∨ x3 = x2 )). Geef van de bovenstaande formules aan of ze waar zijn in respectievelijk de structuren N, Z, Q en R. Opgave 3 Vertaal de volgende zinnen in de predikaatlogika. Gebruik daarbij de volgende vertaalsleutel: Sx ∼ x woont in Sneek, F x ∼ x spreekt Fries. (a) Minstens ´e´en persoon spreekt Fries. (b) Er wonen minstens twee mensen in Sneek. (c) Er wonen hoogstens twee mensen in Sneek. 1 (d) Er wonen precies twee mensen in Sneek. (e) Er wonen precies twee mensen in Sneek die Fries spreken. (f) Er wonen precies twee mensen in Sneek, en die spreken allebei Fries. (g) Beide inwoners van Sneek spreken Fries. Opgave 4 Vertaal de volgende zinnen in de predikaatlogika. Gebruik daarbij de vertaalsleutel van opgave 1. (a) Anna is de enige dochter van Bouke. (b) Anna heeft geen grootmoeder. (c) Anna heeft precies ´e´en zoon, en die is getrouwd met een zus van Bouke. (d) Anna heeft precies twee tantes. Opgave 5 Vertaal het vermoeden van Goldbach in de predicaatlogica. Gebruik hierbij de volgende vertaalsleutel (deze taal heeft dus geen relatiesymbolen, alleen functiesymbolen). 0 ∼ nul s(x) ∼ de opvolger van x a(x, y) ∼ de som van x en y m(x, y) ∼ het product van x en y Opgave 6 Gegeven is de term t = f (x, y, c). Bereken voor elk van de volgende formules ϕ = ϕa , . . . , ϕd de formule [t/x]ϕ, en geef aan of de term t vrij is voor x in ϕ. (a) ϕa = Ax ∧ ∃x Rxy (b) ϕb = Ax ∧ ∃y Rxy (c) ϕb = Ax ∧ ∃x∃y Rxy (d) ϕc = Ax ∧ ∃z Rxy Opgave 7 Geef een inductieve definitie van de verzameling BV (ϕ) van de gebonden variabelen van een formule ϕ. Opgave 8 (INLEVEROPDRACHT)1 Vertaal de volgende zinnen in de predikaatlogika. Gebruik daarbij de vertaalsleutel van opgave 1. (a) Anna heeft precies twee kinderen, en die zijn allebei getrouwd met Bouke. (b) Alle grootouders hebben of alleen dochters, of precies twee zonen, of ze zijn kinderloos. 1 Deze opgave dient te worden ingeleverd bij het werkcollege van 9 mei 2014. 2