Quantoren / Aussagenlogik über Primzahl: (p>1) ∧ ∀x ∀y (p=x·y → x=1 ∨ y=1)

Question

Die Eigenschaft, dass eine natürliche Zahl p eine Primzahl ist, kann man durch die folgende Formel ausdrücken (als Bereich wird ℕ vereinbart):

(p>1) ∧ ∀x ∀y (p=x·y → x=1 ∨ y=1)

Negieren Sie diese Formel und bringen Sie den inneren Teil durch äquivalente Umformungen in eine möglichst einfache Form. Weisen Sie anhand dieser negierten Formel nach, dass p = 15 keine Primzahl ist.

Answer 1

Folgende Regeln werde ich verwenden:

1.) ¬(A∧B) ⇔ (¬A) ∨ (¬B)

2.) ¬(A∨B) ⇔ (¬A) ∧ (¬B)

3.) ¬∀x: A(x) ⇔ ∃x: ¬A(x)

4.) ¬∃x: A(x) ⇔ ∀x: ¬A(x)

5.) ¬(A→B) ⇔ A∧(¬B)

 

Damit negiere ich jetzt die Formel:

¬((p>1) ∧ ∀x ∀y: (p=x·y → x=1 ∨ y=1))

⇔ ¬(p>1) ∨ ¬∀x ∀y: (p=x·y → x=1 ∨ y=1)

⇔ ¬(p>1) ∨ ∃x ¬∀y: (p=x·y → x=1 ∨ y=1)

⇔ ¬(p>1) ∨ ∃x ∃y: ¬(p=x·y → x=1 ∨ y=1)

⇔ ¬(p>1) ∨ ∃x ∃y: p=x·y ∧ ¬(x=1 ∨ y=1)

⇔ ¬(p>1) ∨ ∃x ∃y: p=x·y ∧ ¬(x=1) ∧ ¬(y=1)

 

Jetzt muss man noch ein paar zahlentechnische Sachen überlegen:
Im Bereich der Natürlichen Zahlen gilt ¬(p>1) ⇔ p=1

Die Negation von x=1 ist einfach x≠1, für y analog.

Die Formel lautet also endgültig:

(p=1) ∨ ∃x ∃y: p=x·y ∧ (x≠1) ∧ (y≠1)

Eine Nicht-Primzahl p wird also dadurch gekennzeichnet, dass sie 1 ist oder, dass zwei Zahlen x und y ungleich 1 existieren, sodass p=x*y gilt.

Am Beispiel 15: Die beiden Zahlen existieren, nämlich x=3 und y=5. Beide sind ungleich 1 und es gilt 3*5=15.