maths.free › Set Theory & Logic › Logic and methods of proof

Logic and methods of proof

Connectives, quantifiers, direct proof, contrapositive, contradiction, induction.

A proof is a chain of statements each following from earlier ones by a rule of inference. Direct proof assumes the hypothesis and derives the conclusion; contrapositive proves ¬Q → ¬P instead; contradiction assumes ¬Q and finds an absurdity; induction climbs the integers. Picture it: the truth table below, p → q and ¬p ∨ q agree in every row, which is the contrapositive method justified. Think it: Gödel showed any consistent system rich enough for arithmetic has true statements it cannot prove.

Exemple résolu · truth table of (p implies q) iff (not p or q)

Discrete-Math · Propositional-Logic

Truth table of (p implies q) iff (not p or q)

Étape par étape

  1. \left(p \Rightarrow q\right) \Leftrightarrow \left(q \vee \neg p\right)

    2 variable(s) → 4 rows. Fill in every combination.

  2. \

    A tautology (always true).

Révèle la réponse
\left(p \Rightarrow q\right) \Leftrightarrow \left(q \vee \neg p\right)

À vous Choisissez un problème, ou tapez ou dessinez le vôtre. Chaque étape, une image, la réponse cachée jusqu'à ce que vous le demandiez.

Conservez votre propre travail

Un compte gratuit ajoute des notes sur chaque leçon, un enregistrement de ce que vous avez terminé, vos problèmes résolus en un seul endroit, et un tuteur que vous pouvez demander sur cette page. Les maths eux-mêmes sont ouverts à tout le monde, signé ou non.

Inscription Connexion

Symboles utilisés ici

Appuyez sur n'importe quel symbole pour la définition complète, une image et ce que signifie chaque lettre.

Comment faire: Logic and methods of proof

  1. Write the statement as "if P then Q" with P and Q precise.
  2. Choose a method: direct (assume P), contrapositive (assume not Q), contradiction (assume P and not Q), or induction (for all n).
  3. Each line must cite a definition, an axiom or a previous line.
  4. End when Q appears; mark it ∎.

Questions posées par les gens

Are some infinities bigger than others?

Yes. The integers and the rationals can be listed; the real numbers cannot (Cantor's diagonal argument), so there are strictly more reals than integers.

What is the difference between a relation and a function?

A relation pairs inputs with outputs freely; a function is a relation in which every input gets exactly one output.

Plus en Set Theory & Logic

Sets and operationsRelations, functions and equivalenceCardinality and infinity