Logic & Proof Solver
Formal Proofs, Truth Tables, Inference
Construct formal mathematical proofs step by step. Verify logical equivalence, generate truth tables, and solve propositional logic problems. Free for CS and math students.
Describe the conditional statement to prove. The solver will assume its negation and derive a contradiction.
All Proof Methods Supported
Click any card to load an example into the solver.
Logical Inference Rules
The solver labels every step with the inference rule applied. These are the rules it uses.
p∴ q
¬q∴ ¬p
q → r∴ p → r
¬p∴ q
q∴ p ∧ q
Frequently Asked Questions
Logic and Proof Solver — Formal Proofs with Every Step Labeled
This solver handles the full range of formal proof problems that appear in discrete mathematics, mathematical logic, and theoretical computer science courses. The key difference from a general AI assistant is that every step in the output is labeled with the specific inference rule, theorem, or definition applied — which is exactly what professors expect in formal proof assignments and what students need to understand where their reasoning breaks down.
You can input a statement in plain English, in symbolic notation, or in a mix of both. The solver identifies the type of statement and selects the most appropriate proof strategy automatically, or you can select the proof method yourself from the mode selector.
Choosing the Right Proof Technique
One of the hardest parts of discrete math proofs is knowing which technique to apply. The choice depends on the structure of the statement being proved. Here is a guide to matching statement types to proof methods:
| Statement Type | Recommended Method | Why |
|---|---|---|
| P → Q (direct chain) | Direct proof | Assume P, derive Q step by step — simplest when Q follows naturally |
| P → Q (hard to derive Q) | Contrapositive (¬Q → ¬P) | Negation of conclusion gives a strong assumption to work with |
| P → Q (negation gives contradiction) | Contradiction | Assume P and ¬Q, derive ⊥ — works when irrationality or impossibility is involved |
| ∀n ∈ ℕ, P(n) | Mathematical induction | Statements about all natural numbers require base case + inductive step |
| Verify formula is tautology | Truth table | Enumerate all variable assignments — definitive for propositional logic |
| Show P ≡ Q | Equivalence / truth table | Compare truth tables column by column, or use algebraic laws |
De Morgan’s Laws and Other Logical Equivalences
Logical equivalences are identities that allow you to rewrite formulas into equivalent forms. They are essential tools in formal proofs and Boolean algebra simplification. The most commonly needed equivalences in proof construction include:
- De Morgan’s laws: ¬(p ∧ q) ≡ ¬p ∨ ¬q, and ¬(p ∨ q) ≡ ¬p ∧ ¬q — used constantly when negating compound statements
- Implication rewriting: p → q ≡ ¬p ∨ q — allows converting implications to disjunctions for algebraic manipulation
- Contrapositive equivalence: p → q ≡ ¬q → ¬p — the basis of proof by contrapositive
- Double negation: ¬¬p ≡ p — simplifies negated negations in contradiction proofs
- Distributive laws: p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) — useful when expanding compound propositions
- Absorption: p ∨ (p ∧ q) ≡ p — simplifies formulas with redundant subexpressions
The solver applies these identities automatically at the relevant steps and cites which law was used, making it easy to follow and replicate the reasoning.
Common Errors in Formal Proofs
Students learning to write formal proofs make a consistent set of errors. Recognizing these patterns helps avoid them before submitting work:
- Circular reasoning — using the conclusion as a step in the proof without independently establishing it
- Proving the converse instead of the original statement — proving Q → P when asked for P → Q
- In proof by contradiction, forgetting to explicitly state what the contradiction is — the proof must identify the specific ⊥ derived
- In induction, not clearly stating the inductive hypothesis before using it — the hypothesis must be named and bounded (P(k), not P(n))
- Treating the inductive step as P(k+1) → P(k) instead of P(k) → P(k+1) — the direction is forward, not backward
- In truth tables, missing rows — a formula with n variables requires exactly 2ⁿ rows
Ready to Prove Your Theorem?
Enter your statement above or access full formal proofs with every step labeled.
Get Full Solution Free →